Algoritma Semaphore

Algoritma Semaphore

Semaphore adalah pendekatan yang dikemukakan Dijkstra. Prinsip semaphore

adalah sebagai berikut : Dua proses atau lebih dapat bekerja sama dengan

menggunakan penanda-penanda sederhana. Proses dipaksa berhenti sampai proses

memperoleh penanda tertentu. Sembarang kebutuhan koordinasi kompleks dapat

dipenuhi dengan strukstur penanda yang sesuai kebutuhannya. Variabel khusus untuk

penandaan ini disebut semaphore.

Semaphore adalah alat untuk sinkronisasi yang tidak membutuhkan busy

waiting. Semaphore S berupa variable integer. Semaphore hanya dapat diakses melalui

operasi atomic yang tak dapat diinterupsi sampai kode selesai. Operasi dari semaphore

S adalah wait dan signal berikut :

wait (S):

while S≤ 0 do no-op;

S--;

signal (S):

S++;

Adanya semaphore mempermudah penyelesaian persoalan critical section pada

n proses. Penyelesaian critical section menggunakan semaphore menggunakan variabel

umum berikut :

semaphore mutex;

Variabel semaphore mutex diinisialisasi mutex = 1. Sedangkan struktur program

untuk proses Pi adalah :

do {

wait(mutex);

critical section

signal(mutex);

remainder section

} while (1);

Implementasi semaphore harus dapat menjamin mutual exclusion variabel

semaphore, yaitu hanya mengijinkan satu proses pada satu saat yang boleh

memanipulasi semaphore. Implementasi sebuah semaphore menggunakan struktur data

record sebagai berikut :

typedef struct {

int value;

struct process *L;

} semaphore;

Pada semaphore terdapat dua operasi sederhana yaitu block untuk menghentikan

sementara proses yang menggunakan semaphore dan wakeup(P) untuk melanjutkan

eksekusi proses P yang di-blok. Operasi wait dan signal dari semaphore didefinisikan

sebagai :

wait(S):

S.value--;

if (S.value < 0) {

tambahkan proses ke S.L;

block;

}

signal(S):

S.value++;

if (S.value <= 0) {

hapus proses P dari S.L;

wakeup(P);

}

Sebagai alat sinkronisasi yang umum, semaphore dieksekusi oleh suatu proses

setelah proses lain. Misalnya semaphore B pada proses Pj hanya dieksekusi setelah

semaphore A dieksekusi pada proses Pi. Pada saat menggunakan semaphore, flag

diinisialisasi 0. Kode yang diakses proses Pi dan Pj dapat dilihat berikut ini :

Pi                                            Pj

A                                  wait(flag)

signal(flag)                  B

Semaphore merupakan salah satu sumber daya sistem. Misalnya dua proses P1

dan P2, dua sumber daya kritis R1 dan R2, proses P1 dan P2 harus mengakses kedua

sumber daya. Kondisi berikut dapat terjadi : R1 diberikan ke P1, sedang R2 diberikan ke

P2. Apabila dua proses untuk melanjutkan eksekusi memerlukan kedua sumber daya

sekaligus maka kedua proses akan saling menunggu sumber daya lain selamanya. Tak

ada proses yang dapat melepaskan sumber daya yang telah dipegangnya karena

menunggu sumber daya lain yang tak pernah diperolehnya. Kedua proses dalam kondisi

deadlock, tidak dapat membuat kemajuan apapun.

Pada saat beberapa proses membawa semaphore dan masing-masing proses

menunggu semaphore yang sedang dibawa oleh proses lain maka kemungkinan akan

terjadi deadlock. Misalnya terdapat dua semaphore S dan Q yang diinisialisasi 1.

P0                                           P1

wait(S);                        wait(Q);

wait(Q);                       wait(S);

signal(S);                     signal(Q);

signal(Q);                    signal(S);

Proses P0 dan P1 masing-masing menjalankan operasi wait(S) dan wait(Q). Kemudian

proses P0 dan P1 menjalankan operasi wait(Q) dan wait(S) maka sistem akan deadlock

sampai salah satu proses menjalankan operasi signal.

Apabila suatu proses tidak pernah dihapus dari antrian semaphore setelah suatu

semaphore dihentikan sementara, maka terjadi bloking yang tak terbatas. Keadaan ini

disebut starvation.

Keadaan starvation digambarkan sebagai berikut. Misalnya terdapat tiga proses

P1, P2 dan P3 yang memerlukan pengaksesan sumber daya R secara periodik. Skenario

yang bisa terjadi :

·         P1 sedang diberi sumber daya R, P2 dan P3 blocked menunggu sumber daya R.

·         Ketika P1 keluar dari critical section, P2 dan P3 diijinkan mengakses 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, meski tidak ada deadlock. Pada

situasi ini, P2 mengalami yang disebut Starvation.

Terdapat dua bentuk semaphore yaitu counting semaphore dan binary

semaphore. Counting semaphore menggunakan nilai integer yang mempunyai

jangkauan tak terbatas seperti pada struktur yang telah dijelanskan diatas. Binary

semaphore menggunakan nilai integer dengan jangkauan antara 0 dan 1 sehingga

implementasinya lebih sederhana. Counting semaphore S diatas dapat

diimplementasikan dengan binary semaphore. Struktur data yang digunakan adalah :

binary-semaphore S1, S2;

int C:

Struktur data diatas diinisialisasi dengan

S1 = 1

S2 = 0

C = initial value of semaphore S

Implementasi operasi wait dan signal pada binary semaphore S adalah sebagai berikut :

Operasi wait :

wait(S1);

C--;

if (C < 0) {

signal(S1);

wait(S2);

}

signal(S1);

Operasi signal :

wait(S1);

C ++;

if (C <= 0)

signal(S2);

else

signal(S1)

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.

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.