Π§ΠΈΡ‚Π°ΠΉΡ‚Π΅ ΠΊΠ½ΠΈΠ³ΠΈ ΠΎΠ½Π»Π°ΠΉΠ½ Π½Π° Bookidrom.ru! БСсплатныС ΠΊΠ½ΠΈΠ³ΠΈ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΊΠ»ΠΈΠΊΠ΅

Π§ΠΈΡ‚Π°Ρ‚ΡŒ ΠΎΠ½Π»Π°ΠΉΠ½ Β«Π Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ° ядра LinuxΒ». Π‘Ρ‚Ρ€Π°Π½ΠΈΡ†Π° 48

Автор Π ΠΎΠ±Π΅Ρ€Ρ‚ Π›Π°Π²

Код, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ бСзопасно Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½ΠΎ с ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠΎΠΌ прСрывания, называСтся бСзопасным ΠΏΡ€ΠΈ прСрываниях (interrupt-safe). Код, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ содСрТит Π·Π°Ρ‰ΠΈΡ‚Ρƒ ΠΎΡ‚ ΠΊΠΎΠ½ΠΊΡƒΡ€Π΅Π½Ρ‚Π½ΠΎΠ³ΠΎ доступа ΠΊ рСсурсам ΠΏΡ€ΠΈ симмСтричной многопроцСссорной ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅, называСтся бСзопасным ΠΏΡ€ΠΈ SMP-ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ (SMP-safe). Код, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΈΠΌΠ΅Π΅Ρ‚ Π·Π°Ρ‰ΠΈΡ‚Ρƒ ΠΎΡ‚ ΠΊΠΎΠ½ΠΊΡƒΡ€Π΅Π½Ρ‚Π½ΠΎΠ³ΠΎ доступа ΠΊ рСсурсам ΠΏΡ€ΠΈ вытСснСнии ΠΊΠΎΠ΄Π° ядра, называСтся бСзопасным ΠΏΡ€ΠΈ вытСснСния[45] (preempt-safe). ΠœΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΡ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²ΠΎ всСх этих случаях ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ для обСспСчСния синхронизации ΠΈ Π·Π°Ρ‰ΠΈΡ‚Ρ‹ ΠΎΡ‚ состояний ΠΊΠΎΠ½ΠΊΡƒΡ€Π΅Π½Ρ†ΠΈΠΈ, Π±ΡƒΠ΄ΡƒΡ‚ рассмотрСны Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Π³Π»Π°Π²Π΅.

Π§Ρ‚ΠΎ Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ Π·Π°Ρ‰ΠΈΡ‚Ρ‹

