DISTRIBUTED SYSTEMS Concept and Design – Fifth Edition
George Coulouris
Cambridge University
Jean Dollimore
formerly of Queen Mary, University of London
Tim Kindberg
matter 2 media
Gordon Blair
Lancaster University
Bab ini membahas penerapan transaksi dan kontrol konkurensi untuk berbagibenda dikelola oleh server.Sebuah transaksi mendefinisikan urutan operasi server yang dijamin oleh server untuk menjadi atom di hadapan beberapa klien dan server crash. Bersarang transaksi terstruktur dari set transaksi lainnya. Mereka sangat berguna dalamsistem terdistribusi karena mereka memungkinkan concurrency tambahan.Semua protokol kontrol konkurensi didasarkan pada kriteria serialkesetaraan dan berasal dari aturan konflik antara operasi.
tiga metode
dijelaskan:
Kunci yang digunakan untuk memesan transaksi yang mengakses objek yang sama sesuai dengan urutan kedatangan operasi mereka di objek.
kontrol konkurensi Optimis memungkinkan transaksi untuk melanjutkan sampai mereka siap untuk melakukan, dimana cek dilakukan untuk melihat apakah mereka telah melakukan operasi yang saling bertentangan pada objek.
Timestamp pemesanan menggunakan cap waktu untuk memesan transaksi yang mengakses sama objek menurut kali awal mereka
16 TRANSAKSI DAN CONCURRENCY KONTROL
16.1 Pendahuluan
Tujuan dari transaksi ini adalah untuk memastikan bahwa semua benda dikelola bya Server tetap dalam keadaan konsisten ketika theyare diakses oleh beberapa transaksi dan di hadapan dari server crash. Bab 2 memperkenalkan model kegagalan untuk sistem terdistribusi.Transaksi berurusan dengan kegagalan kecelakaan proses dan kegagalan kelalaian dalamkomunikasi, tapi tidak anytype perilaku sewenang-wenang (atau Bizantium). Kesalahan model untuk transaksi disajikan dalam Bagian 16.1.2.Objek yang dapat dipulihkan setelah crash server mereka disebut dipulihkan benda. Secara umum, objek dikelola bya server yang mungkin disimpan di memori volatile (Misalnya, RAM) atau memori persisten (misalnya, hard disk). Bahkan jika benda disimpan dalam memori volatile, server mayuse gigih memoryto toko yang cukup informasi untuk keadaan objek yang akan sembuh jika proses server crash.
Ini memungkinkan server untuk membuat objek dipulihkan. Sebuah transaksi ditentukan bya klien sebagai mengatur operasi pada objek yang akan dilakukan sebagai unit terpisahkan bythe server benda managingthose. Server harus menjamin bahwa baik seluruh transaksi dilakukan dan hasilnya disimpan di penyimpanan permanen atau, dalam kasus yang satu atau lebih dari themcrashes, efeknya completelyerased. Bab berikutnya membahas isu-isu terkait dengan transaksi yang melibatkan beberapa server, khususnya bagaimana theydecide pada
hasil dari transaksi terdistribusi. Bab ini berkonsentrasi pada isu-isu untuk transaksi di server tunggal. Transaksi A klien juga dianggap sebagai terpisahkan dari sudut pandang dari clients'transactions lain dalam arti bahwa operasi satu transaksi tidak dapat mengamati efek parsial operasi lain. bagian 16.1.1 membahas sinkronisasi sederhana akses ke objek, dan Bagian 16.2 memperkenalkan transaksi, yang membutuhkan teknik yang lebih canggih untuk mencegah interferensi antara klien. Bagian 16.3 membahas transaksi bersarang. Bagian 16,4-16,6 membahas tiga metode concurrencycontrol untuk transaksi yang operasinya semua ditujukan kepada server tunggal (kunci, concurrencycontrol optimis dan timestamp ordering). Bab 17 membahas bagaimana metode ini diperpanjang untuk digunakan dengan transaksi yang operasinya yang ditujukan kepada beberapa server
Untuk menjelaskan beberapa poin yang dibuat dalam bab ini, kita menggunakan bankingexample sebuah, ditunjukkan pada Gambar 16.1. Setiap akun diwakili bya remote object yang antarmuka, Akun, menyediakan operasi untuk membuat deposito dan penarikan dan untuk bertanya tentang dan keseimbangan Menyetel. Setiap cabang dari bankis diwakili bya objek remote antarmuka yang, Cabang, menyediakan operasi untuk creatinga akun baru, untuk lookingup sebuah julukan akun dan untuk bertanya tentang total dana di cabang itu. 16.1.1 sinkronisasi Sederhana (tanpa transaksi)
sinkronisasi Sederhana (tanpa transaksi) Salah satu isu utama bab ini adalah bahwa kecuali jika server dirancang dengan hati-hati, yang operasi yang dilakukan atas nama klien yang berbeda maysometimes mengganggu satu lain. Seperti gangguan mayresult nilai salah dalam objek. Di bagian ini, kita membahas bagaimana operasi klien mungkin disinkronkan tanpa bantuan transaksi.
operasi atom di server • Kita telah melihat dalam bab-bab sebelumnya bahwa penggunaan beberapa benang bermanfaat untuk kinerja di manyservers. Kami juga telah mencatat bahwa penggunaan benang memungkinkan operasi dari beberapa klien untuk menjalankan secara bersamaan dan.
Gambar 16.1 Operasi dari Accountinterface
Deposit (jumlah)
Deposit amountin account
menarik (jumlah)
menarik jumlah dari account
getBalance () oamount
mengembalikan saldo rekening
setBalance (jumlah)
mengatur saldo rekening untuk mencapai
Operasi Interface Cabang
membuat (nama) oaccount
membuat akun baru dengan nama yang diberikan
lookup (nama) oaccount
kembali referensi ke akun dengan nama yang diberikan
branchTotal () oamount
mengembalikan total semua saldo di cabang mungkin mengakses objek yang sama. Oleh karena itu, metode dari objek harus dirancang untuk digunakan dalam konteks multi-threaded. Sebagai contoh, jika metode depositand menarik tidak dirancang untuk digunakan dalam program multi-ulir, maka ada kemungkinan bahwa tindakan dari dua atau lebih eksekusi bersamaan metode bisa disisipkan sewenang-wenang dan memiliki efek aneh pada variabel instance dari objek rekening.
Bab 7 menjelaskan penggunaan kata kunci disinkronkan, yang dapat diterapkan untuk
metode di Jawa untuk memastikan bahwa benang onlyone pada suatu waktu dapat mengakses objek. dalam kami Misalnya, kelas yang mengimplementasikan Accountinterface akan dapat menyatakan metode sebagai disinkronkan. Sebagai contoh: public void disinkronisasi penyimpanan (int jumlah) melempar RemoteException { // Menambahkan amountto saldo rekening} Jika satu thread memanggil metode disinkronkan pada objek, maka objek secara efektif terkunci, dan thread lain yang memanggil salah satu metode yang disinkronisasi akan diblokir sampai lockis dirilis. Sinkronisasi formof ini memaksa eksekusi benang untuk dipisahkan dalam waktu dan memastikan bahwa variabel instance dari satu objek yang diakses secara konsisten. Tanpa sinkronisasi, dua penyimpanan terpisah doa mungkin membaca keseimbangan sebelum baik telah bertambah itu - resultingin sebuah nilai yang tidak benar. Setiap metode yang mengakses instance variable yang dapat varyshould menjadi disinkronisasi. Operasi yang operasi fromconcurrent frominterference gratis menjadi dilakukan di thread lain disebut operasi atom. Penggunaan disinkronkan
16 TRANSAKSI DAN CONCURRENCY KONTROL
metode di Jawa adalah salah satu cara untuk mencapai operasi atom. Namun dalam pemrograman lain lingkungan untuk multi-threaded server operasi pada objek masih harus memiliki operasi atom untuk menjaga benda mereka konsisten. Ini mungkin dicapai bythe penggunaan mekanisme mutual exclusion anyavailable, seperti mutex. Meningkatkan kerjasama klien dengan sinkronisasi operasi server yang
Klien mayuse server sebagai sarana sumber sharingsome. Hal ini dicapai bysome klien menggunakan operasi untuk memperbarui server objek dan klien lainnya usingoperations untuk mengakses mereka. Skema di atas untuk akses disinkronisasi ke obyek menyediakan semua yang diperlukan di manyapplications - mencegah benang interferingwith satu sama lain. Namun, beberapa aplikasi memerlukan wayfor benang untuk berkomunikasi satu sama lain. Misalnya, mayarise situasi di mana operasi yang diminta byone klien tidak dapat diselesaikan sampai suatu operasi yang diminta byanother klien telah dilakukan. Hal ini dapat terjadi ketika beberapa klien adalah produsen dan lain-lain adalah konsumen – yang konsumen mayhave menunggu sampai produser telah memasok lagi komoditi yang dimaksud. Hal ini juga dapat terjadi ketika klien adalah sumber daya sharinga - klien needingthe mayhave sumber daya untuk menunggu klien lain untuk melepaskannya. Kita akan lihat nanti dalam bab ini bahwa situasi yang sama muncul ketika kunci atau cap waktu yang digunakan untuk concurrencycontrol dalam transaksi. Java yang memungkinkan benang untuk berkomunikasi dengan satu sama lain dengan cara yang memecahkan permasalahan di atas. Mereka harus digunakan dalam metode disinkronkan dari sebuah objek. Sebuah thread panggilan waiton obyek sehingga untuk menangguhkan dirinya sendiri dan untuk memungkinkan thread lain untuk melaksanakan metode objek. SEBUAH panggilan benang notifyto waitingon informanythread bahwa keberatan yang telah mengubah beberapa datanya.
Akses ke objek masih atom ketika benang menunggu satu sama lain: benang bahwa panggilan tunggu menyerah lockand yang menunda dirinya sebagai tindakan atom tunggal; Ketika sebuah benang-restart setelah beingnotified itu mengakuisisi baru Lockon objek dan resume eksekusi fromafter menunggu nya. Sebuah thread yang memanggil memberitahu (fromwithin a disinkronkan Metode) melengkapi pelaksanaan metode yang sebelum releasingthe Lockon objek. Mempertimbangkan pelaksanaan Queueobject bersama dengan dua metode: pertama menghapus dan mengembalikan objek pertama dalam antrian, dan appendadds objek yang diberikan kepada akhir antrian. Metode firstwill menguji apakah antrian kosong, dalam hal ini ia akan memanggil waiton antrian.
Jika klien memanggil firstwhen antrian kosong, tidak akan mendapatkan replyuntil klien lain telah menambahkan somethingto antrian - appendoperation yang akan memanggil notifywhen telah menambahkan sebuah objek ke antrian. Hal ini memungkinkan salah satu benang waitingon objek antrian untuk melanjutkan dan untuk mengembalikan objek pertama dalam antrian untuk yang klien. Ketika benang dapat menyinkronkan tindakan mereka pada objek dengan cara waitand memberitahukan, server memegang ke permintaan yang tidak dapat immediatelybe puas dan klien menunggu untuk replyuntil klien lain telah menghasilkan apa yang perlu Pada Bab 16.4, kita membahas pelaksanaan lockas obyek dengan operasi disinkronisasi. Ketika klien berusaha untuk memperoleh kunci, theycan dibuat untuk menunggu sampai lockis dirilis byother klien.
Tanpa kemampuan untuk melakukan sinkronisasi benang dengan cara ini, klien yang tidak bisa immediately- puas misalnya, klien yang memanggil metode pertama pada kosong antrian - diperintahkan untuk TryAgain kemudian. Hal ini tidak memuaskan, karena akan melibatkan klien di pollingthe server dan server dalam permintaan tambahan Melakukan kegiatan. Hal ini juga berpotensi tidak adil karena klien lain mungkin membuat permintaan mereka sebelum klien menunggu mencoba lagi.
16.1.2 Model Kegagalan untuk transaksi
Lampson [1981] mengusulkan sebuah model kesalahan untuk transaksi terdistribusi yang menyumbang kegagalan disk, server dan komunikasi. Dalam model ini, claimis bahwa algoritma workcorrectlyin kehadiran kesalahan diprediksi, tapi tidak ada klaim yang dibuat tentang perilaku mereka ketika bencana terjadi. Meskipun kesalahan mayoccur, theycan menjadi terdeteksi dan ditangani dengan sebelum anyincorrect hasil perilaku.
Model negara yang berikut:
Menulis untuk penyimpanan permanen mungkin gagal, baik oleh writingnothing atau bywritinga nilai yang salah - misalnya, writingto yang wrongblockis bencana. penyimpanan file mayalso pembusukan. Reads penyimpanan frompermanent dapat mendeteksi (bya checksum) ketika data blockof buruk.
Server maycrash sesekali. Ketika server jatuh diganti bya baru Proses, memoryis volatile set pertama untuk keadaan di mana itu tidak ada yang tahu nilai (misalnya, benda) frombefore kecelakaan itu. Setelah itu melakukan sebuah recoveryprocedure usingInformation dalam penyimpanan permanen dan diperoleh dari proses lain untuk mengatur nilai-nilai objek includingthose terkait dengan dua fase commit protocol (lihat Bagian 17.6). Ketika prosesor rusak, itu dibuat untuk kecelakaan sehingga dicegah pesan fromsendingerroneous dan fromwritingwrong nilai-nilai untuk penyimpanan permanen - yaitu, sehingga tidak bisa menghasilkan arbitraryfailures. Crash dapat terjadi kapan saja; khususnya, mereka mayoccur duringrecovery.
Ada mungkin sebuah arbitrarydelaybefore pesan tiba. Sebuah pesan mungkin hilang, digandakan atau rusak. penerima dapat mendeteksi rusak pesan usinga checksum. Kedua pesan palsu dan pesan yang korup tidak terdeteksi dianggap sebagai bencanaModel kesalahan untuk penyimpanan, prosesor permanen dan komunikasi digunakan untuk merancang komponen systemwhose stabil bisa bertahan kesalahan anysingle dan menyajikan Model kegagalan sederhana. Secara khusus, penyimpanan stabil memberikan writeoperation atom di kehadiran satu kesalahan dari writeoperation atau kegagalan kecelakaan dari proses. Ini dicapai dengan mereplikasi setiap blok pada dua diskblocks. Sebuah writeoperation adalah diterapkan pada sepasang diskblocks, dan dalam kasus kesalahan tunggal, satu blockwas baik selalu tersedia. Sebuah stabil processorused penyimpanan yang stabil untuk memungkinkannya untuk memulihkan nya benda setelah terjadi kecelakaan. kesalahan komunikasi yang bertopeng byusinga terpencil terpercaya Prosedur mekanisme menelepon.
16.2 Transaksi
Dalam beberapa situasi, klien memerlukan urutan permintaan terpisah untuk server menjadi atom dalam arti bahwa:
theyare frominterference gratis byoperations beingperformed atas nama lainnya klien konkuren.
Entah semua operasi harus diselesaikan successfullyor mereka harus memiliki efek sama sekali di hadapan server crashe
Gambar 16.2 transaksi perbankan A klien
Transaksi To.withdraw (100);
b.deposit (100);
c.withdraw (200);
b.deposit (200);
Kami kembali ke bankingexample kami untuk menggambarkan transaksi. Seorang klien yang melakukan urutan operasi pada rekening bank tertentu atas nama pengguna akan pertama Lookup yang julukan akun dan kemudian applythe deposito, penarikan dan mendapatkan operasi Balance langsung ke rekening yang bersangkutan. Dalam contoh kita, kita menggunakan akun dengan nama A, Band C. Klien tampak themup dan toko referensi ke themin variabel, jenis pita cof Rekening. Rincian lookingup rekening julukan dan deklarasi dari variabel dihilangkan dari dana contoh.
Gambar 16.2
Gambar 16.2 transaksi perbankan A klien
Transaksi T:
a.withdraw (100);
b.deposit (100);
c.withdraw (200);
b.deposit (200);
menunjukkan contoh dari klien sederhana serangkaian specifyinga transaksi tindakan terkait involvingthe bankaccounts A, Band C. Pengalihan dua tindakan pertama $ 100 dari Ato Band kedua dua mentransfer $ 200 dari CTO B. Seorang klien mencapai Transfer operasi bydoinga penarikan diikuti bya deposito.Transaksi berasal sistem manajemen fromdatabase. Dalam konteks, sebuah Transaksi adalah pelaksanaan programthat sebuah mengakses database. transaksi yang diperkenalkan ke sistem terdistribusi di formof transaksional file server seperti XDFS [Mitchell dan Dion 1982]. Dalam konteks file server transaksional, transaksi adalah pelaksanaan urutan klien meminta untuk operasi file. Transaksi di didistribusikan benda yang disediakan di beberapa sistem penelitian, includingArgus [Liskov 1988] dan Arjuna [Shrivastava et al. 1991]. Dalam konteks yang terakhir ini, transaksi terdiri dari pelaksanaan urutan permintaan klien seperti, misalnya, mereka pada Gambar 16.2. Dari dana titik klien pandang, transaksi adalah urutan operasi yang membentuk langkah, transformingthe server data fromone negara yang konsisten yang lain.Transaksi dapat diberikan sebagai middleware partof. Sebagai contoh, CORBA memberikan spesifikasi untuk Layanan Obyek Transaksi [OMG 2003] dengan IDL interface allowingclients'transactions untuk menyertakan beberapa objek di beberapa server.Klien disediakan dengan operasi untuk specifythe akhir beginningand transaksi.
Klien mempertahankan konteks untuk setiap transaksi, yang merambat dengan masing-masing operasi dalam transaksi itu. Dalam CORBA, obyek transaksional dipanggil dalam lingkup transaksi dan generallyhave beberapa toko gigih yang terkait dengan mereka.Dalam semua konteks ini, transaksi berlaku untuk benda dipulihkan dan dimaksudkan menjadi atom. Hal ini sering disebut transaksi atom. Ada dua aspek untuk atomicity:Semua atau tidak: transaksi A baik selesai dengan sukses, dalam hal efek dari semua operasinya dicatat dalam objek, atau (jika gagal atau sengaja dibatalkan) tidak berpengaruh sama sekali. Ini semua-atau-nothingeffect memiliki dua aspek lebih lanjut dari yang sendiri:
Kegagalan atomicity: Efek adalah atom bahkan ketika server crash Daya tahan: Setelah transaksi telah selesai dengan sukses, semua efeknya disimpan dalam penyimpanan permanen. Kami menggunakan istilah 'storage'to permanen merujuk ke file diselenggarakan pada diskor media permanen lain. Data disimpan dalam file akan bertahan jika proses server crash.Isolasi: Setiap transaksi harus dilakukan tanpa gangguan fromother transaksi; dengan kata lain, efek menengah transaksi tidak harus terlihat transaksi lainnya. boxbelow memperkenalkan sebuah mnemonic, ACID, untuk Sifat rememberingthe transaksi atom. ACID property Lebih keras dan Reuter [1983] menyarankan mnemonic 'ACID'to ingat sifat transaksi, yang adalah sebagai berikut:
Atomicity: transaksi harus semua atau tidak;Konsistensi: transaksi terjadi keadaan yang konsisten systemfromone lain negara yang konsisten; Isolasi;Daya tahan.Kami belum termasuk 'consistency'in daftar sifat transaksi karena umumnya tanggung jawab programmer server dan klien untuk memastikan bahwa transaksi meninggalkan database yang konsisten.Sebagai contoh konsistensi, misalkan di bankingexample itu, obyek memegang sumof semua saldo akun dan nilainya digunakan sebagai hasil dari branchTotal. Klien bisa mendapatkan sumof semua saldo rekening baik byusing branchTotalor bycalling getBalanceon masing-masing rekening. Untuk konsistensi, mereka harus mendapatkan metode hasil fromboth yang sama. Untuk menjaga konsistensi ini,depositand withdrawoperations harus memperbarui holdingthe objek sumof semua saldo rekening.
Untuk mendukung kebutuhan untuk kegagalan atomicityand daya tahan, objek harus dipulihkan; yaitu, ketika proses server crash unexpectedlydue untuk kesalahan hardware atau kesalahan perangkat lunak, perubahan karena semua transaksi selesai harus tersedia dipenyimpanan permanen sehingga ketika server diganti bya proses baru, dapat memulihkan objek untuk mencerminkan semua-atau-nothingeffect. Bythe waktu server mengakui penyelesaian transaksi klien, semua perubahan transaksi untuk objek harus telah dicatat dalam penyimpanan permanen.Sebuah server yang mendukung transaksi harus mensinkronkan operasi sufficientlyto memastikan bahwa persyaratan isolasi terpenuhi. Satu wayof doingthis adalah untuk performthe transaksi serially- satu per satu, di beberapa arbitraryorder. Sayangnya, solusi ini akan generallybe tidak dapat diterima untuk server yang sumber daya yang dibagi oleh beberapa pengguna interaktif. Misalnya, di bankingexample kami itu diinginkan untuk memungkinkan beberapa bankclerks untuk performonline bankingtransactions pada saat yang sama sebagai satu sama lain.
The aimfor anyserver yang mendukung transactionsis untuk memaksimalkan concurrency. Oleh karena itu transaksi diperbolehkan untuk menjalankan concurrentlyif ini akan memiliki yang sama efek sebagai eksekusi seri - yaitu, jika theyare serial equivalentor serializable
TRANSACTIONS AND CONCURRENCY CONTROL
kemampuan transaksi dapat ditambahkan ke server benda dipulihkan. Setiap transaksi dibuat dan dikelola bya koordinator, yang mengimplementasikan interface Koordinator ditunjukkan pada Gambar 16.3 Gambar 16.3 Operasi di Koordinator Antarmuka
terbuka Transaksi () otrans; Memulai transaksi baru dan memberikan yang unik TID trans. pengenal ini akan digunakan dalam operasi lain di transaction.closeTransaction (trans) o (komit, batalkan); Berakhir transaksi: nilai commitreturn menunjukkan bahwa transaksi telah dilakukan; nilai abortreturn menunjukkan bahwa ia memiliki aborted.abort Transaksi (trans); dibatalkan koordinator transaction.The memberikan setiap transaksi pengenal, atau TID. Klien memanggil metode openTransaction koordinator untuk memperkenalkan transaksi baru - pengenal transaksi atau TID dialokasikan dan kembali. Pada akhir transaksi, klien memanggil metode closeTransaction untuk menunjukkan ujungnya - semua benda dipulihkan diakses bythe transaksi harus disimpan. Jika, untuk beberapa alasan, klien ingin membatalkan transaksi, itu memanggil metode abortTransaction - semua dampaknya harus dihapus fromsight.
. Ini adalah apa yang CORBA Layanan Transaksi tidak. Kami tidak akan menunjukkan TIDs di contoh kita.Biasanya, transaksi selesai whenthe klien membuat closeTransaction a permintaan. Jika transaksi telah berkembang secara normal, replystates bahwa transaksi iscommitted- ini merupakan janji kepada klien bahwa semua perubahan yang diminta di transaksi secara permanen dicatat dan bahwa transaksi anyfuture yang mengakses Data yang sama akan melihat hasil dari semua perubahan yang dibuat duringthe transaksi.Atau, mayhave transaksi untuk abortfor salah satu dari beberapa alasan terkait sifat transaksi itu sendiri, konflik dengan transaksi lain atau ke crashingof proses atau komputer.
Ketika transaksi digagalkan pihak yang terlibat(Benda dipulihkan dan koordinator) harus memastikan bahwa tidak ada efeknya terlihat transaksi masa depan, baik dalam benda atau dalam salinan mereka dalam penyimpanan permanen.Sebuah transaksi baik berhasil atau dibatalkan di salah satu dari dua cara – klien dibatalkan itu (usingan abortTransactioncall ke server) atau server dibatalkan itu. Gambar 16.4
Transaksi sejarah kehidupan
BAGIAN 16,2 TRANSAKSI 683
menunjukkan tiga sejarah hidup alternatif ini untuk transaksi. Kami mengacu pada transaksi sebagai failingin kedua kasus yang terakhir.
tindakan layanan terkait untuk memproses crash
Jika proses server crash tiba-tiba, itu akhirnya digantikan. Proses server baru dibatalkan transaksi anyuncommitted dan menggunakan recoveryprocedure untuk mengembalikan nilai-nilai dari objek untuk nilai-nilai yang dihasilkan oleh paling recentlycommitted transaksi. Untuk menghadapi klien yang crash tiba-tiba duringa transaksi, server dapat memberikan setiap transaksi yang expirytime dan membatalkan semua
transaksi yang belum selesai sebelum expirytime nya. tindakan klien terkait dengan proses server crash
Jika server crash saat transaksi adalah berlangsung, klien akan menyadari ini ketika salah satu operasi mengembalikan pengecualian setelah timeout. Jika server crash dan kemudian diganti duringthe kemajuan transaksi, transaksi tidak lagi berlaku dan klien harus diberitahu via pengecualian untuk operasi berikutnya. Dalam kedua kasus, klien maka harus merumuskan rencana,konsultasi possiblyin dengan pengguna manusia, untuk penyelesaian atau ditinggalkannya taskof yang transaksi adalah bagian.
kontrol 16.2.1 Concurrency Bagian ini menggambarkan dua masalah terkenal transaksi bersamaan dikonteks bankingexample - yang 'hilang update'problemand yang' tidak konsisten retrievals'problem. Kami kemudian menunjukkan bagaimana kedua masalah ini dapat dihindari byusing eksekusi seriallyequivalent transaksi. Kami berasumsi seluruh bahwa masing-masing Deposit operasi, menarik, getBalanceand setBalanceis operasi disinkronkan -yaitu, bahwa dampaknya pada variabel contoh yang mencatat saldo akun yang atom.
Masalah Pembaruan hilang • Pembaruan problemis hilang diilustrasikan bythe followingpair transaksi di bankaccounts A, Band C, yang saldo awal adalah $ 100, $ 200 dan$ 300, masing-masing. Transaksi Ttransfers jumlah fromaccount Ato akun B.TransactionUtransfers jumlah B. fromaccount akun CTO Dalam kedua kasus,
Figure 16.5 The lost update problem
jumlah yang ditransfer dihitung untuk meningkatkan keseimbangan Bby10%. Efek bersih dari transaksi executingthe accountBof Tand Ushould adalah untuk meningkatkan keseimbangan accountBby10% dua kali, sehingga nilai akhir adalah $ 242.Now mempertimbangkan efek dari allowingthe transaksi Tand Uto runconcurrently, seperti pada Gambar 16.5. Kedua transaksi mendapatkan keseimbangan Bas $ 200 dan kemudian deposit $ 20
Hasilnya adalah tidak benar, meningkatkan saldo rekening Bby $ 20instead $ 42. Ini adalah sebuah gambaran dari 'update'problem hilang. Update U hilang karena Menimpa tanpa seeingit. Kedua transaksi telah membaca nilai lama sebelum baik menulis nilai baru.
Gambar 16.6 The konsisten retrievals masalah Transaksi: Transaksi: Pada Gambar 16.5 dan seterusnya, kita menunjukkan operasi yang mempengaruhi keseimbangan account di garis berurutan ke bawah halaman, dan pembaca harus menganggap bahwa operasi pada baris tertentu dijalankan pada kemudian waktu daripada yang di baris di atas itu.
retrievals konsisten • Gambar 16.6 menunjukkan contoh lain yang terkait dengan rekening bank di mana transaksi Vtransfers transaksi sumfromaccount Ato Band metode Winvokes thebranchTotal untuk mendapatkan sumof yang saldo semua akun di bank.Angka 16,6 The konsisten retrievals masalah
Transaksi: Transaksi:
Gambar 16.7 Sebuah interleaving serial setara dengan T Dan
Saldo dua bankaccounts, Aand B, keduanya awalnya $ 200. Hasil dari cabang Jumlah meliputi jumlah Aand Bas $ 300, yang merupakan salah. Ini adalah sebuah ilustrasi dari 'retrievals'problem tidak konsisten. retrievals W adalah tidak konsisten karena Vhas dilakukan onlythe penarikan bagian dari transfer pada saat sumis dihitung.Serial kesetaraan
Jika setiap beberapa transaksi diketahui memiliki efek yang benar jika dilakukan sendiri, maka kita dapat menyimpulkan bahwa jika transaksi tersebut dilakukan satu per satu waktu di beberapa urutan efek gabungan juga akan benar. Sebuah interleavingof yang operasi transaksi di mana efek gabungan adalah sama seperti jika transaksi telah dilakukan satu per satu dalam beberapa urutan adalah interleaving serial setara.Ketika kita saythat dua transaksi yang berbeda memiliki effectas yang sama satu sama lain, kita berarti bahwa readoperations mengembalikan nilai-nilai yang sama dan bahwa variabel instance dari obyek memiliki nilai yang sama di akhir.Penggunaan kesetaraan seri sebagai kriteria untuk eksekusi bersamaan benar mencegah terjadinya kehilangan pembaruan dan retrievals tidak konsisten Pembaruan problemoccurs kehilangan ketika dua transaksi membaca nilai lama dari variabel dan kemudian menggunakannya untuk menghitung nilai baru
. Hal ini tidak bisa terjadi jika satu transaksi dilakukan sebelum yang lain, karena transaksi nantinya akan membaca nilai yang ditulis bythe satu sebelumnya. Sebagai interleaving serial setara dengan dua transaksi menghasilkan efek yang sama sebagai salah satu serial, kita dapat memecahkan pembaruan sarana problemby kehilangan serialrekening bersama, B, yang actuallyserial, untuk transaksi Tdoes semua operasi pada B sebelum Udoes transaksi. interleavingof lain Tand Uthat memiliki ini propertyis satu di mana transaksi Ucompletes operasinya pada rekening transaksi Bbefore Tstarts.
Kita sekarang mempertimbangkan efek dari kesetaraan seri dalam kaitannya tertalu tidak konsisten retrievals masalah, di mana transaksi Vis transferringa sumfromaccount Ato Band transaksi Wis obtainingthe sumof semua saldo (lihat Gambar 16.6). The konsisten retrievals problemcan terjadi ketika transaksi pengambilan berjalan bersamaan dengan Pembaruan transaksi. Hal ini tidak bisa terjadi jika transaksi pengambilan dilakukan sebelum atau setelah transaksi update. Sebuah serial setara interleaving dari transaksi pengambilan dan transaksi update, misalnya seperti pada Gambar 16.8, akan mencegah konsisten retrievals terjadi.
Gambar 16.8 Sebuah serial setara interleaving ofVandW
...
Ketika kita saythat sepasang operasi conflictswe berarti bahwa Efek gabungan mereka tergantung pada urutan theyare dieksekusi. untuk menyederhanakan hal yang kita anggap sepasang operasi, readand write.read mengakses nilai sebuah keberatan dan writechanges nilainya. The effectof operasi mengacu pada nilai suatu objek mengatur bya writeoperation dan hasilnya dikembalikan bya readoperation. Konflik aturan untuk writeoperations readand diberikan pada Gambar 16.9.Gambar 16.9 Readand aturan konflik writeoperationOperasi yang berbeda transaksi Alasan konflik baca baca ada Karena efek dari sepasang readoperations tidak tidak tergantung pada urutan theyare dieksekusi baca tulis Ya Karena efek dari readand writeoperation a tergantung pada urutan eksekusi mereka menulis menulis Ya Karena efek dari sepasang writeoperations tergantung pada urutan eksekusi mereka Untuk anypair transaksi, adalah mungkin untuk menentukan urutan pasang conflictingoperations pada objek diakses byboth dari mereka. Serial kesetaraan dapat didefinisikan dalam hal konflik operasi sebagai berikut: Untuk dua transaksi menjadi serial setara, itu adalah necessaryand cukup bahwa semuapasang conflictingoperations dari dua transaksi dieksekusi di sama order pada semua objek theyboth mengakses
Gambar 16.9 Baca Dan operasi write aturan konflik
Gambar 16.10 A interleaving non-serial-setara ope U rasi transaksi Tand U
Akses setiap transaksi untuk benda iand jis serial sehubungan dengan satu sama lain,becauseT membuat semua akses untuk ibefore Udoes dan U membuat semua akses untuk jbefore Tdoes. Tapi pemesanan tidak serial setara, karena pasang operasi yang bertentangan tidak dilakukan dalam urutan yang sama di kedua objek. Seriallyequivalent orderings memerlukan salah satu kondisi followingtwo:
1.Taccessesibefore Uand Taccesses jbefore U.
2.Uaccesses ibefore Tand Uaccesses jbefore T.
Serial kesetaraan digunakan sebagai kriteria untuk derivasi dari concurrencycontrol protokol. protokol ini mencoba untuk cerita bersambung transaksi dalam akses mereka ke obyek.Tiga pendekatan alternatif untuk concurrencycontrol yang commonlyused: penguncian,concurrencycontrol optimis dan timestamp pemesanan. Namun, yang paling praktis sistem menggunakan penguncian, yang dibahas dalam Bagian 16.4. Ketika lockingis digunakan, Server set kunci, diberi label dengan transactionidentifier, di setiap objek sebelum itu diakses dan menghapus kunci ini ketika transaksi telah selesai. Sementara obyek terkunci, onlythe transaksi yang terkunci untuk dapat mengakses objek itu; laintransaksi harus baik menunggu sampai obyek terkunci atau, dalam beberapa kasus, berbagi mengunci. Penggunaan kunci dapat menyebabkan kebuntuan, dengan transaksi waitingfor sama lain untuk kunci rilis - misalnya, ketika sepasang transaksi masing-masing memiliki objek terkunci yang yang lain perlu mengakses.
Kami membahas deadlockproblemand beberapa solusi untuk itu di Bagian 16.4.1.concurrencycontrol Optimis dijelaskan dalam Bagian 16.5. dalam optimis skema, transaksi berlangsung sampai meminta untuk melakukan, dan sebelum diperbolehkan untuk komit server melakukan checkto sebuah temukan operasi apakah telah dilakukan pada anyobjects yang bertentangan dengan operasi transaksi konkuren lain, di mana kasus server dibatalkan dan klien mayrestart itu. The aimof yang checkis untuk memastikan bahwa semua benda yang benar.orderingis timestamp dijelaskan dalam Bagian 16.6. Dalam timestamp memesan, server mencatat waktu terbaru dari readingand writingof setiap objek dan untuk setiap
Gambar 16.11 Bacaan kotor ketika Taborts transaksi
operasi, timestamp transaksi dibandingkan dengan yang dari objek untuk menentukan apakah hal itu dapat dilakukan segera atau harus ditunda atau ditolak. ketika sebuah operasi tertunda, transaksi menunggu; ketika ditolak, transaksi dibatalkan.Pada dasarnya, concurrencycontrol dapat dicapai baik byclients'transactions waitingfor satu sama lain atau transaksi restart setelah konflik antara operasi telah terdeteksi, atau bya kombinasi dari keduanya.
16.2.2 Recoverability dari dibatalkan
Server harus mencatat semua efek dari transaksi yang dilakukan dan tidak ada efek transaksi dibatalkan. Oleh karena itu mereka harus memungkinkan untuk fakta bahwa mayabort transaksi bypreventingit affectingother transaksi konkuren jika ia melakukannya. Bagian ini menggambarkan dua masalah yang terkait dengan transaksi aborsi di konteks bankingexample tersebut. Masalah-masalah ini disebut 'reads'and kotor' premature menulis ', dan kedua themcan terjadi di hadapan eksekusi serial setara transaksi. Isu-isu ini prihatin dengan efek dari operasi pada objek tersebut sebagai saldo rekening bank a. Untuk simplifythings, operasi dianggap dalam dua kategori: readoperations dan writeoperations. Dalam ilustrasi kami, getBalanceis sebuah readoperation dan setBalancea writeoperation. Termanfaatkannya transaksi Kotor berbunyi.
Properti isolasi transaksi mensyaratkan bahwa transaksi tidak melihat negara uncommitted transaksi lainnya. The 'dirtyread'problemis disebabkan bythe interaksi antara readoperation dalam satu transaksi dan operasi menulis awal transaksi lain pada objek yang sama. Pertimbangkan eksekusi diilustrasikan pada Gambar 16.11 Bacaan kotor ketika Taborts transaksi TransactionT: Transaksi U:a.getBalance () a.setBalance (saldo + 10) a.getBalance () a.setBalance (saldo + 20) keseimbangan = a.getBalance () $ 100 a.setBalance (saldo + 10) $ 110 keseimbangan = a.getBalance () $ 110 a.setBalance (saldo + 20) $ 130 melakukan transaksi batalkan transaksi , Di mana T mendapat saldo rekening Aand set ke $ 10 lebih, maka U mendapat saldo rekening Aand set ke $ 20 lebih, dan dua eksekusi adalah serial setara. Sekarang anggaplah bahwa Taborts transaksi setelah Uhas berkomitmen. Kemudian transaksi Uwill telah melihat nilai yang pernah ada, karena Awill dikembalikan ke nya nilai asli. Kami saythat transaksi Uhas dilakukan membaca kotor. Karena memiliki berkomitmen, tidak dapat dibatalkan
Gambar 16.12 Timpa nilai uncommitted
eksekusi yang ketat dari transaksi • Umumnya, diperlukan bahwa transaksi delayboth writeoperations readand mereka sehingga untuk menghindari baik dirtyreads dan menulis dini. Itu eksekusi transaksi disebut strictif penundaan pelayanan baik menulis readand operasi pada objek sampai semua transaksi yang sebelumnya menulis objek yang memiliki baik dilakukan atau dibatalkan. Pelaksanaan yang ketat dari transaksi memberlakukan properti yang diinginkanisolasi.
versi tentatif • Untuk server benda dipulihkan untuk berpartisipasi intransactions, itu harus dirancang sedemikian rupa sehingga anyupdates benda dapat dihapus jika dan ketika transaksi dibatalkan. Untuk membuat ini mungkin, semua operasi update dilakukan selama transaksi dilakukan dalam versi tentatif obyek dalam memori volatile. Setiap transaksi disediakan dengan set sendiri pribadi versi tentatif anyobjects yang itu telah diubah. Semua update operasi dari menyimpan nilai-nilai transaksi dalam transaksi ini set pribadi sendiri. operasi akses dalam suatu transaksi mengambil nilai dari dana transaksi ini menetapkan sendiri pribadi jika mungkin, atau failingthat, dari dana benda.
menulis dini • Pertimbangkan implikasi lain dari possibilitythat transaksi mayabort. satu ini berkaitan dengan interaksi antara writeoperations pada yang sama keberatan belongingto transaksi yang berbeda. Untuk ilustrasi, kita mempertimbangkan dua transaksi getBalance, T Dan U, pada akun A, seperti yang ditunjukkan pada 16.12 Timpa nilai uncommitted TransactionT: Transaksi U:a.setBalance (105) a.setBalance (110)$ 100 a.setBalance (105) $ 105 a.setBalance (110) $ 110 Sebelum transaksi, saldo akun A $ 100. Dua eksekusi adalah serial setara, dengan saldo Tsettingthe menjadi $ 105 dan Usettingit menjadi $ 110. Jika transaksi Uaborts dan Tcommits, keseimbangan harus $ 105.Beberapa sistem database melaksanakan aksi abortbyrestoring 'sebelum images'of semua writesof transaksi. Dalam contoh kita, Ais $ 100 awalnya, yang 'sebelum image'of T'swrite; sama, $ 105 adalah 'sebelum image'of U'swrite. Demikian ifUaborts, kita mendapatkan keseimbangan yang benar dari $ 105.Sekarang perhatikan kasus ketika Ucommits dan kemudian Taborts. Keseimbangan harus $ 110, tetapi sebagai 'sebelum image'of T'swriteis $ 100, kita mendapatkan wrongbalance $ 100.Demikian pula, jika Taborts dan kemudian Uaborts, 'sebelum image'of U'swriteis $ 105 dan kami mendapatkan wrongbalance dari $ 105 - keseimbangan harus kembali $ 100.Untuk memastikan hasil yang benar dalam recoveryscheme yang menggunakan sebelum gambar, menulis operasi harus ditunda sampai transaksi sebelumnya bahwa diperbarui objek yang sama memiliki baik berkomitmen atau dibatalkan
eksekusi yang ketat dari transaksi • Umumnya, diperlukan bahwa transaksi delayboth writeoperations readand mereka sehingga untuk menghindari baik dirtyreads dan menulis dini. Itu eksekusi transaksi disebut strictif penundaan pelayanan baik menulis readand operasi pada objek sampai semua transaksi yang previouslywrote objek yang memiliki baik dilakukan atau dibatalkan. Pelaksanaan yang ketat dari transaksi memberlakukan properti yang diinginkan isolasi.
versi tentatif • Untuk server benda dipulihkan untuk berpartisipasi intransactions, itu harus dirancang sedemikian rupa sehingga anyupdates benda dapat dihapus jika dan ketikatransaksi dibatalkan. Untuk membuat ini mungkin, semua operasi update dilakukan selama transaksi dilakukan dalam versi tentatif obyek dalam memori volatile. Setiap transaksi disediakan dengan set sendiri pribadi versi tentatif anyobjects yang itu telah diubah. Semua update operasi dari menyimpan nilai-nilai transaksi dalam transaksi ini
set pribadi sendiri. operasi akses dalam suatu transaksi mengambil nilai dari dana transaksi ini menetapkan sendiri pribadi jika mungkin, atau failingthat, dari dana benda.Versi tentatif ditransfer ke objek onlywhen transaksi melakukan, bywhich waktu theywill juga telah tercatat dalam penyimpanan permanen. Ini adalah dilakukan dalam satu langkah, duringwhich transaksi lainnya dikecualikan fromaccess untukobjek yang beingaltered. Ketika transaksi dibatalkan, versi tentatif yang
Gambar 16.13 transaksi Bersarang
transaksi bersarang memperluas model transaksi di atas dengan memungkinkan transaksi menjadi terdiri dari transaksi lainnya. Sehingga beberapa transaksi mungkin mulai fromwithin a transaksi, allowingtransactions dianggap sebagai modul yang dapat disusun sebagai wajib.
Transaksi terluar dalam satu set transaksi bersarang disebut top-level transaksi. Transaksi selain transaksi top-level disebut subtransactions.Misalnya, pada Gambar 16,13, Tis transaksi tingkat atas yang dimulai sepasang subtransactions, T1and T2. subtransaction yang T1starts pasangan sendiri subtransactions,T11and T22. Juga, subtransaction T2starts sendiri subtransaction, T21, yang dimulai subtransaction lain, T211.
Sebuah subtransaction muncul atom ke induknya sehubungan dengan kegagalan transaksi dan untuk akses bersamaan. Subtransactions pada tingkat yang sama, seperti T1and T2, dapat menjalankan bersamaan, tetapi akses mereka untuk benda-benda umum serial - misalnya, bythe lockingscheme dijelaskan dalam Bagian 16.4. Setiap subtransaction bisa gagal independentlyof induknya dan dari subtransactions lainnya. Ketika subtransaction sebuah dibatalkan, orangtua transaksi kadang-kadang dapat memilih subtransaction alternatif untuk menyelesaikan tugasnya. Untuk Misalnya, transaksi untuk menyampaikan pesan email ke daftar penerima dapat terstruktur sebagai satu set subtransactions, yang masing-masing memberikan pesan ke salah satu penerima.Jika salah satu atau lebih dari subtransactions gagal, transaksi orangtua bisa merekam fakta dan kemudian melakukan, dengan hasil bahwa semua transaksi anak sukses komit. Saya kemudian bisa mulai transaksi lain untuk mencoba untuk mengirim ulang pesan yang tidakmengirim pertama kalinya.
Gambar 16.13 transaksi Bersarang
Jika transaksi tingkat atas melakukan, maka semua subtransactions yang memiliki provisionallycommitted dapat melakukan juga, asalkan tidak ada nenek moyang mereka memiliki dibatalkan. Dalam contoh kita, komitmen T memungkinkan T1, T11and T12to komit, tapi tidak T21and T211since orang tua mereka, T2, dibatalkan. Perhatikan bahwa efek dari subtransaction tidak permanen sampai transaksi top-level melakukan.Dalam beberapa kasus, maydecide transaksi top-level untuk membatalkan karena satu atau lebih dari yang subtransactions telah dibatalkan. Sebagai contoh, pertimbangkan Transfer berikut transaksi:Mentransfer $ 100 dari BTO A
a.deposit (100)
b.withdraw (100)
Hal ini dapat disusun sebagai sepasang subtransactions, satu untuk withdrawoperation dan yang lain untuk deposit. Ketika dua subtransactions baik komit, Transfer Transaksi juga dapat melakukan. Misalkan withdrawsubtransaction sebuah dibatalkan setiap kali account tekor. Sekarang perhatikan kasus ketika withdrawsubtransaction yang dibatalkan dan depositsubtransaction berkomitmen - dan ingat bahwa komitmen dari Transaksi anak tergantung pada transaksi orangtua melakukan. Kami menganggap bahwa top-level (Transfer) transaksi akan memutuskan untuk membatalkan. The abortingof orang tua transaksi menyebabkan subtransactions untuk membatalkan - sehingga deposittransaction adalah dibatalkan dan semua efeknya dibatalkan.CORBA Obyek Layanan Transaksi mendukung datar dan bersarang transaksi. transaksi bersarang yang particularlyuseful dalam sistem terdistribusi karena transaksi anak mungkin menjalankan server concurrentlyin berbeda. Kami kembali ke masalah ini dalam Bab 17. formof bersarang transaksi ini disebabkan Moss [1985]. varian lain dari transaksi bersarang dengan serializabilityproperties yang berbeda telah diusulkan; untuk Misalnya, melihat Weikum [1991].Transaksi harus terjadwal sehingga efeknya pada data bersama adalah seriallyequivalent.
Sebuah server dapat mencapai kesetaraan serial transaksi byserializingaccess ke benda. Gambar 16.7 menunjukkan contoh bagaimana kesetaraan serial dapat dicapai dengan beberapa derajat transaksi concurrency- Tand Uboth account akses B, tapi T melengkapi akses sebelum Ustarts accessingit.
Contoh sederhana dari serialisasi sebuah mechanismis penggunaan kunci eksklusif. Didalam lockingscheme, server mencoba untuk lockanyobject yang hendak digunakan byany operasi transaksi klien. Jika klien meminta akses ke suatu objek yang sudah terkunci karena transaksi lain klien, permintaan tersebut ditangguhkan dan klien harus menunggu sampai objek tersebut dibuka.Gambar 16.14 menggambarkan penggunaan kunci eksklusif. Ini menunjukkan transaksi yang sama seperti Gambar 16.7, tetapi dengan kolom tambahan untuk setiap penguncian showingthe transaksi,waitingand unlocking. Dalam contoh ini, diasumsikan bahwa ketika transaksi Tand U mulai, saldo rekening A, Perawatan Band belum terkunci. Ketika transaksi Tis tentang menggunakan akun B, terkunci untuk T. Ketika transaksi Uis tentang menggunakan Bit masih
16,4 Kunci
Transaksi harus terjadwal sehingga efeknya pada data bersama adalah serial setara.Sebuah server dapat mencapai kesetaraan serial transaksi dengan serialisasi akses ke benda. Gambar 16.7 menunjukkan contoh bagaimana kesetaraan serial dapat dicapai dengan beberapa derajat transaksi concurrency- Tand Uboth account akses B, tapi T melengkapi akses sebelum Ustarts accessingit.Contoh sederhana dari serialisasi sebuah mechanismis penggunaan kunci eksklusif. Didalam lockingscheme, server mencoba untuk lockanyobject yang hendak digunakan byany
operasi transaksi klien. Jika klien meminta akses ke suatu objek yang sudah terkunci karena transaksi lain klien, permintaan tersebut ditangguhkan dan klien harusmenunggu sampai objek tersebut dibuka.Gambar 16.14 menggambarkan penggunaan kunci eksklusif. Ini menunjukkan transaksi yang sama seperti Gambar 16.7, tetapi dengan kolom tambahan untuk setiap penguncian showingthe transaksi,waitingand unlocking. Dalam contoh ini, diasumsikan bahwa ketika transaksi Tand U mulai, saldo rekening A, Perawatan Band belum terkunci. Ketika transaksi Tis tentang menggunakan akun B, terkunci untuk T. Ketika transaksi Uis tentang menggunakan Bit masih
Gambar 16.14 Transaksi Tan Dengan kunci eksklusif
BAGIAN 16,4 kunci 693
terkunci untuk T, sehingga transaksi Uwaits. Ketika transaksi Tis berkomitmen, Bis terkunci,transaksi dimana Uis dilanjutkan. Penggunaan Lockon yang Beffectivelyserializes yang akses ke B. Perhatikan bahwa jika, misalnya, Treleased yang Lockon Bbetween getBalance nya dan operasi setBalance, transaksi Kami getBalanceoperation di Bcould menjadi interleaved antara mereka.Serial kesetaraan mensyaratkan bahwa semua accessesto transaksi ini objek tertentu serial sehubungan dengan mengakses transaksi byother. Semua pasangan yang saling bertentangan operasi dari dua transaksi harus dieksekusi dalam urutan yang sama. Untuk memastikan ini,transaksi tidak diperbolehkan kunci anynew setelah itu telah merilis kunci. Tahap pertama setiap transaksi adalah 'growingphase', duringwhich kunci baru diperoleh. DalamTahap kedua, kunci dilepaskan (a 'shrinkingphase').
Ini disebut dua-fase penguncian.Kami melihat dalam Bagian 16.2.2 itu karena transaksi mayabort, eksekusi yang ketat diperlukan untuk mencegah dirtyreadsand menulis dini. Di bawah rezim eksekusi yang ketat,transaksi yang perlu untuk membaca atau menulis sebuah objek harus ditunda sampai lainnya transaksi yang menulis objek yang sama telah dilakukan atau dibatalkan. Untuk menegakkan aturan ini,anylocks diterapkan duringthe kemajuan transaksi diadakan sampai transaksi melakukan atau dibatalkan. Ini disebut penguncian dua-fase yang ketat. Kehadiran kunci mencegah transaksi lainnya readingor writingthe benda. Ketika transaksi melakukan,untuk memastikan pemulihan, kunci harus dipegang sampai semua benda diperbarui telah ditulis ke penyimpanan permanen.Sebuah server generallycontains benda numberof besar, dan transaksi yang khas mengakses onlya beberapa themand adalah unlikelyto berbenturan dengan transaksi lancar lainnya. Itu granularitywith yang concurrencycontrol dapat diterapkan ke objek adalah penting
694CHAPTER 16 TRANSAKSI DAN CONCURRENCY KONTROL
masalah, karena ruang lingkup untuk akses bersamaan ke objek dalam server akan terbatas parah jika concurrencycontrol (misalnya, kunci) dapat onlybe diterapkan ke semua objek sekaligus.Dalam bankingexample kami, jika kunci yang diterapkan untuk semua rekening nasabah di cabang, hanya satu bankclerkcould bankingtransaction secara online performan kapan saja – hardlyan kendala diterima!Bagian dari objek yang akses harus serial harus sekecil mungkin; yaitu, hanya saja bagian yang terlibat dalam setiap operasi yang diminta bytransactions.
Dalam bankingexample kami, cabang memegang satu set rekening, masing-masing memiliki keseimbangan. Setiap bankingoperation mempengaruhi satu atau saldo rekening lebih - depositand menarik mempengaruhi satu saldo rekening, dan cabang Jumlah mempengaruhi semua dari mereka.Deskripsi skema concurrencycontrol diberikan di bawah tidak bertanggung
granularity tertentu. Kami membahas protokol concurrencycontrol yang berlaku untuk benda yang operasinya dapat dimodelkan dalam hal writeoperations readand pada benda. Untuk protokol untuk workcorrectly, adalah penting bahwa setiap readand menulis operasi atom di dampaknya pada benda.protokol Concurrencycontrol dirancang untuk mengatasi conflictsbetween operasi dalam transaksi yang berbeda pada objek yang sama. Dalam bab ini, kita menggunakan gagasan konflik antara operasi untuk menjelaskan protokol. konflik aturan untuk readand writeoperations diberikan pada Gambar 16,9, yang menunjukkan bahwa pasangan readoperations transaksi fromdifferent pada objek yang sama tidak bertentangan. Oleh karena itu, sederhana lockthat eksklusif digunakan untuk kedua writeoperations readand mengurangi concurrency lebih daripada yang diperlukan.
Adalah lebih baik untuk mengadopsi lockingscheme yang mengontrol akses ke setiap objek sehingga yang ada dapat beberapa transaksi konkuren objek readingan, atau satu transaksi writingan objek, tetapi tidak keduanya. Ini commonlyreferred sebagai 'banyak pembaca / single writer'scheme. Dua jenis kunci yang digunakan: membaca locksand menulis kunci.
Sebelum readoperation transaksi ini dilakukan, membaca lockshould ditetapkan pada obyek. Sebelum writeoperation transaksi ini dilakukan, tulis lockshould diatur pada objek. Setiap kali tidak mungkin untuk menetapkan lockimmediately, transaksi (dan client) harus menunggu sampai adalah mungkin untuk melakukannya - permintaan klien tidak pernah ditolak.
Sebagai pasang readoperations transaksi fromdifferent tidak konflik, upaya untuk mengatur membaca Lockon obyek dengan membaca lockis selalu sukses. Semua transaksi readingthe berbagi objek yang sama yang membaca kunci- untuk alasan ini, baca kunci kadang-kadangdisebut bersama kunci.Aturan konflik operasi memberitahu kita bahwa:
Jika transaksi Thas alreadyperformed readoperation pada objek tertentu, maka transaksi konkuren U tidak harus writethat objek hingga Tcommits ataudibatalkan.
Jika transaksi Thas alreadyperformed writeoperation pada objek tertentu, maka transaksi konkuren U tidak harus Reador writethat objek hingga Tcommits atau dibatalkan.Untuk menegakkan kondisi 1, permintaan untuk menulis Lockon obyek tertunda bythe kehadiran dari membaca sebuah lockbelongingto transaksi lain. Untuk menegakkan kondisi 2, permintaan untuk baik membaca lockor menulis Lockon obyek tertunda bythe kehadiran menulis kunci belongingto transaksi lain.
BAGIAN 16,4 kunci 695
erkunci untuk T, sehingga transaksi Uwaits. Ketika transaksi Tis berkomitmen, Bis terkunci,transaksi dimana Uis dilanjutkan. Penggunaan Lockon yang Beffectivelyserializes yang akses ke B. Perhatikan bahwa jika, misalnya, Treleased yang Lockon Bbetween getBalance nya dan setBalanceoperations, transaksi U getBalanceoperation di Bcould menjadi interleaved antara mereka.
Serial kesetaraan mensyaratkan bahwa semua accessesto transaksi ini objek tertentu serial sehubungan dengan mengakses transaksi byother. Semua pasangan yang saling bertentangan operasi dari dua transaksi harus dieksekusi dalam urutan yang sama. Untuk memastikan ini,transaksi tidak diperbolehkan kunci anynew setelah itu telah merilis kunci. Tahap pertama setiap transaksi adalah 'growingphase', duringwhich kunci baru diperoleh. Dalam Tahap kedua, kunci dilepaskan (a 'shrinkingphase'). Ini disebut dua-fase penguncian.Kami melihat dalam Bagian 16.2.2 itu karena transaksi mayabort, eksekusi yang ketat diperlukan untuk mencegah dirtyreadsand menulis dini. Di bawah rezim eksekusi yang ketat,transaksi yang perlu untuk membaca atau menulis sebuah objek harus ditunda sampai lainnya
transaksi yang menulis objek yang sama telah dilakukan atau dibatalkan. Untuk menegakkan aturan ini,anylocks diterapkan duringthe kemajuan transaksi diadakan sampai transaksi melakukan atau dibatalkan. Ini disebut penguncian dua-fase yang ketat. Kehadiran kunci mencegah transaksi lainnya readingor writingthe benda. Ketika transaksi melakukan,untuk memastikan pemulihan, kunci harus dipegang sampai semua benda diperbarui telah ditulis ke penyimpanan permanen.
Sebuah server generallycontains benda numberof besar, dan transaksi yang khasmengakses onlya beberapa themand adalah unlikelyto berbenturan dengan transaksi lancar lainnya. Itu granularitywith yang concurrencycontrol dapat diterapkan ke objek adalah penting
Gambar 16,16 Penggunaan kunci di penguncian dua-fase yang ketat
masalah, karena ruang lingkup untuk akses bersamaan ke objek dalam server akan terbatas parah jika concurrencycontrol (misalnya, kunci) dapat onlybe diterapkan ke semua objek sekaligus.Dalam bankingexample kami, jika kunci yang diterapkan untuk semua rekening nasabah di cabang, hanya satu bankclerkcould bankingtransaction secara online performan kapan saja – hardlyan kendala diterima!
Bagian dari objek yang akses harus serial harus sekecil mungkin; yaitu, hanya saja bagian yang terlibat dalam setiap operasi yang diminta bytransactions. Dalam bankingexample kami, cabang memegang satu set rekening, masing-masing memiliki keseimbangan.Setiap bankingoperation mempengaruhi satu atau saldo rekening lebih - depositand menarik mempengaruhi satu saldo rekening, dan cabang Jumlah mempengaruhi semua dari mereka.Deskripsi skema concurrencycontrol diberikan di bawah tidak bertanggung granularity tertentu.
Kami membahas protokol concurrencycontrol yang berlaku untuk benda yang operasinya dapat dimodelkan dalam hal writeoperations readand pada benda. Untuk protokol untuk workcorrectly, adalah penting bahwa setiap readand menulis operasi atom di dampaknya pada benda.protokol Concurrencycontrol dirancang untuk mengatasi conflictsbetween operasi dalam transaksi yang berbeda pada objek yang sama. Dalam bab ini, kita menggunakan gagasan konflik antara operasi untuk menjelaskan protokol. konflik aturan untuk readand writeoperations diberikan pada Gambar 16,9, yang menunjukkan bahwa pasangan readoperations transaksi fromdifferent pada objek yang sama tidak bertentangan. Oleh karena itu, sederhana lockthat eksklusif digunakan untuk kedua writeoperations readand mengurangi concurrency lebih daripada yang diperlukan.
Adalah lebih baik untuk mengadopsi lockingscheme yang mengontrol akses ke setiap objek sehingga yang ada dapat beberapa transaksi konkuren objek readingan, atau satu transaksi writingan objek, tetapi tidak keduanya. Ini commonlyreferred sebagai 'banyak pembaca / single writer'scheme. Dua jenis kunci yang digunakan: membaca locksand menulis kunci.Sebelum readoperation transaksi ini dilakukan, membaca lockshould ditetapkan pada obyek. Sebelum writeoperation transaksi ini dilakukan, tulis lockshould diatur pada
objek. Setiap kali tidak mungkin untuk menetapkan lockimmediately, transaksi (dan client) harus menunggu sampai adalah mungkin untuk melakukannya - permintaan klien tidak pernah ditolak. Sebagai pasang readoperations transaksi fromdifferent tidak konflik, upaya untuk mengatur membaca Lockon obyek dengan membaca lockis selalu sukses. Semua transaksi readingthe berbagi objek yang sama yang membaca kunci- untuk alasan ini, baca kunci kadang-kadang disebut bersama kunci.
Aturan konflik operasi memberitahu kita bahwa:
Jika transaksi Thas alreadyperformed readoperation pada objek tertentu, maka transaksi konkuren U tidak harus writethat objek hingga Tcommits atau dibatalkan.
Jika transaksi Thas alreadyperformed writeoperation pada objek tertentu, maka transaksi konkuren U tidak harus Reador writethat objek hingga Tcommits atau dibatalkan.
Untuk menegakkan kondisi 1, permintaan untuk menulis Lockon obyek tertunda bythe kehadiran dari membaca sebuah lockbelongingto transaksi lain. Untuk menegakkan kondisi 2, permintaan untuk baik membaca lockor menulis Lockon obyek tertunda bythe kehadiran menulis kunci belongingto transaksi lain
Gambar 16.15 kompatibilitas Lock
Gambar 16.15
menunjukkan yang compatibilityof membaca kunci dan menulis kunci pada salah objek tertentu. Entri ke kiri kolom pertama dalam tabel menunjukkan jenis lockalreadyset, jika ada. Entri di atas baris pertama menunjukkan jenis lockrequested. entryin setiap sel menunjukkan efek pada transaksi yang meminta jenis kunci diberikan di atas ketika objek telah terkunci dalam transaksi lain dengan jenis kunci di kiri.
retrievals tidak konsisten dan update hilang disebabkan byconflicts antara membaca operasi dalam satu transaksi dan writeoperations di lain tanpa perlindungan dari Skema concurrencycontrol seperti penguncian. retrievals konsisten dicegah oleh performingthe transaksi pengambilan sebelum atau setelah transaksi update. Jika pengambilan yang transaksi yang lebih dulu, membaca kunci nya delaythe transaksi update. Jika datang kedua, Permintaan untuk membaca kunci menyebabkannya ditunda sampai transaksi update memiliki lengkap.update hilang terjadi ketika dua transaksi membaca nilai dari sebuah objek dan kemudian menggunakan untuk menghitung nilai baru. update hilang dicegah oleh transaksi makinglater delay mereka membaca sampai yang sebelumnya telah selesai. Hal ini dicapai transaksi byeach settinga baca lockwhen membaca obyek dan kemudian promotingit untuk menulis sebuah lockwhen itu menulis objek yang sama - ketika transaksi berikutnya memerlukan membaca lockit akan ditunda sampai transaksi anycurrent telah selesai. Sebuah transaksi dengan lockthat membaca bersama dengan transaksi lain tidak bisa mempromosikan membaca yang lockto menulis kunci, karena yang terakhir akan bertentangan dengan kunci membaca diadakan bythe transaksi lainnya. Oleh karena itu, transaksi tersebut harus meminta kunci menulis dan menunggu untuk kunci membaca lainnya akan dirilis.Lockpromotion mengacu pada konversi lockto a kunci- kuat yaitu,lockthat lebih eksklusif. The lockcompatibilitytable pada Gambar 16.15 menunjukkan kunci exclusivityof relatif. membaca lockallows kunci membaca lainnya, sedangkan menulis lockdoes tidak. Baik memungkinkan kunci tulis lainnya. Oleh karena itu, menulis sebuah lockis lebih eksklusif dari kunci membaca. Kunci mungkin dipromosikan karena hasilnya adalah kunci lebih eksklusif. Saya t tidak aman untuk menurunkan sebuah lockheld bya transaksi sebelum melakukan, karena hasilnya akan lebih permisif dari yang sebelumnya dan mayallow eksekusi byother transaksi yang tidak sesuai dengan kesetaraan serial.
Aturan untuk penggunaan kunci dalam lockingimplementation dua-fase yang ketat diringkas dalam Gambar 16,16. Untuk memastikan bahwa aturan ini dipatuhi, klien tidak memiliki akses ke operasi untuk item lockingor unlocking data. Lockingis dilakukan ketika permintaan untuk writeoperations readand akan segera diterapkan pada dipulihkanbenda, dan unlockingis dilakukan bythe abortoperations commitor transaksi koordinator. masalah, karena ruang lingkup untuk akses bersamaan ke objek dalam server akan terbatas parah
jika concurrencycontrol (misalnya, kunci) dapat onlybe diterapkan ke semua objek sekaligus. Dalam bankingexample kami, jika kunci yang diterapkan untuk semua rekening nasabah di cabang, hanya satu bankclerkcould bankingtransaction secara online performan kapan saja – hardlyan kendala diterima!
Bagian dari objek yang akses harus serial harus sekecil mungkin; yaitu, hanya saja bagian yang terlibat dalam setiap operasi yang diminta bytransactions.Dalam bankingexample kami, cabang memegang satu set rekening, masing-masing memiliki keseimbangan. Setiap bankingoperation mempengaruhi satu atau saldo rekening lebih - depositand menarik mempengaruhi satu saldo rekening, dan cabang Jumlah mempengaruhi semua dari mereka. Deskripsi skema concurrencycontrol diberikan di bawah tidak bertanggung
granularity tertentu. Kami membahas protokol concurrencycontrol yang berlaku untuk benda yang operasinya dapat dimodelkan dalam hal writeoperations readand pada benda. Untuk protokol untuk workcorrectly, adalah penting bahwa setiap readand menulis operasi atom di dampaknya pada benda.protokol Concurrencycontrol dirancang untuk mengatasi conflictsbetween operasi dalam transaksi yang berbeda pada objek yang sama. Dalam bab ini, kita menggunakan gagasan konflik antara operasi untuk menjelaskan protokol. konflik aturan untuk readand writeoperations diberikan pada Gambar 16,9, yang menunjukkan bahwa pasangan readoperations transaksi fromdifferent pada objek yang sama tidak bertentangan. Oleh karena itu, sederhana lockthat eksklusif digunakan untuk kedua writeoperations readand mengurangi concurrency lebih daripada yang diperlukan.
Adalah lebih baik untuk mengadopsi lockingscheme yang mengontrol akses ke setiap objek sehingga yang ada dapat beberapa transaksi konkuren objek readingan, atau satu transaksi writingan objek, tetapi tidak keduanya. Ini commonlyreferred sebagai 'banyak pembaca / single writer'scheme. Dua jenis kunci yang digunakan: membaca locksand menulis kunci.
Sebelum readoperation transaksi ini dilakukan, membaca lockshould ditetapkan pada obyek. Sebelum writeoperation transaksi ini dilakukan, tulis lockshould diatur pada objek. Setiap kali tidak mungkin untuk menetapkan lockimmediately, transaksi (dan client) harus menunggu sampai adalah mungkin untuk melakukannya - permintaan klien tidak pernah ditolak.
Sebagai pasang readoperations transaksi fromdifferent tidak konflik, upaya untuk mengatur membaca Lockon obyek dengan membaca lockis selalu sukses. Semua transaksi readingthe berbagi objek yang sama yang membaca kunci- untuk alasan ini, baca kunci kadang-kadang disebut bersama kunci.
Aturan konflik operasi memberitahu kita bahwa:
Jika transaksi Thas alreadyperformed readoperation pada objek tertentu,maka transaksi konkuren U tidak harus writethat objek hingga Tcommits atau dibatalkan.
Jika transaksi Thas alreadyperformed writeoperation pada objek tertentu,maka transaksi konkuren U tidak harus Reador writethat objek hingga Tcommits atau dibatalkan.
Untuk menegakkan kondisi 1, permintaan untuk menulis Lockon obyek tertunda bythe kehadirandari membaca sebuah lockbelongingto transaksi lain. Untuk menegakkan kondisi 2, permintaan untuk baik membaca lockor menulis Lockon obyek tertunda bythe kehadiran menulis kunci belongingto transaksi lain.
Gambar 16.15 kompatibilitas Lock
Gambar 16.15
menunjukkan yang compatibilityof membaca kunci dan menulis kunci pada salah objek tertentu. Entri ke kiri kolom pertama dalam tabel menunjukkan jenis lockalreadyset, jika ada. Entri di atas baris pertama menunjukkan jenis lockrequested.entryin setiap sel menunjukkan efek pada transaksi yang meminta jenis kunci diberikan di atas ketika objek telah terkunci dalam transaksi lain dengan jenis kunci di kiri.
retrievals tidak konsisten dan update hilang disebabkan byconflicts antara membaca operasi dalam satu transaksi dan writeoperations di lain tanpa perlindungan dari Skema concurrencycontrol seperti penguncian. retrievals konsisten dicegah oleh performingthe transaksi pengambilan sebelum atau setelah transaksi update. Jika pengambilan yang transaksi yang lebih dulu, membaca kunci nya delaythe transaksi update. Jika datang kedua,
Permintaan untuk membaca kunci menyebabkannya ditunda sampai transaksi update memiliki lengkap.update hilang terjadi ketika dua transaksi membaca nilai dari sebuah objek dan kemudian menggunakan untuk menghitung nilai baru. update hilang dicegah oleh transaksi makinglater delay mereka membaca sampai yang sebelumnya telah selesai.
Hal ini dicapai transaksi byeach settinga baca lockwhen membaca obyek dan kemudian promotingit untuk menulis sebuah lockwhen itu menulis objek yang sama - ketika transaksi berikutnya memerlukan membaca lockit akan ditunda sampai transaksi anycurrent telah selesai. Sebuah transaksi dengan lockthat membaca bersama dengan transaksi lain tidak bisa
mempromosikan membaca yang lockto menulis kunci, karena yang terakhir akan bertentangan dengan kunci membaca diadakan bythe transaksi lainnya. Oleh karena itu, transaksi tersebut harus meminta kunci menulis dan menunggu untuk kunci membaca lainnya akan dirilis. Lockpromotion mengacu pada konversi lockto a kunci- kuat yaitu,lockthat lebih eksklusif. The lockcompatibilitytable pada Gambar 16.15 menunjukkan kunci exclusivityof relatif. membaca lockallows kunci membaca lainnya, sedangkan menulis lockdoes tidak. Baik memungkinkan kunci tulis lainnya. Oleh karena itu, menulis sebuah lockis lebih eksklusif dari kunci membaca. Kunci mungkin dipromosikan karena hasilnya adalah kunci lebih eksklusif. Saya ttidak aman untuk menurunkan sebuah lockheld bya transaksi sebelum melakukan, karena hasilnya akan lebih permisif dari yang sebelumnya dan mayallow eksekusi byother
transaksi yang tidak sesuai dengan kesetaraan serial.Aturan untuk penggunaan kunci dalam lockingimplementation dua-fase yang ketat diringkas dalam Gambar 16,16. Untuk memastikan bahwa aturan ini dipatuhi, klien tidak memiliki akses ke operasi untuk item lockingor unlocking data. Lockingis dilakukan ketika permintaan untuk writeoperations readand akan segera diterapkan pada dipulihkan benda, dan unlockingis dilakukan bythe abortoperations commitor transaksi koordinator.
Gambar 16,16 Penggunaan kunci di penguncian dua-fase yang ketat
Ketika operasi mengakses objek dalam transaksi: (A) Jika objek tidak alreadylocked, terkunci dan hasil operasi. (B) Jika objek memiliki transaksi byanother conflictinglockset, transaksi harus menunggu sampai dibuka.(C) Jika objek memiliki transaksi byanother non-conflictinglockset, yang lockisbersama dan hasil operasi.(D) Jika objek telah alreadybeen terkunci dalam transaksi yang sama, lockwill menjadi dipromosikan jika necessaryand hasil operasi. (Dimana promosi adalahdicegah bya conflictinglock, aturan b digunakan.)
Ketika transaksi berkomitmen atau dibatalkan, server membuka semua benda itu terkunci untuk transaksi.Sebagai contoh, CORBA ConcurrencyControl Service [OMG 2000b] dapatdigunakan untuk applyconcurrencycontrol atas nama transaksi atau untuk melindungi benda tanpa usingtransactions.
Ini menyediakan sarana pengumpulan associatinga kunci (disebut lockset) dengan sumber daya seperti benda dipulihkan. Sebuah lockset memungkinkan kunci untuk menjadi diperoleh atau dilepaskan. Metode kunci A lockset akan mengakuisisi lockor blockuntil kunci Bebas; metode lain memungkinkan kunci untuk dipromosikan atau dilepaskan. locksets transaksional mendukung metode yang sama seperti locksets, tetapi metode mereka membutuhkan pengenal transaksi
sebagai argumen. Kami disebutkan sebelumnya bahwa layanan transaksi CORBA tag semua klien permintaan dalam transaksi dengan pengenal transaksi. Hal ini memungkinkan lockto cocok diperoleh sebelum masing-masing objek dipulihkan diakses duringa transaksi. Itu Koordinator transaksi bertanggung jawab untuk kunci releasingthe ketika transaksi melakukan atau dibatalkan.Aturan yang diberikan pada Gambar 16,16 memastikan teliti, karena kunci diadakan sampai transaksi memiliki baik berkomitmen atau dibatalkan. Namun, hal ini tidak necessaryto terus membaca kunci untuk memastikan ketatnya. Baca kunci perlu onlybe diadakan sampai permintaan untuk melakukan atau batalkan tiba. Pelaksanaan kunci
The grantingof kunci akan dilaksanakan bya objek yang terpisah di server yang kita sebut manajer kunci. Lock manager memegang satu set kunci, untuk Misalnya dalam tabel hash. Setiap lockis sebuah instance dari Lockand kelas dikaitkan dengan objek tertentu. The Lockis kelas ditunjukkan pada Gambar 16,17. Setiap instance dari Lock mempertahankan followinginformation di variabel misalnya nya:
identifier dari objek terkunci;
pengenal transaksi transaksi yang currentlyhold kunci (shared
kunci dapat memiliki beberapa pemegang);
LockType a.
Lock kelas
public class Lock {
objek Object swasta; // Objek yang dilindungi oleh kunci
pemegang Vector swasta; // Yang TIDs dari pemegang saat ini
LockType LockType swasta; // Jenis saat
public void disinkronisasi memperoleh (TransID trans, LockType aLockType) {
sementara (/ * transaksi lain memegang lockin modus bertentangan * /) {
try {
Tunggu();
} Catch (InterruptedException e) {} /*...*/
}
jika (holders.isEmpty ()) {// tidak TIDs memegang kunci
holders.addElement (trans);
LockType = aLockType;
} Else if (/ * transaksi lain memegang kunci, berbagi * /)) {
jika (/ * transaksi ini bukan pemegang * /) holders.addElement (trans);
} Else if (/ * transaksi ini adalah pemegang tetapi membutuhkan kunci yang lebih eksklusif * /)
lockType.promote ();
}
}
public void disinkronisasi rilis (TransID trans) {
holders.removeElement (trans); // Hapus dudukan ini
// Set LockType none
notifyAll ();
}
}
Metode Lockare disinkronkan sehingga benang attemptingto memperoleh atau melepaskan lockwill tidak mengganggu satu sama lain. Tapi, di samping itu, upaya untuk memperoleh yang lockuse yang waitmethod setiap kali theyhave menunggu thread lain untuk melepaskannya.
Metode Theacquire melaksanakan aturan yang diberikan pada Gambar 16.15 dan Gambar 16.16. Its specifya argumen pengenal transaksi dan jenis lockrequired bythat transaksi. Ini tes apakah permintaan itu bisa diberikan. Jika transaksi lain memegang lockin modus yang bertentangan, itu memanggil menunggu, yang menyebabkan benang pemanggil menjadiditangguhkan sampai sesuai yang memberitahu. Perhatikan bahwa waitis tertutup sementara, karena semua pelayan akan diberitahu dan beberapa dari mereka maynot dapat melanjutkan. Ketika, akhirnya,
kondisi ini puas, sisa metode set kunci tepat:
jika tidak ada transaksi lain memegang kunci, tambahkan saja transaksi yang diberikan kepada pemegang dan menetapkan jenis;
lain jika transaksi lain memegang kunci, berbagi byaddingthe transaksi yang diberikan
kepada pemegang (kecuali itu adalah pemegang alreadya);
lain jika transaksi ini adalah pemegang tetapi kunci requestinga lebih eksklusif, mempromosikan
Gambar kelas 16,18 LockManager
public class LockManager {
theLocks Hashtable swasta;
public void (object Object, TransID trans, LockType LockType) setLock {
Mengunci foundLock;
disinkronkan (ini) {
// Menemukan kunci yang terkait dengan objek
// Jika tidak ada satu, menciptakan dan menambahkannya ke hashtable
}
foundLock.acquire (trans, LockType);
}
// Menyinkronkan satu ini karena kita ingin menghapus semua entri
public void disinkronisasi membuka (TransID trans) {
Pencacahan e = theLocks.elements ();
sementara (e.hasMoreElements ()) {
Lock aLock = (Lock) (e.nextElement ());
jika (/ * trans adalah pemegang kunci ini * /) aLock.release (trans);
}
}
}
argumen metode Therelease ini specifythe pengenal transaksi transaksi yang adalah kunci releasingthe. Ini akan menghapus pengenal transaksi dari dana pemegang, set kunci ketik untuk noneand panggilan notifyAll. Metode ini akan memberitahu semua waitingthreads dalam kasus ada beberapa transaksi waitingto mendapatkan kunci read - semua dari mereka mungkin dapat melanjutkan. The LockManageris kelas ditunjukkan pada Gambar 16.18.Semua permintaan untuk mengatur kunci dan melepaskan nama themon transaksi dikirim ke sebuah contoh dari LockManager:
argumen metode ThesetLock ini menentukan objek yang transaksi diberikan ingin lockand jenis kunci. Ia menemukan sebuah lockfor yang keberatan di hashtable atau, jika perlu, menciptakan satu. Ini kemudian memanggil metode memperoleh kunci itu.
argumen metode TheunLock ini menentukan transaksi yang kunci releasingits.Ia menemukan semua kunci dalam hashtable yang memiliki transaksi diberikan sebagai pemegang.
Untuk masing-masing, itu panggilan metode rilis.Beberapa pertanyaan kebijakan: Perhatikan bahwa ketika beberapa thread waiton barang terkunci sama, semantik waitensure bahwa setiap transaksi mendapat giliran. Dalam program di atas,
aturan konflik memungkinkan pemegang lockto sebuah berupa beberapa pembaca atau seorang penulis. Itu kedatangan permintaan untuk read lockis selalu diberikan kecuali pemegang memiliki kunci menulis.pembaca diundang untuk mempertimbangkan hal berikut:Apa konsekuensi untuk writetransactions di hadapan steadytrickle sebuah permintaan untuk membaca kunci? Thinkof implementasi alternatif.
Ketika pemegang memiliki kunci menulis, beberapa pembaca dan penulis mungkin menunggu. Itu pembaca harus mempertimbangkan efek dari notifyAlland thinkof alternative pelaksanaan. Jika pemegang membaca locktries untuk mempromosikan lockwhen kunci dibagi, itu akan diblokir. Apakah ada anysolution untuk kesulitan ini? Penguncian aturan untuk transaksi bersarang
The aimof sebuah lockingscheme untuk bersarang transaksi adalah cerita bersambung akses ke objek sehingga:
Setiap set transaksi bersarang adalah entitythat tunggal harus dicegah observingthe efek parsial anyother set transaksi bersarang.
Setiap transaksi dalam satu set transaksi bersarang harus dicegah observingthe efek parsial dari transaksi lainnya dalam set.
Aturan pertama diberlakukan byarrangingthat everylockthat diperoleh bya sukses subtransaction diwariskan oleh orang tua ketika itu selesai. kunci mewarisi juga mewarisi byancestors.
Perhatikan bahwa warisan formof ini melewati fromchild untuk orang tua! Transaksi top-level eventuallyinherits semua kunci yang diakuisisi oleh subtransactions sukses di anydepth dalam transaksi bersarang. Hal ini memastikan bahwa kunci dapat diadakan sampai transaksi tingkat atas telah dilakukan atau dibatalkan, yang mencegah anggota set berbeda transaksi bersarang observingone lain yang parsial efek.
Aturan kedua ditegakkan sebagai berikut:
transaksi Induk tidak diperbolehkan untuk menjalankan concurrentlywith anak mereka transaksi. Jika transaksi orangtua memiliki Lockon objek, itu retainsthe mengunci duringthe waktu itu transaksi anaknya mengeksekusi. Ini berarti bahwa anak transaksi temporarilyacquires induk lockfromits untuk durasi.
subtransactions pada tingkat yang sama diperbolehkan untuk menjalankan secara bersamaan, sehingga ketika mereka mengakses objek yang sama, lockingscheme harus cerita bersambung akses mereka.The followingrules menjelaskan lockacquisition dan rilis:
Untuk subtransaction untuk memperoleh read Lockon obyek, tidak ada transaksi aktif lainnya dapat memiliki write Lockon objek itu, dan onlyretainers menulis sebuah lockare nya leluhur.
Untuk subtransaction untuk memperoleh tulis Lockon objek, tidak lain aktiftransaksi dapat memiliki membaca atau menulis Lockon objek itu, dan onlyretainers dari membaca dan menulis kunci pada objek yang nenek moyangnya.
Ketika subtransaction sebuah melakukan, kunci yang diwarisi byits orangtua, allowingthe orang tua untuk mempertahankan kunci dalam modus yang sama seperti anak.
Ketika subtransaction sebuah dibatalkan, kunci yang dibuang. Jika alreadyretains orang tua kunci, dapat terus melakukannya.
Perhatikan bahwa subtransactions pada tingkat yang sama yang mengakses objek yang sama akan bergiliran memperoleh kunci dipertahankan bytheir orangtua. Hal ini memastikan bahwa akses mereka ke umum objek serial.
Sebagai contoh, misalkan subtransactions T1, T2and T11in Gambar 16.13 semua mengakses objek umum, yang tidak diakses bythe T. transaksi top-level Misalkan bahwa subtransaction T1is pertama untuk mengakses objek dan successfullyacqu
Ketika pemegang memiliki kunci menulis, beberapa pembaca dan penulis mungkin menunggu. Itu pembaca harus mempertimbangkan efek dari notifyAlland thinkof alternative pelaksanaan. Jika pemegang membaca locktries untuk mempromosikan lockwhen kuncidibagi, itu akan diblokir. Apakah ada anysolution untuk kesulitan ini?
Penguncian aturan untuk transaksi bersarang • The aimof sebuah lockingscheme untuk bersarang
transaksi adalah cerita bersambung akses ke objek sehingga:
Setiap set transaksi bersarang adalah entitythat tunggal harus dicegah
observingthe efek parsial anyother set transaksi bersarang.
Setiap transaksi dalam satu set transaksi bersarang harus dicegah
observingthe efek parsial dari transaksi lainnya dalam set.Aturan pertama diberlakukan byarrangingthat everylockthat diperoleh bya sukses subtransaction diwariskan oleh orang tua ketika itu selesai. kunci mewarisi juga mewarisi byancestors. Perhatikan bahwa warisan formof ini melewati fromchild untuk orang tua!
Transaksi top-level eventuallyinherits semua kunci yang diakuisisi oleh subtransactions sukses di anydepth dalam transaksi bersarang. Hal ini memastikan bahwa kunci dapat diadakan sampai transaksi tingkat atas telah dilakukan atau dibatalkan, yang
mencegah anggota set berbeda transaksi bersarang observingone lain yang parsial efek.
Aturan kedua ditegakkan sebagai berikut:
transaksi Induk tidak diperbolehkan untuk menjalankan concurrentlywith anak mereka transaksi. Jika transaksi orangtua memiliki Lockon objek, itu retainsthe mengunci duringthe waktu itu transaksi anaknya mengeksekusi. Ini berarti bahwa anak transaksi temporarilyacquires induk lockfromits untuk durasi.
subtransactions pada tingkat yang sama diperbolehkan untuk menjalankan secara bersamaan, sehingga ketika mereka mengakses objek yang sama, lockingscheme harus cerita bersambung akses mereka.The followingrules menjelaskan lockacquisition dan rilis:
Untuk subtransaction untuk memperoleh read Lockon obyek, tidak ada transaksi aktif lainnya dapat memiliki write Lockon objek itu, dan onlyretainers menulis sebuah lockare nya leluhur.
Untuk subtransaction untuk memperoleh tulis Lockon objek, tidak lain aktif transaksi dapat memiliki membaca atau menulis Lockon objek itu, dan onlyretainers darimembaca dan menulis kunci pada objek yang nenek moyangnya.
Ketika subtransaction sebuah melakukan, kunci yang diwarisi byits orangtua, allowingthe orang tua untuk mempertahankan kunci dalam modus yang sama seperti anak.
Ketika subtransaction sebuah dibatalkan, kunci yang dibuang. Jika alreadyretains orang tua kunci, dapat terus melakukannya.
Perhatikan bahwa subtransactions pada tingkat yang sama yang mengakses objek yang sama akan bergiliran memperoleh kunci dipertahankan bytheir orangtua. Hal ini memastikan bahwa akses mereka ke umum objek serial.
Sebagai contoh, misalkan subtransactions T1, T2and T11in Gambar 16.13 semua mengakses objek umum, yang tidak diakses bythe T. transaksi top-level Misalkan bahwa subtransaction T1is pertama untuk mengakses objek dan successfullyacquires kunci,
Gambar 16.19 Deadlock dengan menulis kunci
yang melewati ke T11for durasi pelaksanaannya, gettingit backwhen T11 melengkapi. Ketika T1completes pelaksanaannya, transaksi top-level Tinherits yang mengunci, yang mempertahankan sampai set transaksi bersarang melengkapi. subtransaction yang T2can memperoleh lockfrom tfor durasi pelaksanaannya.
6.4.1 Deadlock
Penggunaan kunci dapat menyebabkan kebuntuan. Mempertimbangkan penggunaan kunci yang ditunjukkan pada Gambar 16.19
Sejak depositand yang menarik metode adalah atom, kita menunjukkan themacquiringwrite kunci
- Meskipun dalam prakteknya theyread keseimbangan dan kemudian menulis. Setiap themacquires sebuah Lockon satu account dan kemudian akan diblokir ketika mencoba untuk mengakses akun bahwa satu lainnya telah terkunci. Ini adalah deadlocksituation - dua transaksi menunggu, dan masing-masing tergantung pada yang lain untuk merilis lockso itu dapat melanjutkan.
Deadlockis situasi particularlycommon ketika klien terlibat dalam program interaktif, untuk transaksi dalam maylast program interaktif untuk waktu yang lama periode waktu. Hal ini dapat mengakibatkan manyobjects beinglocked dan remainingso, sehingga klien preventingother usingthem.
Perhatikan bahwa subitems lockingof di obyek terstruktur dapat berguna untuk menghindari konflik dan mungkin deadlocksituations. Misalnya, Dayin sebuah diarycould a menjadi terstruktur sebagai satu set timeslots, yang masing-masing dapat dikunci independentlyfor memperbarui. lockingschemes hierarkis berguna jika aplikasi memerlukan rincian yang berbeda dari lockingfor operasi yang berbeda, lihat Bagian 16.4.2. Definisi kebuntuan • Deadlockis keadaan di mana setiap anggota kelompok transaksi adalah waitingfor beberapa anggota lain untuk melepaskan kunci. Menunggu-untuk graphcan digunakan untuk mewakili aitingrelationships antara transaksi saat ini. Dalam menunggu-untuk grafik node mewakili transaksi dan ujung-ujungnya mewakili menunggu-untuk hubungan antara transaksi - ada node tepi fromnode Tto Uwhen transaksi Tis waiting for transaksi untuk melepaskan kunci. Gambar 16.20 menggambarkan grafik menunggu-untuk correspondingto yang deadlocksituation diilustrasikan pada Gambar 16.19. Ingat bahwa deadlockarose karena transaksi Tand Uboth berusaha untuk memperoleh suatu objek yang diselenggarakan oleh yang lain. Oleh karena itu Twaits untuk Uand Uwaits untuk T. dependencybetween The
Gambar 16.20 Grafik menunggu untuk untuk Gambar 16.19
Gambar 16.21
Sebuah siklus dalam grafik menunggu-untuk transaksi tidak langsung, melalui objek dependencyon. The diagramon kanan menunjukkan benda diadakan byand menunggu bytransactions Tand U. Seperti setiap transaksi bisa menunggu untuk objek onlyone, obyek dapat dihilangkan dari dana menunggu-untuk grafik - leavingthe sederhanagrafik di sebelah kiri.
Misalkan, seperti pada Gambar 16.21, Grafik menunggu-untuk mengandung siklus Untuk? U? O? ...o? Vo? T. Setiap transaksi waitingfor yang nexttransaction dalam siklus. Semua ini transaksi diblokir waitingfor kunci. Tak satu pun dari kunci dapat pernah dirilis, dan transaksi menemui jalan buntu. Jika salah satu dari transaksi dalam siklus dibatalkan, maka kunci dilepaskan dan siklus yang rusak. Misalnya, jika transaksi Tin Gambar 16.21 adalah dibatalkan, itu akan merilis alockon sebuah benda yang Vis waitingfor - dan Vwill tidak lagi menjadi waitingfor T.
Sekarang perhatikan skenario di mana tiga transaksi T, Uand Vshare membaca Lockon obyek C, dan transaksi Wholds menulis Lockon objek B, di mana transaksi Vis waitingto mendapatkan kunci (seperti yang ditunjukkan di sebelah kanan pada Gambar 16,22). Itu transaksi Tand Wthen permintaan menulis kunci pada objek C, dan deadlocksituation timbul di mana Twaits untuk Uand V, Vwaits untuk W, dan Wwaits untuk T, Uand V, seperti yang ditunjukkan pada kiri pada Gambar 16,22. Hal ini menunjukkan bahwa meskipun setiap transaksi dapat menunggu onlyone objek pada suatu waktu, itu mungkin terlibat dalam beberapa siklus. Misalnya, transaksi terlibat dalam dua siklus: Vo W o Untuk Vand Vo W o V.??????
Dalam contoh ini, kira thattransaction Vis dibatalkan. Ini akan melepaskan kunci VonCand dua siklus yang melibatkan Vwill menjadi rusak.Pencegahan Deadlock • Salah satu solusinya adalah untuk mencegah kebuntuan. Sebuah apparentlysimple tapi tidak sangat wayto baik mengatasi deadlockproblemis untuk lockall dari benda yang digunakan transaksi ketika mulai. Ini perlu dilakukan sebagai langkah atom tunggal sehingga untuk menghindari deadlockat tahap ini. transaksi tersebut tidak dapat mengalami kebuntuan dengan lainnya transaksi, tetapi akses pendekatan ini unnecessarilyrestricts ke sumber daya bersama. Di Selain itu, kadang-kadang tidak mungkin untuk memprediksi pada awal transaksi yang objek akan digunakan. Ini generallythe kasus dalam aplikasi interaktif, bagi pengguna akan harus bilang benda exactlywhich muka theywere planningto penggunaan - ini adalah terbayangkan dalam aplikasi penjelajahan bergaya, yang memungkinkan pengguna untuk menemukan benda theydo tidak tahu tentang sebelumnya. Deadlock juga dapat dicegah byrequestinglocks di objek dalam urutan yang telah ditetapkan, tetapi hal ini dapat mengakibatkan dini lockingand pengurangan concurrency.
Figure 16.22 Another wait-for graph
Upgrade kunci • CORBA ConcurrencyControl Layanan memperkenalkan jenis ketiga mengunci, yang disebut peningkatan, penggunaan yang dimaksudkan untuk menghindari deadlock. kebuntuan yang sering disebabkan bytwo conflictingtransactions pertama takingread kunci dan kemudian mencoba untuk mempromosikan themto menulis kunci. Sebuah transaksi dengan upgrade Lockon sebuah itemis Data diizinkan untuk membaca item data, tapi ini lockconflicts dengan anyupgrade kunci yang ditetapkan oleh transaksi lain pada item data yang sama. Jenis lockcannot diatur implicitlyby penggunaan readoperation, tapi harus diminta bythe klien. Deteksi Deadlock • Deadlock mungkin terdeteksi byfindingcycles dalam untuk menunggu grafik. Havingdetected kebuntuan, transaksi harus dipilih untuk aborsi untuk istirahat siklus. Perangkat lunak ini bertanggung jawab untuk deadlockdetection dapat menjadi bagian dari manajer kunci. Ini harus memegang representasi dari grafik menunggu-untuk sehingga dapat Checkit untuk siklus dari waktu demi waktu. Tepi ditambahkan ke grafik dan dihapus dari dana grafik bythe kunci unLockoperations setLockand manajer. Pada titik diilustrasikan byFigure 16,22 pada kiri, itu akan memiliki followinginformation yang:
Keunggulan Untuk? U? Isadded setiap kali blok manajer kunci permintaan oleh transaksi untuk kunci pada objek yang sudah terkunci atas nama transaksi U. Perhatikan bahwa ketika
Gambar 16.23 Resolusi kebuntuan pada Gambar 16.1
lockis shared, beberapa tepi mungkin ditambahkan. Tepi Untuk U dihapus setiap kali U rilis sebuah lockthat Tis waitingfor dan memungkinkan Tto melanjutkan. Lihat Latihan 16,14 untuk diskusi tentang pelaksanaan deadlockdetection lebih rinci. Jika transaksi berbagi kunci, yang lockisnot dirilis, tapi ujung-ujungnya leadingto transaksi tertentu dihapus.
Kehadiran siklus mungkin diperiksa setiap kali tepi ditambahkan, atau kurang frequentlyto menghindari unnecessaryoverhead. Ketika deadlockis sebuah terdeteksi, salah satu transaksi dalam siklus harus dipilih dan kemudian dibatalkan. correspondingnode yang dan ujung- ujungnya involvingit harus dikeluarkan dari dana menunggu-untuk grafik. Ini akan terjadipada saat transaksi dibatalkan memiliki kunci yang dihapus.
Pilihan transaksi untuk membatalkan tidak sederhana. Beberapa faktor yang mungkin diperhitungkan adalah usia transaksi dan jumlah siklus di mana ia terlibat.
Timeout • Locktimeouts adalah metode untuk resolusi kebuntuan yang umum bekas. Setiap lockis diberikan jangka waktu terbatas di mana ia kebal. Setelah waktu ini, lockbecomes rentan. Asalkan tidak ada transaksi lain adalah competingfor objek yang terkunci, sebuah objek dengan lockremains rentan terkunci. Namun, jika anyother transaksi waitingto akses dilindungi objek bya kunci rentan, yang lockis rusak (yaitu, objek tersebut unlocked) dan waitingtransaction resume.
Itu transaksi yang lockhas telah rusak adalah normallyaborted.Ada manyproblems dengan penggunaan timeout sebagai deadlock remedyfor: the problemis terburuk yang transaksi terkadang dibatalkan karena kunci mereka menjadi rentan saat transaksi lainnya waitingfor mereka, tapi ada actuallyno jalan buntu. Dalam sistem kelebihan beban, jumlah transaksi timingout akan meningkat,dan transaksi takinga lama dapat dikenakan sanksi. Selain itu, sulit untuk memutuskan panjang yang sesuai untuk timeout. Sebaliknya, jika deadlockdetection digunakan,
Gambar 16,24 Lock kompatibilitas (membaca, menulis dan komit kunci)
transaksi dibatalkan karena kebuntuan terjadi dan pilihan dapat dibuat sebagai yang transaksi untuk membatalkan.Usinglocktimeouts, kita dapat menyelesaikan deadlockin Gambar 16.19 seperti yang ditunjukkan pada Gambar 16.23, di mana menulis lockfor TonAbecomes rentan setelah batas waktu yang periode. Transaksi Uis menunggu untuk memperoleh tulis Lockon A. Oleh karena itu, Tis dibatalkan dan ia melepaskan Lockon A, yang memungkinkan Uto melanjutkan dan menyelesaikan transaksi.
Ketika akses transaksi objek yang terletak di beberapa server yang berbeda, possibilityof kebuntuan didistribusikan muncul. Dalam kebuntuan didistribusikan, grafik menunggu-untuk dapat melibatkan benda-benda di beberapa lokasi. Kami kembali ke topik ini dalam Bagian 17.5. 16.4.2 Meningkatkan concurrency dalam penguncian skema Bahkan ketika lockingrules didasarkan pada konflik antara writeoperations readand dan granularityat yang theyare digunakan adalah sekecil mungkin, masih ada beberapa ruang untuk increasingconcurrency. Kami membahas dua pendekatan yang telah digunakan untuk menangani masalah ini. Dalam pendekatan pertama (penguncian dua versi), yang settingof eksklusif kunci ditunda sampai transaksi berkomitmen. Dalam pendekatan kedua (kunci hirarkis),campuran-granularitylocks digunakan.
penguncian dua versi
Ini adalah skema optimis yang memungkinkan satu transaksi untuk menulis versi tentatif benda sementara transaksi lainnya baca dari dana versi berkomitmen dari objek yang sama.readoperations onlywait jika transaksi lain saat ini committingthe objek yang sama. Skema ini memungkinkan lebih concurrencythan baca-tulis kunci, tapi writingtransactions riskwaitingor bahkan penolakan ketika theyattempt untuk melakukan. Transaksi tidak dapat melakukan writeoperations mereka immediatelyif lainnya transaksi belum selesai telah membaca objek yang sama. Oleh karena itu, transaksi yang permintaan untuk melakukan dalam situasi seperti ini dibuat untuk menunggu sampai readingtransactions memiliki lengkap. Kebuntuan mayoccur ketika transaksi yang waitingto komit. Karena itu,
transaksi mayneed akan dibatalkan ketika theyare waitingto berkomitmen, untuk menyelesaikan kebuntuan.Variasi ini pada jenis dua-fase lockingusesthree ketat kunci: kunci membaca, sebuah menulis lockand komit kunci. Sebelum readoperation transaksi ini dilakukan, read mengunci harus diatur pada objek - upaya untuk mengatur read lockis sukses kecuali objek memiliki kunci komit, dalam hal transaksi menunggu. Sebelum transaksi in
Gambar 16,24 kompatibilitas Lock (membaca, menulis dan melakukan kunci
transaksi dibatalkan karena kebuntuan terjadi dan pilihan dapat dibuat sebagai yang transaksi untuk membatalkan.Usinglocktimeouts, kita dapat menyelesaikan deadlockin Gambar 16.19 seperti yang ditunjukkan pada
Gambar 16.23, di mana menulis lockfor TonAbecomes rentan setelah batas waktu yang periode. Transaksi Uis menunggu untuk memperoleh tulis Lockon A. Oleh karena itu, Tis dibatalkan dan ia melepaskan Lockon A, yang memungkinkan Uto melanjutkan dan menyelesaikan transaksi. Ketika akses transaksi objek yang terletak di beberapa server yang berbeda, possibilityof kebuntuan didistribusikan muncul. Dalam kebuntuan didistribusikan, grafik menunggu-untuk dapat melibatkan benda-benda di beberapa lokasi. Kami kembali ke topik ini dalam Bagian 17.5. 16.4.2 Meningkatkan concurrency dalam penguncian skema Bahkan ketika lockingrules didasarkan pada konflik antara writeoperations readand dan granularityat yang theyare digunakan adalah sekecil mungkin, masih ada beberapa ruang untuk increasingconcurrency. Kami membahas dua pendekatan yang telah digunakan untuk menangani masalah ini. Dalam pendekatan pertama (penguncian dua versi), yang settingof eksklusif kunci ditunda sampai transaksi berkomitmen. Dalam pendekatan kedua (kunci hirarkis),campuran-granularitylocks digunakan.
penguncian dua versi
Ini adalah skema optimis yang memungkinkan satu transaksi untuk menulis versi tentatif benda sementara transaksi lainnya baca dari dana versi berkomitmen dari objek yang sama. readoperations onlywait jika transaksi lain saat ini committingthe objek yang sama. Skema ini memungkinkan lebih concurrencythan baca-tulis
kunci, tapi writingtransactions riskwaitingor bahkan penolakan ketika theyattempt untuk melakukan. Transaksi tidak dapat melakukan writeoperations mereka immediatelyif lainnya transaksi belum selesai telah membaca objek yang sama. Oleh karena itu, transaksi yang permintaan untuk melakukan dalam situasi seperti ini dibuat untuk menunggu sampai readingtransactions memiliki lengkap. Kebuntuan mayoccur ketika transaksi yang waitingto komit. Karena itu, transaksi mayneed akan dibatalkan ketika theyare waitingto berkomitmen, untuk menyelesaikan kebuntuan.
Variasi ini pada jenis dua-fase lockingusesthree ketat kunci: kunci membaca, sebuah menulis lockand komit kunci. Sebelum readoperation transaksi ini dilakukan, read mengunci harus diatur pada objek - upaya untuk mengatur read lockis sukses kecuali objek memiliki kunci komit, dalam hal transaksi menunggu. Sebelum transaksi ini
Gambar 16.25 Lock hirarki untuk contoh perbankan
writeoperation dilakukan, kunci menulis harus diatur pada objek - upaya untuk mengatur write a lockis sukses kecuali objek memiliki write lockor komit kunci, di mana huruf yang menunggu transaksi. Ketika koordinator transaksi menerima permintaan untuk melakukan transaksi, itu mencoba untuk mengkonversi semua menulis kunci bahwa transaksi untuk melakukan kunci. Jika anyof yang objek memiliki kunci outstandingread, transaksi harus menunggu sampai transaksi yang set kunci ini telah selesai dan kunci dilepaskan. The compatibilityof membaca, menulis dan komit kunci ditunjukkan pada Gambar 16.24. Ada dua perbedaan utama dalam kinerja antara penguncian dua versi skema dan ordinaryread-write lockingscheme. Di satu sisi, readoperations di dua-versi lockingscheme ditunda onlywhile transaksi menjadi berkomitmen, bukan duringthe seluruh pelaksanaan transaksi - dalam kebanyakan kasus, commit protocol mengambil onlya sebagian kecil dari waktu yang dibutuhkan untuk performan seluruh transaksi. Di sisi lain, readoperations dari satu transaksi dapat menyebabkan keterlambatan dalam transaksi committingother.
kunci hierarkis • Dalam beberapa aplikasi, yang granularitysuitable untuk satu operasi tidak sesuai untuk operasi lagi. Dalam bankingexample kami, majorityof yang operasi membutuhkan lockingat granularityof yang akun. branchTotaloperation yang berbeda - membaca nilai-nilai semua saldo rekening dan akan muncul untuk meminta membaca Lockon semua dari mereka. Untuk mengurangi lockingoverhead, itu akan berguna untuk memungkinkan kunci dari campuran granularityto hidup berdampingan.
Gray [1978] mengusulkan penggunaan hierarchyof kunci dengan granularities yang berbeda. Pada setiap tingkat, settingof orangtua lockhas efek yang sama assettingall setara anak kunci. Ini irit pada jumlah kunci yang akan ditetapkan. Dalam bankingexample kami, cabang adalah orang tua dan akun tersebut adalah anak-anak (lihat Gambar 16,25).Mixed-granularitylocks dapat berguna dalam diarysystemin sebuah mana data bisa bestructured dengan diaryfor sebuah weekbeingcomposed halaman untuk setiap dayand yang
Gambar 16.26 Lock hirarki untuk buku harian
Gambar 16.27 Lock meja kompatibilitas untuk kunci hirarki
yang terakhir dibagi lebih lanjut ke slot untuk setiap jam dari hari, seperti yang ditunjukkan pada Gambar 16.26.operasi untuk melihat weekwould menyebabkan readlockto diatur di bagian atas inihirarki, sedangkan operasi untuk memasukkan janji akan menyebabkan write a lockto menjadi set pada slot waktu tertentu. Pengaruh membaca Lockon weekwould sebuah adalah untuk mencegah write operasi pada anyof yang substruktur - misalnya, slot waktu untuk setiap Dayin yang minggu.
Dalam skema Gray, setiap node di hierarchycan yang dikunci, givingthe pemilik akses lockexplicit ke node dan akses givingimplicit kepada anak-anak. dalam kami Misalnya, pada Gambar 16,25 baca-tulis Lockon cabang implicitlyread-write kunci semua rekening. Sebelum node anak diberikan kunci baca-tulis, niat untuk baca-tulis lockis set pada node parent dan nenek moyangnya (jika ada). niat lockis kompatibel dengan kunci niat lain tetapi konflik dengan membaca dan menulis kunci accordingto biasa
aturan. Gambar 16,27 memberikan compatibilitytable untuk kunci hirarkis. Grayalso diusulkan jenis ketiga niat satu kunci- yang menggabungkan sifat-sifat read lockwith sebuahniat untuk menulis kunci.
Dalam bankingexample kami, branchTotaloperation meminta membaca Lockon yang cabang, yang implicitlysets kunci membaca pada semua account. Sebuah kebutuhan depositoperation untuk menetapkan tulis Lockon keseimbangan, tapi pertama ia mencoba untuk mengatur niat untuk menulis Lockon cabang. Aturan-aturan ini mencegah operasi ini runningconcurrently. kunci hierarkis memiliki keuntungan dari reducingthe jumlah kunci ketika multiguna granularitylockingis diperlukan. The compatibilitytables dan aturan untuk mempromosikan kunci yang lebih kompleks.
Kunci granularityof campuran bisa alloweach transaksi untuk sebagian locka Ukuran yang dipilih accordingto kebutuhannya. Sebuah longtransaction yang mengakses banyak benda bisa lockthe seluruh koleksi, sedangkan transaksi singkat dapat lockat halus granularity.
CORBA ConcurrencyControl Layanan mendukung variabel-granularitylocking dengan maksud untuk membaca dan niat untuk menulis locktypes. Ini dapat digunakan seperti yang dijelaskan di atas untuk mengambil keuntungan yang applylocks opportunityto di berbeda granularities di Data hierarchicallystructured.
kontrol konkurensi Optimis
Kungand Robinson [1981] mengidentifikasi sejumlah kelemahan yang melekat pada lockingand mengusulkan sebuah pendekatan optimis alternatif untuk serialisasi transaksi yang menghindari kelemahan ini. Kita dapat meringkas kelemahan dari penguncian:
Kunci pemeliharaan merupakan biaya overhead yang tidak hadir dalam sistem yang tidak mendukung akses bersamaan ke data bersama. Bahkan membaca-onlytransactions (query), yang tidak dapat possiblyaffect yang integrityof data, harus, secara umum, penggunaan penguncian untuk menjamin bahwa beingread data tidak diubah byother transaksi pada waktu bersamaan. Tapi mengunci mungkin necessaryonlyin kasus terburuk.
Sebagai contoh, pertimbangkan dua proses client yang concurrentlyincrementingthe nilai-nilai nobjects. Jika program klien mulai pada waktu yang sama dan berjalan selama sekitar jumlah yang sama dari waktu, accessingthe objek di dua urutan yang tidak terkait dan usinga transaksi terpisah untuk mengakses dan kenaikan setiap item, kemungkinan bahwa dua program akan mencoba untuk mengakses objek yang sama pada saat yang sama hanya1 di non rata, sehingga lockingis onlyonce reallyneeded di setiap ntransactions.
Penggunaan kunci dapat mengakibatkan kebuntuan. Deadlockprevention mengurangi concurrency parah, dan karena itu deadlocksituations harus diselesaikan baik menggunakan bythe dari timeout atau bydeadlockdetection. Baik ini adalah penggunaan whollysatisfactoryfor dalam program interaktif.
Untuk menghindari cascadingaborts, kunci tidak bisa dilepaskan sampai akhir transaksi. Potensi ini mayreduce significantlythe untuk concurrency.
Pendekatan alternatif yang diusulkan oleh Kungand Robinson adalah 'optimistic'because itu berdasarkan pengamatan bahwa, dalam sebagian besar aplikasi, kemungkinan dua klien ' transaksi accessingthe objek yang sama rendah. Transaksi diperbolehkan untuk melanjutkan sebagai meskipun tidak ada konflik possibilityof dengan transaksi lainnya sampai klien
melengkapi taskand yang mengeluarkan closeTransactionrequest a. Ketika konflik muncul, beberapa transaksi generallyaborted dan perlu restart bythe klien. Setiap transaksi memiliki followingphases:Tahap bekerja: workingphase duringthe, setiap transaksi memiliki versi tentative dari masing-masing objek yang update. Ini adalah copyof paling recentlycommitted versi dari objek. Penggunaan versi tentatif memungkinkan transaksi untuk membatalkan (Dengan tidak berpengaruh pada objek), baik duringthe workingphase atau jika gagal validasi karena conflictingtransactions lainnya. readoperations dilakukan immediately- jika versi tentatif untuk itu alreadyexists transaksi, readoperation sebuah mengakses itu;
jika tidak, ia mengakses nilai yang paling recentlycommitted objek. Menulis operasi merekam nilai-nilai baru dari objek sebagai nilai-nilai tentatif (yang terlihat transaksi lainnya). Ketika ada beberapa transaksi konkuren,beberapa nilai tentatif yang berbeda dari objek maycoexist yang sama. Selain itu, dua catatan disimpan dari objek diakses dalam transaksi: a setcontainingthe membaca benda membaca bythe transaksi dan menulis set containingthe benda ditulis bythe transaksi. Perhatikan bahwa karena semua readoperations dilakukan pada versi berkomitmen objek (atau salinan dari mereka), dirtyreads tidak dapat terjadi.
tahap validasi: Ketika permintaan Transaksi dekat diterima, transaksi divalidasi untuk menentukan apakah atau tidak beroperasi pada objek konflik dengan operasi transaksi lain pada objek yang sama. Jika validasi berhasil, maka transaksi bisa melakukan. Jika validasi gagal, maka beberapa formof resolusi konflik harus digunakan dan baik transaksi saat ini atau, dalam beberapa kasus, orang-orang dengan yang konflik perlu dibatalkan.Memperbarui fase: Jika transaksi divalidasi, semua perubahan dicatat dalam tentative Versi yang dibuat permanen. Baca-onlytransactions bisa melakukan immediatelyafter passingvalidation. transaksi tulis yang readyto komit sekali versi tentatifdari objek telah disimpan di penyimpanan permanen.
Validasi transaksi • validasi menggunakan aturan read-write konflik untuk memastikan bahwa schedulingof yang transaksi tertentu seriallyequivalent sehubungan dengan semua lainnya transaksi tumpang tindih - yaitu, anytransactions yang belum dilakukan pada saat itu transaksi ini dimulai. Untuk membantu performingvalidation, setiap transaksi ditugaskan sejumlah transaksi ketika memasuki fase validasi (yaitu, ketika masalah klien acloseTransaction). Jika transaksi divalidasi dan selesai dengan sukses, ia tetap nomor ini; jika gagal cek validasi dan dibatalkan, atau jika transaksi membaca hanya, jumlah ini dirilis untuk penugasan. nomor transaksi adalah bilangan bulat ditugaskan di ascendingsequence; jumlah transaksi karena mendefinisikan nya
posisi dalam waktu - transaksi selalu selesai workingphase setelah semua transaksi dengan angka yang lebih rendah. Artinya, transaksi dengan jumlah Tialways mendahului transaksi dengan jumlah Tj jika i <j. (Jika jumlah transaksi yang ditugaskan di yang beginningof workingphase, maka transaksi yang mencapai akhir workingphase sebelum satu dengan angka yang lebih rendah akan harus menunggu sampai satu sebelumnya telah menyelesaikan sebelum dapat divalidasi.)
Uji validasi transaksi TVis berdasarkan konflik antara operasi di pasang transaksi Ti dan Tv. Untuk transaksi Tvto menjadi serializable berkenaan dengan suatu overlappingtransaction Ti
, Operasi mereka harus conformto yang followingrules:
Sebagai validasi dan pemutakhiran fase transaksi umumnya pendek durasinya dibandingkan dengan workingphase itu, penyederhanaan dapat dicapai dengan aturan makingthe bahwa transaksi onlyone mungkin di fase andupdate validasi pada satu waktu. Kapan ada dua transaksi mayoverlap dalam tahap pembaruan, aturan 3 puas. Catatan bahwa ini pembatasan Operasi tulis, bersama-sama dengan fakta bahwa tidak ada dirtyreads dapat terjadi, menghasilkan eksekusi yang ketat. Untuk mencegah tumpang tindih, seluruh validasi dan pemutakhiran fase dapat diimplementasikan sebagai bagian kritis sehingga klien onlyone pada suatu waktu dapat jalankan. Dalam rangka meningkatkan konkurensi, bagian dari validasi dan memperbarui mungkin
Validasi transaksi
dilaksanakan di luar bagian kritis, tetapi penting bahwa penugasan nomor transaksi dilakukan secara berurutan. Kami mencatat bahwa di anyinstant, saat ini jumlah transaksi seperti pseudo-clockthat kutu setiap kali transaksi selesai berhasil.
Validasi transaksi harus memastikan bahwa aturan 1 dan 2 dipatuhi bytestinguntuk tumpang tindih antara benda pasang transaksi Tvand Ti. Ada dua bentukvalidasi - belakang dan ke depan [sulit 1.984]. validasi mundur memeriksa undergoingvalidation transaksi dengan sebelumnya transaksi tumpang tindih lainnya – mereka yang memasuki tahap validasi sebelum. validasi maju memeriksa transaksi undergoingvalidation dengan transaksi kemudian lain, yang masih aktif.
validasi mundur • Karena semua readoperations dari overlappingtransactions sebelumnya dilakukan sebelum validasi Tvstarted, theycannot terpengaruh bythe menulis transaksi saat ini (dan memerintah 1 puas). Validasi transaksi Tvchecks apakah membaca yang ditetapkan (benda dipengaruhi bythe operasi baca dari Tv) tumpang tindih dengan dari menulis set overlappingtransactions sebelumnya, Ti (aturan 2). Jika ada anyoverlap, validasi gagal.
LetstartTnbe jumlah transaksi terbesar ditugaskan (untuk beberapa komitmen lainnya transaksi) pada saat transaksi Tvstarted workingphase dan finishTnbe yang jumlah transaksi terbesar ditetapkan pada saat Tventered tahap validasi.
The followingprogramdescribes yang algorithmfor validasi Tv: boolean valid = true;
untuk (int Ti = startTn + 1; Ti <= FinishTn; Ti ++) {
jika (baca set Tvintersects menulis set Ti
) Valid = false;
}
Gambar 16,28
menunjukkan overlappingtransactions yang mungkin consideredin validasi dari transaksi Tv. Waktu meningkatkan fromleft ke kanan. Transaksi berkomitmen sebelumnya areT1, T2and T3. T1committed sebelum Tvstarted. T2and T3committed sebelum Tv selesai workingphase nya. StartTn + 1 = T2and finishTn = T3. Dalam validasi mundur, membaca set Tv harus dibandingkan dengan menulis set T2and T3.
Dalam validasi mundur, membaca mengatur transaksi beingvalidated dibandingkan dengan menulis set transaksi lain yang telah alreadycommitted. Oleh karena itu, satu-satunya anyconflicts tekad wayto adalah untuk membatalkan transaksi yang undergoingvalidation. Dalam validasi mundur, transaksi yang tidak memiliki readoperations (hanya menulis operasi) tidak perlu diperiksa.
concurrencycontrol optimis dengan validasi mundur mengharuskan menulis set versi berkomitmen lama benda correspondingto recentlycommitted transaksi dipertahankan sampai tidak ada overlappingtransactions unvalidated dengan yang mereka mungkin bertentangan. Setiap kali transaksi yang successfullyvalidated, yang nomor transaksi, startTnand menulis set dicatat dalam daftar precedingtransactions yang dipertahankan bythe layanan transaksi. Catatan daftar thatthis diperintahkan bytransaction jumlah. Di lingkungan dengan longtransactions, retensi lama menulis set objek mungkin masalah. Misalnya, pada Gambar 16,28 menulis set T1, T2, T3and Tv harus dipertahankan sampai transaksi aktif active1completes. Perhatikan bahwa meskipun transaksi aktif memiliki pengenal transaksi, theydo belum memiliki transaksi angka.
validasi maju • Dalam validasi maju dari Tv transaksi, menulis set TVis dibandingkan dengan membaca set semua transaksi overlappingactive - mereka yang masih di workingphase mereka (aturan 1). Aturan 2 adalah automaticallyfulfilled karena aktif transaksi tidak menulis sampai setelah Tvhas selesai. Biarkan transaksi aktif memiliki pengidentifikasi (berturut-turut) transaksi active1to activeN.The followingprogramdescribes yang algorithmfor validasi maju dari Tv:
boolean valid = true;
untuk (int Tid
= Active1; Tid
<= ActiveN; Tid ++) {
jika (write set Tvintersects membaca set Tid
) Valid = false;
}
Pada Gambar 16.28, menulis set Tv transaksi harus dibandingkan dengan membaca set transaksi dengan pengidentifikasi active1and active2. (validasi Teruskan harus memungkinkan untuk fakta bahwa membaca set transaksi aktif maychange duringvalidation dan menulis.) Sebagai membaca set transaksi beingvalidated tidak termasuk dalam cek, baca-onlytransactions selalu lulus pemeriksaan validasi. Sebagai transaksi yang dibandingkan dengan validatingtransaction yang masih aktif, kita memiliki pilihan apakah akan membatalkan validatingtransaction atau untuk mengejar beberapa alternatif resolvingthe wayof konflik. Sulit [1984] menunjukkan beberapa strategi alternatif:
Tunda validasi hingga nanti ketika conflictingtransactions memiliki jadi. Namun, tidak ada jaminan bahwa transaksi beingvalidated akan tarif anybetter di masa depan. Selalu ada kesempatan yang lebih lanjut bertentangan Transaksi aktif maystart sebelum validasi tercapai.
Abort semua transaksi conflictingactive dan melakukan transaksi yang divalidasi.
Abort transaksi beingvalidated. Ini adalah strategybut sederhana memiliki Kerugian yang conflictingtransactions masa depan mungkin goingto batalkan, di mana kasus transaksi di bawah validasi telah dibatalkan tidak perlu.
Perbandingan maju dan validasi mundur • Kami memiliki alreadyseen maju yang validasi memungkinkan flexibilityin resolusi konflik, sedangkan validasi mundur memungkinkan pilihan onlyone - untuk membatalkan transaksi beingvalidated. Secara umum, membaca set transaksi yang jauh lebih besar daripada menulis set. Oleh karena itu, validasi mundur membandingkan membaca possiblylarge mengatur terhadap tua tulis set, sedangkan maju validasi memeriksa satu set write kecil terhadap membaca set transaksi aktif. Kami melihat bahwa validasi mundur memiliki overhead storingold tulis set sampai theyare tidak lagi dibutuhkan. Di sisi lain, ke depan validasi memiliki untuk memungkinkan transaksi baru awal Proses validasi duringthe.
Kelaparan • Ketika transaksi dibatalkan, maka akan normallybe restart bythe klien program. Namun dalam skema yang Relyon restartingtransactions abortingand, tidak ada menjamin bahwa transaksi tertentu akan pernah lulus pemeriksaan validasi, untuk itu mungkin datang ke dalam konflik dengan transaksi lain untuk penggunaan benda setiap kali restart.
Pencegahan transaksi yang pernah beingable untuk melakukan disebut kelaparan.Kemunculan kelaparan yang likelyto menjadi langka, tapi server yang menggunakan optimis concurrencycontrol harus memastikan bahwa klien tidak telah transaksinya dibatalkan berkali-kali. Kungand Robinson menyarankan bahwa ini bisa dilakukan jika server mendeteksi transaksi yang telah dibatalkan beberapa kali. Theysuggest bahwa ketika server mendeteksi transaksi tersebut harus diberikan akses eksklusif bythe penggunaan kritis Bagian dilindungi bya semaphore.
16,6 Timestamp memesan
In concurrencycontrol schemes based on timestamp ordering, each operation in a
transaction is validated when it is carried out. If the operation cannot be validated, the
transaction is aborted immediatelyand can then be restarted bythe client. Each
transaction is assigned a unique timestamp value when it starts. The timestamp defines
its position in the time sequence of transactions. Requests fromtransactions can be
totallyordered accordingto their timestamps. The basic timestamp orderingrule is
based on operation conflicts and is verysimple:
A transaction’s request to write an object is valid onlyif that object was last read and
written byearlier transactions. A transaction’s request to read an object is valid only
if that object was last written byan earlier transaction.
This rule assumes that there is onlyone version of each object and restricts access to one
transaction at a time. If each transaction has its own tentative version of each object it
accesses, then multiple concurrent transactions can access the same object. The
timestamp orderingrule is refined to ensure that each transaction accesses a consistent
set of versions of the objects. It must also ensure that the tentative versions of each object
are committed in the order determined bythe timestamps of the transactions that made
them. This is achieved bytransactions waiting, when necessary, for earlier transactions
to complete their writes. The writeoperations maybe performed after the
closeTransactionoperation has returned, without makingthe client wait. But the client
must wait when readoperations need to wait for earlier transactions to finish. This
Gambar 16,29 konflik Operasi untuk cap waktu pemesana
Memerintah Tc Ti
tulis baca Tc tidak boleh objek writean yang telah readbyany Ti
di mana Ti
> Tc.
Ini mengharuskan Tc ?? timestamp maximumread objek.
tulis menulis Tc tidak harus writean objek yang telah ditulis oleh Ti
di mana Ti> Tc.
Ini mengharuskan Tc> menulis timestamp dari objek berkomitmen.
membaca menulis Tc harus objek tidak readan yang telah ditulis oleh Ti
di mana Ti
> Tc.
Ini mengharuskan Tc> menulis timestamp dari objek berkomitmen.
tidak dapat menyebabkan kebuntuan, karena transaksi onlywait untuk yang sebelumnya (dan tidak ada siklus bisa
terjadi pada grafik menunggu-untuk).
Cap waktu mungkin ditugaskan dari dana clockor server, seperti pada bagian sebelumnya,
a 'pseudo-time' mungkin berdasarkan counter yang bertambah setiap kali timestamp
nilai dikeluarkan. Kami menunda sampai Bab 17 yang generatingtimestamps problemof saat
layanan transaksi didistribusikan dan beberapa server yang terlibat dalam transaksi.
Kita sekarang akan menjelaskan concurrencycontrol berbasis timestamp formof berikut
metode yang diterapkan dalam SDD-1 sistem [Bernstein et al. 1980] dan dijelaskan byCeri
dan Pelagatti [1985].
Seperti biasa, writeoperations dicatat dalam versi tentatif obyek dan
terlihat transaksi lainnya sampai permintaan Transaksi tertutup dikeluarkan dan
transaksi berkomitmen. Everyobject memiliki write timestamp dan satu set tentatif
versi, yang masing-masing memiliki write waktu yang terkait dengan itu; setiap objek juga memiliki
set cap waktu membaca. Menulis timestamp dari (berkomitmen) objek yang lebih awal dari itu
dari anyof versi tentatif, dan set cap waktu membaca dapat direpresentasikan byits
anggota maksimal. Setiap kali writeoperation transaksi pada sebuah objek diterima,
server menciptakan versi tentatif baru dari objek dengan menulis timestamp-nya diatur ke
timestamp transaksi. readoperation Transaksi ini diarahkan ke versi dengan
timestamp maximumwrite kurang dari cap waktu transaksi. Setiap kali
readoperation transaksi pada sebuah objek diterima, timestamp transaksi adalah
ditambahkan ke set cap waktu membaca. Ketika transaksi berkomitmen, nilai-nilai
versi tentatif menjadi nilai-nilai dari objek, dan cap waktu dari tentatif
versi menjadi cap dari correspondingobjects.
Dalam timestamp pemesanan, setiap permintaan bya transaksi untuk writeoperation Reador
pada objek diperiksa untuk melihat apakah itu sesuai dengan aturan konflik operasi. SEBUAH
permintaan bythe transaksi saat Tccan konflik operasi withprevious dilakukan byother
transaksi, Ti
, Yang cap waktu menunjukkan bahwa theyshould menjadi lambat Tc. aturan-aturan ini
ditunjukkan pada Gambar 16.29
, Di mana Ti> Tc berarti Ti
adalah lambatnya Tcand Ti <Tc berarti
Ti
, Adalah awal dari Tc.
Gambar 16.30 operasi Menulis dan cap waktu
Timestamp memesan menulis aturan: Bycombiningrules 1 dan 2 kita mendapatkan followingrule untuk
decidingwhether menerima writeoperation sebuah diminta bytransaction TCON objek D:
jika (Tc ?? timestamp maximumread di D &&
Tc> menulis timestamp pada versi berkomitmen D)
performwriteoperation pada versi tentatif Dwith tulis cap Tc
lain / * menulis terlambat * /
Batalkan transaksi Tc
Jika versi tentatif dengan Tcalreadyexists menulis timestamp, writeoperation adalah
ditujukan untuk itu; sebaliknya, versi tentatif baru dibuat dan diberikan write timestamp
Tc. Perhatikan bahwa setiap writethat 'ysng terlalu late'is dibatalkan - terlambat dalam arti bahwa
transaksi dengan timestamp kemudian telah alreadyread atau tertulis objek.
Gambar 16.30
menggambarkan aksi writeoperation sebuah bytransaction kasus T3in
whereT3 ?? maximumread timestamp pada objek (cap waktu membaca tidak
ditunjukkan). Dalam kasus (a) ke (c), T3> writetimestamp pada versi berkomitmen objek
dan versi tentatif dengan menulis timestamp T3is dimasukkan di tempat yang tepat di
daftar versi tentatif memerintahkan bytheir cap waktu transaksi. Dalam kasus (d),
T3 <writetimestamp pada versi berkomitmen objek dan transaksi
dibatalkan.
pemesanan Timestamp baca aturan: Byusingrule 3 kami tiba di followingrule untuk
decidingwhether untuk menerima langsung, menunggu atau untuk menolak readoperation diminta
bytransaction TCON objek D:
jika (Tc> menulis timestamp pada versi berkomitmen D) {
letDselectedbe versi Dwith timestamp maximumwrite ð Tc
jika (Dselectedis berkomitmen)
performreadoperation pada versi Dselected
lain
waituntil transaksi yang membuat versi Dselectedcommits atau dibatalkan?
readrule kemudian reapplythe
} lain
Batalkan transaksi Tc
catatan:
Jika transaksi Tchas alreadywritten versi sendiri dari objek, ini akan digunakan.
Sebuah readoperation yang tiba terlalu earlywaits untuk transaksi sebelumnya untuk menyelesaikan.
Jika transaksi sebelumnya melakukan, maka Tcwill baca fromits versi berkomitmen. Jika
itu dibatalkan, maka Tcwill ulangi aturan membaca (dan pilih versi sebelumnya). Ini
Aturan mencegah dirtyreads.
Sebuah readoperation yang 'ysng terlalu late'is dibatalkan - itu terlambat dalam arti bahwa
transaksi dengan timestamp kemudian telah alreadywritten objek.
Gambar 16,31 menggambarkan aturan timestamp orderingread. Ini mencakup empat kasus berlabel
(A) sampai (d), yang masing-masing menggambarkan tindakan dari T3 readoperation bytransaction. Di
setiap kasus, versi yang timestamp menulis kurang dari atau sama dengan T3is dipilih. Jika seperti
versi ada, itu ditandai dengan garis. Dalam kasus (a) dan (b) readoperation adalah
diarahkan ke versi berkomitmen - dalam (a) itu adalah onlyversion, sedangkan di (b) ada
Versi tentatif belongingto transaksi kemudian. Dalam kasus (c) readoperation adalah
diarahkan ke versi tentatif dan harus menunggu sampai transaksi yang membuatnya melakukan
atau dibatalkan. Dalam kasus (d) tidak ada versi yang cocok untuk membaca dan transaksi T3is dibatalkan.
Ketika seorang koordinator menerima permintaan untuk melakukan transaksi, akan selalu menjadi
mampu melakukannya karena semua operasi transaksi diperiksa untuk consistencywith
orang-orang dari transaksi sebelumnya sebelum beingcarried keluar. Versi berkomitmen setiap
objek harus dibuat agar timestamp. Oleh karena itu, koordinator kadang-kadang perlu
menunggu transaksi sebelumnya untuk menyelesaikan sebelum writingall versi berkomitmen dari
benda diakses bya transaksi tertentu, tetapi tidak ada kebutuhan untuk klien untuk menunggu. Di
Untuk melakukan transaksi dipulihkan setelah kecelakaan server, versi tentatif
benda dan fakta bahwa transaksi telah dilakukan harus ditulis untuk permanen
penyimpanan sebelum permintaan acknowledgingthe klien untuk melakukan transaksi.
Perhatikan bahwa timestamp ini orderingalgorithmis ketat satu - itu memastikan ketat
eksekusi transaksi (lihat Bagian 16.2). Timestamp orderingread penundaan aturan
readoperation transaksi pada anyobject sampai semua transaksi yang sebelumnya
ditulis bahwa objek telah dilakukan atau dibatalkan. Pengaturan ini untuk melakukan versi di
Agar memastikan bahwa pelaksanaan writeoperation transaksi pada anyobject adalah
ditunda sampai semua transaksi yang telah previouslywritten objek yang telah dilakukan atau
dibatalkan.
Gambar 16,31 Baca Operasi dan cap waktu
Pada Gambar 16.32, kita kembali ke contoh kita concerningthe dua bersamaan bankingtransactions Tand Uintroduced pada Gambar 16.7. Kolom menuju A, Band C mengacu pada informasi tentang rekening dengan nama-nama itu. Setiap akun memiliki entryRTS yangmencatat timestamp maximumread dan entri WTS yang mencatat menulis timestamp dari setiap versi - dengan cap dari versi berkomitmen dalam huruf tebal. Mulanya, semua akun telah melakukan versi ditulis bytransaction S, dan set read cap waktu kosong. Kami berasumsi S <T <U. Contoh ini menunjukkan bahwa ketika transaksiUis readyto mendapatkan keseimbangan Bit akan menunggu Tto lengkap sehingga dapat membaca nilai yang ditetapkan oleh Tif itu melakukan.Metode timestamp saja dijelaskan tidak menghindari deadlock, tetapi sangat mungkin menyebabkan restart. Modifikasi yang dikenal sebagai 'mengabaikan write'rule usang adalah perbaikan. Ini adalah modifikasi aturan timestamp orderingwrite: Jika menulis adalah terlambat itu bisa diabaikan bukan transaksi abortingthe, karena jika tiba dalam waktu efeknya akan telah ditimpa pula. Namun, jika transaksi lain telah membaca objek, transaksi dengan menulis akhir gagal karena membaca timestamp pada item.
Multiversion timestamp ordering • Pada bagian ini, kami telah menunjukkan bagaimana concurrencyprovided timestamp orderingis bybasic ditingkatkan byallowingeach transaksi untuk menulis versi tentatif sendiri objek. Dalam multiversion timestamp pemesanan, yang diperkenalkan byReed [1983], daftar versi berkomitmen tua serta sebagai versi tentatif disimpan untuk setiap objek. Daftar ini merupakan historyof yang nilai-nilai Google Terjemahan untuk Bisnis:Perangkat PenerjemahPenerjemah Situs WebPeluang Pasar Global
Gambar 16.32 Cap waktu dalam transaksi T Dan U
objek. Keuntungan menggunakan beberapa versi adalah bahwa readoperations yang tiba terlambat tidak perlu ditolak. Setiap versi memiliki timestamp terbesar membaca timestamp recordingthe dari setiap transaksi yang telah membaca fromit selain menulis timestamp.
Seperti sebelumnya, setiap kali menulis operasi diterima, diarahkan ke versi tentatif dengan menulis timestamp transaksi. Setiap kali readoperation dilakukan, itu ditujukan untuk versi dengan terbesar tulis cap kurang dari cap waktu transaksi. Jika transaksi timestamp lebih besar dari membaca timestamp dari versi beingused, membaca timestamp dari versi diatur ke timestamp transaksi.
Ketika membaca sebuah datang terlambat, itu dapat diizinkan toread Froman versi berkomitmen tua, sehingga tidak perlu untuk membatalkan readoperations akhir. Dalam multiversion timestamp pemesanan, readoperations selalu diizinkan, meskipun mereka mayhave ke waitfor sebelumnya transaksi untuk menyelesaikan (baik melakukan atau membatalkan), yang menjamin bahwa eksekusi yang dipulihkan. Lihat Latihan 16,22 untuk diskusi tentang cascadingaborts possibilityof.
Hal ini berkaitan dengan aturan 3 di aturan konflik untuk cap waktu pemesanan. Tidak ada konflik antara writeoperations transaksi yang berbeda, karena setiap transaksi menulis versi berkomitmen sendiri objek yang mengakses. Ini menghapus aturan 2 di aturan konflik untuk timestamp ordering, leavingus dengan: Aturan 1. Tc tidak harus writeobjects yang telah readbyany TiwhereTi> Tc. Aturan ini akan rusak jika ada anyversion dari objek dengan membaca timestamp> Tc,tapi onlyif versi ini memiliki write timestamp kurang dari atau sama dengan Tc. (Write ini tidak bisa memiliki anyeffect pada versi.)
Gambar 16.33 Latex Write Operasi akan mematahkan rea
Multiversion timestamp ordering menulis aturan: Sebagai anypotentiallyconflicting readoperation akan diarahkan ke versi terbaru dari sebuah objek, server memeriksa para versi DmaxEarlier dengan timestamp maximumwrite kurang dari atau sama dengan Tc. Kita punya yang followingrule untuk performinga writeoperation diminta objek bytransaction TCON D: jika (baca timestamp ofDmaxEarlier ?? Tc) performwriteoperation pada versi tentatif Dwith tulis cap Tc lain batalkan transaksi Tc
Gambar 16.33 mengilustrasikan sebuah contoh di mana writeis a ditolak. Objek alreadyhas versi berkomitmen dengan menulis cap waktu T1and T2. objek menerima berikut urutan permintaan untuk operasi pada objek:
T3read; T3write; T5read; T4write.
1.T3requests sebuah readoperation, yang menempatkan membaca timestamp versi T3on T2 ini. 2.T3requests sebuah writeoperation, yang membuat versi tentatif baru dengan menulis T3 timestamp.
3.T5requests sebuah readoperation, yang menggunakan versi dengan menulis timestamp T3 (yang timestamp tertinggi yang kurang dari T5).
4.T4requests sebuah writeoperation, yang ditolak karena membaca timestamp T5of versi dengan menulis timestamp T3is lebih besar dari T4. (Jika diizinkan, yang write timestamp dari versi baru akan T4. Jika versi tersebut diizinkan, maka akan membatalkan T5'sreadoperation, yang seharusnya menggunakan versi dengan timestamp T4.)
Ketika transaksi dibatalkan, semua versi yang dibuat akan dihapus. Ketika sebuah transaksi berkomitmen, semua versi yang dibuat dipertahankan, tapi untuk mengontrol penggunaan ruang penyimpanan, versi lama harus dihapus fromtime ke waktu. Meskipun memiliki overhead ruang penyimpanan, multiversion timestamp ordering tidak memungkinkan cukup concurrency, tidak menderita dari kebuntuan dan selalu memungkinkan readoperations. Untuk informasi lebih lanjut tentang multiversion timestamp pemesanan, melihat Bernstein et al. [1987].
Perbandingan metode untuk kontrol concurrency
Kami telah dijelaskan tiga metode yang terpisah untuk akses controllingconcurrent untuk berbagi Data: penguncian dua-fase yang ketat, metode optimis dan timestamp pemesanan. Semua dari metode carrysome overhead dalam waktu dan ruang theyrequire, dan theyall batas untuk batas tertentu potensi untuk operasi bersamaan.
Metode timestamp ordering mirip dengan dua fase lockingin yang digunakan baik pendekatan pesimis di mana konflik antara transaksi terdeteksi karena setiap objek diakses. Di satu sisi, timestamp orderingdecides urutan serialisasi statically- ketika transaksi dimulai. Di sisi lain, dua-fase lockingdecides yang Agar serialisasi secara dinamis accordingto urutan objek yang diakses. Timestamp pemesanan, dan khususnya multiversion timestamp ordering, lebih baik dari ketat dua fase lockingfor baca-onlytransactions. Dua-fase lockingis lebih baik bila operasi dalam transaksi yang predominantlyupdates. Beberapa workuses pengamatan bahwa timestamp orderingis bermanfaat bagi transaksi dengan didominasi readoperations dan lockingis bermanfaat bagi transaksi dengan lebih writesthan readsas argumen untuk skema allowinghybrid di yang beberapa transaksi menggunakan timestamp orderingand lain menggunakan concurrency lockingfor kontrol. Pembaca yang tertarik dalam penggunaan metode campuran harus membaca Bernstein et al. [1987].
Metode pesimis berbeda dalam strategyused ketika conflictingaccess untuk objek terdeteksi. Timestamp orderingaborts transaksi segera, sedangkan penguncian membuat menunggu transaksi - tetapi dengan kemungkinan nanti penaltyof abortingto menghindari kebuntuan. Ketika concurrencycontrol optimis digunakan, semua transaksi yang diizinkan untuk melanjutkan, namun ada juga yang dibatalkan ketika theyattempt untuk melakukan, atau di depan validasi transaksi dibatalkan sebelumnya. Hal ini menyebabkan operasi relativelyefficient ketika ada beberapa konflik, tetapi sejumlah besar mayhave pekerjaan yang harus diulang ketika transaksi dibatalkan.
Lockinghas telah digunakan selama bertahun-tahun dalam sistem database, tapi timestamp orderinghas telah digunakan dalam sistem database SDD-1. Kedua metode telah digunakan dalam File server. Namun, secara historis, metode dominan concurrencycontrol dari akses ke data dalam sistem terdistribusi adalah bylocking- misalnya, seperti yang disebutkan sebelumnya, CORBA ConcurrencyControl Layanan berdasarkan entirelyon penggunaan kunci. Dikhususnya, menyediakan penguncian hierarkis, yang memungkinkan untuk campuran-granularitylockingon Data hierarchicallystructured.
Beberapa penelitian sistem terdistribusi, misalnya Argus [Liskov 1988] dan Arjuna [Shrivastava et al. 1991], telah meneliti penggunaan kunci semantik, timestamp orderingand pendekatan baru untuk longtransactions. Ellis et al. [1991] menulis review persyaratan untuk aplikasi multi-user di yang semua pengguna mengharapkan untuk melihat pemandangan umum objek beingupdated byanyof yang pengguna. Manyof skema memberikan pemberitahuan dari perubahan yang dilakukan byother pengguna, tapi ini contraryto ide isolasi.Barghouti dan Kaiser [1991] menulis review dari apa yang kadang-kadang digambarkan sebagai 'Database canggih applications'- misalnya, koperasi CAD / CAM dan software sistem pembangunan. Dalam aplikasi tersebut, transaksi berlangsung untuk lama, dan pengguna versi independen workon dari objek yang diperiksa froma database umum dan diperiksa ketika workis selesai. Versi mergingof membutuhkan kerjasama antara pengguna.
Simililarly, mekanisme concurrencycontrol atas tidak selalu memadai selama dua puluh pertama centuryapplications yang memungkinkan pengguna untuk berbagi dokumen atas Internet. Manyof bentuk optimis penggunaan kedua concurrencycontrol diikuti oleh resolusi konflik bukannya abortingone dari anypair dari conflictingoperations. The followingare beberapa contoh.
Dropbox • Dropbox [www.dropbox.com] adalah layanan cloud yang menyediakan file cadangan dan memungkinkan pengguna untuk berbagi file dan folder, accessingthemfromanywhere. Dropbox menggunakan formof concurrencycontrol optimis, keepingtrackof consistencyand preventingclashes antara users'updates - yang berada di seluruh file granularityof. Jadi jika dua pengguna membuat update bersamaan ke file yang sama, menulis pertama akan diterima dan yang kedua ditolak. Namun, Dropboxprovides sebuah historyto versi memungkinkan pengguna untuk menggabungkan update mereka manualatau mengembalikan versi sebelumnya.
aplikasi Google • Google Apps [www.google.comI] tercantum pada Gambar 21.2. Mereka termasuk Google Docs, layanan cloud yang menyediakan aplikasi berbasis web (kata processor, spreadsheet dan presentasi) yang memungkinkan pengguna untuk berkolaborasi dengan salah satu lain dengan cara dokumen bersama. Jika beberapa orang mengedit dokumen yang sama secara bersamaan, theywill melihat perubahan masing-masing. Dalam kasus pengolah kata dokumen, pengguna dapat melihat satu kursor dan update lain untuk ditampilkan pada tingkat karakter individu sebagai theyare diketik byanyparticipant. Pengguna yang tersisa untuk menyelesaikan konflik yang terjadi, namun konflik generallyavoided karena pengguna terus menyadari kegiatan masing-masing. Dalam kasus dokumen spreadsheet, users'cursors dan perubahan akan ditampilkan dan diperbarui pada sel tunggal granularityof. Jika dua pengguna mengakses sel yang sama secara bersamaan, update terakhir menang.
Wikipedia • Concurrencycontrol untuk editingis optimis, allowingeditors bersamaan akses ke halaman web di mana menulis pertama diterima dan makinga pengguna berikutnya tulis menunjukkan 'edit conflict'screen dan diminta untuk menyelesaikan konflik.
Dynamo • layanan penyimpanan kunci-nilai Amazon.com ini menggunakan concurrency optimiskontrol dengan resolusi konflik (lihat Boxon yang halaman berikutnya).
Dinamo
Dynamo [DeCandia et al. 2007] adalah salah satu layanan penyimpanan yang digunakan byAmazon.com, yang platformserves puluhan juta pelanggan di peaktimes, usingtens dari ribuan server. Seperti pengaturan membuat verystrongdemands dalam hal kinerja, reliabilityand skalabilitas. Dynamo dirancang untuk mendukung aplikasi seperti shoppingcarts dan daftar best-seller yang membutuhkan onlyprimary keyaccess ke nilai dalam menyimpan data. Data heavilyreplicated dengan maksud untuk providingthe scalabilityand availabilitythat yang keyto layanan ini.
Dynamo menggunakan getand putoperations tunggal daripada transaksi dan melakukan tidak memberikan jaminan isolasi ditentukan dalam ACID properti. Sehingga untuk meningkatkan ketersediaan, juga menyediakan Konsistensi formof lemah yang diterima di aplikasi mendukung. Metode optimis digunakan untuk concurrencycontrol. Dalam kasus di mana versi berbeda, mereka harus berdamai. Aplikasi logika dapat digunakan untuk menggabungkan versi dikasus aplikasi shoppingcart.Dimana logika aplikasi tidak dapat digunakan, rekonsiliasi berbasis timestamp adalahterapan. Dynamo menggunakan aturan bahwa 'menulis terakhir wins'- versi dengan terbesar timestamp menjadi yang baru.
16,8 Ringkasan
Transaksi menyediakan sarana bywhich klien dapat specifysequences operasi yang adalah atom di hadapan transaksi konkuren lain dan server crash. Pertama aspek atomicityis dicapai byrunningtransactions sehingga efek mereka secara serial setara. Efek dari transaksi yang dilakukan dicatat dalam penyimpanan permanen sehingga bahwa layanan transaksi dapat memulihkan crash fromprocess. Untuk memungkinkan transaksi abilityto menggugurkan, tanpa efek samping havingharmful pada transaksi lainnya, eksekusi harus ketat - yaitu, membaca dan menulis dari satu transaksi harus ditunda sampai lainnya transaksi yang menulis objek yang sama memiliki baik berkomitmen atau dibatalkan. Untuk memungkinkan transaksi pilihan baik menggugurkan committingor, operasi mereka dilakukan dalam versi tentatif yang tidak bisa diakses byother transaksi. The tentative versi objek disalin ke benda nyata dan untuk penyimpanan permanen ketika transaksi melakukan.
transaksi bersarang terbentuk bystructuringtransactions fromother sub-transaksi. Nestingis particularlyuseful dalam sistem terdistribusi karena memungkinkan pelaksanaan bersamaan dari subtransactions di server terpisah. Nestingalso memiliki
keuntungan dari allowingindependent bagian recoveryof transaksi. konflik operasi forma dasar untuk derivasi dari concurrencycontrol protokol. Protokol tidak harus onlyensure serializabilitybut juga memungkinkan untuk recoveryby usingstrict eksekusi untuk menghindari masalah yang terkait dengan transaksi batal, seperti cascadingaborts. Tiga strategi alternatif yang mungkin beroperasi schedulingan dalam transaksi. Theyare (1) untuk mengeksekusi segera, (2) ke delayit atau (3) untuk membatalkan itu.
Ketat dua fase lockinguses dua strategi pertama, resortingto aborsi onlyin kasus kebuntuan. Ini memastikan serializabilitybyorderingtransactions according to ketika theyaccess benda-benda umum. Its utama drawbackis yang deadlock dapat terjadi. orderinguses timestamp semua tiga strategi untuk memastikan serializabilitybyordering transactions'accesses ke objek accordingto waktu transaksi mulai. metode initidak dapat menderita fromdeadlocks dan menguntungkan untuk membaca-onlytransactions. Namun,transaksi harus dibatalkan ketika theyarrive terlambat. Multiversion timestamp ordering adalah particularlyeffective.
concurrencycontrol optimis memungkinkan transaksi untuk melanjutkan tanpa anyform dari checkinguntil theyare selesai. Transaksi divalidasi sebelum beingallowed untuk melakukan. validasi mundur membutuhkan pemeliharaan beberapa write set transaksi yang dilakukan, sedangkan maju validasi harus memvalidasi terhadap aktif transaksi dan memiliki keuntungan yang memungkinkan strategi alternatif untuk menyelesaikan konflik. Kelaparan dapat terjadi karena berulang abortingof transaksi yang gagal validasi di concurrencycontrol optimis dan bahkan di cap waktu pemesanan. Google Terjemahan untuk Bisnis:Perangkat PenerjemahPenerjemah Situs WebPeluang Pasar Global
The TaskBagis layanan yang fungsi adalah untuk memberikan repositoryfor sebuah 'tugas deskripsi '. Hal ini memungkinkan klien runningin beberapa komputer ke bagian carryout dari perhitungan secara paralel. Sebuah masterprocess menempatkan deskripsi dari subtasks dari perhitungan di TaskBag, dan workerprocesses pilih tugas dari dana TaskBagand carrythemout, kembali deskripsi dari hasil mereka ke TaskBag. masterthen yang mengumpulkan hasil dan menggabungkan themto menghasilkan hasil akhir
The TaskBagservice memberikan operasi berikut:
setTask memungkinkan klien untuk menambahkan deskripsi tugas untuk tas; klien takeTaskallows untuk mengambil taskdescriptions keluar dari kantong
eorang klien membuat permintaan mengambil Tugas, ketika sebuah taskis tidak tersedia tapi mungkin tersedia segera. Diskusikan keuntungan dan kelemahan dari alternatif berikut:eorang klien membuat permintaan mengambil Tugas, ketika sebuah taskis tidak tersedia tapi mungkin tersediasegera. Diskusikan keuntungan dan kelemahan dari alternatif berikut:
ebuah server mengelola objek a1, a2, ..., an. Server menyediakan dua operasi untuk nya
klien:
membaca (i) mengembalikan nilai ofai;menulis (i, Nilai) memberikan Valueto aiTransaksi Tand Uare didefinisikan sebagai berikut:
T: x = read (j); y = read (i); menulis (j, 44); menulis (i, 33);
U: x = read (k); menulis (i, 55); y = read (j); menulis (k, 66).
Memberikan tiga serial setara interleaving dari transaksi T Dan halaman U. 685
Berikan interleavings serial setara Tand Uin Latihan 16,2 dengan berikut
sifat:
i) yang ketat;
ii) yang tidak ketat tapi tidak bisa menghasilkan Cascading dibatalkan;
iii) yang bisa menghasilkan Cascading dibatalkan
The operationcreateinserts rekening bank baru di cabang. Transaksi Tand U
didefinisikan sebagai berikut:
T: aBranch.create ("Z");
U: z.deposit (10); z.deposit (20).
Asumsikan bahwa Zdoes belum ada. Asumsikan juga bahwa operasi deposito tidak nothingifaccount yang diberikan sebagai argumen tidak ada. Pertimbangkan interleaving berikut transaksi Tand U:
Menyatakan keseimbangan Setelah eksekusi mereka dalam urutan ini. Apakah ini konsisten dengan
eksekusi serial setara Tand U?
Sebuah objek yang baru dibuat seperti Zin Latihan 16,4 kadang-kadang disebut hantu. Darisudut pandang transaksi U, Zis tidak ada pada awalnya dan kemudian muncul (seperti hantu).Jelaskan, dengan contoh, bagaimana hantu bisa terjadi ketika akun dihapus
The 'transfer'transactions Tandu didefinisikan sebagai:T: a.withdraw (4); b.deposit (4);U: c.withdraw (3); b.deposit (3);Misalkan theyare terstruktur sebagai pasangan transaksi bersarang:T1: a.withdraw (4); T2: b.deposit (4);U1: c.withdraw (3); U2: b.deposit (3);
Bandingkan jumlah serial setara interleaving dari T1, T2, U1and U2with yangjumlah serial setara interleaving dari Tand U. Jelaskan whythe penggunaan intransaksi bersarang generallypermits jumlah yang lebih besar dari seriallyequivalent
interleavings daripada yang non-bersarang.
Pertimbangkan recoveryaspects transaksi bersarang didefinisikan dalam Latihan 16,6.
Asumsikan bahwa withdrawtransaction akan batalkan jika akun akan tekor dan bahwa
dalam hal ini transaksi orangtua juga akan membatalkan. Jelaskan serial setara
interleaving dari T1, T2, U1and U2 Dengan sifat sebagai berikut:i) yang ketat;ii) yang tidak ketat.Sejauh mana kriteria ketatnya mengurangi gain concurrency potensi
transaksi bersarang?
Menjelaskan kesetaraan whyserial mengharuskan sekali transaksi telah merilis Lockon sebuah
enjelaskan kesetaraan mengapa seri mengharuskan Sekali Transaksi has telah merilis Lockon SEBUAH SEBUAH objek, TIDAK diperbolehkan untuk review get Lagi kunci.
SEBUAH Server Mengelola objek a1, a2, ..., an. Server MENYEDIAKAN doa Operasi untuk review
Klien:
membaca (i) mengembalikan Nilai ofai
menulis (i, Nilai) memberikan Valueto ai
Transaksi Tand U didefinisikan sebagai berikut:
T: x = read (i); menulis (j, 44);
U: write (i, 55); menulis (j, 66);
Menggambarkan interleaving Dari Transaksi Tand Uinwhich kunci yang dirilis Awal
DENGAN Efek Yang interleaving TID
Pertimbangkan relaksasi kunci dua fase di mana read-only transaksi dapat melepaskan membaca kunci awal. Akan baca-onlytransaction memiliki retrievals konsisten? Akankah objek menjadi tidak konsisten? Ilustrasikan jawaban Anda dengan transaksi berikut TO Android server di Latihan 16.8:T: x = read (i); y = read (j);U: write (i, 55); menulis (j, 66);di mana nilai-nilai awal a and aj 10 dan 20.
Eksekusi transaksi ketat jika membaca dan menulis operasi pada sebuah objek yang
ditunda sampai semua transaksi yang sebelumnya menulis objek yang memiliki baik berkomitmen atau dibatalkan. Menjelaskan bagaimana lockingrules pada Gambar 16,16 memastikan eksekusi yang ketat.
Jelaskan bagaimana situasi non-recoverable bisa timbul jika menulis kunci dilepaskan setelah operasi terakhir dari transaksi tapi sebelum komitmennya
Jelaskan mengapa eksekusi selalu ketat, bahkan jika membaca kunci dilepaskan setelah terakhir operasi transaksi tapi sebelum komitmennya. Berikan pernyataan ditingkatkan dari Aturan 2 pada Gambar 16,16
Pertimbangkan skema deteksi kebuntuan untuk server tunggal. Jelaskan preciselywhen tepi ditambahkan dan dihapus dari dana menunggu-untuk-grafik.Mengilustrasika jawaban Anda sehubungan dengan transaksi berikut, Dan Vatthe server Latihan 16,8
Ketika dirilis tulis yang Lockon a, Baik Tand Vare waitingto mendapatkan write kunci pada saya t. Apakah skema Anda bekerja dengan benar jika T (pertama datang) diberikan pada lockbefore V?
Jika Anda Jawabannya adalah 'Tidak', kemudian memodifikasi deskripsi Anda.
Pertimbangkan kunci hierarkis seperti digambarkan pada Gambar 16.26. Apa kunci harus ditetapkan ketika sebuah Penunjukan ditugaskan untuk slot waktu dalam seminggu w, hari d, pada waktu t? Dalam rangka apa yang harus kunci ini diatur? Apakah urutan theyare dirilis peduli?kunci apa yang harus mengatur kapan slot waktu untuk sehari-hari dari seminggu yang melihat? Can ini dilakukan bila kunci untuk assigningan janji untuk slot waktu yang sudah ditetapkan
Pertimbangkan kontrol konkurensi optimis seperti diterapkan pada transaksi Tand Udefined dalam Latihan 16,9. Misalkan transaksi Tand Uare aktif pada saat yang sama sebagai salah satulain. Menggambarkan hasil di masing-masing kasus berikut:iT'srequest untuk melakukan yang lebih dulu dan mundur validasi digunakan.
ii) U'srequest untuk melakukan yang lebih dulu dan mundur validasi digunakan.
iii) permintaan T untuk melakukan yang lebih dulu dan maju validasi digunakan.
iv) U'srequest untuk melakukan yang lebih dulu dan maju validasi digunakanDalam setiap kasus menggambarkan urutan di mana operasi Tand Uare dilakukan,
menulis rememberingthat tidak dilakukan sampai setelah validasi.
Pertimbangkan interleaving berikut transaksi T Dan U:
Hasil dari concurrencycontrol optimis dengan validasi mundur adalah Twill yang
dibatalkan karena konflik readoperation dengan U'swriteoperation pada ai, meskipun
yang interleavings adalah serial setara. Menyarankan modifikasi algoritma yang
penawaran dengan kasus tersebut.
Membuat perbandingan urutan operasi dari transaksi T Dan U Of Latihan 16.8 yang mungkin di bawah penguncian dua fase (latihan 16,9) dan di bawah kontrol konkurensi optimis (Latihan 16,16).
Pertimbangkan penggunaan timestamp memesan dengan masing-masing contoh interleavings dari transaksi Tand Uin Latihan 16,9. nilai awal dari ai
dan aj 10 dan 20,masing-masing, dan awal membaca dan menulis cap waktu yang t0. Asumsikan bahwa setiap transaksi membuka dan memperoleh cap waktu sebelum operasi pertama; misalnya, dalam (a) Tand U mendapatkan cap waktu t1and t2, masing masing, di mana t0 <t1 <t2. Jelaskan dalam rangka peningkatan waktu efek dari setiap operasi dari Tand U. Untuk setiap operasi, menyebutkan:
i) apakah operasi dapat melanjutkan sesuai dengan write atau aturan baca;
ii) ketika cap waktu ditugaskan untuk transaksi atau benda;
iii) ketika benda tentatif dibuat dan ketika nilai-nilai mereka ditetapkan.
Apa nilai-nilai akhir dari objectsand cap waktu mereka
Ulangi latihan 16.19 untuk interleaving berikut transaksi T Dan U:
Ulangi latihan 16.20 menggunakan multiversion timestamp pemesanan.
Dalam multiversion timestamp ordering, baca operasi dapat mengakses versi tentatif
benda. Berikan contoh untuk menunjukkan bagaimana Cascading dibatalkan dapat terjadi jika semua membaca operasi yang diizinkan untuk melanjutkan segera.
Apa keuntungan dan kelemahan dari multiversion timestamp pemesanan di
perbandingan dengan timestamp ordering biasa?
Featured Post
How to fix Unity - Your browser does not support graphics API WebGL 2
Your browser does not support graphics API "WebGL 2" which is required for this content. Troubleshooting Guide: Resolving "Yo...
-
Terima kasih dalam dunia kesehatan sekarang ini di Indonesia sudah mulai terasa keringanannya, dengan adanya BPJS ini kita bisa berobat gra...
-
saya rasa untuk menghilangkan password bios pada PC rata-rata sudah pada bisa, meskipun tanpa harus menghafal password tersebut. yaitu de... -
Mesin Air Submersible atau yang sering disebut kebanyakan orang (satelit) ini sangat bagus, dengan sistemnya yang canggih dan fleksible. tip... -
pernahkah anda mengenal virus ramnit atau yang lebih dikenal lagi virus seperti berikut : shortcut1.ink shortcut2.ink shortcut3.ink shor...
-
BIDANG STUDI KEAHLIAN : TEKNOLOGI INFORMASI DAN KOMUNIKASI PROGRAM STUDI KEAHLIAN : TEKNIK KOMPUTER DAN INFORMATIKA PAKET ... -
SOAL A 1) Berikut ini yang termasuk komponen elektronika dengan jenis komponen pasif yaitu .... a) Power Supply b) Amplifier c) ... -
BIDANG STUDI KEAHLIAN : TEKNOLOGI INFORMASI DAN KOMUNIKASI PROGRAM STUDI KEAHLIAN : TEKNIK KOMPUTER DAN INFORMATIKA PAKET ... -
SOAL A 1. Organisasi komputer sangat berhubungan dengan unit operasional dan interkoneksinya dalam komputer. Berikut ini yang termasuk ... -
SOAL A 1. Berikut ini yang bukan merupakan fungsi dasar dari kinerja komputer adalah .... a) Data processing b) Data storage c...
0 komentar:
Post a Comment