Vaqt tamg'asi asosida paralellikni boshqarish - Timestamp-based concurrency control

Ushbu maqolada bir nechta muammolar mavjud. Iltimos yordam bering uni yaxshilang yoki ushbu masalalarni muhokama qiling munozara sahifasi. (Ushbu shablon xabarlarini qanday va qachon olib tashlashni bilib oling) Bu maqola emas keltirish har qanday manbalar. Iltimos yordam bering ushbu maqolani yaxshilang tomonidan ishonchli manbalarga iqtiboslarni qo'shish. Manbaga ega bo'lmagan materialga qarshi chiqish mumkin va olib tashlandi. Manbalarni toping: "Vaqt tamg'asi asosida taqqoslashni boshqarish"  – Yangiliklar  · gazetalar  · kitoblar  · olim  · JSTOR (2007 yil iyun) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) Ushbu maqola haqiqat aniqligi bahsli. Tegishli munozarani munozara sahifasi. Iltimos, bahsli bayonotlar mavjudligini ta'minlashga yordam bering ishonchli manbalar. (2012 yil aprel) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) Bu maqola mavzu bilan tanish bo'lmaganlar uchun etarli bo'lmagan kontekstni taqdim etadi. Iltimos yordam bering maqolani takomillashtirish tomonidan o'quvchi uchun ko'proq kontekstni taqdim etish. (2020 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Yilda Kompyuter fanlari, a vaqt belgisiga asoslangan parallellikni boshqarish algoritm a blokirovka qilinmaydigan paralellikni boshqarish usul. Ba'zilarida ishlatiladi ma'lumotlar bazalari yordamida tranzaktsiyalarni xavfsiz bajarish vaqt belgilari.

Ishlash

Taxminlar

• Har bir vaqt tamg'asi qiymati noyobdir va vaqtni aniq ifodalaydi.
• Hech qanday vaqt tamg'asi bir xil bo'lishi mumkin emas.
• Yuqori qiymatga ega bo'lgan vaqt tamg'asi, pastroq qiymatga ega bo'lgan vaqt tamg'asiga nisbatan keyinroq sodir bo'ladi.

Vaqt tamg'asini yaratish

Vaqt tamg'asini yaratish uchun bir necha xil usullardan foydalanilgan

• Vaqt tamg'asi sifatida tranzaksiya boshlanganda tizim soatining qiymatidan foydalaning.
• Vaqt tamg'asi sifatida tranzaksiya boshida ko'paytiriladigan zararli xavfsiz umumiy hisoblagichdan foydalaning.
• Yuqoridagi ikkita usulning kombinatsiyasi.

Rasmiy

Har bir bitim (${ displaystyle T_ {i}}$) bu tartiblangan harakatlar ro'yxati (${ displaystyle A_ {ix}}$). Tranzaksiya birinchi amalni bajarishdan oldin (${ displaystyle A_ {i1}}$), u oqim bilan belgilanadi vaqt tamg'asi yoki boshqa har qanday narsa qat'iy buyurtma qilingan ketma-ketlik: ${ displaystyle TS (T_ {i}) = HOZIR ()}$. Har bir operatsiyaga, avvaliga, unga bog'liq bo'lgan dastlab bo'sh operatsiyalar to'plami beriladi, ${ displaystyle DEP (T_ {i}) = []}$va dastlab yangilangan eski ob'ektlar to'plami, ${ displaystyle OLD (T_ {i}) = []}$.

Har biri ob'ekt ${ displaystyle (O_ {j})}$ ma'lumotlar bazasida paralellikni boshqarish uchun ishlatilmaydigan ikkita vaqt tamg'asi maydoni berilgan: ${ displaystyle RTS (O_ {j})}$ bu ob'ekt qiymatidan bitim tomonidan oxirgi marta foydalanilgan vaqt, ${ displaystyle WTS (O_ {j})}$ ob'ektning qiymati oxirgi marta bitim bilan yangilangan vaqt.

Barcha uchun ${ displaystyle T_ {i}}$:

Har bir harakat uchun ${ displaystyle A_ {ix}}$:

