Қайшылық жағдайы: процестердің өзара тоқталып қалуы

Кіріспе

Мүшелердің бір-бірін тоқтатып тұрған жағдайы. Компьютерлік ғылымдағы ұғым.

Бір мезгілдегі есептеулерде, тұйықталу – бұл топтың кез келген мүшесінің басқа мүше күтіп тұрғандықтан, оның ішінде өзінен де, іс-әрекет ете алмайтын жағдай. Әрқайсысы басқа мүшеден әрекет жасауды күтеді, мысалы, хабарлама жіберуді немесе, көбінесе, құлыпты босатуды. Тұйықталу мультипроцессорлық жүйелерде, параллель есептеуде және таратылған жүйелерде жиі кездесетін мәселе, себебі мұндай жағдайларда жүйелер ортақ ресурстарды бөлісу үшін және процестерді синхрондау үшін бағдарламалық немесе аппараттық құлыптарды қолданады. Операциялық жүйеде тұйықталу, процесс немесе жіп (thread) қажетті жүйелік ресурсты басқа күтіп тұрған процесс ұстап тұрғандықтан күту күйіне өткенде пайда болады, ал ол процесс өз кезегінде басқа күтіп тұрған процесс ұстап тұрған тағы бір ресурсты күтеді. Егер процесс өзіне қажетті ресурстарды басқа процесс пайдаланып жатқандықтан, өз күйін өзгерте алмайтын жағдайға түсіп, белгісіз мерзімге тоқтаса, жүйе тұйықталып қалды делінеді. Коммуникациялық жүйелерде тұйықталулар көбінесе ресурстар үшін таласқа қарағанда сигналдардың жоғалуына немесе бұзылуына байланысты туындайды.

Мөлдір тұйықтықты басқару

Қазіргі операциялық жүйелердің көпшілігі өлі тұйықталуды (deadlock) болдырмайды. Өлі тұйықталу орын алғанда, әртүрлі операциялық жүйелер оған әртүрлі, стандартты емес жолдармен жауап береді. Көптеген тәсілдер Коффманның төрт шартының, әсіресе төртінші шартының орын алуын болдырмау арқылы жұмыс істейді. Басты тәсілдер келесідей.

Жолдың тұйықталуына мән бермеу

Бұл тәсілде, тұйықталу ешқашан туындамайды деп қарастырылады. Бұл сондай-ақ "Құстар" алгоритмінің қолданылуы болып табылады. Бұл тәсіл алғаш рет MINIX және UNIX жүйелерінде пайдаланылған.

Анықтау

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

Алдын алу

Тұйықталуды алдын алу Коффманның төрт шартының біреуінің пайда болуын болдырмау арқылы жұмыс істейді. Өзара қолдану шартын жою, яғни ешбір процесс ресурстың эксклюзивті қолданысына ие болмайды дегенді білдіреді. Бұл бұрала алмайтын ресурстар үшін мүмкін емес. Бірақ ресурстарды тізбектей қолдану мүмкін болған жағдайда да, тұйықталу орын алуы мүмкін. Өзара қолданудан аулақ болатын алгоритмдер бұғаттамайтын синхронизация алгоритмдері деп аталады. Күту және ұстау шартын, немесе ресурсты ұстап тұру шартын процестерді бастау алдында (немесе белгілі бір операциялар жиынтығын орындамас бұрын) қажетті барлық ресурстарды сұрату арқылы жоюға болады. Мұндай алдын ала білімді қамтамасыз ету көбінесе қиынға соғады және, әйтеуір, ресурстарды тиімсіз пайдалануға әкеледі. Тағы бір жол – процестерге тек қана ресурстардың болмаған жағдайында ғана сұрануды талап ету; Біріншіден, олар қазіргі уақытта ұстап тұрған барлық ресурстарды босатып, содан кейін қажетті барлық ресурстарды бастапқы күйден сұрауы керек. Бұл да көбінесе іс жүзінде мүмкін емес. Өйткені ресурстар ұзақ уақыт бойы пайдаланылмаған күйде қалуы мүмкін. Сонымен қатар, танымал ресурсқа қажетті процесс шексіз күтуге мәжбүр болуы мүмкін, себебі мұндай ресурс әрқашан басқа бір процесске бөлінеді, нәтижесінде ресурс жетіспеушілігі туындайды. (Мұндай алгоритмдер, мысалы, тізбектелген талон, «барлығы немесе ештеңе» алгоритмдері деп аталады.) Алдын ала алу шартын болдырмау да қиын немесе мүмкін емес болуы мүмкін, өйткені процесс белгілі бір уақытқа ресурсқа ие болуы керек, әйтпесе өңдеу нәтижесі дұрыс болмауы мүмкін немесе жүйе тұрақтанбай қалуы мүмкін. Дегенмен, алдын ала алуды жүзеге асыра алмау басымдық алгоритмінің жұмысына кедергі келтіруі мүмкін. «Блокировкаланған» ресурсты алдын ала алу, әдетте, кері қайтаруды білдіреді және одан аулақ болу керек, себебі ол өте көп шығындарға әкеледі. Алдын ала алуға мүмкіндік беретін алгоритмдерге құлыптамасыз және күтусіз алгоритмдер, сондай-ақ оптимистік параллелизмді басқару жатады. Егер процестің бірнеше ресурсты ұстап тұрғанда, оған бірден бөлінбейтін басқа ресурс(тар) қажет болса, бұл шартты сол процестің қазіргі уақытта ұстап тұрған барлық ресурстарын босату арқылы жоюға болады. Соңғы шарт – дөңгелек күту шарты. Дөңгелек күтуден аулақ болатын тәсілдерге маңызды бөлімдерде үзілістерді өшіру және ресурстардың ішінара ретін анықтау үшін иерархияны пайдалану жатады. Егер айқын иерархия болмаса, тіпті ресурстардың жад адресі де реттеуді анықтау үшін қолданылады және ресурстар санаудың өсу ретімен сұралады.

