Кіріспе

Синкрондау механизмі
Компьютерлік ғылымда, оқылған көшірмені жаңарту (RCU) – синхрондау механизмі, ол құлып примитивтерін пайдаланудан аулақтайды, ал бірнеше жіптер бір мезгілде сілтемелер арқылы байланыстырылған және ортақ дерек құрылымдарына жататын элементтерді оқиды және жаңартады (мысалы, тізімдер, ағаштар, хэш-кестелер). Кез келген жіп ортақ жадтағы дерек құрылымдарының элементтерін енгізгенде немесе жойғанда, барлық оқырмандарға ескі немесе жаңа құрылымды көру және өту кепілдендіріледі, осылайша қарама-қайшылықтарды болдырмауға болады (мысалы, null сілтемелерді жою). RCU-дың негізгі кепілдігін жаңартуларды жою және қайтару кезеңдеріне бөлу арқылы пайдалануға болады. Жою кезеңі дерек элементтеріне сілтемелерді дерек құрылымынан жояды (мүмкін, оларды осы дерек элементтерінің жаңа нұсқаларына сілтемелермен алмастыру арқылы) және RCU оқу жағындағы маңызды бөлімдермен бір мезгілде орындалуы мүмкін. RCU оқырмандарымен бір мезгілде жою кезеңін орындаудың қауіпсіз болуының себебі – қазіргі заманғы процессорлардың семантикасы оқырмандарға дерек құрылымының жартылай жаңартылған сілтемесін емес, ескі немесе жаңа нұсқасын көруді кепілдейді. Шақыру мерзімі өткеннен кейін, ескі нұсқаға сілтеме жасайтын оқырмандар болмайды, сондықтан қайтару кезеңі сол ескі нұсқаны құраған деректерді босатуға (қайтарып алуға) қауіпсіздік береді. Жаңартуды жою және қайтару кезеңдеріне бөлу жаңартушыға жою кезеңін дереу орындауға және жою кезеңінде белсенді барлық оқырмандар аяқталғанға дейін, яғни, шақыру мерзімі өткенге дейін қайтару кезеңін кейінге қалдыруға мүмкіндік береді. Осылайша, RCU-дың жаңарту тізбегі келесідей болады:

RCU-мен қорғалған дерек құрылымдарына кіретін барлық оқырмандар өз сілтемелерін RCU оқу жағындағы маңызды бөлім ішінде орындайды. Дерек құрылымына сілтемелерді жою, соның салдарынан кейінгі оқырмандар оған сілтеме ала алмайды. Барлық алдыңғы оқырмандар (олар жойылған дерек құрылымына сілтемелерін сақтап қалуы мүмкін) RCU оқу жағындағы маңызды бөлімдерін аяқтағанша күтіңіз, шақыру мерзімі біткенше күтіңіз. Осы кезде дерек құрылымына сілтемелерді ұстап тұрған оқырман болмайды, сондықтан оны қазір қауіпсіз түрде қайтаруға болады (мысалы, босатуға). Жоғарыдағы процедурада (алдыңғы схемаға сәйкес), жаңартушы жою және қайтару қадамдарын орындайды, бірақ қайтаруды мүлдем басқа жіп жасауы жиі тиімді. Сілтемелерді санау оқырманға жоюды орындауға мүмкіндік береді, сондықтан бір жіп жаңарту қадамын (жоғарыдағы 2-қадам) және қайтару қадамын (жоғарыдағы 4-қадам) орындаса да, оларды бөлек қарастыру пайдалы. RCU – ортақ дерек құрылымы үшін ең көп қолданылатын блоктамайтын алгоритмдердің бірі. RCU кез келген оқырман саны үшін күтусіз жұмыс істейді. Бір жазушыны қолданатын RCU жазушы үшін де блоктамайды. RCU-дың кейбір көп жазушыны қолданатын нұсқалары блоктамайды. RCU-дың басқа көп жазушыны қолданатын нұсқалары жазушыларды құлыппен реттейді.

Қолданылуы

