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

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 () bu tartiblangan harakatlar ro'yxati (). Tranzaksiya birinchi amalni bajarishdan oldin (), u oqim bilan belgilanadi vaqt tamg'asi yoki boshqa har qanday narsa qat'iy buyurtma qilingan ketma-ketlik: . Har bir operatsiyaga, avvaliga, unga bog'liq bo'lgan dastlab bo'sh operatsiyalar to'plami beriladi, va dastlab yangilangan eski ob'ektlar to'plami, .

Har biri ob'ekt ma'lumotlar bazasida paralellikni boshqarish uchun ishlatilmaydigan ikkita vaqt tamg'asi maydoni berilgan: bu ob'ekt qiymatidan bitim tomonidan oxirgi marta foydalanilgan vaqt, ob'ektning qiymati oxirgi marta bitim bilan yangilangan vaqt.

Barcha uchun :

Har bir harakat uchun :
Agar qiymatidan foydalanishni xohlaydi :
Agar keyin bekor qilish (yaqinda yozilgan qiymat qiymatning ustiga yozilgan),
Aks holda, bog'liqliklar to'plamini yangilang va sozlang ;
Agar qiymatini yangilashni xohlaydi :
Agar keyin bekor qilish (so'nggi ish zarrachasi allaqachon eski qiymatga tayanadi),
Agar keyin o'tish (the Tomas yozish qoidasi ),
Aks holda oldingi qiymatlarni saqlang, , o'rnatilgan va qiymatini yangilang .
Tranzaksiya mavjud bo'lsa-da tugamagan: Kutmoq
Agar bitim bo'lsa keyin bekor qilindi bekor qilish
Aks holda: qilmoq.

Kimga bekor qilish:

Har biriga yilda
Agar teng keyin tiklang va

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 va :

Bu TO rejalashtiruvchisi tomonidan ishlab chiqarilishi mumkin, ammo uni qayta tiklash mumkin emas 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