Кіріспе
CPU нұсқаулығы жад орнын 1-ге орнату және оның бұрынғы мәнін қайтару үшін. Компьютерлік ғылымда тест және орнату нұсқаулығы – жад орнына 1 мәнін жазу (бекіту) және оның ескі мәнін бір атомдық (яғни, үзілмейтін) операция ретінде қайтару үшін қолданылатын нұсқаулық. Шақырушы нәтижені «тексеріп», күй шақыру арқылы өзгергенін анықтай алады. Егер бірнеше процесс бірдей жад орнына қол жеткізе алса және бір процесс тест және орнату операциясын орындап жатса, басқа процесс бірінші процестің тест және орнату операциясы аяқталғанға дейін жаңа тест және орнату операциясын бастай алмайды. Орталық процессор (CPU) басқа электрондық компоненттер, мысалы, қос портты жад арқылы ұсынылатын тест және орнату нұсқауларын пайдалана алады; CPU өзі де тест және орнату нұсқауларын ұсына алады. Атомдық тест және орнату нұсқаулығын пайдаланып құлыпты былай құруға болады:
In computer science, the test and set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i. e., non interruptible) operation. The caller can then "test" the result to see if the state was changed by the call. If multiple processes may access the same memory location, and if a process is currently performing a test and set, no other process may begin another test and set until the first process's test and set is finished. A central processing unit (CPU) may use a test and set instruction offered by another electronic component, such as dual port RAM; a CPU itself may also offer a test and set instruction. A lock can be built using an atomic test and set instruction as follows:
This code assumes that the memory location was initialized to 0 at some point prior to the first test and set. The calling process obtains the lock if the old value was 0, otherwise the while loop spins waiting to acquire the lock. This is called a spinlock. At any point, the holder of the lock can simply set the memory location back to 0 to release the lock for acquisition by another this does not require any special handling as the holder "owns" this memory location. "Test and test and set" is another example. Maurice Herlihy (1991) proved that test and set (1 bit comparand) has a finite consensus number and can solve the wait free consensus problem for at most two concurrent processes. In contrast, compare and swap (32 bit comparand) offers a more general solution to this problem, and in some implementations compare double and swap (64 bit comparand) is also available for extended utility.
Бұл код жад орны алғашқы тест және орнату операциясынан бұрын 0 мәнімен инициализацияланғанын болжайды. Шақырушы процесс ескі мән 0 болса, құлыпты алады, әйтпесе while циклы құлыпты алу үшін күте береді. Бұл спинлок деп аталады. Кез келген уақытта құлыпты ұстап тұрған процесс жад орнына 0 мәнін қайтару арқылы құлыпты босата алады, бұл басқа процесс үшін құлыпты алуға мүмкіндік береді және арнайы өңдеуді қажет етпейді, себебі ұстап тұрған процесс осы жад орнына «иелік етеді». «Тексеру және тест және орнату» – тағы бір мысал. Морис Герлихи (1991) тест және орнату (1 бит салыстыру) шекті консенсус санына ие екенін және ең көп дегенде екі параллель процесс үшін күтусіз консенсус мәселесін шеше алатынын дәлелдеді. Керісінше, салыстыру және алмастыру (32 бит салыстыру) осы мәселенің көбірек жалпылама шешімін ұсынады, ал кейбір жүзеге асыруларда қос салыстыру және алмастыру (64 бит салыстыру) кеңейтілген мүмкіндіктер үшін де қол жетімді.
In computer science, the test and set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i. e., non interruptible) operation. The caller can then "test" the result to see if the state was changed by the call. If multiple processes may access the same memory location, and if a process is currently performing a test and set, no other process may begin another test and set until the first process's test and set is finished. A central processing unit (CPU) may use a test and set instruction offered by another electronic component, such as dual port RAM; a CPU itself may also offer a test and set instruction. A lock can be built using an atomic test and set instruction as follows:
This code assumes that the memory location was initialized to 0 at some point prior to the first test and set. The calling process obtains the lock if the old value was 0, otherwise the while loop spins waiting to acquire the lock. This is called a spinlock. At any point, the holder of the lock can simply set the memory location back to 0 to release the lock for acquisition by another this does not require any special handling as the holder "owns" this memory location. "Test and test and set" is another example. Maurice Herlihy (1991) proved that test and set (1 bit comparand) has a finite consensus number and can solve the wait free consensus problem for at most two concurrent processes. In contrast, compare and swap (32 bit comparand) offers a more general solution to this problem, and in some implementations compare double and swap (64 bit comparand) is also available for extended utility.
Сынау мен жиынтықты аппараттық іске асыру
DPRAM сынақтары мен орнату нұсқаулары әртүрлі тәсілдермен жұмыс істей алады. Міне, екі нұсқасы, екеуі де 2 портты DPRAM-ды сипаттайды, бұл 2 жеке электрондық құрылғыға (мысалы, 2 процессор) DPRAM-дағы кез келген жад орнына қол жеткізуге мүмкіндік береді.
1-өзгеріс
CPU 1 тест және орнату нұсқаулығын берген кезде, DPRAM алдымен жад орнының мекенжайын арнайы жерге сақтап, бұл туралы "ішкі жазба" жасайды. Егер осы сәтте CPU 2 сол жад орнына тест және орнату нұсқаулығын берсе, DPRAM бірінші кезекте өзінің "ішкі жазбасын" тексереді, жағдайды анықтап, CPU 2-ге күтіп қайтадан талпыну керектігін хабарлайтын BUSY үзілісін шығарады. Бұл үзіліс механизмін қолдана отырып, бос күту немесе спинлоктің іске асырылуы. Бәрі аппараттық жылдамдықпен орындалғандықтан, CPU 2 спинлоктен шығу үшін күтетін уақыт өте қысқа. CPU 2 жад орнына кіруге тырысқан-тырыспаған, DPRAM CPU 1 берген тестті орындайды. Егер тест сәтті аяқталса, DPRAM жад орнын CPU 1 берген мәнге орнатады. Содан кейін DPRAM CPU 1 жазып қалдырған "ішкі жазбаны" жояды. Осы кезде CPU 2 тест және орнату нұсқаулығын бере алады, ол сәтті орындалады.
2-ші түрлендіру
CPU 1 «жад орны А»-ға жазу үшін сынақ және орнату нұсқауын береді. DPRAM жад орны А-дағы мәнді бірден сақтамайды, бірақ ағымдағы мәнді арнайы тіркегішке бірден көшіріп, сондай-ақ жад орны А-ның мазмұнын арнайы «белгі мәніне» орнатады. Егер осы кезде CPU 2 жад орны А-ға сынақ және орнату нұсқауын берсе, DPRAM арнайы белгі мәнін анықтап, 1-варианттағыдай, BUSY үзілісін тудырады. CPU 2 жад орнына кіруге тырысқан-тырыспағанына қарамастан, DPRAM енді CPU 1-дің сынағын орындайды. Егер сынақ сәтті аяқталса, DPRAM жад орны А-ны CPU 1 көрсеткен мәнге орнатады. Егер сынақ сәтсіз болса, DPRAM мәнді арнайы тіркегіштен жад орны А-ға қайта көшіреді. Екі операцияның бірі де арнайы белгі мәнін жояды. Егер CPU 2 енді сынақ және орнату нұсқауын берсе, ол сәтті орындалады.
Сынау және орнату құлыптарының қызмет көрсетуін бағалау
Жалпы құлыптарды бағалаудың төрт негізгі өлшемі – даусыз құлыпты алудың кешігу мерзімі, шина трафигі, әділдік және жадты сақтау. Тестілеу және орнату екі өлшем бойынша нашар нәтижелер көрсетеді, атап айтқанда, жоғары шина трафигі және әділетсіздік. Егер P1 процессоры құлыпты алса, ал P2 процессоры да оны күтіп тұрса, P2 құлыпты алуға тырысып, шина транзакцияларын қайта-қайта орындай береді. Процессор құлыпты алғаннан кейін, сол құлыпты алуға ниеттенген басқа процессорлар, құлыпты иеленгенше шина транзакцияларын үнемі бастап отырады. Бұл тестілеу және орнату үшін шина трафигінің қажеттілігін күрт арттырады. Бұл кэштен және үйлесімсіздік қателерден туындаған барлық трафикті баяулатады. Шина трафигі құлыпты алу әрекеттерінің сәтсіздігінен толып кеткендіктен, бұл бөлімнің жалпы өнімділігі төмендейді. Тестілеу және тестілеу және орнату, TSL-ге қарағанда жақсырақ, себебі ол құлыпты алу сұраныстарын үздіксіз жібермейді. Әділдікті қарастырғанда, процессор құлып босатылғанда оны алуға лайықты мүмкіндік ала ма, соны қарастырамыз. Ең нашар жағдайда процессор ашарлауға ұшырауы мүмкін, яғни ол бос болғанына қарамастан, ұзақ уақыт бойы құлыпты иелене алмайды. TSL үшін жадты сақтау шығыны дерлік жоқ, себебі тек бір құлып қажет. Даусыз кешігу де төмен, себебі тек бір атомдық команда мен тармақталу қажет.