Лэмпорттың нан пісіру алгоритмі: бірнеше жіптер арасында ортақ ресурстарды қауіпсіз бөлісу үшін өзара құлыптау алгоритмі. Деректердің бұзылуын болдырмайды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ресурстарды қауіпсіз бөлісу логикасы
Logic for safely sharing computer resources
Лампорттың нан пісіру алгоритмі – компьютерлік ғалым Лесли Лампорттың бір мезгілде орындалатын жүйелердің формалды дұрыстығын терең зерттеуінің бір бөлігі ретінде жасалған компьютерлік алгоритм. Ол өзара қол жеткізуді (mutual exclusion) пайдалану арқылы бірнеше жіптер арасында ортақ ресурстарды пайдалану қауіпсіздігін арттыруға бағытталған. Компьютер ғылымында бірнеше жіптердің бір уақытта бірдей ресурстарға қол жеткізуі жиі кездеседі. Егер екі немесе одан көп жіп бірдей жад орнына жазуға тырысса немесе бір жіп екіншісі жад орнына жазуды аяқтамас бұрын оқыса, деректердің бұзылуы мүмкін. Лампорттың нан пісіру алгоритмі – деректердің бұзылу қаупін болдырмау үшін кодтың маңызды бөлімдеріне бір мезгілде кіруді қамтамасыз ететін көптеген өзара қол жеткізу алгоритмдерінің бірі.
Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion. In computer science, it is common for multiple threads to simultaneously access the same resources. Data corruption can occur if two or more threads try to write into the same memory location, or if one thread reads a memory location before another has finished writing into it. Lamport's bakery algorithm is one of many mutual exclusion algorithms designed to prevent concurrent threads entering critical sections of code concurrently to eliminate the risk of data corruption.
Салыстырмалылық
Лампорттың ойынша, нан пісіру орталығының кіреберісінде нөмір тағайындау машинасы орнатылған, осылайша әрбір клиентке бірегей нөмір беріледі. Клиенттер орталыққа келген сайын нөмірлер бірге өседі. Жалпы сандық көрсеткіш қазір қызмет көрсетіліп жатқан клиенттің нөмірін көрсетеді. Қалған барлық клиенттер нан пісіруші ағымдағы клиентке қызмет көрсетуді аяқтап, келесі нөмір көрсетілгенше кезекте күтуі керек. Клиент сатып алуын аяқтап, нөмірін қайтарғаннан кейін, кассир келесі клиентке қызмет көрсету үшін нөмірді арттырады. Сол клиент қайтадан сатып алу үшін нөмір тағайындау машинасынан жаңа нөмір алуы тиіс. Аналогия бойынша, "клиенттер" – бұл i әрпімен белгіленетін, жаһандық айнымалыдан алынған жіптер. Компьютерлік архитектураның шектеулеріне байланысты Лампорттың аналогиясының кейбір бөліктеріне шағын түзетулер енгізу қажет. Бірнеше жіп бірдей n нөмірін сұрағанда алуы мүмкін; мұны болдырмауға болмайды (алғашқыда өзара қатынастың мәселесін шешпей, бұл алгоритмнің мақсаты). Сондықтан жіп идентификаторы i де басымдыққа ие деп есептеледі. i-нің кіші мәні жоғары басымдықты білдіреді және жоғары басымдылыққа ие жіптер алдымен сындық бөлімге кіреді.
Lamport envisioned a bakery with a numbering machine at its entrance so each customer is given a unique number. Numbers increase by one as customers enter the store. A global counter displays the number of the customer that is currently being served. All other customers must wait in a queue until the baker finishes serving the current customer and the next number is displayed. When the customer is done shopping and has disposed of his or her number, the clerk increments the number, allowing the next customer to be served. That customer must draw another number from the numbering machine in order to shop again. According to the analogy, the "customers" are threads, identified by the letter i, obtained from a global variable. Due to the limitations of computer architecture, some parts of Lamport's analogy need slight modification. It is possible that more than one thread will get the same number n when they request it; this cannot be avoided (without first solving the mutual exclusion problem, which is the goal of the algorithm). Therefore, it is assumed that the thread identifier i is also a priority. A lower value of i means a higher priority and threads with higher priority will enter the critical section first.
Критикалық емес бөлім
Критикалық емес бөлім – эксклюзивті қолжеткізуді қажет етпейтін кодтың бөлігі. Ол басқа жіптердің ресурстарына және орындалуына араласпайтын, жіпке тән есептеуді көрсетеді. Бұл бөлім сауда жасағаннан кейін ақшаны әмианға салу сияқты әрекеттерге ұқсас.
The non critical section is the part of code that doesn't need exclusive access. It represents some thread specific computation that doesn't interfere with other threads' resources and execution. This part is analogous to actions that occur after shopping, such as putting change back into the wallet.