Linux жүйесіндегі сеқлок құлыптағышы: параллель операциялар үшін жылдам жазу механизмі
Seqlock
Linux жүйесіндегі сеqlock (тізбек құлпы) – екі параллель операция арасындағы ортақ айнымалыларға жылдам жазуды қамтамасыз ететін құлып механизмі. Жүйелік тұрақталдық, жазу ашарлығын болдырмау.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Seqlock (sequence lock) – екі параллель операциялық жүйелік түйін арасында ортақ айнымалылардың жылдам жазылуын қолдау үшін Linux-та қолданылатын арнайы құлыптау механизмі. Семантикасы 2.5.59 нұсқасында бекітілді және 2.6.x тұрақты ядро сериясында қолданылады. Seqlock-тар Стивен Хемингермен әзірленді, ал бастапқыда Андреа Арканджелидің бұрынғы жұмысына негізделген frlock деп аталды. Алғашқы іске асырылу x86 64 уақыт кодында болды, онда нақты құлыпты пайдалану мүмкін болмаған пайдаланушы кеңістігімен синхрондау қажет болды. Бұл оқырман-жазушы тұрақтылығын қамтамасыз ететін және жазушының аштықтан қалуын болдырмайтын механизм. Seqlock құлыптан басқа реттік нөмірді сақтау үшін жад бөлігін қамтиды. Құлып екі жазушының синхрондауын қамтамасыз етеді, ал санауыш оқырмандардағы сәйкестікті көрсетеді. Жазушы ортақ деректерді жаңартудан басқа, құлыпты алғаннан кейін де, босатқаннан бұрын да реттік нөмірді арттырады. Оқырмандар ортақ деректерді оқығаннан бұрын және кейін реттік нөмірді тексереді. Егер реттік нөмір екі рет те тақ болса, жазушы деректерді оқыған кезде құлыпты алған және деректер өзгеруі мүмкін. Егер реттік нөмірлер әртүрлі болса, жазушы деректерді оқылып жатқанда өзгерткен. Екі жағдайда да оқырмандар бір реттік нөмірді бұрын және кейін оқығанға дейін қайталап талпынады (цикл арқылы). Оқырман ешқашан тоқтамайды, бірақ жазу орындалып жатса, қайталап көруі мүмкін; бұл деректер өзгертпеген жағдайда оқырмандарды жеделдетеді, себебі олар дәстүрлі оқу-жазу құлыптарындағыдай құлыпты алудың қажеті жоқ. Сондай-ақ, жазушылар оқырмандарды күтпейді, ал дәстүрлі оқу-жазу құлыптарында күтеді, көптеген оқырмандар болған жағдайда ресурстардың аштығына әкелуі мүмкін (себебі жазушы оқырмандардың болмауын күтуі керек). Осы екі фактордың арқасында seqlock көптеген оқырмандар мен азырақ жазушылар бар жағдайда дәстүрлі оқу-жазу құлыптарынан тиімдірек. Кемшілігі – жазу белсенділігі тым жоғары болса немесе оқырман тым баяу болса, олар тікелей тұрып қалуы мүмкін (және оқырмандар аштықтан зардап шегуі мүмкін). Бұл техника меңзерлерді қамтитын деректер үшін жұмыс істемейді, өйткені кез келген жазушы оқырман бұрыннан орындаған меңзерді жарамсыз деп тануы мүмкін. Seqlock арқылы көрсетілген жад бөлігін жаңарту қалыпты, бірақ меңзердің өзін жаңартуға рұқсат етілмейді. Егер меңзерлерді жаңарту немесе өзгерту қажет болса, оқылған көшірмені жаңартуды синхрондау әдісін қолдану ұсынылады. Бұл алғаш рет жүйелік уақыт санағышын жаңартуда қолданылды. Әр уақыт үзілісі күннің уақытын жаңартады; операциялық жүйенің ішкі пайдалануы мен қосымшалар үшін уақытты көптеген оқырмандар оқи алады, бірақ жазулар салыстырмалы түрде сирек және бір мезгілде бір ғана болады. Мысалы, BSD уақыт санағыш коды ұқсас әдісті қолданады. Seqlock-ты уақыт санағышы үшін пайдаланудың бір қиындығы – оны жөндеушімен аяқтау мүмкін емес. Қайталап тексеру логикасы әрдайым іске қосылады, өйткені жөндеуші оқу жарысын орындау үшін жеткілікті баяу.
A seqlock (short for sequence lock) is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines. The semantics stabilized as of version 2.5.59, and they are present in the 2.6. x stable kernel series. The seqlocks were developed by Stephen Hemminger and originally called frlocks, based on earlier work by Andrea Arcangeli. The first implementation was in the x86 64 time code where it was needed to synchronize with user space where it was not possible to use a real lock. It is a reader–writer consistent mechanism which avoids the problem of writer starvation. A seqlock consists of storage for saving a sequence number in addition to a lock. The lock is to support synchronization between two writers and the counter is for indicating consistency in readers. In addition to updating the shared data, the writer increments the sequence number, both after acquiring the lock and before releasing the lock. Readers read the sequence number before and after reading the shared data. If the sequence number is odd on either occasion, a writer had taken the lock while the data was being read and it may have changed. If the sequence numbers are different, a writer has changed the data while it was being read. In either case readers simply retry (using a loop) until they read the same even sequence number before and after. The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read–write lock. Also, writers do not wait for readers, whereas with traditional read–write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers). Because of these two factors, seqlocks are more efficient than traditional read–write locks for the situation where there are many readers and few writers. The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve). The technique will not work for data that contains pointers, because any writer could invalidate a pointer that a reader has already followed. Updating the memory block being pointed to is fine using seqlocks, but updating the pointer itself is not allowed. In a case where the pointers themselves must be updated or changed, using read copy update synchronization is preferred. This was first applied to system time counter updating. Each time interrupt updates the time of the day; there may be many readers of the time for operating system internal use and applications, but writes are relatively infrequent and only occur one at a time. The BSD timecounter code for instance appears to use a similar technique. One subtle issue of using seqlocks for a time counter is that it is impossible to step through it with a debugger. The retry logic will trigger all the time because the debugger is slow enough to make the read race occur always.