Кіріспе
Бағдарламалық жасақтаманың бір мезгілде орындалуының мәселесі Компьютерлік ғылымда, «ұйықтап жатқан шаштараз» мәселесі – бірнеше операциялық жүйе процестері болғанда туындайтын күрделіліктерді көрсететін, процестер арасындағы байланыс және синхрондаудың классикалық мәселесі. Бұл мәселені 1965 жылы компьютерлік ғылымның негізін қалаушы Эдсгер Дейкстра ұсынған, ол оны жалпы семафорлар көбінесе артық екенін көрсету үшін пайдаланған. Егер клиенттер болмаса, шаштараз креслода ұйықтап кетеді. Клиент шаштараз ұйықтап жатса, оны оятуы керек. Егер клиент шаштараз жұмыс істеп тұрғанда келсе, барлық орындықтар толған болса, клиент кетеді, ал бос орындық болса, онда отырады. Шаштараз шаш кесуді аяқтағаннан кейін, күту залында күтіп тұрған клиенттер бар ма екенін тексеріп, егер жоқ болса, ұйықтап кетеді.
In computer science, the sleeping barber problem is a classic inter process communication and synchronization problem that illustrates the complexities that arise when there are multiple operating system processes. The problem was originally proposed in 1965 by computer science pioneer Edsger Dijkstra, who used it to make the point that general semaphores are often superfluous. If there are no customers, the barber falls asleep in the chair
A customer must wake the barber if he is asleep
If a customer arrives while the barber is working, the customer leaves if all chairs are occupied and sits in an empty chair if it's available
When the barber finishes a haircut, he inspects the waiting room to see if there are any waiting customers and falls asleep if there are none
Екі негізгі қиындық бар. Біріншіден, шаштараз клиент шаш кесу үшін күтіп тұрғанда ұйықтап қалуы мүмкін, себебі барлық әрекеттер – күту залын тексеру, шаштаразханаға кіру, күту залындағы орындықты алу – белгілі бір уақыт алады. Атап айтқанда, клиент шаштараздың шаш кесіп жатқанын көріп, күту залына қайтып орын іздеуге барады, бірақ күту залына қайтып бара жатқанда шаштараз шаш кесуді аяқтап, күту залына келеді, ол бос болып шығады (клиент баяу болғандықтан немесе дәретханаға барғандықтан) және осылайша шаштараз креслода ұйықтап кетеді. Екіншіден, күту залында бір ғана бос орын болғанда екі клиент бір уақытта келсе, екеуі де сол орынға отыруға тырысады; тек бірінші келген адам ғана отыра алады. Көптеген ұйықтап жатқан шаштараз мәселесінде күтіп тұрған клиенттер арасында бірнеше шаштаразды үйлестірудің қосымша қиындығы бар.
Шешімдер
Бірнеше мүмкін шешімдер бар, бірақ барлық шешімдерге мутекс қажет, ол бір уақытта тек бір қатысушы ғана күйін өзгерте алатынын қамтамасыз етеді. Шаштараз клиенттерді тексермес бұрын бөлме статусының мутексін иеленуі керек және оны ұйықтағанда немесе шаш қиғанда босатуы керек; клиент дүкенге кірмес бұрын оны иеленуі керек және күту залында немесе шаштараз креслосында отырғанда, сондай-ақ орын болмағандықтан дүкеннен шыққанда босатуы керек. Бұл жоғарыда айтылған екі проблеманы да шешеді. Жүйенің күйін көрсету үшін бірнеше семафорлар да қажет. Мысалы, күту залындағы адамдардың санын көрсетуге болады.