Π–ΠΈΠ·Π½Π΅Π½Π½ΠΎ Π²Π°ΠΆΠ½ΠΎ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊΠΈΠ΅ Π΄Π°Π½Π½Ρ‹Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π·Π°Ρ‰ΠΈΡ‚Ρ‹. Π’Π°ΠΊ ΠΊΠ°ΠΊ любой ΠΊΠΎΠ΄, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ ΠΏΠ°Ρ€Π°Π»Π»Π΅Π»ΡŒΠ½ΠΎ, ΠΌΠΎΠΆΠ΅Ρ‚ ΠΏΠΎΡ‚Ρ€Π΅Π±ΠΎΠ²Π°Ρ‚ΡŒ Π·Π°Ρ‰ΠΈΡ‚Ρ‹. ВСроятно, Π»Π΅Π³Ρ‡Π΅ ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ, ΠΊΠ°ΠΊΠΈΠ΅ Π΄Π°Π½Π½Ρ‹Π΅ Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π·Π°Ρ‰ΠΈΡ‚Ρ‹, ΠΈ Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ дальшС, ΠΎΡ‚Ρ‚Π°Π»ΠΊΠΈΠ²Π°ΡΡΡŒ ΠΎΡ‚ этого. ΠžΡ‡Π΅Π²ΠΈΠ΄Π½ΠΎ, Ρ‡Ρ‚ΠΎ всС Π΄Π°Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ доступны Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ ΠΏΠΎΡ‚ΠΎΠΊΡƒ выполнСния, Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π·Π°Ρ‰ΠΈΡ‚Ρ‹, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ этот ΠΏΠΎΡ‚ΠΎΠΊ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ этим Π΄Π°Π½Π½Ρ‹ΠΌ. НапримСр, Π»ΠΎΠΊΠ°Π»ΡŒΠ½Ρ‹Π΅ ΠΏΠ΅Ρ€Π΅ΠΌΠ΅Π½Π½Ρ‹Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π²Ρ‹Π΄Π΅Π»ΡΡŽΡ‚ΡΡ Π² автоматичСской памяти (ΠΈ Ρ‚Π΅, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ находятся Π² динамичСски выдСляСмой памяти, Ссли ΠΈΡ… адрСса хранятся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² стСкС), Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ Π½ΠΈΠΊΠ°ΠΊΠΈΡ… Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ, Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ½ΠΈ ΡΡƒΡ‰Π΅ΡΡ‚Π²ΡƒΡŽΡ‚ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π² стСкС Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡŽΡ‰Π΅Π³ΠΎΡΡ ΠΏΠΎΡ‚ΠΎΠΊΠ°. Π’ΠΎΡ‡Π½ΠΎ Ρ‚Π°ΠΊ ΠΆΠ΅ Π΄Π°Π½Π½Ρ‹Π΅, ΠΊ ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΌ обращаСтся Ρ‚ΠΎΠ»ΡŒΠΊΠΎ ΠΎΠ΄Π½ΠΎ Π·Π°Π΄Π°Π½ΠΈΠ΅, Π½Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ примСнСния Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ (Ρ‚Π°ΠΊ ΠΊΠ°ΠΊ ΠΎΠ΄ΠΈΠ½ ΠΏΠΎΡ‚ΠΎΠΊ ΠΌΠΎΠΆΠ΅Ρ‚ Π²Ρ‹ΠΏΠΎΠ»Π½ΡΡ‚ΡŒΡΡ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π° ΠΎΠ΄Π½ΠΎΠΌ процСссорС Π² любой ΠΌΠΎΠΌΠ΅Π½Ρ‚ Π²Ρ€Π΅ΠΌΠ΅Π½ΠΈ).

Π§Ρ‚ΠΎ ΠΆΠ΅ Ρ‚ΠΎΠ³Π΄Π° Ρ‚Ρ€Π΅Π±ΡƒΠ΅Ρ‚ примСнСния Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ? Π­Ρ‚ΠΎ β€” Π±ΠΎΠ»ΡŒΡˆΠΈΠ½ΡΡ‚Π²ΠΎ Π³Π»ΠΎΠ±Π°Π»ΡŒΠ½Ρ‹Ρ… структур Π΄Π°Π½Π½Ρ‹Ρ… ядра. Π•ΡΡ‚ΡŒ Ρ…ΠΎΡ€ΠΎΡˆΠ΅Π΅ эмпиричСскоС ΠΏΡ€Π°Π²ΠΈΠ»ΠΎ: Ссли, ΠΊΡ€ΠΎΠΌΠ΅ ΠΎΠ΄Π½ΠΎΠ³ΠΎ, Π΅Ρ‰Π΅ ΠΈ Π΄Ρ€ΡƒΠ³ΠΎΠΉ ΠΏΠΎΡ‚ΠΎΠΊ ΠΌΠΎΠΆΠ΅Ρ‚ ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ Π΄Π°Π½Π½Ρ‹ΠΌ, Ρ‚ΠΎ эти Π΄Π°Π½Π½Ρ‹Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ примСнСния ΠΊΠ°ΠΊΠΎΠ³ΠΎ-Π»ΠΈΠ±ΠΎ Ρ‚ΠΈΠΏΠ° Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ. Если Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ Π²ΠΈΠ΄Π½ΠΎ ΠΊΠΎΠΌΡƒ-Ρ‚ΠΎ Π΅Ρ‰Π΅ β€” Π±Π»ΠΎΠΊΠΈΡ€ΡƒΠΉΡ‚Π΅ Π΅Π³ΠΎ. ΠŸΠΎΠΌΠ½ΠΈΡ‚Π΅, Ρ‡Ρ‚ΠΎ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π΄Π°Π½Π½Ρ‹Π΅, Π° Π½Π΅ ΠΊΠΎΠ΄.

ΠŸΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Ρ‹ ΠšΠžΠΠ€Π˜Π“Π£Π ΠΠ¦Π˜Π˜ ядра: SMP ΠΈΠ»ΠΈ UP

