Ұйқыдағы шаштараз мәселесі - Sleeping barber problem

Жылы Информатика, шаштараз мәселесі классикалық процесаралық байланыс және үндестіру бірнеше арасындағы проблема операциялық жүйе процестер. Мәселе, шаштаразды клиенттер болған кезде ұстау, жоқ кезде демалу және тәртіпті түрде жасау сияқты.

Ұйқыдағы шаштараз мәселесі көбіне байланысты Edsger Dijkstra (1965), информатиканың бастаушыларының бірі.

Анықтама

Аналогия бір шаштараз бар гипотетикалық шаштаразға негізделген. Шаштараздың кесу бөлмесінде бір шаштараз орындығы және ішінде бірнеше орындықтар бар күту бөлмесі бар. Шаштараз клиенттің шашын қырқуды аяқтаған кезде, ол клиентті жұмыстан шығарады және күту бөлмесіне басқа күте тұрғандардың бар-жоғын білу үшін барады. Егер бар болса, ол олардың біреуін орындыққа әкеліп, шаштарын қиып алады. Егер жоқ болса, ол орындыққа оралып, сол жерде ұйықтайды.

Әр клиент келгенде, шаштараздың не істеп жатқанын көреді. Егер шаштараз ұйықтап жатса, клиент оны оятып, кесу бөлмесінің креслоларына отырады. Егер шаштараз шашты қырқып жатса, клиент күту залында қалады. Егер күту залында бос орындық болса, клиент оған отырады және өз кезегін күтеді. Егер бос орындық болмаса, тапсырыс беруші кетеді.

Мәселелер туындайды

Аңқау талдау негізінде, жоғарыда келтірілген шешімдер шаштараз келген клиенттің келуін жоғалтқанға дейін шашты қырқумен, келесі тұтынушы келгенге дейін ұйықтаумен дүкеннің дұрыс жұмыс істеуін қамтамасыз етуі керек. Іс жүзінде жоспарлаудың жалпы проблемаларына иллюстрациялық сипатта болатын бірқатар мәселелер туындауы мүмкін.

Мәселелердің барлығы шаштараздың да, тапсырыс берушінің де әрекеттері (күту бөлмесін тексеру, дүкенге кіру, күту бөлмесінің креслоларын қабылдау және т.б.) барлығы белгісіз уақытты алумен байланысты. Мысалы, клиент келіп, шаштараздың шаш қырқып жатқанын байқауы мүмкін, сондықтан ол күту бөлмесіне барады. Олар жолда жүрген кезде шаштараз қазіргі шаштарын аяқтап, күту бөлмесін тексеруге кетеді. Ешкім жоқ болғандықтан (мүмкін күту залы алыс және шаштараз клиенттің жанынан өтіп бара жатқан шығар, немесе клиент дәретханаға барған немесе орындыққа қарай бара жатқан, шаштараз оны кетіп қалды деп ойлаған шығар). орындықтарына оралып, ұйықтап жатыр. Шаштараз қазір клиентті күтуде, ал клиент шаштаразды күтуде.

Басқа жағдайда күту залында бір орындық болған кезде екі клиент бір уақытта келуі мүмкін. Олар шаштараздың шаш қырқып жатқанын байқайды, күту бөлмесіне барады және екеуі де жалғыз орындықты иеленуге тырысады.

Шешімдер

Көптеген мүмкін шешімдер бар. Әрқайсысының негізгі элементі а мутекс, бұл қатысушылардың біреуі ғана күйді бірден өзгерте алатындығына кепілдік береді. Шаштараз клиенттерді тексермес бұрын осы өзара алып тастауды (бөлме мәртебесін) сатып алуы / орындауы және ұйықтай бастағанда немесе шаштарын қиюы керек. Клиент оны дүкенге кірер алдында иемденіп, оны күту залы креслосына немесе шаштараз креслоларына отырғаннан кейін, сондай-ақ орындар болмағандықтан дүкеннен шыққан кезде босатуы керек. Бұл алдыңғы бөлімде айтылған екі мәселені де жояды. Бірқатар семафоралар жүйенің күйін көрсету үшін де қажет. Мысалы, күту залындағы адамдардың санын сақтауға болады.

