Concurrency: SALINGPENGECUALIAN DANsinkronisasi5.1 Prinsip ConcurrencyContoh SederhanaKondisi rasSistem Operasi Kekhawatiranproses InteraksiPersyaratan untuk Pengecualian Reksa5.2 Reksa Pengecualian: Dukungan HardwareMenonaktifkan interruptInstruksi Mesin Khusus5.3 Semaphorereksa PengecualianMasalah Produser / KonsumenImplementasi Semaphore5.4 MonitorMonitor dengan SinyalModel alternatif Monitor dengan Beritahu dan Broadcast5,5 Message PassingsinkronisasimengatasiFormat pesanantrian Disiplinreksa Pengecualian5,6 Pembaca / Masalah PenulisPembaca Memiliki PrioritasPenulis Memiliki Prioritas5.7 Ringkasan5.8 Bacaan yang Direkomendasikan5,9 Key Persyaratan, Pertanyaan Review, dan Masalah

BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

Tema sentral dari desain sistem operasi semua prihatin dengan manajemenproses dan benang:• Multiprogramming: Pengelolaan beberapa proses dalamUniprocessor sistem.• Multiprocessing: Manajemen banyak proses dalam multiprosesor.• Terdistribusi pengolahan: Pengelolaan beberapa proses yang dijalankan padabeberapa, komputer proliferasi systems.The didistribusikan terbaru dari cluster adalahPerdana contoh dari jenis sistem.Mendasar untuk semua bidang, dan mendasar untuk OS desain, konkurensi.Concurrency mencakup sejumlah masalah desain, termasuk komunikasi antaraproses, berbagi dan bersaing untuk sumber daya (seperti memori, file, dan I / O akses),sinkronisasi kegiatan beberapa proses, dan alokasiprosesor waktu untuk processes.We akan melihat bahwa isu-isu ini muncul bukan hanya dalam multiprocessing

dan didistribusikan lingkungan pengolahan, tetapi bahkan dalam prosesor tunggal multiprogrammingsistem.Concurrency muncul dalam tiga konteks yang berbeda:• Beberapa aplikasi: Multiprogramming diciptakan untuk memungkinkan pemrosesanwaktu untuk secara dinamis dibagi di antara sejumlah aplikasi yang aktif.• Structured aplikasi: Sebagai perpanjangan dari prinsip-prinsip desain modulardan pemrograman terstruktur, beberapa aplikasi dapat secara efektif diprogramsebagai seperangkat proses konkuren.• Operasi sistem struktur: Keuntungan penataan yang sama berlaku untuk sistemprogram, dan kita telah melihat bahwa sistem operasi itu sendiri seringkali dilaksanakansebagai serangkaian proses atau thread.Karena pentingnya topik ini, empat bab dan lampiran iniBuku fokus pada isu-isu terkait konkurensi. Bab ini dan kesepakatan berikutnya dengan konkurensidalam multiprogramming dan sistem multiprocessing. Bab 16 dan 18 memeriksakonkurensi isu yang terkait dengan pemrosesan terdistribusi. Meskipun sisanyabuku ini meliputi sejumlah topik penting lainnya di OS desain, konkurensiakan memainkan peran utama dalam pertimbangan kita dari semua topik lainnya.Bab ini dimulai dengan pengenalan konsep concurrency danimplikasi dari pelaksanaan processes.1We beberapa konkuren menemukan bahwakebutuhan dasar untuk mendukung proses konkuren adalah kemampuan untuk menegakkan salingpengecualian, yaitu, kemampuan untuk mengecualikan semua proses lain dari tindakansementara satu proses diberikan kemampuan itu. Selanjutnya, kita memeriksa beberapa hardwaremekanisme yang dapat mendukung saling pengecualian. Kemudian kita melihat solusi yangtidak melibatkan menunggu sibuk dan yang dapat didukung baik oleh OS atau diberlakukan olehbahasa compilers.We memeriksa tiga pendekatan: Semaphore, monitor, dan pesanlewat.1For kesederhanaan, kita biasanya merujuk pada pelaksanaan proses bersamaan. Bahkan, sebagaimana telah kita lihatdalam bab sebelumnya, dalam beberapa sistem unit dasar dari konkurensi adalah benang bukansuatu proses.

5,1 / PRINSIP concurrency

Tabel 5.1 Beberapa Kunci Related Terms ke Concurrencyoperasi atom Urutan satu atau lebih pernyataan yang tampaknya dapat dibagi, yaitu, tidak lainproses dapat melihat keadaan peralihan atau mengganggu operasi.Sebuah bagian penting bagian dari kode dalam sebuah proses yang membutuhkan akses ke sumber daya bersama dan yang harustidak akan dieksekusi ketika proses lain adalah di bagian yang sesuai dari kode.kebuntuan Situasi di mana dua atau lebih proses yang tidak dapat melanjutkan karena masing-masing sedang menungguuntuk salah satu orang lain untuk melakukan sesuatu.livelock Situasi di mana dua atau lebih proses secara terus-menerus mengubah negara mereka di respon

perubahan dalam proses lain (es) tanpa melakukan pekerjaan yang bermanfaat.Persyaratan saling pengecualian bahwa ketika satu proses dalam bagian kritis yang mengakses sumber daya bersama,tidak ada proses lain mungkin dalam bagian kritis yang mengakses salah satu dari mereka sumber daya bersama.Kondisi ras Situasi di mana beberapa benang atau proses membaca dan menulis item data bersama danhasil akhir tergantung pada waktu relatif eksekusi mereka.kelaparan Situasi di mana proses runnable yang terlupakan tanpa batas oleh scheduler;meskipun mampu untuk melanjutkan, tidak pernah dipilih

Dua masalah klasik dalam konkurensi digunakan untuk menggambarkan konsep dan membandingkanpendekatan yang disajikan dalam masalah produsen / konsumen chapter.The diperkenalkandalam Bagian 5.3 dan digunakan sebagai contoh berjalan. Bab ini ditutup denganpembaca / penulis masalah.Diskusi kita tentang konkurensi terus dalam Bab 6, dan kami menunda diskusidari mekanisme concurrency sistem contoh kita sampai akhir bab itu.Lampiran A mencakup topik tambahan pada konkurensi.Tabel 5.1 berisi daftar beberapa istilah kunci yang berhubungan dengan konkurensi.5.1 PRINSIP concurrencyDalam sistem single-prosesor multiprogramming, proses disisipkan dalam waktu untukmenghasilkan penampilan eksekusi simultan (Gambar 2.12a). Meskipun sebenarnyapengolahan paralel tidak tercapai, dan meskipun ada sejumlah tertentuoverhead yang terlibat dalam switching bolak-balik antara proses, eksekusi interleavedmemberikan manfaat besar dalam efisiensi pengolahan dan penataan program.Dalam sistem multi-prosesor, adalah mungkin tidak hanya untuk interleave pelaksanaanbeberapa proses tetapi juga untuk mereka tumpang tindih (Gambar 2.12b).Pada pandangan pertama, mungkin tampak bahwa interleaving dan tumpang tindih mewakili fundamentalberbagai mode eksekusi dan masalah yang berbeda hadir. Pada kenyataannya, baikteknik dapat dipandang sebagai contoh pengolahan bersamaan, dan keduanya hadirmasalah yang sama. Dalam kasus Uniprocessor, masalah berasal dari dasarkarakteristik sistem multiprogramming: Kecepatan relatif pelaksanaanproses yang tidak dapat diprediksi. Hal ini tergantung pada kegiatan proses lain,cara di mana OS menangani interupsi, dan kebijakan penjadwalan dari OS. Parakesulitan berikut muncul:1. Berbagi sumber daya global yang penuh dengan contoh peril.For, jika dua prosesbaik menggunakan variabel global yang sama dan keduanya melakukan membaca dan menulis padavariabel itu, maka urutan yang membaca dan menulis berbagai dieksekusi adalahkritis. Sebuah contoh dari masalah ini ditampilkan dalam ayat berikut.

Tabel 5.1 Beberapa Kunci Related Terms ke Concurrencyoperasi atom Urutan satu atau lebih pernyataan yang tampaknya dapat dibagi, yaitu, tidak lainproses dapat melihat keadaan peralihan atau mengganggu operasi.

Sebuah bagian penting bagian dari kode dalam sebuah proses yang membutuhkan akses ke sumber daya bersama dan yang harustidak akan dieksekusi ketika proses lain adalah di bagian yang sesuai dari kode.kebuntuan Situasi di mana dua atau lebih proses yang tidak dapat melanjutkan karena masing-masing sedang menungguuntuk salah satu orang lain untuk melakukan sesuatu.livelock Situasi di mana dua atau lebih proses secara terus-menerus mengubah negara mereka di responperubahan dalam proses lain (es) tanpa melakukan pekerjaan yang bermanfaat.Persyaratan saling pengecualian bahwa ketika satu proses dalam bagian kritis yang mengakses sumber daya bersama,tidak ada proses lain mungkin dalam bagian kritis yang mengakses salah satu dari mereka sumber daya bersama.Kondisi ras Situasi di mana beberapa benang atau proses membaca dan menulis item data bersama danhasil akhir tergantung pada waktu relatif eksekusi mereka.kelaparan Situasi di mana proses runnable yang terlupakan tanpa batas oleh scheduler;meskipun mampu untuk melanjutkan, tidak pernah dipilih.M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 Page 207208 BAB 5 / Concurrency: PENGECUALIAN DAN SALING SYNCHRONIZAT

BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi2. Sulit bagi OS untuk mengelola alokasi sumber daya secara optimal. Sebagai contoh,Sebuah proses dapat meminta penggunaan, dan diberikan kontrol, sebuah I / O tertentusaluran dan kemudian ditangguhkan sebelum menggunakan channel. Ini mungkin tidak diinginkanuntuk OS hanya untuk mengunci saluran dan mencegah penggunaannya oleh proses lainnya, memangini dapat menyebabkan kondisi kebuntuan, seperti dijelaskan dalam Bab 6.3. Ini menjadi sangat sulit untuk menemukan kesalahan pemrograman karena hasil yangbiasanya tidak deterministik dan direproduksi (misalnya, lihat [LEBL87, CARR89,SHEN02] untuk diskusi tentang hal ini).Semua kesulitan tersebut di atas menampilkan diri dalam sistem multiprosesorjuga, karena di sini juga kecepatan relatif dari pelaksanaan proses-proses tidak dapat diprediksi.Sebuah sistem multiprosesor juga harus berhadapan dengan masalah yang timbul dari simultanpelaksanaan beberapa proses. Pada dasarnya, bagaimanapun, masalahadalah sama dengan yang untuk systems.This Uniprocessor harus menjadi jelas saat diskusihasil.Contoh SederhanaPertimbangkan prosedur berikut:kekosongan echo (){Dagu = getchar ();chout = dagu;putchar (chout);}