Π’Π°ΠΊ ΠΊΠ°ΠΊ ядро ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΎΠ½Π½ΠΎΠΉ систСмы Linux ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ сконфигурировано Π½Π° этапС компиляции, ΠΈΠΌΠ΅Π΅Ρ‚ смысл "ΠΏΠΎΠ΄ΠΎΠ³Π½Π°Ρ‚ΡŒ" ядро ΠΏΠΎΠ΄ Π΄Π°Π½Π½Ρ‹ΠΉ Ρ‚ΠΈΠΏ ΠΌΠ°ΡˆΠΈΠ½Ρ‹. Π’Π°ΠΆΠ½ΠΎΠΉ Ρ„ΡƒΠ½ΠΊΡ†ΠΈΠ΅ΠΉ ядра являСтся ΠΏΠΎΠ΄Π΄Π΅Ρ€ΠΆΠΊΠ° симмСтричной многопроцСссорной ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚ΠΊΠΈ (SMP), которая Π²ΠΊΠ»ΡŽΡ‡Π°Π΅Ρ‚ΡΡ с ΠΏΠΎΠΌΠΎΡ‰ΡŒΡŽ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π° ΠΊΠΎΠ½Ρ„ΠΈΠ³ΡƒΡ€Π°Ρ†ΠΈΠΈ ядра CONFIG_SMP. На однопроцСссорной (uniprocessor, UP) машинС ΠΈΡΡ‡Π΅Π·Π°ΡŽΡ‚ ΠΌΠ½ΠΎΠ³ΠΈΠ΅ ΠΏΡ€ΠΎΠ±Π»Π΅ΠΌΡ‹, связанныС с Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ°ΠΌΠΈ, ΠΈ, ΡΠ»Π΅Π΄ΠΎΠ²Π°Ρ‚Π΅Π»ΡŒΠ½ΠΎ, Ссли ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ CONFIG_SMP Π½Π΅ установлСн, Ρ‚ΠΎ ΠΊΠΎΠ΄, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Π½Π΅Ρ‚ нСобходимости, Π½Π΅ компилируСтся Π² исполняСмый ΠΎΠ±Ρ€Π°Π· ядра. НапримСр, это позволяСт Π½Π° однопроцСссорной машинС ΠΎΡ‚ΠΊΠ°Π·Π°Ρ‚ΡŒΡΡ ΠΎΡ‚ Π½Π°ΠΊΠ»Π°Π΄Π½Ρ‹Ρ… расходов, связанных со спин-Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ°ΠΌΠΈ. Аналогичный ΠΏΡ€ΠΈΠ΅ΠΌ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ для ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€Π° CONFIG_PREEMPT (ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ ядра, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ ΡƒΠΊΠ°Π·Ρ‹Π²Π°Π΅Ρ‚, Π±ΡƒΠ΄Π΅Ρ‚ Π»ΠΈ ядро вытСсняСмым). Π’Π°ΠΊΠΎΠ΅ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅ являСтся ΠΎΡ‚Π»ΠΈΡ‡Π½Ρ‹ΠΌ ΠΏΡ€ΠΎΠ΅ΠΊΡ‚Π½Ρ‹ΠΌ Ρ€Π΅ΡˆΠ΅Π½ΠΈΠ΅, ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΎΠ±Ρ‰ΠΈΠΉ Ρ‡Π΅Ρ‚ΠΊΠΈΠΉ исходный ΠΊΠΎΠ΄, Π° Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΡ‹ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ ΠΏΡ€ΠΈ нСобходимости. Π Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΊΠΎΠΌΠ±ΠΈΠ½Π°Ρ†ΠΈΠΈ ΠΏΠ°Ρ€Π°ΠΌΠ΅Ρ‚Ρ€ΠΎΠ² CONFIG_SMP ΠΈ CONFIG_PREEMPT Π½Π° Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Ρ… Π°ΠΏΠΏΠ°Ρ€Π°Ρ‚Π½Ρ‹Ρ… ΠΏΠ»Π°Ρ‚Ρ„ΠΎΡ€ΠΌΠ°Ρ… ΠΏΠΎΠ·Π²ΠΎΠ»ΡΡŽΡ‚ ΠΊΠΎΠΌΠΏΠΈΠ»ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π² ядро Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΌΠ΅Ρ…Π°Π½ΠΈΠ·ΠΌΡ‹ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ.

