Readers-Writers & The Dining Philosophers Problem
Maharmon Arnaldo Api Perdana Contact:
[email protected] Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Pembahasan • • • • • •
Masalah Readers-Writers Program Readers-Writers Solusi Readers-Writers Masalah The Dining Philosopher Semafor Sebagai Solusi Solusi Masalah The Dining Philosoper
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Readers - Writers • Terdiri dari dua proses: – Readers, yang berfungsi sebagai pembaca – Writers, yang berfungsi sebagai pembaca dan penulis
• Kedua proses berbagi sumber daya penyimpanan yang sama • Masalah: Adanya beberapa pembaca dan penulis yang ingin mengakses suatu berkas secara bersamaan • Tujuan: data tidak menjadi korupsi Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Kondisi Readers - Writers • Pembaca dapat membaca secara simultan • Hanya boleh ada satu penulis pada suatu saat • Bila ada yang menulis, tidak boleh ada yang membaca
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Readers public class Reader extends Thread { public Reader(int r, Database db) { readerNum = r; server = db; } public void run() { int c; while (true) { //System.out.println("reader " + readerNum + " is sleeping."); Database.napping(); System.out.println("reader " + readerNum + " wants to read."); c = server.startRead(); Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Readers (2) // you have access to read from the database System.out.println("reader " + readerNum + " is reading. Reader Count = " + c); Database.napping(); System.out.print("reader " + readerNum + " is done reading. "); c = server.endRead(); //System.out.println("reader " + readerNum + " is done reading. Count = " +c); } } private Database private int readerNum;
server;
} Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Writers public class Writer extends Thread { public Writer(int w, Database db) { writerNum = w; server = db; } public void run() { while (true) { //System.out.println("writer " + writerNum + " is sleeping."); Database.napping(); System.out.println("writer " + writerNum + " wants to write."); server.startWrite(); Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Writers (2) // you have access to write to the database System.out.println("writer " + writerNum + " is writing."); Database.napping(); System.out.println("writer " + writerNum + " is done writing."); server.endWrite(); //System.out.println("writer " + writerNum + " is done writing."); } } private Database server; private int writerNum; } Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Readers - Writers • Pembaca Diprioritaskan • Penulis Diprioritaskan • Pembaca Dan Penulis Mendapat Prioritas yang sama
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Dengan Pembaca Diprioritaskan •
Bisa terjadi Starvation untuk proses Writer public void mulaiMembaca(){ mutex.tunggu(); nPembaca++; if (nPembaca == 1) brks.tunggu(); mutex.sinyal(); } public void selesaiMembaca(){ mutex.tunggu(); --nPembaca; if (nPembaca == 0) brks.sinyal(); mutex.sinyal(); } public void mulaiMenulis(){ brks.tunggu(); } public void selesaiMenulis(){ brks.sinyal(); }
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Dengan Penulis Diprioritaskan •
Dapat menyebabkan starvation untuk proses Reader. public void mulaiMembaca(){ mutex1.tunggu(); baca.tunggu(); mutex2.tunggu(); nPembaca++; if (nPembaca == 1) tulis.tunggu(); mutex2.sinyal(); baca.sinyal(); mutex1.sinyal(); } public void selesaiMembaca(){ mutex2.tunggu(); nPembaca--; if (nPembaca == 0) tulis.sinyal(); mutex2.sinyal(); }
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Dengan Penulis Diprioritaskan (2) public void mulaiMenulis(){ mutex3.tunggu(); nPenulis++; if (nPenulis == 1) baca.tunggu(); mutex3.sinyal(); tulis.tunggu(); } public void selesaiMenulis(){ tulis.sinyal(); mutex3.tunggu(); nPenulis--; if (nPenulis == 0) baca.sinyal(); mutex3.sinyal(); }
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Dengan Pembaca Dan Penulis Mendapat Prioritas Sama • Ada kemungkinan terjadi antrian yang panjang
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Dining Philosophers
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Dining Philosophers • Merupakan masalah klasik sinkronisasi karena menjadi contoh bagi masalah concurrencycontrol pada tingkat yang lebih tinggi • Representasi sederhana atas kebutuhan untuk mengalokasikan sumber daya kepada beberapa proses tanpa terjadi deadlock maupun starvation • Diketahui sejumlah (N) filsuf yang hanya memiliki tiga kondisi; berpikir, lapar, dan makan duduk pada meja bundar • Di antara para filsuf terdapat satu buah sumpit dan di tengah meja terdapat semangkuk mie Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Dining Philosophers (2) • Yang harus diperhatikan: ¾Deadlock: Semua filsuf ingin makan dan telah memegang sumpit ¾Starvation: Ada filsuf yang kelaparan dalam waktu yang lama
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Semafor • Solusi yang mungkin langsung terlihat adalah dengan menggunakan semafor. • Setiap sumpit mewakili sebuah semafor. • Jika filsuf ingin mengambil sumpit, ia jalankan perintah wait • Jika filsuf ingin meletakkan kembali sumpit, ia jalankan perintah signal Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Semafor (2) var chopstick: array [0..4] of semaphore; repeat wait (chopstick [i]); wait (chopstick [i + 1 mod 5 ]); … eat … signal (chopstick [i]); signal (chopstick [i + 1 mod 5 ]); … think … until false Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Kelemahan Semaphor • Low Level • Karena tersebar di seluruh program, maka sulit dalam pemeliharaannya • Error yang terjadi sulit untuk dideteksi • Lebih baik menggunakan high-level construct • Dapat terjadi deadlock! Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!
Solusi Dining Philosophers • Filsuf hanya bisa mengambil sumpit jika kedua sumpit di sampingnya ada • Menggunakan solusi asimetris • Jumlah filsuf pada suatu meja maksimal adalah empat • Menggunakan Monitor
Copyright (C) 2004 Api Perdana, Maharmon Arnaldo. Slide ini untuk pemakaian pribadi dan kegiatan yang berkaitan dengan perkuliahan Sistem Operasi. Kami TIDAK bertanggung-jawab atas KEAKURATAN mau pun KERUGIAN yang mungkin terjadi akibat memanfaatkan slide ini!