Prosedur ini menunjukkan unsur-unsur penting dari sebuah program yang akan memberikan karaktergema prosedur; masukan diperoleh dari keystroke satu keyboard pada suatu waktu.Setiap karakter input disimpan di dagu variabel. Hal ini kemudian ditransfer ke variabelchout dan dikirim ke layar. Setiap program dapat memanggil prosedur ini berulang kali untukmenerima input pengguna dan menampilkannya pada layar pengguna.Sekarang perhatikan bahwa kita memiliki sistem single-prosesor yang mendukung multiprogrammingsingle user. Pengguna dapat melompat dari satu aplikasi ke yang lain, dan masing-masingaplikasi menggunakan keyboard yang sama untuk input dan layar yang sama untuk output. Karenasetiap aplikasi perlu menggunakan echo prosedur, masuk akal untuk itu harusprosedur bersama yang dimuat ke bagian memori global untuk semua aplikasi.Jadi, hanya satu salinan dari prosedur echo digunakan, menghemat ruang.Berbagi memori utama di antara proses ini berguna untuk mengizinkan efisien daninteraksi di antara proses menutup. Namun, berbagi tersebut dapat menyebabkan masalah.Perhatikan urutan berikut:1. Proses P1 memanggil prosedur gema dan terganggu segera setelahgetchar kembali nilai dan menyimpannya di dagu. Pada titik ini, yang paling barukarakter dimasukkan, x, disimpan di dagu variabel.2. Proses P2 diaktifkan dan memanggil prosedur gema, yang berjalan pada kesimpulan,memasukkan dan kemudian menampilkan satu karakter, y, di layar.

5,1 / PRINSIP concurrency 2093. P1 proses dilanjutkan. Pada saat ini, x nilai telah ditimpa di dagudan karena itu hilang. Sebaliknya, dagu mengandung y, yang ditransfer ke choutdan ditampilkan.Dengan demikian, karakter pertama adalah hilang dan karakter kedua ditampilkan twice.TheInti dari masalah ini adalah variabel bersama dagu, global. Beberapa proses memilikiakses ke variabel ini. Jika satu proses pembaruan variabel global dan kemudian terganggu,proses lain dapat mengubah variabel sebelum proses pertama dapat menggunakan nyanilai. Misalkan, bagaimanapun, bahwa kita mengizinkan hanya satu proses pada suatu waktu berada dalam prosedur tersebut.Kemudian urutan di atas akan menghasilkan berikut ini:1. Proses P1 memanggil prosedur gema dan terganggu segera setelahkesimpulan dari fungsi input. Pada titik ini, yang paling baru masukkarakter, x, disimpan di dagu variabel.2. Proses P2 diaktifkan dan memanggil prosedur gema. Namun, karena P1 adalahmasih di dalam prosedur gema, walaupun saat ini ditangguhkan, P2 adalah diblokir darimemasuki prosedur. Oleh karena itu, P2 adalah ditangguhkan menunggu ketersediaanprosedur gema.3. Pada beberapa waktu kemudian, P1 proses dilanjutkan dan menyelesaikan pelaksanaan echo.Thekarakter yang tepat, x, akan ditampilkan.4. Ketika keluar P1 echo, ini menghilangkan blok pada P2.When P2 kemudian dilanjutkan,prosedur echo berhasil dipanggil.Contoh ini menunjukkan bahwa perlu untuk melindungi variabel global bersama (danlainnya berbagi sumber daya global) dan bahwa satu-satunya cara untuk melakukannya adalah untuk mengontrol kode

yang mengakses variabel. Jika kita menerapkan disiplin yang hanya satu proses pada suatu waktudapat masuk echo dan bahwa sekali dalam gema prosedur yang harus dijalankan untuk selesai sebelumitu tersedia untuk proses lain, maka jenis kesalahan hanya dibahas tidak akanterjadi. Bagaimana disiplin yang dapat dikenakan adalah topik utama dari bab ini.Masalah ini dinyatakan dengan asumsi bahwa ada sebuah prosesor tunggal,multiprogramming misalnya OS.The menunjukkan bahwa masalah konkurensiterjadi bahkan ketika ada prosesor tunggal. Dalam sistem multiprosesor, yang samamasalah sumber daya bersama dilindungi muncul, dan solusi sama bekerja. Pertama, misalkanbahwa tidak ada mekanisme untuk mengontrol akses ke variabel global bersama:1. Proses P1 dan P2 sama-sama menjalankan, masing-masing pada prosesor terpisah. Keduaproses memanggil prosedur gema.2. Kejadian berikut terjadi, kejadian pada baris yang sama terjadi secara paralel:Proses P1 P2 Proses• •Dagu = getchar (); •• Dagu = getchar ();chout = dagu; chout = dagu;putchar (chout); •• putchar (chout);• •

SALING PENGECUALIAN dan sinkronisasi

Hasilnya adalah bahwa input karakter ke P1 hilang sebelum ditampilkan, daninput karakter ke P2 ditampilkan oleh P1 dan P2. Sekali lagi, mari kita tambahkankemampuan menegakkan disiplin bahwa hanya satu proses pada suatu waktu mungkin dalam gema.Kemudian urutan berikut terjadi:1. Proses P1 dan P2 sama-sama menjalankan, masing-masing pada prosesor terpisah. P1 memanggilprosedur gema.2. Sementara P1 adalah di dalam prosedur gema, P2 memanggil echo. Karena P1 adalah masih di dalamprosedur echo (apakah P1 adalah ditangguhkan atau mengeksekusi), P2 adalah diblokir darimemasuki prosedur. Oleh karena itu, P2 adalah ditangguhkan menunggu ketersediaanprosedur gema.3. Pada waktu kemudian, proses P1 selesai pelaksanaan gema, keluar bahwa prosedur,dan terus mengeksekusi. Segera setelah keluar dari P1 dari gema, P2 kembalidan mulai mengeksekusi echo.Dalam kasus sistem uniprocessor, alasan kita punya masalah adalah bahwainterupsi dapat menghentikan eksekusi instruksi mana saja dalam suatu proses. Dalam kasus multiprosesorsistem, kami memiliki kondisi yang sama dan, di samping itu, masalah dapatdisebabkan karena dua proses secara simultan dapat mengeksekusi dan keduanya berusaha untukmengakses variabel global yang sama. Namun, solusi untuk kedua jenis masalah adalahsama: kontrol akses ke sumber daya bersama.

Kondisi rasSebuah kondisi lomba terjadi ketika beberapa proses atau thread membaca dan menulis dataitem sehingga hasil akhir tergantung pada urutan eksekusi instruksi dibeberapa proses. Mari kita mempertimbangkan dua contoh sederhana.Sebagai contoh pertama, anggaplah bahwa dua proses, P1 dan P2, berbagi globalvariabel a. Pada titik tertentu dalam pelaksanaannya, P1 update ke nilai 1, dan di beberapatitik dalam pelaksanaannya, update P2 ke 2.Thus nilai, dua tugas dalam perlombaan untukmenulis variabel a. Dalam contoh ini "pecundang" dari perlombaan (proses yang updateterakhir) menentukan nilai akhir a.Sebagai contoh kami yang kedua, mempertimbangkan dua proses, P3 dan P4, bahwa saham globalvariabel b dan c, dengan nilai awal b = 1 dan c = 2. Pada titik tertentu dalam pelaksanaannya,P3 mengeksekusi tugas b = b + c, dan pada titik tertentu dalam pelaksanaannya, P4mengeksekusi tugas c = b + c. Perhatikan bahwa dua proses update yang berbedavariabel. Namun demikian, nilai akhir dari dua variabel tergantung pada urutan dalamdua proses yang mengeksekusi dua tugas. Jika P3 menjalankan tugas nyapernyataan pertama, maka nilai final b = 3 dan c = 5. Jika P4 menjalankan nyatugas pernyataan pertama, maka nilai final b = 4 dan c = 3.Lampiran A termasuk diskusi tentang kondisi ras menggunakan Semaphore sebagaicontoh.Sistem Operasi KekhawatiranApa desain dan isu-isu manajemen yang diangkat oleh adanya konkurensi? Kamibisa daftar keprihatinan berikut:1. OS harus dapat melacak berbagai processes.This dilakukan denganpenggunaan blok kontrol proses dan digambarkan dalam Bab 4

5,1 / PRINSIP concurrency 2112. OS harus mengalokasikan dan DEALLOCATE berbagai sumber daya untuk setiap proses aktif.Pada kali, beberapa proses menginginkan akses ke sumber daya yang sama resource.Thesetermasuk• Waktu Processor: ini adalah fungsi penjadwalan, yang dibahas di Bagian Empat.• Memori: Sebagian besar sistem operasi menggunakan memori topik scheme.The virtualdibahas di Bagian Tiga.• File: Dibahas pada Bab 12.• I / O device: Dibahas di Bab 11.3. OS harus melindungi data dan sumber daya fisik dari setiap proses yang tidak diinginkan terhadapgangguan oleh processes.This lain melibatkan teknik yang berhubungan denganmemori, file, dan I / O device. Sebuah pengobatan umum perlindungan ditemukan dalamBab 14.4. Fungsi dari sebuah proses, dan output yang dihasilkannya, harus independenkecepatan di mana pelaksanaannya dilakukan relatif terhadap kecepatan lainnyaprocesses.This bersamaan adalah subjek dari bab ini.Untuk memahami bagaimana masalah kecepatan kemerdekaan dapat diatasi, kitaperlu melihat cara di mana proses dapat berinteraksi.Proses InteraksiKita dapat mengklasifikasikan cara-cara di mana proses berinteraksi atas dasar derajat

yang mereka menyadari existence.Table masing-masing 5,2 daftar tiga gelar yang mungkinditambah kesadaran konsekuensi masing-masing:Tabel 5.2 Proses InteraksiPengaruh Tingkat Kesadaran Hubungan Itu SatuApakah pada prosesLainnyaPotensi KontrolMasalahMenyadari prosessama lainPersaingan • Hasil dari satuproses independentindakan orang lain• Waktu prosesmungkin akan terpengaruh• Reksa pengecualian• Deadlock (terbarukansumber daya)• KelaparanProses tidak langsungmenyadari satu sama lain (misalnya,bersama objek)Kerjasama dengan berbagi Hasil • satuProses mungkin tergantungpada informasidiperoleh dari orang lain• Waktu prosesmungkin akan terpengaruh• Reksa pengecualian• Deadlock (terbarukansumber daya)• Kelaparan• Data koherensiProses langsung menyadarisatu sama lain (memiliki komunikasiprimitiftersedia bagi mereka)Kerjasama dengan komunikasi• Hasil dari satuProses mungkin tergantungpada informasidiperoleh dari orang lain• Waktu prosesmungkin akan terpengaruh• Deadlock (habissumber daya)• KelaparanM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 211• Proses tidak menyadari satu sama lain: Ini adalah independen proses th

212 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