ΠŸΡ€ΠΈ написании ΠΊΠΎΠ΄Π° Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΎΠ±Π΅ΡΠΏΠ΅Ρ‡ΠΈΡ‚ΡŒ всС Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Π΅ Π²Π°Ρ€ΠΈΠ°Π½Ρ‚Ρ‹ Π·Π°Ρ‰ΠΈΡ‚Ρ‹ для всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… случаСв ΠΆΠΈΠ·Π½ΠΈ ΠΈ всСх Π²ΠΎΠ·ΠΌΠΎΠΆΠ½Ρ‹Ρ… сцСнариСв, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ рассмотрСны.

ΠŸΡ€ΠΈ написании ΠΊΠΎΠ΄Π° ядра слСдуСт Π·Π°Π΄Π°Ρ‚ΡŒ сСбС ΡΠ»Π΅Π΄ΡƒΡŽΡ‰ΠΈΠ΅ вопросы.

β€’ Π―Π²Π»ΡΡŽΡ‚ΡΡ Π»ΠΈ Π΄Π°Π½Π½Ρ‹Π΅ Π³Π»ΠΎΠ±Π°Π»ΡŒΠ½Ρ‹ΠΌΠΈ? ΠœΠΎΠΆΠ΅Ρ‚ Π»ΠΈ Π΄Ρ€ΡƒΠ³ΠΎΠΉ ΠΏΠΎΡ‚ΠΎΠΊ выполнСния, ΠΊΡ€ΠΎΠΌΠ΅ Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ, ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ этим Π΄Π°Π½Π½Ρ‹ΠΌ?

β€’ Π―Π²Π»ΡΡŽΡ‚ΡΡ Π»ΠΈ Π΄Π°Π½Π½Ρ‹Π΅ совмСстно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹ΠΌΠΈ ΠΈΠ· контСкста процСсса ΠΈ ΠΈΠ· контСкста прСрывания? Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ Π»ΠΈ ΠΈΡ… совмСстно Π΄Π²Π° ΠΎΠ±Ρ€Π°Π±ΠΎΡ‚Ρ‡ΠΈΠΊΠ° ΠΏΡ€Π΅Ρ€Ρ‹Π²Π°Π½ΠΈΠΉ?

β€’ Π•сли процСсс Π²ΠΎ врСмя доступа ΠΊ Π΄Π°Π½Π½Ρ‹ΠΌ Π±ΡƒΠ΄Π΅Ρ‚ вытСснСн, ΠΌΠΎΠΆΠ΅Ρ‚ Π»ΠΈ Π½ΠΎΠ²Ρ‹ΠΉ процСсс, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π·Π°ΠΏΠ»Π°Π½ΠΈΡ€ΠΎΠ²Π°Π½ Π½Π° Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅, ΠΎΠ±Ρ€Π°Ρ‰Π°Ρ‚ΡŒΡΡ ΠΊ этим ΠΆΠ΅ Π΄Π°Π½Π½Ρ‹ΠΌ?

β€’ ΠœΠΎΠΆΠ΅Ρ‚ Π»ΠΈ Ρ‚Π΅ΠΊΡƒΡ‰ΠΈΠΉ процСсс ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ Π² состояниС оТидания (Π·Π°Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒΡΡ) Π½Π° ΠΊΠ°ΠΊΠΎΠΉ-Π»ΠΈΠ±ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†ΠΈΠΈ? Если Π΄Π°, Ρ‚ΠΎ Π² ΠΊΠ°ΠΊΠΎΠΌ состоянии ΠΎΠ½ оставляСт всС совмСстно ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌΡ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅?

β€’ Π§Ρ‚ΠΎ Π·Π°ΠΏΡ€Π΅Ρ‰Π°Π΅Ρ‚ ΠΎΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡ‚ΡŒ ΠΏΠ°ΠΌΡΡ‚ΡŒ, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΉ находятся Π΄Π°Π½Π½Ρ‹Π΅?

β€’ Π§Ρ‚ΠΎ ΠΏΡ€ΠΎΠΈΠ·ΠΎΠΉΠ΄Π΅Ρ‚, Ссли эта ΠΆΠ΅ функция Π±ΡƒΠ΄Π΅Ρ‚ Π²Ρ‹Π·Π²Π°Π½Π° Π½Π° Π΄Ρ€ΡƒΠ³ΠΎΠΌ процСссорС?

β€’ ΠšΠ°ΠΊ всС это ΡƒΡ‡Π΅ΡΡ‚ΡŒ?