2008 жылдың басына қарай Linux ядросында RCU API-нің 2000-ға жуық қолданылуы тіркелді, оның ішінде желілік протоколдар жиынтығы және жадты басқару жүйесі. 2014 жылға қарай 9 мыңнан астам қолданылу болды. 2006 жылдан бері зерттеушілер RCU және оған ұқсас техникаларды көптеген мәселелерді шешу үшін қолданды, соның ішінде динамикалық талдау үшін қолданылатын метадеректерді басқару, кластерленген нысандардың қызмет ету мерзімін басқару, K42 зерттеулік операциялық жүйесінде нысандардың қызмет ету мерзімін басқару және бағдарламалық қамтамастың транзакциялық жадын оңтайландыру. Dragonfly BSD RCU-ға ұқсас техниканы қолданады, ол Linux-тың Sleepable RCU (SRCU) нұсқасына ең жақын.

Артықшылықтары мен кемшіліктері

Барлық оқырмандар аяқталғанша күту мүмкіндігі RCU оқырмаларына әлдеқайда жеңіл салмақты синхрондауды пайдалануға мүмкіндік береді, кейбір жағдайларда тіпті синхрондау қажет болмайды. Ал, дәстүрлі құлыптау схемаларында оқырмандар деректерді жаңартушының дерек құрылымын өздерінің астынан жоюына жол бермеу үшін ауыр салмақты синхрондауды қолдануға міндетті. Бұл себепті, құлыптауға негізделген жаңартулар әдетте деректерді сол жерінде жаңартады және осылайша оқырмандарды шығарып тастауы тиіс. Керісінше, RCU негізделген жаңартулар заманауи процессорлардағы жеке сәйкес келген көрсеткіштерге жазу атомдық болатындығынан пайдаланып, байланысты құрылымдағы деректерді оқырмандарға кедеріс келтірмей атомдық түрде қосуға, жоюға және алмастыруға мүмкіндік береді. Сонымен, бір мезгілдегі RCU оқырмандары ескі нұсқаларға қол жеткізуді жалғастыра алады және заманауи SMP компьютерлік жүйелерде өте қымбатқа түсетін атомдық оқу-өзгерту-жазу нұсқауларын, жад кедергілерін және кэш қателіктерін, тіпті құлыптау таласы болмаған жағдайда да, болдырмайды. RCU-ның оқуға арналған примитивтерінің жеңілдігі, тамаша өнімділік, кеңейтімділік және нақты уақыт жауабынан өзге де қосымша артықшылықтар ұсынады. Мысалы, олар көптеген тұйыққа түсу және тірі тұйыққа түсу жағдайларына қарсы иммунитет береді. Әрине, RCU-ның кемшіліктері де бар. Мысалы, RCU – бұл көбінесе оқу көп, жаңарту аз болатын жағдайларда жақсы жұмыс істейтін, бірақ жаңартуға ғана бағытталған жұмыс жүктемелері үшін көбінесе қолданылмайтын мамандандырылған техника. Тағы бір мысал келтерсек, RCU оқырмалары мен жаңартуларының бір мезгілде орындалуы RCU-ның оқу жағындағы примитивтерінің жеңілдігін қамтамасыз етеді, бірақ кейбір алгоритмдер оқу/жаңарту бірмезгілдігіне ыңғайлы болмауы мүмкін. RCU-мен он жылдан астам тәжірибе жинақтағанымызға қарамастан, оның қолданылу аясының нақты шегі әлі де зерттеу нысаны болып табылады.

Патенттер

Бұл техника АҚШ-тың 1995 жылғы 15 тамызда шығарылған және Sequent Computer Systems компаниясына тиесілі бағдарламалық қамтамасыз ету патентымен, сондай-ақ (2009 03 30 күні мерзімі өткен), (2010 04 05 күні мерзімі өткен), (2009 05 18 күні мерзімі өткен) және (2009 05 25 күні мерзімі өткен) патенттерімен қамтылған. Қазір мерзімі өткен АҚШ патенты осыған ұқсас техниканы қамтиды. RCU сонымен қатар SCO v. IBM сот процесіндегі бір талаптың нысаны болып табылады.