Proses tidak menyadari satu sama lain: Ini adalah proses independen yangtidak dimaksudkan untuk bekerja contoh terbaik together.The dari situasi ini adalah multiprogramming yangproses independen beberapa. Ini dapat berupa batch yangpekerjaan atau sesi interaktif atau campuran. Meskipun proses tidak bekerjabersama-sama, OS perlu khawatir tentang kompetisi untuk sumber daya.Sebagai contoh, dua aplikasi independen mungkin baik ingin akses yang samadisk atau file atau printer.The OS harus mengatur akses ini.• Proses tidak langsung menyadari satu sama lain: Ini adalah proses yang tidak selalumenyadari satu sama lain dengan ID masing-masing proses tapi bahwa akses berbagike beberapa objek, seperti buffer I / O. Proses tersebut menunjukkan kerjasamadalam berbagi objek umum.• Proses langsung menyadari satu sama lain: Ini adalah proses yang dapatberkomunikasi dengan satu sama lain dengan ID proses dan yang dirancang untuk bekerjabersama-sama pada beberapa kegiatan. Sekali lagi, proses seperti pameran kerjasama.Kondisi tidak akan selalu menjadi seperti jelas seperti yang disarankan dalam Tabel 5.2. Sebaliknya,beberapa proses mungkin menunjukkan aspek dari persaingan dan kerjasama. Namun demikian,itu adalah produktif untuk memeriksa setiap dari tiga item dalam daftar sebelumnya secara terpisahdan menentukan implikasinya untuk OS.Persaingan antara Proses untuk proses Sumber Daya serentak datangke dalam konflik dengan satu sama lain ketika mereka bersaing untuk penggunaan sumber yang sama.Dalam bentuk murni, kita dapat menggambarkan situasi sebagai berikut. Dua atau lebih prosesperlu untuk mengakses sumber daya selama eksekusi mereka. Setiap proses tidak sadaradanya proses lainnya, dan masing-masing untuk tidak terpengaruh oleh eksekusidari proses lainnya. Maka dari ini bahwa setiap proses harus meninggalkannegara dari sumber daya apapun yang menggunakan terpengaruh. Contoh sumber daya termasuk I / O device,memori, prosesor waktu, dan jam.Tidak ada pertukaran informasi antara proses bersaing. Namun,eksekusi dari satu proses dapat mempengaruhi perilaku proses bersaing.Secara khusus, jika dua proses kedua ingin akses ke sumber daya tunggal, maka satu prosesakan dialokasikan bahwa sumber daya oleh OS, dan yang lain harus wait.Therefore,proses yang ditolak akses akan melambat. Dalam kasus ekstrim,Proses diblokir mungkin tidak pernah mendapatkan akses ke sumber daya dan karenanya tidak akan pernah menghentikanberhasil.Dalam kasus proses bersaing tiga masalah kontrol harus dihadapi.Pertama adalah kebutuhan untuk saling pengecualian. Misalkan dua atau lebih proses membutuhkanakses ke sumber daya nonsharable tunggal, seperti printer. Selamaeksekusi, setiap proses akan mengirimkan perintah ke perangkat I / O, menerima statusnyainformasi, mengirim data, dan / atau menerima data. Kita akan menyebut seperti

sumber daya sebagai sumber daya kritis, dan bagian dari program yang menggunakannya kritisbagian dari program. Adalah penting bahwa hanya satu program pada satu waktu diizinkandi section.We kritis tidak bisa hanya mengandalkan OS untuk memahami dan menegakkanpembatasan ini karena persyaratan rinci mungkin tidak jelas. Dalam halprinter, misalnya, kita ingin setiap proses individu untuk memiliki kontrolprinter sementara itu mencetak seluruh file. Jika tidak, baris dari proses bersaing akandisisipkan.212 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasiM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 2125.1

5,1 / PRINSIP concurrency 213Penegakan saling pengecualian menciptakan dua masalah kontrol tambahan.Salah satunya adalah bahwa kebuntuan. Sebagai contoh, mempertimbangkan dua proses, P1 dan P2, dan dua sumber daya,R1 dan R2. Anggaplah bahwa setiap proses membutuhkan akses ke kedua sumber daya untukmelakukan sebagian fungsinya. Maka adalah mungkin untuk memiliki situasi berikut:OS memberikan R1 untuk P2, dan R2 untuk P1. Setiap proses menunggu salah satu dari dua sumber daya.Tidak akan melepaskan sumber daya yang sudah memiliki sampai telah mengakuisisisumber daya lainnya dan melakukan fungsi yang membutuhkan baik sumber daya. Keduaproses yang deadlock.Masalah kontrol akhir adalah kelaparan. Misalkan tiga proses (P1, P2, P3)masing-masing memerlukan akses ke sumber daya periodik R. Pertimbangkan situasi di mana P1 adalah dikepemilikan sumber daya, dan kedua P2 dan P3 yang tertunda, menunggu sumber daya itu.Ketika P1 keluar critical section, P2 atau P3 baik harus diizinkan akses keR. Asumsikan bahwa OS hibah akses ke P3 dan P1 itu lagi membutuhkan akses sebelumP3 menyelesaikan critical section. Jika OS hibah akses ke P1 P3 setelah selesai,dan kemudian bergantian memberikan akses ke P1 dan P3, maka P2 mungkin selamanyamenolak akses ke sumber daya, meskipun tidak ada situasi kebuntuan.Pengendalian kompetisi pasti melibatkan OS karena OS yang mengalokasikansumber daya. Selain itu, proses itu sendiri akan perlu untuk dapat mengekspresikankebutuhan untuk saling pengecualian dalam beberapa mode, seperti pengunciansumber daya sebelum digunakan. Setiap solusi akan melibatkan beberapa dukungan dari OS, sepertisebagai pemberian fasilitas penguncian. Gambar 5.1 mengilustrasikan saling pengecualianMekanisme dalam istilah abstrak. Ada proses n untuk dilakukan sekaligus.Setiap proses meliputi (1) bagian kritis yang beroperasi pada beberapa Ra sumber daya, dan(2) kode tambahan sebelum dan sesudahnya bagian penting yang tidak melibatkanakses ke Ra. Karena semua proses mengakses sumber daya Ra yang sama, diinginkan bahwahanya satu proses pada suatu waktu berada di section.To kritis menegakkan saling pengecualian, duafungsi yang disediakan: entercritical dan exitcritical. Fungsi masing-masingmengambil sebagai argumen nama sumber daya yang adalah subjek kompetisi.Setiap proses yang mencoba untuk memasuki critical section, sementara proses lain adalah dalam

critical section, untuk sumber daya yang sama, dibuat untuk menunggu.Masih untuk memeriksa mekanisme khusus untuk menyediakan fungsientercritical dan exitcritical. Untuk saat ini, kita menunda masalah ini sementarakita mempertimbangkan kasus-kasus lain dari interaksi proses./ * PROSES 1 * /kekosongan P1{sementara (benar) {/ * Kode sebelumnya /;entercritical (Ra);/ * Critical section * /;exitcritical (Ra);/ * Kode berikut * /;}}/ * PROSES 2 * /kekosongan P2{sementara (benar) {/ * Kode sebelumnya * /;entercritical (Ra);/ * Critical section * /;exitcritical (Ra);/ * Kode berikut * /;}}/ * PROSES n * /kekosongan Pn{sementara (benar) {/ * Kode sebelumnya * /;entercritical (Ra);/ * Critical section * /;exitcritical (Ra);/ * Kode berikut * /;}}• • •Gambar 5.1 Ilustrasi Pengecualian ReksaM05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 Page 213Kerjasama antara Proses dengan Berbagi Kasus kerjasama denganberbagi mencakup proses yang berinteraksi dengan proses lain tanpa secara eksplisitsadar dari mereka. Sebagai contoh, beberapa proses mungkin memiliki akses ke variabel bersamaatau untuk berbagi file atau database. Proses dapat menggunakan dan memperbarui data bersama tanpa

referensi untuk proses lain tapi tahu bahwa proses lain mungkin memiliki akses keyang data.Thus yang sama proses harus bekerja sama untuk memastikan bahwa data mereka berbagidikelola dengan baik. Mekanisme kontrol harus menjamin integritasberbagi data.Karena data yang diselenggarakan pada sumber daya (perangkat, memori), masalah kontroltentang pengecualian bersama, kebuntuan, dan kelaparan yang lagi present.The satunya perbedaanadalah bahwa item data dapat diakses dalam dua mode yang berbeda, membaca dan menulis, danoperasi hanya menulis harus saling eksklusif.Namun, atas dan di atas masalah ini, persyaratan baru diperkenalkan:bahwa koherensi data. Sebagai contoh sederhana, pertimbangkan sebuah aplikasi pembukuan diberbagai data item yang dapat diperbarui. Misalkan dua item data a dan b adalah untukdipertahankan dalam suatu hubungan? b.That, setiap program yang update satu nilaijuga harus memperbarui lain untuk mempertahankan hubungan. Sekarang perhatikan berikutdua proses:P1:a = a + 1;b = b + 1;P2:b = 2 * b;a = 2 * a;Jika negara awalnya konsisten, setiap proses yang diambil secara terpisah akan meninggalkanberbagi data dalam keadaan konsisten. Sekarang perhatikan eksekusi konkuren berikuturutan, di mana dua proses saling pengecualian menghormati masing-masing individuitem data (a dan b):a = a + 1;b = 2 * b;b = b + 1;a = 2 * a;Pada akhir urutan eksekusi, kondisi? b tidak lagi berlaku. UntukMisalnya, jika kita mulai dengan a = b = 1, pada akhir urutan eksekusi kita memiliki?4 dan b? 3. Masalahnya dapat dihindari dengan menyatakan seluruh urutan di setiapproses untuk menjadi bagian kritis.Jadi kita melihat bahwa konsep kritis adalah bagian penting dalam kasus kerjasamadengan berbagi. Abstrak fungsi yang sama entercritical danexitcritical dibahas sebelumnya (Gambar 5.1) dapat digunakan di sini. Dalam hal ini, argumenuntuk fungsi bisa menjadi variabel, file, atau benda bersama lainnya. Selain itu,jika bagian kritis digunakan untuk menyediakan integritas data, maka mungkin tidak adasumber daya yang spesifik atau variabel yang dapat diidentifikasi sebagai argumen. Dalam kasus itu, kami214 BAB

214 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

