Кіріспе
Бір мезгілдегі бағдарламалаудағы кейбір операциялардың қасиеттері
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that:
The extended list can be re expressed as a sequential history (is serializable). That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return.
Бір мезгілдегі бағдарламалауда операция (немесе операциялар жиынтығы) егер шақыру және жауап беру оқиғаларының реттелген тізімінен тұрса, линеарлы болып саналады, оған жауап беру оқиғаларын қосып кеңейтуге болады: кеңейтілген тізімді тізбекті тарих ретінде қайта жазуға болады (сериалдастырылуы мүмкін). Бұл тізбекті тарих бастапқы кеңейтілмеген тізімнің ішкі жиыны болып табылады. Формальды түрде, бұл оқиғалардың өзгертілмеген тізімі линеарлы болады, егер оның шақырулары тізбектелген болса және тізбекті кестедегі кейбір жауаптар әлі қайтарылмаған болса.
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that:
The extended list can be re expressed as a sequential history (is serializable). That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return.
Сызықтық сипатқа ие болу тарихы
Сызықтық тұтастық тұтастықтық моделі ретінде 1987 жылы Herlihy және Wing енгізді. Ол атомдық операцияның "бір мезгілде орындалатын операциялармен тоқтатылмайтын (немесе тоқтатылмайтын) операция" сияқты, күшті шектеулі анықтамаларын қамтыды, бұл анықтамалар операцияның қашан басталып, қашан аяқталуы туралы нақты мәлімет бермейді. Атомдық объектіні оның тізбектік сипаттамасынан бірден және толыққанды түсінуге болады, өйткені параллель орындалатын операциялар тізімі әрқашан бірінен кейін бірі орындалғандай көрінеді; ешқандай қателіктерге жол жоқ. Атап айтқанда, сызықтық тұтастық жүйенің инварианттарының барлық операциялармен сақталуын қамтамасыз етеді: егер әрбір операция жеке инвариантты сақтаса, онда жүйе тұтастай алғанда да солай болады.
Жоғары деңгейдегі атомдық операциялар
Сызықтылыққа жетудің ең оңай жолы – сыни бөлімдерде бастапқы операциялардың топтарын орындау. Қатаң айтқанда, тәуелсіз операцияларға олардың сыни бөлімдерін бір-бірімен қабаттастыруға мұқият рұқсат етуге болады, егер бұл сызықтылықты бұзбаса. Мұндай тәсіл үлкен көлемдегі құлыптардың құнын параллелизмнің артықшылықтарымен теңестіруі керек. Зерттеушілер ұнататын (бірақ әлі де бағдарламалық жасақтама индустриясында кеңінен қолданылмаған) тағы бір тәсіл – аппараттық құралдармен ұсынылған түпкілікті атомдық примитивтерді пайдаланып сызықты объектіні жобалау. Бұл қол жетімді параллелизмді барынша арттырып, синхронизация шығындарын азайтуға мүмкіндік береді, бірақ объектінің дұрыс жұмыс істейтінін көрсететін математикалық дәлелдеуді қажет етеді. Бұл екеуінің де пайдалы комбинациясы – транзакциялық жад абстракциясын ұсыну. Сыни бөлімдердегідей, пайдаланушы басқа жіптерден оқшауланған түрде орындалуы тиіс ретті кодты белгілейді. Одан кейін жүйе кодтың атомдық түрде орындалуын қамтамасыз етеді. Мұндай абстракция дерекқормен өзара әрекеттескенде жиі қолданылады; мысалы, Spring Framework-ті пайдаланғанда, әдіске @Transactional аннотациясын қою барлық жабық дерекқор операцияларының бір дерекқор транзакциясында орындалуын қамтамасыз етеді. Транзакциялық жад бір қадам алға басып, жадпен өзара әрекеттесудің барлық түрлерінің атомдық түрде орындалуын қамтамасыз етеді. Дерекқор транзакцияларына ұқсас, транзакциялардың құрамына қатысты мәселелер туындайды, әсіресе дерекқор және жадтағы транзакциялар үшін. Сызықты объектілерді жобалау кезіндегі жалпы қағида – «барлығы немесе ештеңе» интерфейсін ұсыну: операция толығымен сәтті орындалады немесе ол сәтсіз аяқталып, ештеңе істемейді. (ACID дерекқорлары бұл қағиданы атомдық деп атайды.) Егер операция сәтсіз аяқталса (әдетте бір уақытта орындалатын операцияларға байланысты), пайдаланушы қайтадан тырысып, әдетте басқа операцияны орындауы керек. Мысалы:
Compare and swap (салыстыру және алмастыру) жаңа мәнді тек егер орналасқан жердегі мән ұсынылған ескі мәнмен сәйкес келсе ғана жазады. Бұл әдетте read-modify-CAS (оқып өзгерту-CAS) тізбегінде қолданылады: пайдаланушы орналасқан жерді оқиды, жазу үшін жаңа мәнді есептейді және оны CAS (салыстырып алмастыру) арқылы жазады; егер мән бір уақытта өзгерсе, CAS сәтсіз аяқталады және пайдаланушы қайтадан тырысады. Load link/store conditional (жүктеу сілтемесі/сақтау шарты) осы үлгіні тікелей кодтайды: пайдаланушы load link (жүктеу сілтемесі) арқылы орналасқан жерді оқиды, жазу үшін жаңа мәнді есептейді және оны store conditional (сақтау шарты) арқылы жазады; егер мән бір уақытта өзгерсе, SC (сақтау шарты) сәтсіз аяқталады және пайдаланушы қайтадан тырысады. Дерекқор транзакциясында, егер транзакция бір уақытта орындалатын операцияға байланысты (мысалы, тұйықталу) аяқталмаса, транзакция тоқтатылады және пайдаланушы қайтадан тырысуы керек.
Compare and swap writes a new value into a location only if the latter's contents matches a supplied old value. This is commonly used in a read modify CAS sequence: the user reads the location, computes a new value to write, and writes it with a CAS (compare and swap); if the value changes concurrently, the CAS will fail and the user tries again. Load link/store conditional encodes this pattern more directly: the user reads the location with load link, computes a new value to write, and writes it with store conditional; if the value has changed concurrently, the SC (store conditional) will fail and the user tries again. In a database transaction, if the transaction cannot be completed due to a concurrent operation (e. g. in a deadlock), the transaction will be aborted and the user must try again.