Agar ${ displaystyle A_ {ix}}$ qiymatidan foydalanishni xohlaydi ${ displaystyle O_ {j}}$:

Agar ${ displaystyle WTS (O_ {j})> TS (T_ {i})}$ keyin bekor qilish (yaqinda yozilgan qiymat qiymatning ustiga yozilgan),

Aks holda, bog'liqliklar to'plamini yangilang ${ displaystyle DEP (T_ {i}). mathrm {add} (WTS (O_ {j}))}$ va sozlang ${ displaystyle RTS (O_ {j}) = max (RTS (O_ {j}), TS (T_ {i}))}$;

Agar ${ displaystyle A_ {ix}}$ qiymatini yangilashni xohlaydi ${ displaystyle O_ {j}}$:

Agar ${ displaystyle RTS (O_ {j})> TS (T_ {i})}$ keyin bekor qilish (so'nggi ish zarrachasi allaqachon eski qiymatga tayanadi),

Agar ${ displaystyle WTS (O_ {j})> TS (T_ {i})}$ keyin o'tish (the Tomas yozish qoidasi ),

Aks holda oldingi qiymatlarni saqlang, ${ displaystyle OLD (T_ {i}). mathrm {add} (O_ {j}, WTS (O_ {j}))}$, o'rnatilgan ${ displaystyle WTS (O_ {j}) = TS (T_ {i})}$va qiymatini yangilang ${ displaystyle O_ {j}}$.

Tranzaksiya mavjud bo'lsa-da ${ displaystyle DEP (T_ {i})}$ tugamagan: Kutmoq

Agar bitim bo'lsa ${ displaystyle DEP (T_ {i})}$ keyin bekor qilindi bekor qilish

Aks holda: qilmoq.

Kimga bekor qilish:

Har biriga ${ displaystyle ( mathrm {old} O_ {j}, mathrm {old} WTS (O_ {j}))}$ yilda ${ displaystyle OLD (T_ {i})}$

Agar ${ displaystyle WTS (O_ {j})}$ teng ${ displaystyle TS (T_ {i})}$ keyin tiklang ${ displaystyle O_ {j} = mathrm {old} O_ {j}}$ va ${ displaystyle WTS (O_ {j}) = mathrm {old} WTS (O_ {j})}$

Norasmiy

Har doim bitim boshlanganda, u vaqt tamg'asini oladi. Ushbu vaqt tamg'asi boshqa operatsiyalarga nisbatan operatsiyani bajarish tartibini ko'rsatadi. Shunday qilib, bitta ob'ektga ta'sir ko'rsatadigan ikkita operatsiyani hisobga olgan holda, avvalroq vaqt tamg'asi bilan operatsiyani bajarish keyingi vaqt tamg'asi bilan ishlashdan oldin bajarilishi kerak. Biroq, agar birinchi navbatda noto'g'ri operatsiyaning ishlashi taqdim etilsa, u bekor qilinadi va operatsiyani qayta boshlash kerak.

Ma'lumotlar bazasidagi har bir ob'ekt a vaqt tamg'asini o'qing, ob'ekt ma'lumotlari o'qilganda har doim yangilanadi va a vaqt tamg'asini yozish, ob'ekt ma'lumotlari o'zgarganda har doim yangilanadi.

Agar bitim ob'ektni o'qishni xohlasa,

• ammo bitim boshlandi oldin ob'ektniki vaqt tamg'asini yozish bu narsa bitim boshlangandan so'ng ob'ekt ma'lumotlarini o'zgartirganligini anglatadi. Bunday holda, bitim bekor qilinadi va uni qayta boshlash kerak.
• va bitim boshlandi keyin ob'ektniki vaqt tamg'asini yozish, bu degani xavfsiz ob'ektni o'qish. Bunday holda, agar bitim vaqt tamg'asi ob'ektnikidan keyin bo'lsa vaqt tamg'asini o'qing, o'qish vaqt tamg'asi bitim vaqt tamg'asiga o'rnatiladi.

Agar bitim ob'ektga yozishni xohlasa,

• ammo bitim boshlandi oldin ob'ektniki vaqt tamg'asini o'qing bu narsa ob'ektga bir nazar tashlaganligini anglatadi va biz bu ob'ekt ma'lumotlarining nusxasini olgan deb o'ylaymiz. Shunday qilib biz ob'ektga hech qanday nusxa ko'chirilgan ma'lumotlarni yaroqsiz holga keltira olmaymiz, shuning uchun tranzaksiya bekor qilinadi va uni qayta boshlash kerak.
• va bitim boshlandi oldin ob'ektniki vaqt tamg'asini yozish bu bizning operatsiyani boshlaganimizdan beri biron narsa ob'ektni o'zgartirganligini anglatadi. Bunday holda biz Tomas qoidani yozadi va oddiygina yozish operatsiyamizni o'tkazib yuboring va odatdagidek davom eting; bitimni bekor qilish yoki qayta boshlash shart emas
• aks holda, bitim ob'ektga yozadi, va ob'ekt vaqt tamg'asini yozish bitimning vaqt tamg'asiga o'rnatiladi.

Qayta tiklanishi

Shuni esda tutingki, asosiy shaklda vaqt tamg'asini buyurtma qilish qayta tiklanadigan tarixlarni keltirib chiqarmaydi. Masalan, operatsiyalar bilan quyidagi tarixni ko'rib chiqing ${ displaystyle T_ {1}}$ va ${ displaystyle T_ {2}}$:

${ displaystyle W_ {1} (x) ; R_ {2} (x) ; W_ {2} (y) ; C_ {2} ; R_ {1} (z) ; C_ {1}})$