Если ΠΊΠΎΡ€ΠΎΡ‚ΠΊΠΎ, Ρ‚ΠΎ ΠΏΠΎΡ‡Ρ‚ΠΈ всС Π³Π»ΠΎΠ±Π°Π»ΡŒΠ½Ρ‹Π΅ Π΄Π°Π½Π½Ρ‹Π΅ Ρ‚Ρ€Π΅Π±ΡƒΡŽΡ‚ примСнСния Ρ‚Π΅Ρ… ΠΈΠ»ΠΈ Π΄Ρ€ΡƒΠ³ΠΈΡ… ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠ² синхронизации, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Π±ΡƒΠ΄ΡƒΡ‚ рассмотрСны Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΉ Π³Π»Π°Π²Π΅.

Π’Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ

Π’Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° (тупиковая ситуация, deadlock) β€” это состояниС, ΠΏΡ€ΠΈ ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΏΠΎΡ‚ΠΎΠΊ ΠΎΠΆΠΈΠ΄Π°Π΅Ρ‚ Π½Π° освобоТдСниС ΠΎΠ΄Π½ΠΎΠ³ΠΎ ΠΈΠ· рСсурсов, Π° всС рСсурсы ΠΏΡ€ΠΈ этом Π·Π°Ρ…Π²Π°Ρ‡Π΅Π½Ρ‹. ΠŸΠΎΡ‚ΠΎΠΊΠΈ Π±ΡƒΠ΄ΡƒΡ‚ ΠΎΠΆΠΈΠ΄Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ Π΄Ρ€ΡƒΠ³Π°, ΠΈ ΠΎΠ½ΠΈ Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ смогут ΠΎΡΠ²ΠΎΠ±ΠΎΠ΄ΠΈΡ‚ΡŒ Π·Π°Ρ…Π²Π°Ρ‡Π΅Π½Π½Ρ‹Π΅ рСсурсы. ΠŸΠΎΡΡ‚ΠΎΠΌΡƒ Π½ΠΈ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ² Π½Π΅ смоТСт ΠΏΡ€ΠΎΠ΄ΠΎΠ»ΠΆΠ°Ρ‚ΡŒ Π²Ρ‹ΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ ΠΎΠ·Π½Π°Ρ‡Π°Π΅Ρ‚ Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ.

Π₯ΠΎΡ€ΠΎΡˆΠ°Ρ аналогия β€” это пСрСкрСсток, Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ стоят Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΏΠΎΠ΄ΡŠΠ΅Ρ…Π°Π»ΠΈ с Ρ‡Π΅Ρ‚Ρ‹Ρ€Π΅Ρ… Ρ€Π°Π·Π½Ρ‹Ρ… сторон. КаТдая машина ΠΎΠΆΠΈΠ΄Π°Π΅Ρ‚, ΠΏΠΎΠΊΠ° Π½Π΅ ΡƒΠ΅Π΄ΡƒΡ‚ ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ°ΡˆΠΈΠ½Ρ‹, ΠΈ Π½ΠΈ ΠΎΠ΄Π½Π° ΠΈΠ· машин Π½Π΅ смоТСт ΡƒΠ΅Ρ…Π°Ρ‚ΡŒ; Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Π΅ получаСтся тупиковая ситуация.

Π‘Π°ΠΌΡ‹ΠΉ простой ΠΏΡ€ΠΈΠΌΠ΅Ρ€ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈβ€” это самоблокировка[46] (self-deadlock). Если ΠΏΠΎΡ‚ΠΎΠΊ выполнСния пытаСтся Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Ρ‚Ρƒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ, ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΎΠ½ ΡƒΠΆΠ΅ ΡƒΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚, Ρ‚ΠΎ Π΅ΠΌΡƒ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π΄ΠΎΠΆΠ΄Π°Ρ‚ΡŒΡΡ, ΠΏΠΎΠΊΠ° Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ освобоТдСна. Но ΠΏΠΎΡ‚ΠΎΠΊ Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ освободит Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ, ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ ΠΎΠ½ ΠΎΠΆΠΈΠ΄Π°Π΅Ρ‚ Π½Π° Π΅Π΅ Π·Π°Ρ…Π²Π°Ρ‚, ΠΈ это ΠΏΡ€ΠΈΠ²ΠΎΠ΄ΠΈΡ‚ ΠΊ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²ΠΎΠΉ ситуации.

Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ

Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ Π΅Ρ‰Π΅ Ρ€Π°Π·