Kerjasama antara Proses dengan Berbagi Kasus kerjasama denganberbagi mencakup proses yang berinteraksi dengan proses lain tanpa secara eksplisitsadar dari mereka. Sebagai contoh, beberapa proses mungkin memiliki akses ke variabel bersamaatau untuk berbagi file atau database. Proses dapat menggunakan dan memperbarui data bersama tanpareferensi untuk proses lain tapi tahu bahwa proses lain mungkin memiliki akses keyang data.Thus yang sama proses harus bekerja sama untuk memastikan bahwa data mereka berbagidikelola dengan baik. Mekanisme kontrol harus menjamin integritasberbagi data.Karena data yang diselenggarakan pada sumber daya (perangkat, memori), masalah kontroltentang pengecualian bersama, kebuntuan, dan kelaparan yang lagi present.The satunya perbedaanadalah bahwa item data dapat diakses dalam dua mode yang berbeda, membaca dan menulis, danoperasi hanya menulis harus saling eksklusif.Namun, atas dan di atas masalah ini, persyaratan baru diperkenalkan:bahwa koherensi data. Sebagai contoh sederhana, pertimbangkan sebuah aplikasi pembukuan diberbagai data item yang dapat diperbarui. Misalkan dua item data a dan b adalah untukdipertahankan dalam suatu hubungan? b.That, setiap program yang update satu nilaijuga harus memperbarui lain untuk mempertahankan hubungan. Sekarang perhatikan berikutdua proses:P1:a = a + 1;b = b + 1;P2:b = 2 * b;a = 2 * a;Jika negara awalnya konsisten, setiap proses yang diambil secara terpisah akan meninggalkanberbagi data dalam keadaan konsisten. Sekarang perhatikan eksekusi konkuren berikuturutan, di mana dua proses saling pengecualian menghormati masing-masing individuitem data (a dan b):a = a + 1;b = 2 * b;b = b + 1;a = 2 * a;Pada akhir urutan eksekusi, kondisi? b tidak lagi berlaku. UntukMisalnya, jika kita mulai dengan a = b = 1, pada akhir urutan eksekusi kita memiliki?4 dan b? 3. Masalahnya dapat dihindari dengan menyatakan seluruh urutan di setiapproses untuk menjadi bagian kritis.Jadi kita melihat bahwa konsep kritis adalah bagian penting dalam kasus kerjasamadengan berbagi. Abstrak fungsi yang sama entercritical danexitcritical dibahas sebelumnya (Gambar 5.1) dapat digunakan di sini. Dalam hal ini, argumenuntuk fungsi bisa menjadi variabel, file, atau benda bersama lainnya. Selain itu,jika bagian kritis digunakan untuk menyediakan integritas data, maka mungkin tidak adasumber daya yang spesifik atau variabel yang dapat diidentifikasi sebagai argumen. Dalam kasus itu, kami

214 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasiM05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 Hal 2145,1 / PRINSIP concurrency 215bisa memikirkan argumen sebagai identifier yang dibagi di antara bersamaanproses untuk mengidentifikasi bagian-bagian penting yang harus saling eksklusif.Kerjasama antara Proses Komunikasi Dalam oleh dua kasus pertamayang telah kita bahas, setiap proses memiliki lingkungan yang terisolasi sendiri yang tidaktermasuk proses lainnya. Interaksi antara proses-proses yang tidak langsung. Dalam keduakasus, ada berbagi. Dalam kasus persaingan, mereka berbagi sumber daya tanpamenyadari proses-proses lainnya. Dalam kasus kedua, mereka berbagi nilai-nilai,dan meskipun setiap proses tidak secara eksplisit menyadari proses-proses lain, ia sadarkebutuhan untuk mempertahankan data integrity.When proses bekerja sama dengan komunikasi,Namun, berbagai proses berpartisipasi dalam upaya bersama yang menghubungkan semuakomunikasi processes.The menyediakan cara untuk menyinkronkan, atau koordinat,berbagai kegiatan.Biasanya, komunikasi dapat dicirikan sebagai terdiri dari pesan yangbeberapa macam. Primitif untuk mengirim dan menerima pesan dapat diberikan sebagai bagian daribahasa pemrograman atau disediakan oleh kernel OS.Karena tidak ada yang dibagi antara proses dalam tindakan lewat pesan,saling pengecualian bukan persyaratan kontrol untuk kerjasama semacam ini. Namun,masalah kebuntuan dan kelaparan yang masih ada. Sebagai contoh dari kebuntuan,dua proses mungkin diblokir, masing-masing menunggu komunikasi darilain. Sebagai contoh kelaparan, mempertimbangkan tiga proses, P1, P2, dan P3, yang menunjukkanperilaku berikut. P1 adalah berulang kali mencoba untuk berkomunikasi dengan baikP2 atau P3, dan P2 dan P3 keduanya berusaha untuk berkomunikasi dengan P1. Sebuahurutan bisa timbul di mana P1 P2 pertukaran dan informasi berulang kali, sementara P3diblokir menunggu komunikasi dari P1. Tidak ada kebuntuan, karena P1tetap aktif, tapi P3 adalah kelaparan.Persyaratan untuk Pengecualian ReksaSetiap fasilitas atau kemampuan yang adalah untuk memberikan dukungan untuk saling pengecualian harusmemenuhi persyaratan sebagai berikut:1. Saling pengecualian harus ditegakkan: Hanya satu proses pada suatu waktu yang dibolehkan masukyang kritis bagian, di antara semua proses yang memiliki bagian penting untuk hal yang samasumber daya atau shared object.2. Sebuah proses yang menghentikan di bagian tidak kritis yang harus melakukannya tanpa menggangguproses lainnya.3. Ini tidak harus mungkin untuk proses yang membutuhkan akses ke bagian kritis akan tertundatanpa batas: tidak ada jalan buntu atau kelaparan.4. Ketika proses tidak ada pada bagian kritis, proses apapun yang masuk ke permintaan kritisbagian harus diperbolehkan untuk masuk tanpa penundaan.5. Tidak ada asumsi yang dibuat tentang kecepatan relatif proses atau jumlah prosesor.6. Sebuah proses tetap dalam bagian penting dalam waktu yang terbatas saja.Ada sejumlah cara di mana persyaratan untuk saling pengecualian

bisa puas. Salah satu cara adalah untuk meninggalkan tanggung jawab dengan proses-proses yang inginuntuk mengeksekusi proses concurrently.Thus, apakah mereka adalah sistem program atau aplikasiprogram, akan diminta untuk berkoordinasi dengan satu sama lain untuk menegakkan

216 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

saling pengecualian, tanpa dukungan dari bahasa pemrograman atau OS.We yangdapat merujuk ke ini sebagai pendekatan perangkat lunak. Meskipun pendekatan ini rentan terhadap tinggipengolahan overhead dan bug, hal ini tetap berguna untuk menguji pendekatan tersebutuntuk mendapatkan pemahaman yang lebih baik tentang kompleksitas topik processing.This bersamaantercakup dalam Lampiran A. Pendekatan kedua melibatkan penggunaan tujuan khususinstructions.These mesin memiliki keunggulan mengurangi overhead namun demikianakan ditampilkan untuk menjadi menarik sebagai solusi umum tujuan; mereka ditutupidalam Bagian 5.2. Pendekatan ketiga adalah untuk menyediakan beberapa tingkat dukungan dalam OS ataubahasa pemrograman. Tiga dari pendekatan tersebut yang paling penting diperiksadalam Bagian 5.3 melalui 5,5.5.2 SALING PENGECUALIAN: DUKUNGAN HARDWARESejumlah algoritma perangkat lunak untuk menegakkan saling pengecualian telah dikembangkan.Pendekatan perangkat lunak cenderung memiliki overhead pemrosesan tinggi dan risikokesalahan logis adalah signifikan. Namun, studi ini menggambarkan banyak algoritmakonsep dasar dan potensi masalah dalam program bersamaan berkembang.Untuk pembaca yang tertarik, Lampiran A termasuk diskusi tentang pendekatan perangkat lunak.Pada bagian ini, kita melihat beberapa pendekatan hardware menarik untuk salingpengecualian.Menonaktifkan InterruptDalam sistem uniprocessor, proses konkuren tidak dapat memiliki eksekusi tumpang tindih;mereka hanya dapat disisipkan. Selain itu, proses akan terus berjalan sampai memanggillayanan OS atau sampai interrupted.Therefore, untuk menjamin mutual exclusion,itu sudah cukup untuk mencegah sebuah proses dari yang terganggu. Kemampuan ini dapatdiberikan dalam bentuk primitif yang didefinisikan oleh kernel OS untuk menonaktifkan dan mengaktifkaninterupsi. Sebuah proses kemudian dapat menegakkan saling pengecualian dengan cara berikut(Bandingkan Gambar 5.1):sementara (benar) {/ * Menonaktifkan interrupts * /;/ * Critical section * /;/ * Mengaktifkan interupsi * /;/ * Sisanya * /;}Karena bagian kritis tidak dapat terganggu, saling pengecualian dijamin.

Harga pendekatan ini, bagaimanapun, adalah efisiensi eksekusi bisa high.Theakan terasa terdegradasi karena prosesor terbatas pada kemampuannya untuk interleaveproses. Masalah kedua adalah bahwa pendekatan ini tidak akan bekerja dalam multiprosesorarsitektur. Ketika komputer mencakup lebih dari satu prosesor, adalah mungkin(Dan khas) selama lebih dari satu proses yang akan mengeksekusi pada suatu waktu. Dalam hal ini, dinonaktifkaninterupsi tidak menjamin mutual exclusion.216 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasiM05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 Hal 2165,2 / SALING PENGECUALIAN: HARDWARE DUKUNGAN 217Instruksi Mesin KhususDalam konfigurasi multiprosesor, beberapa prosesor berbagi akses ke umummemori utama. Dalam hal ini, tidak ada hubungan master / slave, melainkan prosesorberperilaku independen dalam hubungan teman sebaya. Tidak ada mekanisme interupsiantara prosesor yang saling pengecualian dapat didasarkan.Pada tingkat perangkat keras, seperti yang disebutkan, akses ke lokasi memori termasuksetiap akses lain untuk yang location.With sama ini sebagai dasar, prosesordesainer telah mengusulkan beberapa instruksi mesin yang melakukan dua tindakanatom, 2 seperti membaca dan menulis atau membaca dan pengujian, dari memori tunggallokasi dengan satu instruksi fetch siklus. Selama pelaksanaan instruksi, akseske lokasi memori yang diblokir untuk setiap referensi instruksi lain yanglokasi.Pada bagian ini, kita melihat dua dari instruksi yang paling sering dilaksanakan.Lainnya dijelaskan dalam [RAYN86] dan [STON93].Bandingkan & Swap Instruksi Instruksi membandingkan & swap, juga disebutbandingkan dan pertukaran instruksi, dapat didefinisikan sebagai berikut [HERL90]:compare_and_swap int (int * kata, int testval, int newval){int oldval;oldval = * kataif (== oldval testval) * kata = newval;kembali oldval;}Versi instruksi pemeriksaan lokasi memori (* kata) terhadapUji nilai (testval). Jika nilai saat ini lokasi memori adalah testval, itu digantidengan newval, jika dibiarkan tidak berubah. Nilai memori lama selalu dikembalikan;dengan demikian, lokasi memori telah diperbarui jika nilai yang dikembalikan adalahsama seperti instruksi value.This tes atom karena itu memiliki dua bagian: bandingkan adalahdibuat antara nilai memori dan nilai tes, jika nilai berbeda swap terjadi.Seluruh membandingkan & fungsi swap dilakukan atom, yaitu, ia tidak taklukgangguan.Versi lain dari instruksi ini mengembalikan nilai Boolean: true jika swapterjadi; palsu sebaliknya. Beberapa versi instruksi ini tersedia di hampir semuaprosesor keluarga (x86, IA64, sparc, / 390, dll), dan kebanyakan sistem operasi menggunakan iniinstruksi untuk mendukung konkurensi.Gambar 5.2a menunjukkan sebuah protokol saling pengecualian berdasarkan penggunaan instruksi ini.3 Sebuah baut bersama variabel diinisialisasi ke 0. Satu-satunya proses yang dapatcritical section adalah salah satu yang menemukan baut sama dengan 0. Semua lainnya proses

