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.
Nissa MJ/0922018
D3/Manajemen Informatika
Sumber : Zarkazi.blogspot.com
Continue Reading...
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.
Nissa MJ/0922018
D3/Manajemen Informatika
Sumber : Zarkazi.blogspot.com