ΠΆΠ΄Π°Ρ‚ΡŒ, ΠΏΠΎΠΊΠ° Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ освобоТдСна

...

Аналогично рассмотрим n ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ² ΠΈ n Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ. Если ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ ΠΏΠΎΡ‚ΠΎΠΊ ΡƒΠ΄Π΅Ρ€ΠΆΠΈΠ²Π°Π΅Ρ‚ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ, Π½Π° ΠΊΠΎΡ‚ΠΎΡ€ΡƒΡŽ ΠΎΠΆΠΈΠ΄Π°Π΅Ρ‚ Π΄Ρ€ΡƒΠ³ΠΎΠΉ ΠΏΠΎΡ‚ΠΎΠΊ, Ρ‚ΠΎ всС ΠΏΠΎΡ‚ΠΎΠΊΠΈ Π±ΡƒΠ΄ΡƒΡ‚ Π·Π°Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²Π°Π½Ρ‹ Π΄ΠΎ Ρ‚Π΅Ρ… ΠΏΠΎΡ€, ΠΏΠΎΠΊΠ° Π½Π΅ освободятся Ρ‚Π΅ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ, Π½Π° освобоТдСниС ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Ρ… ΠΎΠΆΠΈΠ΄Π°ΡŽΡ‚ ΠΏΠΎΡ‚ΠΎΠΊΠΈ. НаиболСС часто Π²ΡΡ‚Ρ€Π΅Ρ‡Π°ΡŽΡ‰ΠΈΠΉΡΡ ΠΏΡ€ΠΈΠΌΠ΅Ρ€ β€” это Π΄Π²Π° ΠΏΠΎΡ‚ΠΎΠΊΠ° ΠΈ Π΄Π²Π΅ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ, Ρ‡Ρ‚ΠΎ часто называСтся Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° Ρ‚ΠΈΠΏΠ° ABBA (ABBA deadlock).

ΠŸΠΎΡ‚ΠΎΠΊ 1                                                                ΠŸΠΎΡ‚ΠΎΠΊ 2

Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ А             Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ Π’

ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ° Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ Π’     ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ° Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ А

ΠΎΠΆΠΈΠ΄Π°Π½ΠΈΠ΅ освобоТдСния Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ Π’ ΠΎΠΆΠΈΠ΄Π°Π½ΠΈΠ΅ освобоТдСния Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ А

Оба ΠΏΠΎΡ‚ΠΎΠΊΠ° Π±ΡƒΠ΄ΡƒΡ‚ ΠΎΠΆΠΈΠ΄Π°Ρ‚ΡŒ Π΄Ρ€ΡƒΠ³ Π΄Ρ€ΡƒΠ³Π°, ΠΈ Π½ΠΈ ΠΎΠ΄ΠΈΠ½ ΠΈΠ· ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ² Π½ΠΈΠΊΠΎΠ³Π΄Π° Π½Π΅ освободит ΠΏΠ΅Ρ€Π²ΠΎΠ½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎ Π·Π°Ρ…Π²Π°Ρ‡Π΅Π½Π½ΠΎΠΉ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ, поэтому Π½ΠΈ ΠΎΠ΄Π½Π° ΠΈΠ· Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ освобоТдСна. Вакая тупиковая ситуация Π΅Ρ‰Π΅ называСтся deadly embrace (Π±ΡƒΠΊΠ²Π°Π»ΡŒΠ½ΠΎ. ΡΠΌΠ΅Ρ€Ρ‚Π΅Π»ΡŒΠ½Ρ‹Π΅ ΠΎΠ±ΡŠΡΡ‚ΠΈΡ).

Π’Π°ΠΆΠ½ΠΎ Π½Π΅ Π΄ΠΎΠΏΡƒΡΡ‚ΠΈΡ‚ΡŒ появлСниС Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ. Π₯отя слоТно ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ Π³ΠΎΡ‚ΠΎΠ²Ρ‹ΠΉ ΠΊΠΎΠ΄ Π½Π° Π½Π°Π»ΠΈΡ‡ΠΈΠ΅ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ, ΠΌΠΎΠΆΠ½ΠΎ Π½Π°ΠΏΠΈΡΠ°Ρ‚ΡŒ ΠΊΠΎΠ΄, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π½Π΅ содСрТит Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ. Π’Π°ΠΊΡƒΡŽ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π΄Π°Π΅Ρ‚ соблюдСниС Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… простых ΠΏΡ€Π°Π²ΠΈΠ».