A көптеген ұйықтайтын шаштараздар мәселесі күтіп тұрған клиенттер арасында бірнеше шаштаразды үйлестірудің қосымша күрделілігі бар.

Іске асыру

Келесісі псевдокод шаштараз бен тұтынушы арасындағы синхронизацияға кепілдік береді тығырық тегін, бірақ әкелуі мүмкін аштық тапсырыс берушінің. Аштық мәселесін шаштараз оларға бірінші кезекте қызмет ете алатындай етіп клиенттер келген кезде қосылатын кезекті қолдану арқылы шешуге болады (FIFO => First In, First Out) Функциялар күту () және сигнал беру ( ) функциялар болып табылады семафоралар. С-кодты белгілеуде күту () - P (), сигнал () - V ().

# Алғашқы екеуі мутекс (тек 0 немесе 1 мүмкін)Семафор шаштаразДайын = 0Семафор WRSeats қол жетімділігі = 1     # егер 1 болса, күту залындағы орындар санын көбейтуге немесе азайтуға боладыСемафор сақтық дайын = 0         # қазіргі уақытта күту залында қызмет көрсетуге дайын клиенттер саныint numberOfFreeWRSatats = N     # күту залындағы орындардың жалпы саныдеф Шаштараз():  уақыт шын:                   # Шексіз циклде жүгіріңіз.    күте тұрыңыз(сақтық дайын)             # Клиент сатып алуға тырысыңыз - егер жоқ болса, ұйықтаңыз.    күте тұрыңыз(WRSeats қол жетімділігі)         # Оян - қол жетімді орындардың # түрін өзгертуге рұқсат алуға тырыс, әйтпесе ұйықта.    numberOfFreeWRSatats += 1    # Күту бөлмесінің бір орындығы бос болады.    сигнал(шаштаразДайын)         # Мен кесуге дайынмын.    сигнал(WRSeats қол жетімділігі)       # Енді орындықтардың құлпы қажет емес.    № (Мұнда шаш қиыңыз.)деф Тапсырыс беруші():  уақыт шын:                   # Бірнеше тұтынушыны модельдеу үшін шексіз циклде жүгіріңіз.    күте тұрыңыз(WRSeats қол жетімділігі)         # Күту бөлмесінің орындықтарына қол жеткізуге тырысыңыз.    егер numberOfFreeWRSatats > 0: # Егер бос орындар болса:      numberOfFreeWRSatats -= 1  # орындыққа отырыңыз      сигнал(сақтық дайын)         # клиент болғанша күтіп тұрған шаштаразға хабарлаңыз      сигнал(WRSeats қол жетімділігі)     # енді орындықтарды құлыптаудың қажеті жоқ      күте тұрыңыз(шаштаразДайын)         # шаштараз дайын болғанша күтіңіз      № (Мұнда шашты кесіңіз.)    басқа:                       # әйтпесе, бос орындар жоқ; қиын сәттілік -      сигнал(WRSeats қол жетімділігі)     # бірақ орындықтардың құлпын босатуды ұмытпаңыз!      # (Шашты қиюсыз қалдырыңыз.)

Сондай-ақ қараңыз

Әдебиеттер тізімі

  • Қазіргі операциялық жүйелер (2-ші шығарылым) арқылы Таненбаум Эндрю С. (ISBN  0-13-031358-0)
  • Семафорлардың кішкентай кітабы Аллен Б. Дауни, http://greenteapress.com/semaphores
  • Бірізді процестермен ынтымақтастық Дайкстра Э.В. Техникалық есеп EWD-123, 1965, Эйндховен технологиялық университеті, Нидерланды.