di2The atom istilah yang berarti instruksi diperlakukan sebagai langkah tunggal yang tidak dapat terganggu.3The membangun parbegin (... P1, P2,, Pn) berarti mengikuti: menangguhkan eksekusi utamaProgram; memulai eksekusi konkuren prosedur P1, P2,. . . , Pn, ketika semua P1, P2,. . . , Pn telahdihentikan, melanjutkan program utama.

218 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi/ * Program * mutualexclusion /const int n = / * jumlah proses * /;int baut;kekosongan P (int i){sementara (benar) {sementara (compare_and_swap (baut, 0, 1) == 1)/ * Melakukan apa-apa * /;/ * Critical section * /;baut = 0;/ * Sisanya * /;}}void main (){baut = 0;parbegin (P (1), P (2), ..., P (n));}/ * Program * mutualexclusion /const int n = / * jumlah proses ** /;int baut;kekosongan P (int i){Keyi int = 1;sementara (benar) {melakukan pertukaran (Keyi, baut)sementara (Keyi = 0!);/ * Critical section * /;baut = 0;/ * Sisanya * /;}}void main (){baut = 0;parbegin (P (1), P (2), ..., P (n));}Gambar 5.2 Dukungan Hardware untuk Pengecualian Reksa(a) Bandingkan dan swap instruksi (b) Pertukaran instruksi

masukkan ke bagian kritis mereka ke mode menunggu sibuk. Sibuk menunggu panjang, atauberputar menunggu, mengacu pada teknik di mana suatu proses dapat berbuat apa-apa sampai mendapatizin untuk memasuki critical section tapi terus mengeksekusi instruksi atau menetapkaninstruksi bahwa tes variabel yang diperlukan untuk mendapatkan entrance.When prosesmeninggalkan critical section, ia ulang baut untuk 0; pada titik ini satu dan hanya satu dariproses menunggu yang diberikan akses ke critical section. Pilihan prosestergantung pada proses yang terjadi untuk menjalankan instruksi membandingkan & swap yangberikutnya.Bursa Instruksi Instruksi pertukaran dapat didefinisikan sebagai berikut:kekosongan tukar (int mendaftar, memori int){int temp;temp = memori;memori = mendaftar;mendaftar = temp;}Bursa instruksi isi daftar dengan sebuah lokasi memori.Baik Intel IA-32 arsitektur (Pentium) dan arsitektur IA-64 (Itanium)mengandung instruksi XCHG.Gambar 5.2b menunjukkan sebuah protokol saling pengecualian berdasarkan penggunaan pertukaraninstruksi. Sebuah baut bersama variabel diinisialisasi ke 0. Setiap proses menggunakan lokalvariabel kunci yang diinisialisasi untuk memproses hanya 1.The yang dapat memasuki critical sectionadalah salah satu yang menemukan baut sama dengan 0. Ini termasuk semua proses lain dari kritisbagian dengan menetapkan baut untuk 1.When proses meninggalkan critical section, ia ulang baut untuk0, memungkinkan proses lain untuk mendapatkan akses ke critical section.218 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi/ * Program * mutualexclusion /const int n = / * jumlah proses * /;int baut;kekosongan P (int i){sementara (benar) {sementara (compare_and_swap (baut, 0, 1) == 1)/ * Melakukan apa-apa * /;/ * Critical section * /;baut = 0;/ * Sisanya * /;}}void main (){baut = 0;parbegin (P (1), P (2), ..., P (n));}

/ * Program * mutualexclusion /const int n = / * jumlah proses ** /;int baut;kekosongan P (int i){Keyi int = 1;sementara (benar) {melakukan pertukaran (Keyi, baut)sementara (Keyi = 0!);/ * Critical section * /;baut = 0;/ * Sisanya * /;}}void main (){baut = 0;parbegin (P (1), P (2), ..., P (n));}Gambar 5.2 Dukungan Hardware untuk Pengecualian Reksa(A) Bandingkan dan swap instruksi (b) Pertukaran instruksiM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 2185,3 / Semaphore 219Perhatikan bahwa ekspresi berikut selalu memegang karena cara di manavariabel diinisialisasi dan karena sifat dari algoritma pertukaran:Jika baut = 0, maka proses tidak ada di bagian kritis. Jika baut = 1, maka tepat satuproses dalam bagian kritis, yaitu proses key yang nilainya sama dengan 0.Sifat-sifat Pendekatan Mesin-Instruksi Penggunaan khususinstruksi mesin untuk menegakkan saling pengecualian memiliki sejumlah keuntungan:• Hal ini berlaku untuk sejumlah proses di kedua prosesor tunggal atau beberapaprosesor berbagi memori utama.• Hal ini sederhana dan karena itu mudah untuk memverifikasi.• Hal ini dapat digunakan untuk mendukung beberapa bagian penting; setiap bagian kritis dapatdidefinisikan oleh variabel sendiri.Ada beberapa kelemahan yang serius:• Sibuk menunggu digunakan. Jadi, sementara proses sedang menunggu akses ke kritisbagian, terus untuk mengkonsumsi waktu prosesor.• Kelaparan adalah mungkin. Ketika sebuah proses meninggalkan critical section dan lebih darisatu proses sedang menunggu, pemilihan proses menunggu adalah sewenang-wenang. Jadi,beberapa proses tanpa batas bisa mengakses.• Deadlock adalah mungkin. Pertimbangkan skenario berikut pada prosesor tunggalsistem. Proses P1 mengeksekusi instruksi khusus (misalnya, membandingkan & swap,pertukaran) dan memasuki critical section. P1 kemudian menyela untuk memberikanprosesor ke P2, yang memiliki prioritas lebih tinggi. Jika P2 sekarang mencoba untuk menggunakansumber daya yang sama seperti P1, maka akan ditolak akses karena saling pengecualianmekanisme. Dengan demikian akan masuk ke lingkaran menunggu sibuk. Namun, P1 tidak akan pernah

diberangkatkan karena itu adalah prioritas yang lebih rendah dari yang lain P2, proses siap.Karena kelemahan dari kedua perangkat lunak dan solusi perangkat keras hanyadiuraikan, kita perlu mencari mekanisme lain.5.3 SemaphoreKita sekarang beralih ke mekanisme bahasa OS dan pemrograman yang digunakan untuk menyediakankonkurensi. Tabel 5.3 merangkum mekanisme use.We umum dimulai, dibagian ini, dengan Semaphore. Dua bagian berikutnya membahas monitor dan pesanlewat. Mekanisme lainnya dalam Tabel 5.3 dibahas ketika merawat spesifikcontoh sistem operasi, dalam Bab 6 dan 13.Kemajuan besar pertama dalam berurusan dengan masalah proses konkurendatang pada tahun 1965 dengan risalah Dijkstra [DIJK65]. Dijkstra prihatin dengan desaindari OS sebagai kumpulan proses sekuensial dan bekerja sama dengan pengembanganmekanisme yang efisien dan dapat diandalkan untuk mendukung kerjasama. Inimekanisme dapat dengan mudah digunakan oleh proses pengguna jika prosesor dan OSmembuat mekanisme yang tersedia.

220 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

Tabel 5.3 Mekanisme Concurrency UmumSemafor Sebuah nilai integer digunakan untuk sinyal antara proses. Hanya tiga operasi mungkin dapatdilakukan pada semaphore, yang semuanya atom: inisialisasi, pengurangan, dan kenaikan.Operasi pengurangan dapat mengakibatkan pemblokiran proses, dan kenaikanpengoperasian dapat mengakibatkan blokir dari sebuah proses. Juga dikenal sebagai menghitung suatusemaphore atau semaphore umum.Sebuah semafor biner Semafor yang mengambil hanya nilai-nilai 0 dan 1.Mirip dengan semafor biner mutex. Perbedaan utama antara keduanya adalah bahwa proses yangmengunci mutex (set nilai ke nol) harus menjadi salah satu untuk membukanya (menetapkan nilai 1).Kondisi Variabel Sebuah tipe data yang digunakan untuk memblokir proses atau thread sampai kondisi tertentu adalah benar.Sebuah memantau membangun bahasa pemrograman yang merangkum variabel, prosedur akses daninisialisasi kode dalam variabel data abstrak type.The monitor hanya dapatdiakses melalui prosedur akses dan hanya satu proses dapat aktif mengaksesmemonitor di salah satu prosedur time.The akses bagian kritis. Memantau mungkinmemiliki antrian proses yang sedang menunggu untuk mengaksesnya.Acara Flags Sebuah kata memori yang digunakan sebagai mekanisme sinkronisasi. Kode aplikasi dapat mengaitkanacara yang berbeda dengan setiap bit dalam bendera. Sebuah thread dapat menunggu baik peristiwa tunggalatau kombinasi kejadian dengan memeriksa bit satu atau beberapa bendera yang sesuai.Benang diblokir sampai semua bit yang diperlukan diatur (DAN) atau sampai setidaknya satudari bit diatur (OR).Kotak surat / Pesan Sebuah cara untuk dua proses untuk bertukar informasi dan yang dapat digunakan untuk

sinkronisasi.Mutual exclusion spinlocks mekanisme di mana suatu proses mengeksekusi dalam infinite loop menunggunilai dari variabel kunci untuk menunjukkan ketersediaan.