β€’ Π–ΠΈΠ·Π½Π΅Π½Π½ΠΎ Π²Π°ΠΆΠ½Ρ‹ΠΌ являСтся порядок Π·Π°Ρ…Π²Π°Ρ‚Π° Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ. Π’Π»ΠΎΠΆΠ΅Π½Π½Ρ‹Π΅ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ всСгда Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒΡΡ Π² ΠΎΠ΄Π½ΠΎΠΌ ΠΈ Ρ‚ΠΎΠΌ ΠΆΠ΅ порядкС. Π­Ρ‚ΠΎ ΠΏΡ€Π΅Π΄ΠΎΡ‚Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ Π½Π΅ΡΠΊΠΎΠ»ΡŒΠΊΠΈΡ… ΠΏΠΎΡ‚ΠΎΠΊΠΎΠ² (deadly embrace). ΠŸΠΎΡ€ΡΠ΄ΠΎΠΊ Π·Π°Ρ…Π²Π°Ρ‚Π° Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π΄ΠΎΠΊΡƒΠΌΠ΅Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π΄Ρ€ΡƒΠ³ΠΈΠ΅ Ρ‚ΠΎΠΆΠ΅ ΠΌΠΎΠ³Π»ΠΈ Π΅Π³ΠΎ ΡΠΎΠ±Π»ΡŽΠ΄Π°Ρ‚ΡŒ.

β€’ ΠΠ΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΡ€Π΅Π΄ΠΎΡ‚Π²Ρ€Π°Ρ‰Π°Ρ‚ΡŒ зависания. Π‘Π»Π΅Π΄ΡƒΠ΅Ρ‚ ΡΠΏΡ€ΠΎΡΠΈΡ‚ΡŒ сСбя: "ВсСгда Π»ΠΈ этот ΠΊΠΎΠ΄ смоТСт Π·Π°Π²Π΅Ρ€ΡˆΠΈΡ‚ΡŒΡΡ?". Если Π½Π΅ выполнится ΠΊΠ°ΠΊΠΎΠ΅-Π»ΠΈΠ±ΠΎ условиС, Ρ‚ΠΎ Π½Π΅ Π±ΡƒΠ΄Π΅Ρ‚ Π»ΠΈ Ρ‡Ρ‚ΠΎ-Ρ‚ΠΎ ΠΎΠΆΠΈΠ΄Π°Ρ‚ΡŒ Π²Π΅Ρ‡Π½ΠΎ?

β€’ ΠΠ΅ Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ ΠΎΠ΄Π½Ρƒ ΠΈ Ρ‚Ρƒ ΠΆΠ΅ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ Π΄Π²Π°ΠΆΠ΄Ρ‹.

β€’ Π‘Π»ΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π² схСмС Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ β€” Π²Π΅Ρ€Π½Ρ‹ΠΉ ΠΏΡƒΡ‚ΡŒ ΠΊ Ρ‚ΡƒΠΏΠΈΠΊΠΎΠ²Ρ‹ΠΌ ситуациям, поэтому ΠΏΡ€ΠΈ Ρ€Π°Π·Ρ€Π°Π±ΠΎΡ‚ΠΊΠ΅ Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΡΡ‚Ρ€Π΅ΠΌΠΈΡ‚ΡŒΡΡ ΠΊ простотС.

