Penjelasan Semaphore
Semaphore adalah salah satu cara menangani critical section, yang dikemukakan
oleh Dijkstra. Prinsip semaphore sebagai berikut:
Dua proses atau lebih dapat bekerja sama dengan menggunakan penandapenanda sederhana. Proses dipaksa berhenti sampai proses memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan penanda yang sesuai kebutuhannya. Variabel khusus untuk penandan ini disebut semaphore. Semaphore mempunyai dua property, yaitu :
1. Semaphore dapat diinisialisasi dengan nilai nonnegative.
2. Terdapat dua operasi terhadap semaphore yaitu Down dan Up. Nama asli yang disampaikan Dijkstra adalah operasi P dan V.
Semaphore S merupakan variabel bertipe integer yang diakses dengan 2 standar operasi atomic, yaitu wait dan signal. Operasi-operasi ini diwakili dengan P (wait) dan V (signal) sebagai berikut:
wait(S) : while S £ 0 do no_op;
S:=S – 1;
signal(S) : S:=S+1;
Misalkan ada 2 proses yang sedang berjalan secara konkuren, yaitu P1 dengan pernyataan S1 dan P2 dengan pernyataan S2. Andaikan kita mengharapkan S2 baru akan dijalankan hanya setelah S1 selesai. Hal ini dapat dilakukan dengan menggunakan bantuan semaphore synch (dengan nilai awal =0) yang akan di-share oleh kedua proses.
Untuk Proses P 1 :
S1;
signal(synch);
Untuk proses P2 :
wait(synch);
S2;
Karena nilai awal untuk synch adalah nol, maka P2 akan mengeksekusi S2 hanya setelah P1 mengerjakan signal (synch) setelah S1. Salah satu kerugian dari penggunaan semaphore diatas adalah adanya busy waiting. Apabila suatu proses menempati critical section, dan ada proses lain yang ingin masuk critical section, maka akan terjadi iterasi secara terus -menerus pada entry section. Hal ini akan menimbulkan masalah pada sistem yang menggunakan konsep multiprogramming.
Untuk menghindari busy waiting, dilakukan modifikasi pada operasi wait dan signal. Jika suatu proses sedang mengeksekusi operasi wait, maka nilai semaphore menjadi tidak positif. Pada saat ini proses akan memblok dirinya (block ) dan ditempatkan pada waiting queue. Proses yang sedang diblok akan menunggu hingga semaphore S direstart, yaitu pada saat beberapa proses yang lain mengeksekusi operasi signal. Suatu proses akan direstart dengan operasi wakeup, yang akan mengubah proses dari keadaan waiting ke ready.
Untuk mengimplmentasikan hal ini, semaphore dirancang dalam bentuk record :
type semaphore= Record
value : integer;
L: list of process;
end;
Var s: semaphore
Operasi-operasi pda semaphore;
wait(S) S.value :=S.value-1;
if S.value < 0 then
Begin
Tambahkan proses ini ke S.L.
block;
end;
Algoritma Semaphore Dijkstra
Model untuk algoritma Dijkstra semaphore dengan menggunakan rendevous
adalah sebagai berikut :
#define p 0
#define v 1
chan sema = [0] of { bit };
proctype dijkstra()
{ byte count = 1;
do
:: (count == 1) -> sema!p; count = 0
:: (count == 0) -> sema? v; count = 1
od
}
proctype user()
{ do
:: sema? p;
/* critical section */
sema!v;
/* non-critical section */
od
}
init
{ run dijkstra(); run user();
run user(); run user()
}
Algoritma Semaphore Dijkstra
Model untuk algoritma Dekker adalah sebagai berikut :
Bit x, y; /* signal masuk/keluar dari section */
byte mutex; /* # proses yang masuk critical section. */
byte turn,A_TURN,B_TURN; /* giliran siapa? */
active proctype A() {
x = 1;
turn = B_TURN;
(y == 0 || turn == A_TURN);
mutex++;
mutex–;
x = 0;
}
active proctype B() {
y = 1;
turn = A_TURN;
(x == 0 || turn == B_TURN);
mutex++;
mutex–;
y = 0;
}
active proctype monitor() {
assert(mutex != 2);
}
Algoritma Semaphore Peterson
Model untuk algoritma 3 (Peterson) adalah sebagai berikut :
#define true 1
#define false 0
bool flag[2];
bool turn;
proctype user(bool i)
{ flag[i] = true;
turn = i;
(flag[1-i] == false || turn == 1-i);
crit: skip; /* critical section */
flag[i] = false
}
init { atomic { run user(0); run user(1) } }
Penjelasan lebih Lanjut
1. Konsep Dasar Semaphore
Semaphore termasuk pendekatan yang diajukan oleh Djikstra, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.Semaphore mempunyai dua sifat, yaitu:
Semaphore dapat diinisialisasi dengan nilai non-negatif.
Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.
Semaphore adalah salah satu teknik sinyal sederhana, dan merupakan konsep penting dalam OS desain, dimana sebuah nilai integer digunakan untuk pensinyalan antara proses. Hanya tiga operasi yang mungkin dilakukan pada semaphore, yang semuanya atom: inisialisasi, penurunan, dan penaikan. Operasi pengurangan dapat mengakibatkan terhalangnya proses, dan kenaikan dari pengoperasian yang sedang berlangsung dapat mengakibatkan terblokirnya suatu proses. Hal ini juga dikenal sebagai sebuah perhitungan semaphore atau semaphore umum.
Semaphore adalah bendera digunakan untuk memeriksa apakah sumber daya saat ini sedang digunakan oleh thread atau proses. Misalnya, jika suatu proses ingin menggunakan printer, terlebih dahulu perlu memastikan printer tersedia dengan memeriksa untuk melihat apakah semaphore telah ditetapkan. jika sudah diatur, maka perlu menunggu untuk proses yang saat ini telah selesai. Namun, jika printer bebas, proses ini akan menetapkan semaphore dan mulai menggunakan printer, memblokir akses ke semua proses lainnya sampai selesai.
Semaphore adalah teknik klasik untuk melindungi bagian penting dari kode dari yang secara simultan dieksekusi oleh lebih dari satu thread. Semaphore adalah generalisasi dari monitor. Sebuah monitor memungkinkan hanya satu thread untuk mengunci objek sekaligus. Semaphore A N memungkinkan proses. Proses meraih semaphore-eksklusif untuk menggunakan semi disebut menenggak semaphore karena mereka diimplementasikan dengan integer Countdown yang decrements untuk setiap kunci dan kenaikan untuk masing-masing membuka. Jika semaphore adalah sepenuhnya terisi, thread baru ingin menggunakannya akan menunggu sampai thread beberapa rilis kunci dengan upping semaphore itu. Untuk semaphore untuk bekerja, cek untuk penuh, dan penurunan harus dilakukan semua dalam satu instruksi yang tidak pernah terputus atom. Instruksi monitor JVM menyediakan dukungan hardware yang diperlukan untuk mensimulasikan semaphores.
Semaphore s, lain kontribusi penting oleh EW Dijkstra, dapat dilihat sebagai ekstensi untuk mutex kunci. Semaphore adalah suatu obyek dengan dua metode Tunggu dan Sinyal, sebuah integer swasta counter dan antrian swasta (benang). Semantik dari semaphore adalah sangat sederhana. Misalkan S adalah semaphore yang swasta counter telah diinisialisasi ke integer non-negatif.
Ketika Tunggu dijalankan oleh thread, kita memiliki dua kemungkinan:
Penghitung S adalah positif
Dalam hal ini, konter ini mengalami penurunan sebesar 1 dan benang kembali pelaksanaannya.
Penghitung S adalah nol
Dalam hal ini, benang ditangguhkan dan dimasukkan ke dalam antrian pribadi S.
Ketika Sinyal dijalankan oleh thread, kami juga memiliki dua kemungkinan:
Antrian S tidak memiliki benang menunggu
Penghitung S ditingkatkan oleh satu dan benang kembali pelaksanaannya.
Antrian S telah menunggu threads
Dalam hal ini, konter S harus nol (lihat pembahasan Tunggu di atas). Salah satu benang menunggu akan diizinkan untuk meninggalkan antrian dan melanjutkan pelaksanaannya. Benang yang mengeksekusi Sinyal juga terus.
Operasi Tunggu atau Signal adalah atom. Ini berarti sekali kegiatan Tunggu mulai (yaitu, pengujian dan penurunan nilai counter dan memasukkan benang ke dalam antrian), mereka akan terus sampai akhir tanpa gangguan apapun. Lebih tepatnya, meskipun ada banyak langkah untuk melaksanakan Tunggu dan Signal, langkah-langkah ini dianggap sebagai instruksi non-interruptible tunggal. Demikian pula, hal yang sama berlaku untuk Sinyal. Apalagi, jika lebih dari satu benang mencoba mengeksekusi Tunggu (atau sinyal), hanya satu dari mereka akan berhasil. Kita tidak boleh membuat asumsi tentang mana thread akan berhasil.
Tunggu karena dapat menyebabkan thread untuk memblokir (yaitu, ketika counter nol), ia memiliki efek yang sama dari operasi kunci dari sebuah kunci mutex. Demikian pula, sebuah sinyal dapat melepaskan benang tunggu, dan mirip dengan membuka operasi. Bahkan, semaphores dapat digunakan sebagai kunci mutex. Pertimbangkan S semaphore dengan nilai awal 1. Kemudian, Tunggu dan Signal sesuai untuk mengunci dan membuka:
Mari kita periksa bagaimana sepasang Tunggu dan Signal dapat menjamin pengecualian bersama. Perlu diingat bahwa nilai awal counter dari S adalah 1. Misalkan sejumlah benang mencoba untuk eksekusi Tunggu. Karena hanya ada satu thread berhasil dapat mengeksekusi Tunggu, thread ini, katakanlah A, menyebabkan counter berkurang sebesar 1, dan memasuki bagian yang kritis. Karena nilai awal counter adalah 1, sekali thread A memasuki critical section, konter menjadi 0, dan, sebagai hasilnya, semua usaha berikutnya dalam melaksanakan Tunggu akan diblokir. Oleh karena itu, membenarkan klaim kita bahwa Tunggu mirip untuk mengunci.
Ketika Sebuah thread keluar dari critical section, Sinyal dijalankan. Jika ada menunggu benang, salah satu dari mereka akan dirilis, dan thread ini dirilis memasuki critical section. Perhatikan bahwa counter masih nol (karena, dalam hal ini, Sinyal tidak meningkatkan dan Tunggu tidak mengurangi counter), yang berarti semua thread berikutnya yang mencoba mengeksekusi Tunggu diblokir. Di sisi lain, jika tidak ada benang menunggu, pelaksanaan Sinyal menyebabkan nilai dari counter akan meningkat dengan 1, sehingga nilai saat ini 1. Dalam hal ini, thread berikutnya yang mengeksekusi Tunggu bisa masuk ke bagian kritis. Oleh karena itu, Sinyal mirip untuk membuka. Singkatnya, kita belajar bahwa pengaturan counter untuk 1 awalnya akan menjamin bahwa paling banyak satu thread bisa di bagian kritis, jika semua benang yang melibatkan mengikuti Tunggu sama – urutan Sinyal.
Jika Anda berhati-hati, Anda akan melihat bahwa nilai counter adalah 1 atau 0, dan tidak pernah memiliki nilai lain. Oleh karena itu, disebut sebagai semaphore biner. Jika kita mengganti counter dengan variabel Boolean dan menafsirkan 1 dan 0 sebagai benar (yaitu, kunci terbuka) dan false (yaitu, kunci tertutup), masing-masing, maka semaphore biner menjadi kunci mutex! Karena itu, Anda dapat menggunakan kunci mutex atau semaphore biner bergantian.
Namun, keindahan menggunakan semaphores adalah bahwa nilai awal tidak harus 1. Bisa jadi ada nilai non-negatif. Kemudian kita akan membahas teknik-teknik lain semaphores menggunakan.
Kemajuan besar pertama dalam menangani masalah proses konkuren datang pada tahun 1965 dengan risalah Dijkstra [DIJK65]. Dijkstra prihatin dengan desain dari OS sebagai kumpulan proses sekuensial dan bekerja sama dengan pembangunan mekanisme yang efisien dan dapat diandalkan untuk mendukung kerja sama. Mekanisme ini hanya bias mudah digunakan oleh proses pengguna jika prosesor dan OS membuat mekanisme yang tersedia.
[DOWN07] menunjukkan tiga konsekuensi menarik dari definisi semaphore:
• Secara umum, tidak ada cara untuk mengetahui sebelum proses decrement semaphore sebuah akan terblokir atau tidak.
• Setelah proses increment semaphore dan proses lain akan berjalan, kedua proses terus berjalan bersamaan. Tidak ada cara untuk mengetahui proses, jika salah satu, akan segera melanjutkan pada sistem prosesor tunggal.
• Saat sinyal Anda semaphore, Anda tidak perlu tahu apakah proses yang lain sedang menunggu, sehingga jumlah proses yang diblokir mungkin nol atau satu.
Konsep Dasar Monitor
Monitor termasuk kumpulan prosedur, variabel dan struktur data di satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur yang dideklarasikan minitor untuk mengakses struktur internal.
Java menggunakan monitor ke benang koordinasi untuk memastikan mereka tidak tersandung saling mengakses data yang sama. Dengan monitor, Anda mengunci obyek, bagian-bagian penting dari kode atau Anda mengunci seluruh metode dengan menyatakan mereka disinkronisasi. Monitor memiliki dukungan hardware test dan mengatur di belakang mereka untuk memastikan cek thread untuk melihat apakah monitor sudah dikunci dan jika tidak, menyita mengunci semua dalam satu operasi atom non-interruptible. Tanpa atomicity, thread mungkin periksa apakah monitor tidak terkunci, dan memiliki beberapa thread lain ambil monitor sebelum mendapat kesempatan untuk menguncinya. Puritan akan menunjukkan bahwa monitor sebenarnya bukan kunci, melainkan kunci adalah cara yang digunakan untuk melindungi bagian penting dari kode.
Monitor Sebuah bahasa pemrograman membangun yang merangkum variabel, prosedur akses dan inisialisasi kode dalam suatu variabel tipe data abstrak. Monitor hanya dapat diakses melalui prosedur akses dan hanya satu proses yang dapat secara aktif mengakses monitor dalam satu waktu. Prosedur-prosedur pengaksesan adalah bagian penting. Dimana monitor mungkin memiliki antrian proses-proses yang sedang menunggu untuk mengaksesnya.
Anda mungkin mendapatkan pengalaman dari belajar semua contoh semaphore bahwa sinyal dan menunggu panggilan masih dapat tersebar di mana-mana dalam program anda dengan cara yang tidak terlalu terstruktur dengan baik. Jika Anda benar-benar mendapatkan seperti perasaan, konsep monitor datang untuk menyelamatkan. Konsep monitor berasal dari 1974 kertas CAR Hoare’s.
Sebuah monitor memiliki empat komponen seperti yang ditunjukkan di bawah ini: inisialisasi, data pribadi, prosedur memonitor, dan antrian masuk monitor. Komponen inisialisasi berisi kode yang digunakan tepat satu kali ketika monitor dibuat, Bagian data pribadi berisi semua data pribadi, termasuk prosedur swasta, yang hanya dapat digunakan dalam monitor. Dengan demikian, barang-barang pribadi tidak terlihat dari luar monitor. Prosedur monitor prosedur yang dapat dipanggil dari luar monitor. Antrian entri memantau berisi semua thread yang disebut prosedur monitor tapi belum diberikan izin. Kita akan kembali ke ini segera.
Oleh karena itu, monitor terlihat seperti kelas dengan inisialisasi, data pribadi dan prosedur monitor sesuai dengan konstruktor, data pribadi dan metode kelas tersebut. Satu-satunya perbedaan utama adalah bahwa kelas tidak memiliki antrian masuk.
Monitor yang seharusnya digunakan dalam lingkungan multithreaded atau multiproses di mana beberapa thread / proses dapat menghubungi prosedur monitor pada saat yang sama meminta layanan. Dengan demikian, monitor menjamin bahwa setiap saat paling banyak satu thread bisa mengeksekusi dalam monitor! Apa artinya ini? Ketika thread panggilan prosedur monitor, kita dapat melihat prosedur monitor disebut sebagai perpanjangan ke thread panggilan. Jika prosedur monitor disebut dalam eksekusi, kita akan mengatakan thread memanggil di monitor melaksanakan prosedur monitor disebut.
Sekarang, jika dua thread di monitor (yaitu, mereka adalah melaksanakan dua, mungkin, monitor prosedur yang sama), beberapa data pribadi dapat dimodifikasi oleh kedua benang pada saat yang sama menyebabkan kondisi ras terjadi. Oleh karena itu, untuk menjamin keutuhan data pribadi, monitor saling memberlakukan pengecualian implisit. Lebih tepatnya, jika thread panggilan prosedur monitor, thread ini akan diblokir jika ada thread lain eksekusi pada monitor. Mereka benang yang tidak diberikan izin masuk akan antri masuk ke antrian monitor luar monitor. Ketika monitor menjadi kosong (yaitu, tidak ada thread mengeksekusi di dalamnya), salah satu benang dalam antrian entri akan dirilis dan diberikan izin untuk menjalankan prosedur monitor disebut. Meskipun kita mengatakan “antrian masuk,” Anda tidak harus melihat secara harfiah. Lebih tepatnya, ketika thread harus dilepaskan dari antrian masuk, Anda tidak perlu menganggap kebijakan apapun yang thread yang akan dirilis.
Secara ringkas, monitor memastikan saling eksklusi otomatis sehingga tidak ada lebih dari satu thread bisa mengeksekusi dalam memonitor setiap saat. Ini adalah kemampuan yang sangat usably dan berguna.
Monitor sebagai Mini-OS
Konsep monitor sangat mirip dengan sebuah sistem operasi. Satu dapat mempertimbangkan inisialisasi sebagaimana data yang diinisialisasi ketika sistem boot up, data pribadi dan kode sebagai struktur data internal dan fungsi dari sebuah sistem operasi, dan prosedur monitor sebagai panggilan sistem. Program-program, tentu saja, benang yang membuat permintaan layanan. Oleh karena itu, monitor bisa dianggap sebagai mini-OS dengan layanan terbatas.
2. Persamaan dan perbedaannya:
Sejak menunggu operasi sinyal pada semaphores dan pada monitor kondisi variabel yang sama, untuk membantu Anda membedakan perbedaan mereka dan menggunakannya dengan benar, berikut ini adalah perbandingan singkat.Semaphore Monitor – Kondisi Variabel
Dapat digunakan di mana saja dalam program, tetapi seharusnya tidak digunakan dalam monitor Hanya dapat digunakan pada monitor
Wait() tidak selalu memblokir pemanggil (yaitu, ketika counter semaphore lebih besar dari nol). Wait() selalu blok pemanggil.
Signal() baik melepaskan thread yang diblokir, jika ada satu, atau meningkatkan semaphore counter. Signal() baik melepaskan thread yang diblokir, jika ada satu, atau sinyal hilang seolah-olah itu tidak pernah terjadi.
Jika Signal () melepaskan thread yang diblokir, pemanggil dan thread dirilis & keduanya melanjutkan. Jika Signal () melepaskan thread yang diblokir, pemanggil hasil monitor (tipe Hoare) atau terus (Mesa Type). Hanya satu dari pemanggil atau threadyang dirilis dapat melanjutkan, tapi tidak keduanya.
Perbedaan:
operasi semaphore tersebar pada seluruh section program
pada monitor, sinkronosasi dikendalikan oleh prosedur tertentu, dimana shared data hanya bisa diakses melalui prosedur tersebut
dalam penggunaan semaphore mungkin timbul kesalahan yang sulit terdeteksi (misal: deadlock), yang dicegah oleh monitor
Di samping itu, sinyal operasi menunggu kondisi variabel monitor mirip dengan P dan operasi V pada perhitungan semaphores. Sebuah pernyataan tunggu dapat memblokir proses itu eksekusi, sedangkan pernyataan sinyal dapat menyebabkan proses lain menjadi diblokir. Namun, ada beberapa perbedaan di antara mereka. Ketika sebuah proses mengeksekusi operasi P, tidak selalu menghalangi proses tersebut karena semaphore penghitungan mungkin lebih besar dari nol. Sebaliknya, ketika sebuah pernyataan menunggu dieksekusi, selalu blok proses. Saat tugas yang mengeksekusi operasi V pada semaphore, itu baik unblocks suatu tugas menunggu yang semaphore atau increment yang semaphore counter jika tidak ada tugas untuk membuka. Di sisi lain, jika suatu proses mengeksekusi pernyataan sinyal ketika tidak ada proses lain untuk membuka blokir, tidak ada efek pada variabel kondisi.
Perbedaan lain antara semaphores dan monitor adalah bahwa pengguna terbangun oleh operasi V dapat melanjutkan eksekusi tanpa penundaan. Sebaliknya, pengguna terbangun oleh operasi sinyal restart hanya ketika monitor terkunci.
Selain itu, solusi monitor terstruktur lebih banyak dari yang satu dengan semaphores karena data dan prosedur yang dikemas dalam satu modul tunggal dan bahwa pengecualian saling disediakan secara otomatis oleh pelaksanaannya.
3. Pengertian Deadlock dan Starvation beserta contohnya:
a) Deadlock
Deadlock secara bahasa berarti buntu atau kebuntuan. Dalam definisi lebih lengkap, deadlock berarti suatu keadaan dimana sistem seperti terhenti dikarenakan setiap proses memiliki sumber daya yang tidak bisa dibagi dan menunggu untuk mendapatkan sumber daya yang sedang dimiliki oleh proses lain. Keadaan seperti ini hanya dapat terjadi pada akses terhadap sumber daya yang tidak bisa dibagi atau non-sharable.
Contoh:
kasus ilustrasi dari kejadian deadlock pada dunia nyata, yaitu pada lalu lintas dijembatan. Dapat dilihat bahwa kedua mobil yang berada di tengah-tengah jembatan tidak dapat maju dan hanya
menunggu. Penyelesaian dari masalah tersebut adalah salah satu dari mobil tersebut mundur, sehingga mobil yang lain dapat maju. Mobil pada kasus ini adalah proses, sedangkan jembatan adalah sumber daya. Kedua mobil berebut untuk menggunakan sumber daya, namun karena sumber daya tersebut hanya dapat digunakan oleh satu proses saja, maka terjadilah deadlock.
Ilustrasinya:
ü Dua Proses, P1 dan P2
ü Dua Resource kritis R1 dan R2
ü Proses P1 dan P2 harus mengakses kedua sumber daya.
Kondisi berikut dapat terjadi : R1 diberikan ke P1, sedang R2 di berikan ke P2.
Karena untuk melanjutkan ekssekusi memerlukan sumber daya sekaligus maka kedua proses akan saling menunggu sumber daya yang lainnya, selamanya. Tidak ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena menunnggu sumber daya lain yang tidak pernah diperolehnya. Keduanya tidak membuat proses kemajuan apapaun, kedua proses tersebut dalam kondisi deadlock.
Kondisi deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semua yang terlibat tidak dapat mengakhiri prosesnya secara benar. Beragam mekanisme diusulkan untuk mengatasi kondisi deadlock.
b) Starvation
Ilustrasinya :
ü Terdapat tiga proses P1, P1, dan P3
ü P1, P2, dan P3 memerlukan pengaksesan sumber daya R secara periodik
Terjadi Skenario berikut:
ü P1 sedang di beri sumber daya R, P2, dan P3 Blocked menunggu sumber daya R.
ü Ketika P1 keluar daricritical section, P2 dan P3 diijinkan mengakse R.
ü Asumsi P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan ke P1 yang saat itu kembali membutuhkan sumber daya R.
Jika pemberian hak akses bergantian terus-menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R. meskipun tidak ada deadlock, pada sutuasi ini P2 mengalami starvation.
Untuk pemahaman lebih jelas, berikut detail dari penjelasannya:
Deadlock adalah situasi di mana dua atau lebih proses yang tidak dapat dilanjutkan karena masing-masing sedang menunggu satu yang lain untuk melakukan sesuatu.
Deadlock mengacu situasi di mana satu set dari dua atau lebih proses yang menunggu untuk anggota lain dimana diset untuk menyelesaikan operasi untuk memprosesnya, tapi tidak ada anggota yang mampu memproses. Deadlock adalah fenomena yang sulit untuk mengantisipasi, dan tidak ada solusi umum yang mudah untuk mengatasi masalah ini. Ada tiga pendekatan utama untuk berurusan dengan deadlock: pencegahan, penghindaran, dan deteksi.
Dalam Hal ini, dimungkinkan untuk dua atau lebih program yang akan menutup telepon menunggu satu sama lain. Sebagai contoh, dua program mungkin masing-masing memerlukan dua perangkat I / O untuk melakukan beberapa operasi (misalnya, disk untuk menyalin tape). Salah satu program telah
merebut kendali dari salah satu perangkat dan program lain yang memiliki kontrol dari perangkat lain. Setiap menunggu program lain untuk melepaskan sumber daya yang diinginkan. Deadlock tersebut mungkin tergantung pada waktu kesempatan alokasi sumber daya dan pelepasannya.
Prinsip-Prinsip Deadlock
Deadlock dapat didefinisikan sebagai memblokir permanen dari serangkaian proses yang baik bersaing untuk sumber daya sistem atau berkomunikasi satu sama lain. Satu set proses adalah jalan buntu ketika setiap proses dalam set diblokir menunggu suatu peristiwa (biasanya membebaskan beberapa sumber daya yang diminta) yang hanya dapat dipicu oleh lain diblokir proses dalam set. Deadlock adalah permanen karena tidak ada peristiwa yang pernah dipicu. Tidak seperti masalah lain dalam proses manajemen bersamaan, ada ada solusi efisien dalam kasus umum.
Semua kebuntuan melibatkan konflik akan kebutuhan sumber daya oleh dua atau lebih proses. Sebuah contoh umum adalah kebuntuan lalu lintas. Gambar 6.1a menunjukkan situasi di mana empat mobil telah tiba di sebuah simpang empat arah berhenti di kurang lebih sama waktu. Keempat kuadran dari persimpangan adalah sumber daya di mana kendali dibutuhkan. Secara khusus, jika semua empat mobil ingin pergi langsung melalui persimpangan itu, kebutuhan sumber daya adalah sebagai berikut:
• Mobil 1, bepergian ke utara, membutuhkan kuadran a dan b.
• Mobil 2, membutuhkan kuadran b dan c.
• Mobil 3, membutuhkan kuadran c dan d.
• Mobil 4, membutuhkan kuadran d dan a.
Aturan khas jalan di Amerika Serikat adalah bahwa mobil di halte empat arah harus menunda untuk mobil segera haknya. Aturan ini bekerja jika hanya ada dua atau tiga mobil di persimpangan. Misalnya, jika hanya utara dan arah barat mobil tiba di persimpangan, mobil utara akan menunggu dan mobil ke arah barat diterima. Namun, jika semua empat mobil tiba pada waktu yang sama, masing-masing akan menahan diri dari memasuki persimpangan, ini menyebabkan kebuntuan potensial. Kebuntuan ini hanya potensial, tidak aktual, karena sumber daya yang diperlukan tersedia untuk salah satu mobil untuk melanjutkan. Jika salah satu mobil akhirnya melanjutkan, maka yang lain juga dapat melanjutkannya.
Namun, jika semua empat mobil mengabaikan aturan dan lanjutkan (hati-hati) ke perempatan pada saat yang sama, maka setiap mobil merebut satu sumber daya (satu kuadran) tetapi tidak dapat dilanjutkan karena kedua sumber daya yang diperlukan telah disita oleh mobil lain. Ini merupakan kebuntuan yang sebenarnya.
Mari kita lihat gambaran dari kebuntuan yang melibatkan proses-proses dan komputer
sumber daya. Gambar 6.2 (berdasarkan satu di [BACO03]), yang kami sebut sebagai diagram kemajuan bersama, menggambarkan kemajuan dua proses yang bersaing untuk dua sumber. Setiap proses membutuhkan penggunaan eksklusif dari kedua sumber daya untuk sebuah tertentu jangka waktu tertentu. Dua proses, P dan Q, mempunyai bentuk umum berikut:
Process P Process Q
• • • • • •
Get A Get B
• • • • • •
Get B Get A
• • • • • •
Release A Release B
• • • • • •
Release B Release A
• • • • • •
Sebagai contoh sederhana, Deadlock terjadi jika dua proses memerlukan dua sumber daya yang sama untuk melanjutkan dan masing-masing memiliki satu kepemilikan. Kecuali beberapa tindakan yang diambil, setiap proses akan menunggu tanpa batas waktu untuk sumber daya yang hilang tersebut.
Starvation adalah situasi di mana proses runnable yang terlupakan tanpa batas oleh penjadwal; meskipun mampu melanjutkan, tetapi tidak pernah dipilih.
Starvation mengacu pada situasi di mana suatu proses siap untuk mengeksekusi tetapi terus ditolak akses ke prosesor untuk mendahulukan proses lainnya. Dalam sebagian besar, starvation ditangani sebagai isu penjadwalan.
Contoh, perhatikan dua proses, P1 dan P2, dan dua sumber daya, R1 dan R2. Misalkan bahwa setiap proses membutuhkan akses ke kedua sumber daya untuk melakukan sebagian fungsinya. Maka mungkin untuk memiliki situasi berikut ini:
OS menugaskan R1 untuk P2, dan R2 untuk P1. Setiap proses sedang menunggu salah satu dari dua sumber daya. Tidak akan melepaskan sumber daya yang sudah memiliki sampai telah mengakuisisi sumber daya lainnya dan melakukan fungsi yang membutuhkan baik sumber daya. Kedua proses ini menemui deadlock (jalan buntu).
Sebuah masalah pengendalian akhir ini adalah starvation. Misalkan tiga proses (P1, P2, P3) masing-masing membutuhkan akses berkala kepada sumber daya R. Pertimbangkan situasi di mana P1 adalah memiliki sumber daya, dan kedua P2 dan P3 yang tertunda, menunggu sumber daya itu.
Ketika keluar dari critical section P1, baik P2 atau P3 harus diberi akses ke R. Asumsikan bahwa OS memberikan akses ke P3 dan bahwa P1 lagi membutuhkan akses sebelum P3 menyelesaikan critical section-nya. Jika OS memberikan akses ke P3 P1 setelah selesai, dan kemudian bergantian memberikan akses ke P1 dan P3, maka P2 dapat tanpa batas waktu menolak akses ke sumber daya, meskipun tidak ada situasi deadlock.
Sumber : blog.ub.ac.id/.../semaphore-dan-monitor-algoritmanya-deker-peterso...
TUGAS SISTEM OPERASI
Ari Fitrianingsih
0922002
Semaphore adalah salah satu cara menangani critical section, yang dikemukakan
oleh Dijkstra. Prinsip semaphore sebagai berikut:
Dua proses atau lebih dapat bekerja sama dengan menggunakan penandapenanda sederhana. Proses dipaksa berhenti sampai proses memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan penanda yang sesuai kebutuhannya. Variabel khusus untuk penandan ini disebut semaphore. Semaphore mempunyai dua property, yaitu :
1. Semaphore dapat diinisialisasi dengan nilai nonnegative.
2. Terdapat dua operasi terhadap semaphore yaitu Down dan Up. Nama asli yang disampaikan Dijkstra adalah operasi P dan V.
Semaphore S merupakan variabel bertipe integer yang diakses dengan 2 standar operasi atomic, yaitu wait dan signal. Operasi-operasi ini diwakili dengan P (wait) dan V (signal) sebagai berikut:
wait(S) : while S £ 0 do no_op;
S:=S – 1;
signal(S) : S:=S+1;
Misalkan ada 2 proses yang sedang berjalan secara konkuren, yaitu P1 dengan pernyataan S1 dan P2 dengan pernyataan S2. Andaikan kita mengharapkan S2 baru akan dijalankan hanya setelah S1 selesai. Hal ini dapat dilakukan dengan menggunakan bantuan semaphore synch (dengan nilai awal =0) yang akan di-share oleh kedua proses.
Untuk Proses P 1 :
S1;
signal(synch);
Untuk proses P2 :
wait(synch);
S2;
Karena nilai awal untuk synch adalah nol, maka P2 akan mengeksekusi S2 hanya setelah P1 mengerjakan signal (synch) setelah S1. Salah satu kerugian dari penggunaan semaphore diatas adalah adanya busy waiting. Apabila suatu proses menempati critical section, dan ada proses lain yang ingin masuk critical section, maka akan terjadi iterasi secara terus -menerus pada entry section. Hal ini akan menimbulkan masalah pada sistem yang menggunakan konsep multiprogramming.
Untuk menghindari busy waiting, dilakukan modifikasi pada operasi wait dan signal. Jika suatu proses sedang mengeksekusi operasi wait, maka nilai semaphore menjadi tidak positif. Pada saat ini proses akan memblok dirinya (block ) dan ditempatkan pada waiting queue. Proses yang sedang diblok akan menunggu hingga semaphore S direstart, yaitu pada saat beberapa proses yang lain mengeksekusi operasi signal. Suatu proses akan direstart dengan operasi wakeup, yang akan mengubah proses dari keadaan waiting ke ready.
Untuk mengimplmentasikan hal ini, semaphore dirancang dalam bentuk record :
type semaphore= Record
value : integer;
L: list of process;
end;
Var s: semaphore
Operasi-operasi pda semaphore;
wait(S) S.value :=S.value-1;
if S.value < 0 then
Begin
Tambahkan proses ini ke S.L.
block;
end;
Algoritma Semaphore Dijkstra
Model untuk algoritma Dijkstra semaphore dengan menggunakan rendevous
adalah sebagai berikut :
#define p 0
#define v 1
chan sema = [0] of { bit };
proctype dijkstra()
{ byte count = 1;
do
:: (count == 1) -> sema!p; count = 0
:: (count == 0) -> sema? v; count = 1
od
}
proctype user()
{ do
:: sema? p;
/* critical section */
sema!v;
/* non-critical section */
od
}
init
{ run dijkstra(); run user();
run user(); run user()
}
Algoritma Semaphore Dijkstra
Model untuk algoritma Dekker adalah sebagai berikut :
Bit x, y; /* signal masuk/keluar dari section */
byte mutex; /* # proses yang masuk critical section. */
byte turn,A_TURN,B_TURN; /* giliran siapa? */
active proctype A() {
x = 1;
turn = B_TURN;
(y == 0 || turn == A_TURN);
mutex++;
mutex–;
x = 0;
}
active proctype B() {
y = 1;
turn = A_TURN;
(x == 0 || turn == B_TURN);
mutex++;
mutex–;
y = 0;
}
active proctype monitor() {
assert(mutex != 2);
}
Algoritma Semaphore Peterson
Model untuk algoritma 3 (Peterson) adalah sebagai berikut :
#define true 1
#define false 0
bool flag[2];
bool turn;
proctype user(bool i)
{ flag[i] = true;
turn = i;
(flag[1-i] == false || turn == 1-i);
crit: skip; /* critical section */
flag[i] = false
}
init { atomic { run user(0); run user(1) } }
Penjelasan lebih Lanjut
1. Konsep Dasar Semaphore
Semaphore termasuk pendekatan yang diajukan oleh Djikstra, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.Semaphore mempunyai dua sifat, yaitu:
Semaphore dapat diinisialisasi dengan nilai non-negatif.
Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.
Semaphore adalah salah satu teknik sinyal sederhana, dan merupakan konsep penting dalam OS desain, dimana sebuah nilai integer digunakan untuk pensinyalan antara proses. Hanya tiga operasi yang mungkin dilakukan pada semaphore, yang semuanya atom: inisialisasi, penurunan, dan penaikan. Operasi pengurangan dapat mengakibatkan terhalangnya proses, dan kenaikan dari pengoperasian yang sedang berlangsung dapat mengakibatkan terblokirnya suatu proses. Hal ini juga dikenal sebagai sebuah perhitungan semaphore atau semaphore umum.
Semaphore adalah bendera digunakan untuk memeriksa apakah sumber daya saat ini sedang digunakan oleh thread atau proses. Misalnya, jika suatu proses ingin menggunakan printer, terlebih dahulu perlu memastikan printer tersedia dengan memeriksa untuk melihat apakah semaphore telah ditetapkan. jika sudah diatur, maka perlu menunggu untuk proses yang saat ini telah selesai. Namun, jika printer bebas, proses ini akan menetapkan semaphore dan mulai menggunakan printer, memblokir akses ke semua proses lainnya sampai selesai.
Semaphore adalah teknik klasik untuk melindungi bagian penting dari kode dari yang secara simultan dieksekusi oleh lebih dari satu thread. Semaphore adalah generalisasi dari monitor. Sebuah monitor memungkinkan hanya satu thread untuk mengunci objek sekaligus. Semaphore A N memungkinkan proses. Proses meraih semaphore-eksklusif untuk menggunakan semi disebut menenggak semaphore karena mereka diimplementasikan dengan integer Countdown yang decrements untuk setiap kunci dan kenaikan untuk masing-masing membuka. Jika semaphore adalah sepenuhnya terisi, thread baru ingin menggunakannya akan menunggu sampai thread beberapa rilis kunci dengan upping semaphore itu. Untuk semaphore untuk bekerja, cek untuk penuh, dan penurunan harus dilakukan semua dalam satu instruksi yang tidak pernah terputus atom. Instruksi monitor JVM menyediakan dukungan hardware yang diperlukan untuk mensimulasikan semaphores.
Semaphore s, lain kontribusi penting oleh EW Dijkstra, dapat dilihat sebagai ekstensi untuk mutex kunci. Semaphore adalah suatu obyek dengan dua metode Tunggu dan Sinyal, sebuah integer swasta counter dan antrian swasta (benang). Semantik dari semaphore adalah sangat sederhana. Misalkan S adalah semaphore yang swasta counter telah diinisialisasi ke integer non-negatif.
Ketika Tunggu dijalankan oleh thread, kita memiliki dua kemungkinan:
Penghitung S adalah positif
Dalam hal ini, konter ini mengalami penurunan sebesar 1 dan benang kembali pelaksanaannya.
Penghitung S adalah nol
Dalam hal ini, benang ditangguhkan dan dimasukkan ke dalam antrian pribadi S.
Ketika Sinyal dijalankan oleh thread, kami juga memiliki dua kemungkinan:
Antrian S tidak memiliki benang menunggu
Penghitung S ditingkatkan oleh satu dan benang kembali pelaksanaannya.
Antrian S telah menunggu threads
Dalam hal ini, konter S harus nol (lihat pembahasan Tunggu di atas). Salah satu benang menunggu akan diizinkan untuk meninggalkan antrian dan melanjutkan pelaksanaannya. Benang yang mengeksekusi Sinyal juga terus.
Operasi Tunggu atau Signal adalah atom. Ini berarti sekali kegiatan Tunggu mulai (yaitu, pengujian dan penurunan nilai counter dan memasukkan benang ke dalam antrian), mereka akan terus sampai akhir tanpa gangguan apapun. Lebih tepatnya, meskipun ada banyak langkah untuk melaksanakan Tunggu dan Signal, langkah-langkah ini dianggap sebagai instruksi non-interruptible tunggal. Demikian pula, hal yang sama berlaku untuk Sinyal. Apalagi, jika lebih dari satu benang mencoba mengeksekusi Tunggu (atau sinyal), hanya satu dari mereka akan berhasil. Kita tidak boleh membuat asumsi tentang mana thread akan berhasil.
Tunggu karena dapat menyebabkan thread untuk memblokir (yaitu, ketika counter nol), ia memiliki efek yang sama dari operasi kunci dari sebuah kunci mutex. Demikian pula, sebuah sinyal dapat melepaskan benang tunggu, dan mirip dengan membuka operasi. Bahkan, semaphores dapat digunakan sebagai kunci mutex. Pertimbangkan S semaphore dengan nilai awal 1. Kemudian, Tunggu dan Signal sesuai untuk mengunci dan membuka:
Mari kita periksa bagaimana sepasang Tunggu dan Signal dapat menjamin pengecualian bersama. Perlu diingat bahwa nilai awal counter dari S adalah 1. Misalkan sejumlah benang mencoba untuk eksekusi Tunggu. Karena hanya ada satu thread berhasil dapat mengeksekusi Tunggu, thread ini, katakanlah A, menyebabkan counter berkurang sebesar 1, dan memasuki bagian yang kritis. Karena nilai awal counter adalah 1, sekali thread A memasuki critical section, konter menjadi 0, dan, sebagai hasilnya, semua usaha berikutnya dalam melaksanakan Tunggu akan diblokir. Oleh karena itu, membenarkan klaim kita bahwa Tunggu mirip untuk mengunci.
Ketika Sebuah thread keluar dari critical section, Sinyal dijalankan. Jika ada menunggu benang, salah satu dari mereka akan dirilis, dan thread ini dirilis memasuki critical section. Perhatikan bahwa counter masih nol (karena, dalam hal ini, Sinyal tidak meningkatkan dan Tunggu tidak mengurangi counter), yang berarti semua thread berikutnya yang mencoba mengeksekusi Tunggu diblokir. Di sisi lain, jika tidak ada benang menunggu, pelaksanaan Sinyal menyebabkan nilai dari counter akan meningkat dengan 1, sehingga nilai saat ini 1. Dalam hal ini, thread berikutnya yang mengeksekusi Tunggu bisa masuk ke bagian kritis. Oleh karena itu, Sinyal mirip untuk membuka. Singkatnya, kita belajar bahwa pengaturan counter untuk 1 awalnya akan menjamin bahwa paling banyak satu thread bisa di bagian kritis, jika semua benang yang melibatkan mengikuti Tunggu sama – urutan Sinyal.
Jika Anda berhati-hati, Anda akan melihat bahwa nilai counter adalah 1 atau 0, dan tidak pernah memiliki nilai lain. Oleh karena itu, disebut sebagai semaphore biner. Jika kita mengganti counter dengan variabel Boolean dan menafsirkan 1 dan 0 sebagai benar (yaitu, kunci terbuka) dan false (yaitu, kunci tertutup), masing-masing, maka semaphore biner menjadi kunci mutex! Karena itu, Anda dapat menggunakan kunci mutex atau semaphore biner bergantian.
Namun, keindahan menggunakan semaphores adalah bahwa nilai awal tidak harus 1. Bisa jadi ada nilai non-negatif. Kemudian kita akan membahas teknik-teknik lain semaphores menggunakan.
Kemajuan besar pertama dalam menangani masalah proses konkuren datang pada tahun 1965 dengan risalah Dijkstra [DIJK65]. Dijkstra prihatin dengan desain dari OS sebagai kumpulan proses sekuensial dan bekerja sama dengan pembangunan mekanisme yang efisien dan dapat diandalkan untuk mendukung kerja sama. Mekanisme ini hanya bias mudah digunakan oleh proses pengguna jika prosesor dan OS membuat mekanisme yang tersedia.
[DOWN07] menunjukkan tiga konsekuensi menarik dari definisi semaphore:
• Secara umum, tidak ada cara untuk mengetahui sebelum proses decrement semaphore sebuah akan terblokir atau tidak.
• Setelah proses increment semaphore dan proses lain akan berjalan, kedua proses terus berjalan bersamaan. Tidak ada cara untuk mengetahui proses, jika salah satu, akan segera melanjutkan pada sistem prosesor tunggal.
• Saat sinyal Anda semaphore, Anda tidak perlu tahu apakah proses yang lain sedang menunggu, sehingga jumlah proses yang diblokir mungkin nol atau satu.
Konsep Dasar Monitor
Monitor termasuk kumpulan prosedur, variabel dan struktur data di satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur yang dideklarasikan minitor untuk mengakses struktur internal.
Java menggunakan monitor ke benang koordinasi untuk memastikan mereka tidak tersandung saling mengakses data yang sama. Dengan monitor, Anda mengunci obyek, bagian-bagian penting dari kode atau Anda mengunci seluruh metode dengan menyatakan mereka disinkronisasi. Monitor memiliki dukungan hardware test dan mengatur di belakang mereka untuk memastikan cek thread untuk melihat apakah monitor sudah dikunci dan jika tidak, menyita mengunci semua dalam satu operasi atom non-interruptible. Tanpa atomicity, thread mungkin periksa apakah monitor tidak terkunci, dan memiliki beberapa thread lain ambil monitor sebelum mendapat kesempatan untuk menguncinya. Puritan akan menunjukkan bahwa monitor sebenarnya bukan kunci, melainkan kunci adalah cara yang digunakan untuk melindungi bagian penting dari kode.
Monitor Sebuah bahasa pemrograman membangun yang merangkum variabel, prosedur akses dan inisialisasi kode dalam suatu variabel tipe data abstrak. Monitor hanya dapat diakses melalui prosedur akses dan hanya satu proses yang dapat secara aktif mengakses monitor dalam satu waktu. Prosedur-prosedur pengaksesan adalah bagian penting. Dimana monitor mungkin memiliki antrian proses-proses yang sedang menunggu untuk mengaksesnya.
Anda mungkin mendapatkan pengalaman dari belajar semua contoh semaphore bahwa sinyal dan menunggu panggilan masih dapat tersebar di mana-mana dalam program anda dengan cara yang tidak terlalu terstruktur dengan baik. Jika Anda benar-benar mendapatkan seperti perasaan, konsep monitor datang untuk menyelamatkan. Konsep monitor berasal dari 1974 kertas CAR Hoare’s.
Sebuah monitor memiliki empat komponen seperti yang ditunjukkan di bawah ini: inisialisasi, data pribadi, prosedur memonitor, dan antrian masuk monitor. Komponen inisialisasi berisi kode yang digunakan tepat satu kali ketika monitor dibuat, Bagian data pribadi berisi semua data pribadi, termasuk prosedur swasta, yang hanya dapat digunakan dalam monitor. Dengan demikian, barang-barang pribadi tidak terlihat dari luar monitor. Prosedur monitor prosedur yang dapat dipanggil dari luar monitor. Antrian entri memantau berisi semua thread yang disebut prosedur monitor tapi belum diberikan izin. Kita akan kembali ke ini segera.
Oleh karena itu, monitor terlihat seperti kelas dengan inisialisasi, data pribadi dan prosedur monitor sesuai dengan konstruktor, data pribadi dan metode kelas tersebut. Satu-satunya perbedaan utama adalah bahwa kelas tidak memiliki antrian masuk.
Monitor yang seharusnya digunakan dalam lingkungan multithreaded atau multiproses di mana beberapa thread / proses dapat menghubungi prosedur monitor pada saat yang sama meminta layanan. Dengan demikian, monitor menjamin bahwa setiap saat paling banyak satu thread bisa mengeksekusi dalam monitor! Apa artinya ini? Ketika thread panggilan prosedur monitor, kita dapat melihat prosedur monitor disebut sebagai perpanjangan ke thread panggilan. Jika prosedur monitor disebut dalam eksekusi, kita akan mengatakan thread memanggil di monitor melaksanakan prosedur monitor disebut.
Sekarang, jika dua thread di monitor (yaitu, mereka adalah melaksanakan dua, mungkin, monitor prosedur yang sama), beberapa data pribadi dapat dimodifikasi oleh kedua benang pada saat yang sama menyebabkan kondisi ras terjadi. Oleh karena itu, untuk menjamin keutuhan data pribadi, monitor saling memberlakukan pengecualian implisit. Lebih tepatnya, jika thread panggilan prosedur monitor, thread ini akan diblokir jika ada thread lain eksekusi pada monitor. Mereka benang yang tidak diberikan izin masuk akan antri masuk ke antrian monitor luar monitor. Ketika monitor menjadi kosong (yaitu, tidak ada thread mengeksekusi di dalamnya), salah satu benang dalam antrian entri akan dirilis dan diberikan izin untuk menjalankan prosedur monitor disebut. Meskipun kita mengatakan “antrian masuk,” Anda tidak harus melihat secara harfiah. Lebih tepatnya, ketika thread harus dilepaskan dari antrian masuk, Anda tidak perlu menganggap kebijakan apapun yang thread yang akan dirilis.
Secara ringkas, monitor memastikan saling eksklusi otomatis sehingga tidak ada lebih dari satu thread bisa mengeksekusi dalam memonitor setiap saat. Ini adalah kemampuan yang sangat usably dan berguna.
Monitor sebagai Mini-OS
Konsep monitor sangat mirip dengan sebuah sistem operasi. Satu dapat mempertimbangkan inisialisasi sebagaimana data yang diinisialisasi ketika sistem boot up, data pribadi dan kode sebagai struktur data internal dan fungsi dari sebuah sistem operasi, dan prosedur monitor sebagai panggilan sistem. Program-program, tentu saja, benang yang membuat permintaan layanan. Oleh karena itu, monitor bisa dianggap sebagai mini-OS dengan layanan terbatas.
2. Persamaan dan perbedaannya:
Sejak menunggu operasi sinyal pada semaphores dan pada monitor kondisi variabel yang sama, untuk membantu Anda membedakan perbedaan mereka dan menggunakannya dengan benar, berikut ini adalah perbandingan singkat.Semaphore Monitor – Kondisi Variabel
Dapat digunakan di mana saja dalam program, tetapi seharusnya tidak digunakan dalam monitor Hanya dapat digunakan pada monitor
Wait() tidak selalu memblokir pemanggil (yaitu, ketika counter semaphore lebih besar dari nol). Wait() selalu blok pemanggil.
Signal() baik melepaskan thread yang diblokir, jika ada satu, atau meningkatkan semaphore counter. Signal() baik melepaskan thread yang diblokir, jika ada satu, atau sinyal hilang seolah-olah itu tidak pernah terjadi.
Jika Signal () melepaskan thread yang diblokir, pemanggil dan thread dirilis & keduanya melanjutkan. Jika Signal () melepaskan thread yang diblokir, pemanggil hasil monitor (tipe Hoare) atau terus (Mesa Type). Hanya satu dari pemanggil atau threadyang dirilis dapat melanjutkan, tapi tidak keduanya.
Perbedaan:
operasi semaphore tersebar pada seluruh section program
pada monitor, sinkronosasi dikendalikan oleh prosedur tertentu, dimana shared data hanya bisa diakses melalui prosedur tersebut
dalam penggunaan semaphore mungkin timbul kesalahan yang sulit terdeteksi (misal: deadlock), yang dicegah oleh monitor
Di samping itu, sinyal operasi menunggu kondisi variabel monitor mirip dengan P dan operasi V pada perhitungan semaphores. Sebuah pernyataan tunggu dapat memblokir proses itu eksekusi, sedangkan pernyataan sinyal dapat menyebabkan proses lain menjadi diblokir. Namun, ada beberapa perbedaan di antara mereka. Ketika sebuah proses mengeksekusi operasi P, tidak selalu menghalangi proses tersebut karena semaphore penghitungan mungkin lebih besar dari nol. Sebaliknya, ketika sebuah pernyataan menunggu dieksekusi, selalu blok proses. Saat tugas yang mengeksekusi operasi V pada semaphore, itu baik unblocks suatu tugas menunggu yang semaphore atau increment yang semaphore counter jika tidak ada tugas untuk membuka. Di sisi lain, jika suatu proses mengeksekusi pernyataan sinyal ketika tidak ada proses lain untuk membuka blokir, tidak ada efek pada variabel kondisi.
Perbedaan lain antara semaphores dan monitor adalah bahwa pengguna terbangun oleh operasi V dapat melanjutkan eksekusi tanpa penundaan. Sebaliknya, pengguna terbangun oleh operasi sinyal restart hanya ketika monitor terkunci.
Selain itu, solusi monitor terstruktur lebih banyak dari yang satu dengan semaphores karena data dan prosedur yang dikemas dalam satu modul tunggal dan bahwa pengecualian saling disediakan secara otomatis oleh pelaksanaannya.
3. Pengertian Deadlock dan Starvation beserta contohnya:
a) Deadlock
Deadlock secara bahasa berarti buntu atau kebuntuan. Dalam definisi lebih lengkap, deadlock berarti suatu keadaan dimana sistem seperti terhenti dikarenakan setiap proses memiliki sumber daya yang tidak bisa dibagi dan menunggu untuk mendapatkan sumber daya yang sedang dimiliki oleh proses lain. Keadaan seperti ini hanya dapat terjadi pada akses terhadap sumber daya yang tidak bisa dibagi atau non-sharable.
Contoh:
kasus ilustrasi dari kejadian deadlock pada dunia nyata, yaitu pada lalu lintas dijembatan. Dapat dilihat bahwa kedua mobil yang berada di tengah-tengah jembatan tidak dapat maju dan hanya
menunggu. Penyelesaian dari masalah tersebut adalah salah satu dari mobil tersebut mundur, sehingga mobil yang lain dapat maju. Mobil pada kasus ini adalah proses, sedangkan jembatan adalah sumber daya. Kedua mobil berebut untuk menggunakan sumber daya, namun karena sumber daya tersebut hanya dapat digunakan oleh satu proses saja, maka terjadilah deadlock.
Ilustrasinya:
ü Dua Proses, P1 dan P2
ü Dua Resource kritis R1 dan R2
ü Proses P1 dan P2 harus mengakses kedua sumber daya.
Kondisi berikut dapat terjadi : R1 diberikan ke P1, sedang R2 di berikan ke P2.
Karena untuk melanjutkan ekssekusi memerlukan sumber daya sekaligus maka kedua proses akan saling menunggu sumber daya yang lainnya, selamanya. Tidak ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena menunnggu sumber daya lain yang tidak pernah diperolehnya. Keduanya tidak membuat proses kemajuan apapaun, kedua proses tersebut dalam kondisi deadlock.
Kondisi deadlock merupakan kondisi terparah karena banyak proses dapat terlibat dan semua yang terlibat tidak dapat mengakhiri prosesnya secara benar. Beragam mekanisme diusulkan untuk mengatasi kondisi deadlock.
b) Starvation
Ilustrasinya :
ü Terdapat tiga proses P1, P1, dan P3
ü P1, P2, dan P3 memerlukan pengaksesan sumber daya R secara periodik
Terjadi Skenario berikut:
ü P1 sedang di beri sumber daya R, P2, dan P3 Blocked menunggu sumber daya R.
ü Ketika P1 keluar daricritical section, P2 dan P3 diijinkan mengakse R.
ü Asumsi P3 diberi hak akses. Kemudian setelah selesai, hak akses kembali diberikan ke P1 yang saat itu kembali membutuhkan sumber daya R.
Jika pemberian hak akses bergantian terus-menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R. meskipun tidak ada deadlock, pada sutuasi ini P2 mengalami starvation.
Untuk pemahaman lebih jelas, berikut detail dari penjelasannya:
Deadlock adalah situasi di mana dua atau lebih proses yang tidak dapat dilanjutkan karena masing-masing sedang menunggu satu yang lain untuk melakukan sesuatu.
Deadlock mengacu situasi di mana satu set dari dua atau lebih proses yang menunggu untuk anggota lain dimana diset untuk menyelesaikan operasi untuk memprosesnya, tapi tidak ada anggota yang mampu memproses. Deadlock adalah fenomena yang sulit untuk mengantisipasi, dan tidak ada solusi umum yang mudah untuk mengatasi masalah ini. Ada tiga pendekatan utama untuk berurusan dengan deadlock: pencegahan, penghindaran, dan deteksi.
Dalam Hal ini, dimungkinkan untuk dua atau lebih program yang akan menutup telepon menunggu satu sama lain. Sebagai contoh, dua program mungkin masing-masing memerlukan dua perangkat I / O untuk melakukan beberapa operasi (misalnya, disk untuk menyalin tape). Salah satu program telah
merebut kendali dari salah satu perangkat dan program lain yang memiliki kontrol dari perangkat lain. Setiap menunggu program lain untuk melepaskan sumber daya yang diinginkan. Deadlock tersebut mungkin tergantung pada waktu kesempatan alokasi sumber daya dan pelepasannya.
Prinsip-Prinsip Deadlock
Deadlock dapat didefinisikan sebagai memblokir permanen dari serangkaian proses yang baik bersaing untuk sumber daya sistem atau berkomunikasi satu sama lain. Satu set proses adalah jalan buntu ketika setiap proses dalam set diblokir menunggu suatu peristiwa (biasanya membebaskan beberapa sumber daya yang diminta) yang hanya dapat dipicu oleh lain diblokir proses dalam set. Deadlock adalah permanen karena tidak ada peristiwa yang pernah dipicu. Tidak seperti masalah lain dalam proses manajemen bersamaan, ada ada solusi efisien dalam kasus umum.
Semua kebuntuan melibatkan konflik akan kebutuhan sumber daya oleh dua atau lebih proses. Sebuah contoh umum adalah kebuntuan lalu lintas. Gambar 6.1a menunjukkan situasi di mana empat mobil telah tiba di sebuah simpang empat arah berhenti di kurang lebih sama waktu. Keempat kuadran dari persimpangan adalah sumber daya di mana kendali dibutuhkan. Secara khusus, jika semua empat mobil ingin pergi langsung melalui persimpangan itu, kebutuhan sumber daya adalah sebagai berikut:
• Mobil 1, bepergian ke utara, membutuhkan kuadran a dan b.
• Mobil 2, membutuhkan kuadran b dan c.
• Mobil 3, membutuhkan kuadran c dan d.
• Mobil 4, membutuhkan kuadran d dan a.
Aturan khas jalan di Amerika Serikat adalah bahwa mobil di halte empat arah harus menunda untuk mobil segera haknya. Aturan ini bekerja jika hanya ada dua atau tiga mobil di persimpangan. Misalnya, jika hanya utara dan arah barat mobil tiba di persimpangan, mobil utara akan menunggu dan mobil ke arah barat diterima. Namun, jika semua empat mobil tiba pada waktu yang sama, masing-masing akan menahan diri dari memasuki persimpangan, ini menyebabkan kebuntuan potensial. Kebuntuan ini hanya potensial, tidak aktual, karena sumber daya yang diperlukan tersedia untuk salah satu mobil untuk melanjutkan. Jika salah satu mobil akhirnya melanjutkan, maka yang lain juga dapat melanjutkannya.
Namun, jika semua empat mobil mengabaikan aturan dan lanjutkan (hati-hati) ke perempatan pada saat yang sama, maka setiap mobil merebut satu sumber daya (satu kuadran) tetapi tidak dapat dilanjutkan karena kedua sumber daya yang diperlukan telah disita oleh mobil lain. Ini merupakan kebuntuan yang sebenarnya.
Mari kita lihat gambaran dari kebuntuan yang melibatkan proses-proses dan komputer
sumber daya. Gambar 6.2 (berdasarkan satu di [BACO03]), yang kami sebut sebagai diagram kemajuan bersama, menggambarkan kemajuan dua proses yang bersaing untuk dua sumber. Setiap proses membutuhkan penggunaan eksklusif dari kedua sumber daya untuk sebuah tertentu jangka waktu tertentu. Dua proses, P dan Q, mempunyai bentuk umum berikut:
Process P Process Q
• • • • • •
Get A Get B
• • • • • •
Get B Get A
• • • • • •
Release A Release B
• • • • • •
Release B Release A
• • • • • •
Sebagai contoh sederhana, Deadlock terjadi jika dua proses memerlukan dua sumber daya yang sama untuk melanjutkan dan masing-masing memiliki satu kepemilikan. Kecuali beberapa tindakan yang diambil, setiap proses akan menunggu tanpa batas waktu untuk sumber daya yang hilang tersebut.
Starvation adalah situasi di mana proses runnable yang terlupakan tanpa batas oleh penjadwal; meskipun mampu melanjutkan, tetapi tidak pernah dipilih.
Starvation mengacu pada situasi di mana suatu proses siap untuk mengeksekusi tetapi terus ditolak akses ke prosesor untuk mendahulukan proses lainnya. Dalam sebagian besar, starvation ditangani sebagai isu penjadwalan.
Contoh, perhatikan dua proses, P1 dan P2, dan dua sumber daya, R1 dan R2. Misalkan bahwa setiap proses membutuhkan akses ke kedua sumber daya untuk melakukan sebagian fungsinya. Maka mungkin untuk memiliki situasi berikut ini:
OS menugaskan R1 untuk P2, dan R2 untuk P1. Setiap proses sedang menunggu salah satu dari dua sumber daya. Tidak akan melepaskan sumber daya yang sudah memiliki sampai telah mengakuisisi sumber daya lainnya dan melakukan fungsi yang membutuhkan baik sumber daya. Kedua proses ini menemui deadlock (jalan buntu).
Sebuah masalah pengendalian akhir ini adalah starvation. Misalkan tiga proses (P1, P2, P3) masing-masing membutuhkan akses berkala kepada sumber daya R. Pertimbangkan situasi di mana P1 adalah memiliki sumber daya, dan kedua P2 dan P3 yang tertunda, menunggu sumber daya itu.
Ketika keluar dari critical section P1, baik P2 atau P3 harus diberi akses ke R. Asumsikan bahwa OS memberikan akses ke P3 dan bahwa P1 lagi membutuhkan akses sebelum P3 menyelesaikan critical section-nya. Jika OS memberikan akses ke P3 P1 setelah selesai, dan kemudian bergantian memberikan akses ke P1 dan P3, maka P2 dapat tanpa batas waktu menolak akses ke sumber daya, meskipun tidak ada situasi deadlock.
Sumber : blog.ub.ac.id/.../semaphore-dan-monitor-algoritmanya-deker-peterso...
TUGAS SISTEM OPERASI
Ari Fitrianingsih
0922002