Prinsip mendasar adalah ini: Dua atau lebih proses dapat bekerja sama denganberarti sinyal yang sederhana, sehingga proses dapat dipaksa berhenti pada suatu tempat tertentusampai telah menerima sinyal yang spesifik. Setiap kebutuhan koordinasi kompleks dapatpuas dengan struktur yang tepat dari sinyal. Untuk sinyal, variabel khususSemaphore disebut digunakan. Untuk mengirimkan sinyal melalui s semaphore, proses mengeksekusiprimitif semSignal (s) Untuk menerima sinyal melalui semaphore s,. prosesmengeksekusi semWait primitif (s), jika sinyal yang sesuai belumditransmisikan, proses ini ditunda sampai pengiriman membutuhkan place.4Untuk mencapai efek yang diinginkan, kita dapat melihat semaphore sebagai variabel yang memilikinilai integer pada yang hanya tiga operasi didefinisikan:1. Sebuah semafor dapat diinisialisasi ke nilai integer non-negatif.2. Para decrements operasi semWait nilai semaphore. Jika nilai menjadinegatif, maka proses mengeksekusi semWait tersebut akan diblokir. Jika tidak,Proses berlanjut eksekusi.3. Increment Operasi semSignal nilai semaphore. Jika dihasilkannilai kurang dari atau sama dengan nol, maka proses diblokir oleh operasi semWait,jika ada, tidak diblokir.220 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasiMakalah aslinya 4in Dijkstra dan dalam banyak literatur, huruf P digunakan untuk semWait dan suratV untuk semSignal, ini adalah inisial dari kata-kata Belanda untuk tes (proberen) dan kenaikan (verhogen).Dalam beberapa literatur, istilah menunggu dan sinyal yang digunakan. Buku ini menggunakan semWait dansemSignal untuk kejelasan, dan untuk menghindari kebingungan dengan menunggu operasi serupa dan sinyal di monitor, dibahasselanjutnya.Tabel 5.3 Mekanisme Concurrency UmumSemafor Sebuah nilai integer digunakan untuk sinyal antara proses. Hanya tiga operasi mungkin dapatdilakukan pada semaphore, yang semuanya atom: inisialisasi, pengurangan, dan kenaikan.Operasi pengurangan dapat mengakibatkan pemblokiran proses, dan kenaikanpengoperasian dapat mengakibatkan blokir dari sebuah proses. Juga dikenal sebagai menghitung suatusemaphore atau semaphore umum.Sebuah semafor biner Semafor yang mengambil hanya nilai-nilai 0 dan 1.Mirip dengan semafor biner mutex. Perbedaan utama antara keduanya adalah bahwa proses yangmengunci mutex (set nilai ke nol) harus menjadi salah satu untuk membukanya (menetapkan nilai 1).Kondisi Variabel Sebuah tipe data yang digunakan untuk memblokir proses atau thread

sampai kondisi tertentu adalah benar.Sebuah memantau membangun bahasa pemrograman yang merangkum variabel, prosedur akses daninisialisasi kode dalam variabel data abstrak type.The monitor hanya dapatdiakses melalui prosedur akses dan hanya satu proses dapat aktif mengaksesmemonitor di salah satu prosedur time.The akses bagian kritis. Memantau mungkinmemiliki antrian proses yang sedang menunggu untuk mengaksesnya.Acara Flags Sebuah kata memori yang digunakan sebagai mekanisme sinkronisasi. Kode aplikasi dapat mengaitkanacara yang berbeda dengan setiap bit dalam bendera. Sebuah thread dapat menunggu baik peristiwa tunggalatau kombinasi kejadian dengan memeriksa bit satu atau beberapa bendera yang sesuai.Benang diblokir sampai semua bit yang diperlukan diatur (DAN) atau sampai setidaknya satudari bit diatur (OR).Kotak surat / Pesan Sebuah cara untuk dua proses untuk bertukar informasi dan yang dapat digunakan untuksinkronisasi.Mutual exclusion spinlocks mekanisme di mana suatu proses mengeksekusi dalam infinite loop menunggunilai dari variabel kunci untuk menunjukkan ketersediaan.M05_STAL6329_06_SE_C05.QXD 2/28/08 03:53 Halaman 2205,3 / Semaphore 221Selain tiga operasi, tidak ada cara untuk memeriksa atau memanipulasiSemaphore.Kami menjelaskan operasi ini sebagai follows.To mulai, semaphore memiliki nol ataupositif nilai. Jika nilai positif, nilai yang sama dengan jumlah proses yangdapat mengeluarkan menunggu dan segera melanjutkan untuk mengeksekusi. Jika nilai nol, baik olehinisialisasi atau karena sejumlah proses sama dengan nilai awal semafortelah mengeluarkan menunggu, proses selanjutnya untuk mengeluarkan menunggu diblokir, dan semaphore yangnilai berjalan negatif. Setiap drive menunggu berikutnya nilai semaphore lebih jauh kedikurangi nilai negatif territory.The sama dengan jumlah proses yang menunggu untuk dibuka.Setiap sinyal melepas blok salah satu proses menunggu ketika semafornilai negatif.[DOWN07] menunjukkan tiga konsekuensi menarik dari semaphore tersebutdefinisi:• Secara umum, tidak ada cara untuk mengetahui sebelum proses decrement semaphoreapakah akan memblokir atau tidak.• Setelah proses increment semaphore dan proses lain mendapat terbangun,kedua proses terus berjalan concurrently.There ada cara untuk mengetahui yangproses, jika salah, akan terus segera pada sistem uniprocessor.• Ketika Anda sinyal semaphore, Anda tidak perlu tahu apakah yang lainproses menunggu, sehingga jumlah proses diblokir mungkin nol atau satu.Gambar 5.3 menunjukkan definisi yang lebih formal dari primitif untuk Semaphore.Primitif semWait dan semSignal diasumsikan atom. Sebuah lebih terbatasversi, yang dikenal sebagai semafor biner, didefinisikan pada Gambar 5.4. Sebuah binersemaphore hanya dapat mengambil nilai 0 dan 1 dan dapat didefinisikan sebagai berikuttiga operasi:

1. Sebuah semafor biner dapat diinisialisasi ke 0 atau 1.struct {semaphoreint hitung;queueType antrian;};kekosongan semWait (semaphore s){s.count--;jika (s.count <0) {/ * Tempat proses ini dalam s.queue * /;/ * Blok proses ini * /;}}kekosongan semSignal (semaphore s){s.count + +;jika (s.count <= 0) {/ * Menghapus proses P dari s.queue * /;/ * Proses P tempat di daftar siap * /;}}Gambar 5.3 Definisi Primitif Semafor

222 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasistruct {binary_semaphoreenum {nol, satu} nilai;queueType antrian;};kekosongan semWaitB (binary_semaphore s){if (== s.value satu)s.value = nol;else {/ * Tempat proses ini dalam s.queue * /;/ * Blok proses ini * /;}}kekosongan semSignalB (semaphore s){jika (s.queue kosong ())s.value = satu;else {/ * Menghapus proses P dari s.queue * /;/ * Proses P tempat di daftar siap * /;}}Gambar 5.4 Definisi Semaphore Binary Primitif

2. Operasi semWaitB memeriksa nilai semaphore. Jika nilai nol, makaproses mengeksekusi semWaitB tersebut akan diblokir. Jika nilai satu, makanilai diubah menjadi nol dan proses berlanjut eksekusi.3. Operasi semSignalB memeriksa untuk melihat apakah ada proses yang diblokir padasemaphore (nilai semaphore sama dengan nol). Jika demikian, maka proses diblokir olehsemWaitB operasi dibuka. Jika tidak ada proses yang diblokir, maka nilaidari semaphore diatur ke satu.Pada prinsipnya, seharusnya lebih mudah untuk mengimplementasikan semafor biner, dan dapatditunjukkan bahwa ia memiliki kekuatan ekspresif sama dengan semaphore umum (lihat Soal5.17). Untuk kontras dua jenis Semaphore, semaphore nonbinary inisering disebut sebagai salah satu semafor semaphore menghitung atau umum.Suatu konsep yang terkait dengan semafor mutex biner. Perbedaan utama antarakeduanya adalah bahwa proses yang mengunci mutex (menetapkan nilai nol) harusmenjadi satu untuk membukanya (menetapkan nilai 1). Sebaliknya, adalah mungkin bagi satu prosesuntuk mengunci semafor biner dan bagi orang lain untuk membuka it.5Untuk kedua Semaphore Semaphore menghitung dan biner, antrian yang digunakan untukproses terus menunggu di semafor. Timbul pertanyaan ketertiban dalamproses mana yang dihapus dari antrian tersebut. Kebijakan penghapusan paling adil adalahpertama-di-first-out (FIFO): Proses yang telah diblokir terpanjang dilepaskandari antrian yang pertama, sebuah semafor yang definisinya mencakup kebijakan ini disebutsemafor yang kuat. Sebuah semafor yang tidak menentukan urutan di mana222 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasistruct {binary_semaphoreenum {nol, satu} nilai;queueType antrian;};kekosongan semWaitB (binary_semaphore s){if (== s.value satu)s.value = nol;else {/ * Tempat proses ini dalam s.queue * /;/ * Blok proses ini * /;}}kekosongan semSignalB (semaphore s){jika (s.queue kosong ())s.value = satu;else {/ * Menghapus proses P dari s.queue * /;/ * Proses P tempat di daftar siap * /;}}Gambar 5.4 Definisi Semaphore Binary Primitif

5in beberapa literatur, dan dalam beberapa buku teks, tak ada perbedaan antara biner mutex dansemaphore. Namun, dalam praktiknya, sejumlah sistem operasi, seperti Linux, Windows, dan Solaris,menawarkan fasilitas mutex yang sesuai dengan definisi dalam buku ini.M05_STAL6329_06_SE_C05.QXD 2/21/08 9:25 Hal 2225,3 / Semaphore 223proses akan dihapus dari antrian adalah semafor lemah. Gambar 5.5, berdasarkansatu di [DENN84], adalah contoh dari operasi semaphore yang kuat. Berikutproses A, B, dan C tergantung pada hasil dari proses D. Awalnya (1), A adalah berjalan;B, C, dan D siap, dan jumlah semafor adalah 1, menunjukkan bahwa salah satuProsesorDiblokir antrian antrian Siap SemaforSebuahs? 1 C D B1ProsesorDiblokir antrian antrian Siap SemaforBs? 0 A D C2ProsesorDiblokir antrian antrian Siap SemaforDB s? 1 A? C3ProsesorDiblokir antrian antrian Siap SemaforDs? 0 B A C4ProsesorDiblokir antrian antrian Siap SemaforCs? 0 D B A5ProsesorDiblokir antrian antrian Siap SemaforDSebuah B s C? ? 36ProsesorDiblokir antrian antrian Siap SemaforDB A s? 2 C?7Gambar 5.5 Contoh Mekanisme Semafor