ΠŸΠ΅Ρ€Π²Ρ‹ΠΉ ΠΏΡƒΠ½ΠΊΡ‚ Π²Π°ΠΆΠ½Ρ‹ΠΉ ΠΈ Π½Π°ΠΈΠΌΠ΅Π½Π΅Π΅ слоТный для выполнСния. Если Π΄Π²Π΅ ΠΈΠ»ΠΈ Π±ΠΎΠ»Π΅Π΅ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΎΠΊ Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°ΡŽΡ‚ΡΡ Π² ΠΎΠ΄Π½ΠΎΠΌ мСстС, Ρ‚ΠΎ ΠΎΠ½ΠΈ всСгда Π΄ΠΎΠ»ΠΆΠ½Ρ‹ Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒΡΡ Π² строго ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Π½ΠΎΠΌ порядкС. Допустим, Ρƒ нас Π΅ΡΡ‚ΡŒ Ρ‚Ρ€ΠΈ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ cat, dog ΠΈ fox, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΡŽΡ‚ΡΡ для Π·Π°Ρ‰ΠΈΡ‚Ρ‹ Π΄Π°Π½Π½Ρ‹Ρ… с Ρ‚Π°ΠΊΠΈΠΌΠΈ ΠΆΠ΅ ΠΈΠΌΠ΅Π½Π°ΠΌΠΈ. И Π΅Ρ‰Π΅ допустим, Ρ‡Ρ‚ΠΎ Ρƒ нас Π΅ΡΡ‚ΡŒ функция, которая Π΄ΠΎΠ»ΠΆΠ½Π° Ρ€Π°Π±ΠΎΡ‚Π°Ρ‚ΡŒ с этими трСмя структурами Π΄Π°Π½Π½Ρ‹Ρ… ΠΎΠ΄Π½ΠΎΠ²Ρ€Π΅ΠΌΠ΅Π½Π½ΠΎβ€” Π½Π°ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΌΠΎΠΆΠ΅Ρ‚ ΠΊΠΎΠΏΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅ ΠΌΠ΅ΠΆΠ΄Ρƒ Π½ΠΈΠΌΠΈ. Π’ любом случаС, для Ρ‚ΠΎΠ³ΠΎ Ρ‡Ρ‚ΠΎΠ±Ρ‹ Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ Π±Π΅Π·ΠΎΠΏΠ°ΡΠ½ΠΎΡΡ‚ΡŒ доступа, эти структуры Π΄Π°Π½Π½Ρ‹Ρ… Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ Π·Π°Ρ‰ΠΈΡ‰Π°Ρ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ°ΠΌΠΈ. Если ΠΎΠ΄Π½Π° функция Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Π΅Ρ‚ эти Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ Π² ΡΠ»Π΅Π΄ΡƒΡŽΡ‰Π΅ΠΌ порядкС: cat, dog ΠΈ Π² ΠΊΠΎΠ½Ρ†Π΅ fox, Ρ‚ΠΎ любая другая функция Π΄ΠΎΠ»ΠΆΠ½Π° Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ эти Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ (ΠΈΠ»ΠΈ Ρ‚ΠΎΠ»ΡŒΠΊΠΎ Π½Π΅ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ ΠΈΠ· Π½ΠΈΡ…) Π² Ρ‚ΠΎΠΌ ΠΆΠ΅ порядкС. НапримСр, Ссли Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒ сначала Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ fox, Π° ΠΏΠΎΡ‚ΠΎΠΌ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ dog, Ρ‚ΠΎ это ΠΏΠΎΡ‚Π΅Π½Ρ†ΠΈΠ°Π»ΡŒΠ½Π°Ρ Π²ΠΎΠ·ΠΌΠΎΠΆΠ½ΠΎΡΡ‚ΡŒ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΈ (Π° Π·Π½Π°Ρ‡ΠΈΡ‚, ошибки Π² Ρ€Π°Π±ΠΎΡ‚Π΅), ΠΏΠΎΡ‚ΠΎΠΌΡƒ Ρ‡Ρ‚ΠΎ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ° dog всСгда Π΄ΠΎΠ»ΠΆΠ½Π° Π·Π°Ρ…Π²Π°Ρ‚Ρ‹Π²Π°Ρ‚ΡŒΡΡ ΠΏΠ΅Ρ€Π΅Π΄ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠΎΠΉ fox. И Π΅Ρ‰Π΅ Ρ€Π°Π· рассмотрим ΠΏΡ€ΠΈΠΌΠ΅Ρ€, ΠΊΠ°ΠΊ ΠΌΠΎΠΆΠ΅Ρ‚ Π²ΠΎΠ·Π½ΠΈΠΊΠ½ΡƒΡ‚ΡŒ Π²Π·Π°ΠΈΠΌΠΎΠ±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΠ°.

ΠŸΠΎΡ‚ΠΎΠΊ 1                                                                   ΠŸΠΎΡ‚ΠΎΠΊ 2

Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ cat             Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ fox

Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ dog             ΠΏΠΎΠΏΡ‹Ρ‚ΠΊΠ° Π·Π°Ρ…Π²Π°Ρ‚ΠΈΡ‚ΡŒ Π±Π»ΠΎΠΊΠΈΡ€ΠΎΠ²ΠΊΡƒ dog