Deadlock prevention works by preventing one of the four Coffman conditions from occurring. Removing the mutual exclusion condition means that no process will have exclusive access to a resource. This proves impossible for resources that cannot be spooled. But even with spooled resources, the deadlock could still occur. Algorithms that avoid mutual exclusion are called non blocking synchronization algorithms. The hold and wait or resource holding conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations). This advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to request resources only when it has none; First, they must release all their currently held resources before requesting all the resources they will need from scratch. This too is often impractical. It is so because resources may be allocated and remain unused for long periods. Also, a process requiring a popular resource may have to wait indefinitely, as such a resource may always be allocated to some process, resulting in resource starvation. (These algorithms, such as serializing tokens, are known as the all or none algorithms.) The no preemption condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, the inability to enforce preemption may interfere with a priority algorithm. Preemption of a "locked out" resource generally implies a rollback, and is to be avoided since it is very costly in overhead. Algorithms that allow preemption include lock free and wait free algorithms and optimistic concurrency control. If a process holding some resources and requests for some another resource(s) that cannot be immediately allocated to it, the condition may be removed by releasing all the currently being held resources of that process. The final condition is the circular wait condition. Approaches that avoid circular waits include disabling interrupts during critical sections and using a hierarchy to determine a partial ordering of resources. If no obvious hierarchy exists, even the memory address of resources has been used to determine ordering and resources are requested in the increasing order of the enumeration.

Тірілік

Тірілік тұйыққа ұқсас, бірақ тірілікке қатысқан процестердің күйлері бір-біріне қатысты үнемі өзгеріп отырады, бірақ ешқайсысы да ілгерілемейді. Бұл терминді 1975 жылы Эдвард А. Эшкрофт әуе компанияларының брондау жүйелерін зерттеу жұмысында қолданған. Тірілік – ресурстардың жетіспеушілігінің ерекше түрі; жалпы анықтамада тек белгілі бір процесс ілгерілемейтіні айтылады. Тірілік, тұйықтан кейін қалпына келтіруге арналған кейбір алгоритмдермен байланысты тәуекел. Егер бірнеше процесс әрекет етсе, тұйық анықтау алгоритмі қайта-қайта шақырылуы мүмкін. Мұны тек бір процесске (кездейсоқ немесе басымдық бойынша таңдалған) әрекет етуге рұқсат беру арқылы болдырмауға болады.

Таратылған тұйықталу

Таратылған мәмілелер немесе бір мезгілделік басқару қолданылған кезде таратылған жүйелерде таратылған тұйықтар пайда болуы мүмкін. Таратылған тұйықтарды тұйықтарды анықтағыштан жергілікті күту графиктерінен глобалды күту графигін құру арқылы немесе шеттерді іздеу сияқты таратылған алгоритм арқылы анықтауға болады. Фантомдық тұйықтар – жүйе ішіндегі кешігулер салдарынан таратылған жүйеде бұрмаланған түрде анықталатын, бірақ шындығында болмайтын тұйықтар. Мысалы, егер процесс R1 ресурсын босатып, R2 ресурсын сұраса, ал бірінші хабарлама жоғалып кетсе немесе кешіксе, координатор (тұйықтарды анықтаушы) қателікпен тұйықталуды анықтауы мүмкін (егер R1 ресурсы бар кезде R2 ресурсын сұрау тұйықталуға себеп болса).