M05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 223Hasil D's available.When Sebuah mengeluarkan instruksi semWait di semaphore s,semaphore decrements ke 0, dan A dapat terus melaksanakan; kemudian itubergabung kembali berjalan B queue.Then siap (2), akhirnya mengeluarkan instruksi semWait,dan diblokir, memungkinkan D untuk menjalankan (3). Ketika D melengkapi hasil baru, isu-isu yangsemSignal instruksi, yang memungkinkan B untuk pindah ke ready queue (4). D bergabung kembaliantrian siap dan C mulai untuk menjalankan (5) tetapi diblokir ketika isu semWait suatuinstruksi. Demikian pula, A dan B berjalan dan diblokir pada semaphore, mengizinkan Duntuk melanjutkan eksekusi (6). Ketika D memiliki hasilnya, menerbitkan semSignal, yang mentransferC untuk antrian siap. Kemudian siklus D akan merilis A dan B dari Diblokirnegara.Untuk algoritma saling pengecualian dibahas pada subseksi berikutnya dan diilustrasikanpada Gambar 5.6, Semaphore yang kuat menjamin kebebasan dari kelaparan, sementaraSemaphore lemah melakukan not.We akan menganggap Semaphore kuat karena mereka lebihnyaman dan karena ini adalah bentuk semaphore biasanya disediakan oleh operasisistem.Reksa PengecualianGambar 5.6 menunjukkan solusi mudah untuk masalah mutual exclusion menggunakansemaphore s (bandingkan Gambar 5.1). Pertimbangkan proses n, diidentifikasi dalam P array (i),semua yang memerlukan akses ke sumber daya yang sama. Setiap proses memiliki bagian kritisdigunakan untuk mengakses sumber daya. Dalam setiap proses, sebuah semWait (s) dieksekusi sebelumyang penting bagian. Jika nilai dari s menjadi negatif, proses tersebut akan diblokir. Jikanilai 1, maka adalah decremented ke 0 dan proses segera memasuki criticalbagian, karena s tidak lagi positif, tidak ada proses lain akan dapat masuk nyakritis bagian.Semafor diinisialisasi ke 1. Dengan demikian, proses pertama yang mengeksekusisemWait akan dapat memasuki critical section segera, pengaturan nilai ske 0. Setiap proses lain mencoba untuk memasuki critical section akan merasa sibuk danakan diblokir, pengaturan nilai s ke -1. Setiap jumlah proses mungkin mencobaentri; setiap hasil usaha tersebut tidak berhasil dalam pengurangan lebih lanjut dari nilais.When proses yang awalnya memasuki bagian kritis berangkat, s bertambah224

224 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi/ * Program * mutualexclusion /const int n = / * jumlah proses * /;semaphore s = 1;kekosongan P (int i){sementara (benar) {semWait (s);/ * Critical section * /;semSignal (s);/ * Sisanya * /;

}}void main (){parbegin (P (1), P (2), P (n)...);}Gambar 5.6 Pengecualian Reksa Menggunakan Semaphore

Hasil D's available.When Sebuah mengeluarkan instruksi semWait di semaphore s,semaphore decrements ke 0, dan A dapat terus melaksanakan; kemudian itubergabung kembali berjalan B queue.Then siap (2), akhirnya mengeluarkan instruksi semWait,dan diblokir, memungkinkan D untuk menjalankan (3). Ketika D melengkapi hasil baru, isu-isu yangsemSignal instruksi, yang memungkinkan B untuk pindah ke ready queue (4). D bergabung kembaliantrian siap dan C mulai untuk menjalankan (5) tetapi diblokir ketika isu semWait suatuinstruksi. Demikian pula, A dan B berjalan dan diblokir pada semaphore, mengizinkan Duntuk melanjutkan eksekusi (6). Ketika D memiliki hasilnya, menerbitkan semSignal, yang mentransferC untuk antrian siap. Kemudian siklus D akan merilis A dan B dari Diblokirnegara.Untuk algoritma saling pengecualian dibahas pada subseksi berikutnya dan diilustrasikanpada Gambar 5.6, Semaphore yang kuat menjamin kebebasan dari kelaparan, sementaraSemaphore lemah melakukan not.We akan menganggap Semaphore kuat karena mereka lebihnyaman dan karena ini adalah bentuk semaphore biasanya disediakan oleh operasisistem.Reksa PengecualianGambar 5.6 menunjukkan solusi mudah untuk masalah mutual exclusion menggunakansemaphore s (bandingkan Gambar 5.1). Pertimbangkan proses n, diidentifikasi dalam P array (i),semua yang memerlukan akses ke sumber daya yang sama. Setiap proses memiliki bagian kritisdigunakan untuk mengakses sumber daya. Dalam setiap proses, sebuah semWait (s) dieksekusi sebelumyang penting bagian. Jika nilai dari s menjadi negatif, proses tersebut akan diblokir. Jikanilai 1, maka adalah decremented ke 0 dan proses segera memasuki criticalbagian, karena s tidak lagi positif, tidak ada proses lain akan dapat masuk nyakritis bagian.Semafor diinisialisasi ke 1. Dengan demikian, proses pertama yang mengeksekusisemWait akan dapat memasuki critical section segera, pengaturan nilai ske 0. Setiap proses lain mencoba untuk memasuki critical section akan merasa sibuk danakan diblokir, pengaturan nilai s ke -1. Setiap jumlah proses mungkin mencobaentri; setiap hasil usaha tersebut tidak berhasil dalam pengurangan lebih lanjut dari nilais.When proses yang awalnya memasuki bagian kritis berangkat, s bertambah224 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi/ * Program * mutualexclusion /const int n = / * jumlah proses * /;semaphore s = 1;

kekosongan P (int i){sementara (benar) {semWait (s);/ * Critical section * /;semSignal (s);/ * Sisanya * /;}}void main (){parbegin (P (1), P (2), P (n)...);}Gambar 5.6 Pengecualian Reksa Menggunakan SemaphoreM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 2245,3 / Semaphore 225dan salah satu proses yang diblokir (jika ada) akan dihapus dari antrian diblokirproses yang terkait dengan semaphore dan dimasukkan ke dalam state.When Siap itu berikutnyadijadwalkan oleh OS, mungkin memasuki critical section.Gambar 5.7, berdasarkan satu di [BACO03], menunjukkan urutan yang mungkin selama tigaproses menggunakan disiplin saling pengecualian dari Gambar 5.6. Dalam contoh ini tigaproses (A, B, C) mengakses sumber daya bersama dilindungi oleh kunci semaphore. ProsesSebuah mengeksekusi semWait (kunci), karena semaphore memiliki nilai 1 pada saatoperasi semWait, A dapat langsung memasuki bagian kritis dan semaphore yangberlangsung pada 0.While nilai A dalam critical section, baik B dan C melakukansemWait operasi dan yang diblokir menunggu ketersediaan semafor.Ketika A critical section keluar dan melakukan semSignal (kunci), B, yang merupakanproses pertama dalam antrian, sekarang dapat memasuki critical section.Program Gambar 5.6 dapat sama baiknya menangani persyaratan yang lebihdari satu proses diperbolehkan dalam critical section pada persyaratan time.This terpenuhihanya dengan menginisialisasi semafor dengan nilai tertentu. Jadi, setiap saat, yangnilai s.count dapat diartikan sebagai berikut:• s.count> 0: s.count adalah jumlah proses yang dapat mengeksekusi semWait (s)tanpa suspensi (jika tidak semSignal (s) dijalankan untuk sementara). Sepertisituasi akan memungkinkan Semaphore untuk mendukung sinkronisasi serta salingpengecualian.BC BC1100? 1? 1? 2semWait (kunci)SebuahNilai

semaphore kunciAntrian untuksemafor kunci B CsemSignal (kunci)semSignal (kunci)semSignal (kunci)semWait (kunci)semWait (kunci)KritisdaerahNormaleksekusiDiblokir padatiang sinyalkunciPerhatikan bahwa yang normaleksekusi dapatdilanjutkan secara paraleltapi itu pentingdaerah adalah serial.Gambar 5.7 Proses Mengakses data Bersama Dilindungi oleh Semafor suatu

226 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi

• s.count <0: Besarnya s.count adalah jumlah proses disuspensikan dalams.queue.Masalah Produser / KonsumenKami sekarang memeriksa salah satu masalah yang paling umum yang dihadapi dalam pengolahan konkuren:produsen / konsumen problem.The pernyataan umum adalah ini: ada satu ataulebih produsen menghasilkan beberapa jenis data (catatan, karakter) dan menempatkanini di buffer.There adalah konsumen tunggal yang mengambil barang-barang keluar dari buffer satupada suatu waktu. Sistem ini harus dibatasi untuk mencegah tumpang tindih operasi buffer.Artinya, hanya satu agen (produsen atau konsumen) dapat mengakses buffer pada setiapsatu masalah time.The adalah untuk memastikan bahwa produsen tidak akan mencoba untuk menambahkan data ke dalambuffer jika itu penuh dan bahwa konsumen tidak akan mencoba untuk menghapus data dari kosongbuffer.We akan melihat sejumlah solusi untuk masalah ini untuk menggambarkan baikdaya dan perangkap Semaphore.Untuk memulai, mari kita asumsikan bahwa buffer tidak terbatas dan terdiri dari sebuah array linierelemen. Dalam istilah abstrak, kita dapat mendefinisikan fungsi produsen dan konsumensebagai berikut:produser: konsumen:sementara (benar) {while (true) {/ * Menghasilkan barang v * /, sedangkan (di <keluar =)b [di] = v; / * melakukan apa-apa * /;di + +; w = b [keluar];

Keluar} + +;/ * Item mengkonsumsi w * /;}Gambar 5.8 mengilustrasikan struktur penyangga b. Produsen dapat menghasilkanitem dan menyimpannya dalam buffer dengan kecepatan sendiri. Setiap kali, indeks (dalam) kebuffer bertambah. Hasil konsumen dengan cara yang sama tetapi haruspastikan bahwa itu tidak berusaha untuk membaca dari buffer kosong. Oleh karena itu,226 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasib [1] b [2]Keluarb [3] b [4] b [5]0 1 2 3 4DalamCatatan: Area Berbayang menunjukkan sebagian dari buffer yang ditempatiGambar 5.8 Buffer Tak Terbatas untukProdusen / Konsumen SoalAnimasi:Produsen / KonsumenM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 2265,3 / Semaphore 227konsumen memastikan bahwa produsen telah maju di luar itu (di luar>) sebelummelanjutkan.Mari kita mencoba untuk menerapkan sistem ini menggunakan Semaphore biner. Gambar 5.9 adalahpertama mencoba. Daripada berurusan dengan indeks masuk dan keluar, kami hanya dapat melacakjumlah item dalam buffer, dengan menggunakan variabel integer n (= dalam - keluar). Paras semaphore digunakan untuk menegakkan saling pengecualian; penundaan semaphore digunakan untukmemaksa konsumen untuk semWait jika buffer kosong.Solusi ini tampaknya agak mudah. Produsen bebas untuk menambahbuffer setiap saat. Ia melakukan semWaitB (s) sebelum menambahkan dansemSignalB (s) setelahnya untuk mencegah konsumen atau produsen lainnya darimengakses buffer selama operasi append. Juga, sementara di bagian kritis,kelipatannya produser nilai dari n. Jika n = 1, maka buffer itu kosong hanya sebelumuntuk menambahkan ini, sehingga produsen melakukan semSignalB (delay) untuk mengingatkan konsumenini konsumen fact.The dimulai dengan menunggu untuk item pertama yang akan diproduksi,menggunakan semWaitB (delay). Ini kemudian mengambil item dan decrements n dalam critical section.Jika produsen dapat tetap di depan konsumen (situasi umum),maka konsumen akan jarang blok pada penundaan semaphore karena n biasanya akanmenjadi positif. Oleh karena itu kedua produsen dan konsumen berjalan lancar./ * Program producerconsumer * /int n;binary_semaphore s = 1, delay = 0;