Bu TO rejalashtiruvchisi tomonidan ishlab chiqarilishi mumkin, ammo uni qayta tiklash mumkin emas ${ displaystyle T_ {2}}$ bajarilmagan bitimdan o'qisa ham, bajaradi. Qayta tiklanadigan tarixlarni yaratganligiga ishonch hosil qilish uchun rejalashtiruvchi har bir operatsiyadagi boshqa operatsiyalar ro'yxatini saqlab qo'yishi mumkin dan o'qingva ushbu ro'yxat oldin faqat bitimlardan iborat bitim tuzilishiga yo'l qo'ymaslik. Kaskadli abortlardan saqlanish uchun, rejalashtiruvchi tuzilmagan bitimlar tomonidan yozilgan ma'lumotlarni quyidagicha belgilashi mumkin iflos, va hech qachon bunday ma'lumotlar elementida belgilanmasdan oldin o'qish operatsiyasini boshlashiga yo'l qo'ymang. Qattiq tarixga ega bo'lish uchun rejalashtiruvchi iflos narsalar bilan ishlashga yo'l qo'ymasligi kerak.

Amalga oshirish masalalari

Vaqt tamg'asi o'lchamlari

Bu ikkita qo'shni vaqt tamg'alari o'rtasida o'tgan minimal vaqt. Agar vaqt tamg'asining o'lchamlari juda katta (qo'pol) bo'lsa, ikki yoki undan ortiq vaqt tamg'alarining teng bo'lishi ehtimoli ko'payadi va shu bilan ba'zi operatsiyalarni tartibsiz amalga oshirishga imkon beradi. Masalan, bizda sekundiga yuzta noyob vaqt tamg'alarini yarata oladigan tizim mavjud deb faraz qilsak va bir-biridan 2 millisekundada sodir bo'ladigan ikkita hodisani hisobga olsak, ular haqiqatan ham turli vaqtlarda bo'lganiga qaramay, ularga bir xil vaqt tamg'asi beriladi.

Vaqt belgisini qulflash

Ushbu texnik qulflanmagan bo'lsa ham, Tranzaksiya davomida Ob'ekt bir vaqtning o'zida kirish huquqidan qulflanmagan bo'lsa ham, har bir vaqt tamg'asini Ob'ektga qarshi yozib olish uchun Ob'ekt yoki uning uchun juda qisqa muddat qulflanishi kerak. ishonchli vakil.

Shuningdek qarang

• Ko'p sonli parallellikni boshqarish
• Vaqt tamg'asi (hisoblash)