kekosongan produser (){sementara (benar) {menghasilkan ();semWaitB (s);append ();n + +;if (n == 1) semSignalB (delay);semSignalB (s);}}kekosongan konsumen (){semWaitB (delay);sementara (benar) {semWaitB (s);mengambil ();n -;semSignalB (s);mengkonsumsi ();if (n == 0) semWaitB (delay);}}void main (){n = 0;parbegin (produsen, konsumen);

konsumen memastikan bahwa produsen telah maju di luar itu (di luar>) sebelummelanjutkan.Mari kita mencoba untuk menerapkan sistem ini menggunakan Semaphore biner. Gambar 5.9 adalahpertama mencoba. Daripada berurusan dengan indeks masuk dan keluar, kami hanya dapat melacakjumlah item dalam buffer, dengan menggunakan variabel integer n (= dalam - keluar). Paras semaphore digunakan untuk menegakkan saling pengecualian; penundaan semaphore digunakan untukmemaksa konsumen untuk semWait jika buffer kosong.Solusi ini tampaknya agak mudah. Produsen bebas untuk menambahbuffer setiap saat. Ia melakukan semWaitB (s) sebelum menambahkan dansemSignalB (s) setelahnya untuk mencegah konsumen atau produsen lainnya darimengakses buffer selama operasi append. Juga, sementara di bagian kritis,kelipatannya produser nilai dari n. Jika n = 1, maka buffer itu kosong hanya sebelumuntuk menambahkan ini, sehingga produsen melakukan semSignalB (delay) untuk mengingatkan konsumenini konsumen fact.The dimulai dengan menunggu untuk item pertama yang akan diproduksi,menggunakan semWaitB (delay). Ini kemudian mengambil item dan decrements n dalam

critical section.Jika produsen dapat tetap di depan konsumen (situasi umum),maka konsumen akan jarang blok pada penundaan semaphore karena n biasanya akanmenjadi positif. Oleh karena itu kedua produsen dan konsumen berjalan lancar./ * Program producerconsumer * /int n;binary_semaphore s = 1, delay = 0;kekosongan produser (){sementara (benar) {menghasilkan ();semWaitB (s);append ();n + +;if (n == 1) semSignalB (delay);semSignalB (s);}}kekosongan konsumen (){semWaitB (delay);sementara (benar) {semWaitB (s);mengambil ();n -;semSignalB (s);mengkonsumsi ();if (n == 0) semWaitB (delay);}}void main (){n = 0;parbegin (produsen, konsumen);}Gambar 5.9 Sebuah Solusi Salah ke Buffer Tak Terbatas-Produsen / Konsumen SoalMenggunakan Semaphore BinerM05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 227228 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasiAda, bagaimanapun, sebuah cacat dalam hal ini program.When konsumen telah habisbuffer, perlu untuk me-reset semaphore keterlambatan sehingga akan dipaksa untuk menunggusampai produser telah menempatkan item dalam buffer. Ini adalah tujuan daripernyataan: jika n == 0 semWaitB (delay). Pertimbangkan skenario yang diuraikan dalamTabel 5.4. Pada baris 14, konsumen gagal untuk mengeksekusi operasi semWaitB. Parakonsumen memang knalpot buffer dan set n untuk 0 (baris 8), namun produsentelah bertambah n sebelum konsumen dapat mengujinya dalam baris 14. Hasilnya adalahsemSignalB tidak diimbangi dengan semWaitB sebelumnya. Nilai -1 untuk n pada baris 20berarti bahwa konsumen telah dikonsumsi item dari buffer yang tidakada. Ini tidak akan melakukan hanya untuk memindahkan pernyataan kondisional dalam

kritisbagian dari konsumen karena ini dapat menyebabkan kebuntuan (misalnya, setelah baris 8 daritabel).Perbaikan untuk masalah ini adalah untuk memperkenalkan variabel bantu yang dapat diatur dalamkonsumen penting bagian untuk digunakan di kemudian hari. Hal ini ditunjukkan pada Gambar 5.10. Sebuah hati-hatijejak logika harus meyakinkan Anda bahwa kebuntuan dapat tidak lagi terjadi.Tabel 5.4 Skenario Kemungkinan untuk Program Gambar 5.9Produsen Konsumen s n Keterlambatan1 1 0 02 semWaitB (s) 0 0 03 n + + 0 1 04 if (n == 1)(SemSignalB (delay)) 0 1 15 semSignalB (s) 1 1 16 semWaitB (delay) 1 1 07 semWaitB (s) 0 1 08 n - 0 0 09 semSignalB (s) 1 0 010 semWaitB (s) 0 0 011 n + + 0 1 012 if (n == 1)(SemSignalB (delay)) 0 1 113 semSignalB (s) 1 1 114 if (n == 0) (semWaitB (delay)) 1 1 115 semWaitB (s) 0 1 116 n - 0 0 117 semSignalB (s) 1 0 118 if (n == 0) (semWaitB (delay)) 1 0 019 semWaitB (s) 0 0 020 n - 0 -1 021 semiSignlaB (s) 1 -1 0CATATAN: Putih mewakili daerah bagian kritis dikendalikan oleh semaphore s.

Ada, bagaimanapun, sebuah cacat dalam hal ini program.When konsumen telah habisbuffer, perlu untuk me-reset semaphore keterlambatan sehingga akan dipaksa untuk menunggusampai produser telah menempatkan item dalam buffer. Ini adalah tujuan daripernyataan: jika n == 0 semWaitB (delay). Pertimbangkan skenario yang diuraikan dalamTabel 5.4. Pada baris 14, konsumen gagal untuk mengeksekusi operasi semWaitB. Parakonsumen memang knalpot buffer dan set n untuk 0 (baris 8), namun produsentelah bertambah n sebelum konsumen dapat mengujinya dalam baris 14. Hasilnya adalahsemSignalB tidak diimbangi dengan semWaitB sebelumnya. Nilai -1 untuk n pada baris 20berarti bahwa konsumen telah dikonsumsi item dari buffer yang tidakada. Ini tidak akan melakukan hanya untuk memindahkan pernyataan kondisional dalam kritisbagian dari konsumen karena ini dapat menyebabkan kebuntuan (misalnya, setelah baris 8

daritabel).Perbaikan untuk masalah ini adalah untuk memperkenalkan variabel bantu yang dapat diatur dalamkonsumen penting bagian untuk digunakan di kemudian hari. Hal ini ditunjukkan pada Gambar 5.10. Sebuah hati-hatijejak logika harus meyakinkan Anda bahwa kebuntuan dapat tidak lagi terjadi.Tabel 5.4 Skenario Kemungkinan untuk Program Gambar 5.9Produsen Konsumen s n Keterlambatan1 1 0 02 semWaitB (s) 0 0 03 n + + 0 1 04 if (n == 1)(SemSignalB (delay)) 0 1 15 semSignalB (s) 1 1 16 semWaitB (delay) 1 1 07 semWaitB (s) 0 1 08 n - 0 0 09 semSignalB (s) 1 0 010 semWaitB (s) 0 0 011 n + + 0 1 012 if (n == 1)(SemSignalB (delay)) 0 1 113 semSignalB (s) 1 1 114 if (n == 0) (semWaitB (delay)) 1 1 115 semWaitB (s) 0 1 116 n - 0 0 117 semSignalB (s) 1 0 118 if (n == 0) (semWaitB (delay)) 1 0 019 semWaitB (s) 0 0 020 n - 0 -1 021 semiSignlaB (s) 1 -1 0CATATAN: Putih mewakili daerah bagian kritis dikendalikan oleh semaphore s.M05_STAL6329_06_SE_C05.QXD 2/21/08 09:25 Halaman 2285,3 / Semaphore 229/ * Program producerconsumer * /int n;binary_semaphore s = 1, delay = 0;kekosongan produser (){sementara (benar) {menghasilkan ();semWaitB (s);append ();n + +;if (n == 1) semSignalB (delay);semSignalB (s);}}kekosongan konsumen ()

{int m; / * variabel lokal * /semWaitB (delay);sementara (benar) {semWaitB (s);mengambil ();n -;m = n;semSignalB (s);mengkonsumsi ();if (m == 0) semWaitB (delay);}}void main (){n = 0;parbegin (produsen, konsumen);}Gambar 5.10 Sebuah Solusi untuk Masalah Benar-Buffer Tak Terbatas Produsen / Konsumen MenggunakanBinary SemaphoreSebuah solusi yang agak bersih bisa diperoleh jika Semaphore umum (jugadisebut menghitung Semaphore) digunakan, seperti yang ditunjukkan pada Gambar variabel 5.11.The n sekarangsemaphore. Nilainya masih sama dengan jumlah item di dalam buffer. Mendugasekarang bahwa dalam transkrip program ini, kesalahan dibuat dan operasisemSignal (s) dan semSignal (n) adalah interchanged.This akan memerlukan bahwasemSignal (n) operasi dilakukan pada bagian kritis produser tanpainterupsi oleh konsumen atau lain producer.Would ini mempengaruhi program?Tidak, karena konsumen harus menunggu pada kedua Semaphore sebelum melanjutkan dalam setiapkasus.Sekarang anggaplah bahwa semWait (n) dan semWait (s) operasi secara tidak sengajaterbalik. Ini menghasilkan, yang serius memang fatal, cacat. Jika konsumenpernah memasuki critical section bila buffer kosong (n.count = 0), maka produser tidak adapernah bisa append ke buffer dan sistem jalan buntu. Ini adalah yang baikcontoh kehalusan Semaphore dan kesulitan memproduksi benardesain.

230 BAB 5 / Concurrency: PENGECUALIAN SALING dan sinkronisasi/ * Program producerconsumer * /semafor n = 0, s = 1;kekosongan produser (){sementara (benar) {menghasilkan ();semWait (s);append ();

semSignal (s);semSignal (n);}}kekosongan konsumen (){sementara (benar) {semWait (n);semWait (s);mengambil ();semSignal (s);mengkonsumsi ();}}void main (){parbegin (produsen, konsumen);}Gambar 5.11 Sebuah Solusi untuk Masalah Tak Terbatas-Buffer Produsen / Konsumen Menggunakan Semaphoreb [1] b [2]keluarb [3] b [4] b [5] b [n]dalamb [1] b [2]dalamb [3] b [4] b [5] b [n]keluar(a)(b)Gambar 5.12 Edaran Buffer terbatas untukProdusen / Konsumen