Fakultas Ilmu Komputer Universitas Indonesia
UTS: Sistim Komputer
Ujian tertulis bersifat tutup buku, kecuali untuk 2 lembar referensi.
• • •
Waktu ujian: 120 menit (8:00 – 10:00). Jumlah soal 20 (3 lembar). Periksa jumlah soal. Kerjakan dengan rapih, pada kertas terpisah. Jangan lupa tulis nama dan no. mhs/i. Kejujuran dan integritas harap menjadi perhatian utama setiap peserta. Contek-mencontek nilai E !
A. Memilih: Lingkari jawaban yang paling tepat. 1. Fungsi manakah di bawah ini yang mendukung OS dalam mempermudah user menggunakan komputer? c. file system. 2. Struktur OS manakah di bawah ini yang memungkinkan menjalankan lebih dari satu jenis sistim operasi secara bersamaan? d. virtual machine. 3. Mekanisme manakah di bawah ini yang mungkinkan user proses mengakses resource hardware melalui instruksi privilege yang dikontrol oleh OS? e. system call. 4. Status proses manakah di bawah ini yang pada satu saat hanya diberikan kepada satu proses (dari seluruh proses yang ada) oleh scheduler: b. run. 5. Yang bukan merupakan lingkup OS modern dalam manajemen proses adalah: c. mendukung alokasi memori 6. Misalkan terdapat variasi dari round-robin scheduling dimana entry pada ready queue berupa pointer ke PCB. Apakah akibatnya jika kita memperbolehkan terdapat 2 pointer pada ready queue yang menunjuka ke proses yang sama pada PCB? b. proses akan bertambah jatah CPU. 7. Salah satu cara untuk mendeteksi terjadinya deadlock adalah: b. circular wait (cycle pada resource allocation graph) 8. Dengan menggunakan semaphore dan monitor suatu sistim OS dapat melakukan : b. mencegah timbulnya race condition 9. Jika kita dapat merancang bahwa semua resources dapat digunakan secara bersamaan (tanpa ada hak pemakaian eksklusif untuk resource tersebut) maka dapat disimpulkan untuk pemakaian resources tersebut: a. deadlock tidak akan pernah terjadi 10. Misalkan anda mengubah time slice (waktu quantum) yang besar dari suatu round-robin scheduling menjadi jauh lebih kecil. Pernyataan manakah di bawah ini yang benar sebagai akibat dari perubahan tersebut: b. II saja. I. mendukung pemakaian waktu CPU lebih efisien. II. mendukung multi-user sistim lebih baik karena response sistim lebih cepat. III. mengakibatkan jatah pemakaian CPU lebih adil.
B. Jawablah dengan ringkas dan lengkap. (Jawaban tidak lebih dari 10 kalimat) (Nilai 40) Solusi: kata kunci dalam huruf miring. 11. Terangkan dengan ringkas perbedaan (kontras) antara sistim OS dengan multi-threading dan multitasking? • multi-threading: OS mampu menjalankan thread-thread (lightweight process) dari berbagai proses dengan melakukan switching antar thread tersebut.
Magister Teknologi Informasi Universitas Indonesia
Page 1/JM-RMS/V1.1/2001
•
multi-tasking: OS mampu menjalankan berbagai proses/task switching antar proses tersebut.
dengan melakukan
Perbedaan dalam hal waktu switching (overhead untuk CPU) pada multi-threading lebih kecil dibandingkan multi-tasking. 12. Untuk OS Solaris, terangkan perbedaan antara context switch di antara thread dalam satu task (proses) dengan context switch antara thread dari task (proses) yang berlainan. Context switch untuk thread dalam satu task cepat dan efisien dengan dukungan user level thread, karena tidak memerlukan informasi resources kernel atau yang lain (masih dalam satu proses). Context switch thread untuk proses yang berlainan relatif akan lebih lama, karena pasti akan menyebabkan terjadi switching antar proses (LWP: lighweight process) sehingga informasi pada PCB harus disimpan dan di-restore. 13. Apakah perbedaan antara pre-emptive scheduling dan non preemptive scheduling? Non-Preemptive: Bila CPU telah dialokasikan (schedule) ke suatu proses, maka proses tersebut dapat menggunakan CPU tersebut sampai proses tersebut block karena request I/O atau terminate. Preemptive: selain scheduling dapat dilakukan pada dua event di atas, maka scheduling dapat terjadi jika proses sedang run (interrupt karena waktu quantum / time slice habis) dan diganti proses lain, atau status dari wait menjadi ready (misalkan proses prioritas lebih tinggi, dapat langsung mendapatkan jatah CPU setelah selesai I/O request). Dengan kata lain pre-emptive dapat melakukan interupsi proses yang sedang run dan menjalankan scheduling CPU. Note: definisi textbook untuk non-preemptive scheduling => scheduling atau pemilihan proses mana yang akan mendapatkan jatah CPU akan dilakukan jika proses berpindah dari status run ke status wait (misalkan saat melakukan I/O request dan proses block, sehingga state berpindah dari run ke wait); atau proses yang sedang run terminate.
Berikan justifikasi mengapa non preemptive scheduling tidak dapat digunakan untuk suatu data center (computer center). Data center digunakan oleh multi user dan banyak proses sehingga jika non premptive scheduling yang digunakan terdapat kemungkinan proses yang tidak pernah teminate (misalkan loop terus menerus) dan tidak pernah melakukan I/O request atau block secara sukarela, akan memonopoli pemakaian CPU. 14. Apakah kelebihan jika kita mempunyai waktu quantum yang berbeda untuk setiap tingkat pada “multilevel -proses I/O intensive waktu quantum kecil, sedangkan level yang lain waktu quantum besar). Berdasarkan pengelompokan antrian proses pada setiap level sesuai dengan karakteristik Page 2/JM – RMS -V1.1/2001
kelompok proses tersebut (interaktif, batch, atau I/O intensive dll). Dengan adanya flexibilitas waktu quantum yang berbeda antar level, maka scheduling dapat lebih optimal dalam memberikan response atau mengurangi overhead yang timbul. Misalkan untuk proses interaktif waktu quantum kecil (time-sharing), sedangkan untuk batch jobs dimana CPU intensive, maka waktu quantum kecil hanya meningkatkan overhead (context switch yang sering) dari pemakaian CPU sehingga dipilih waktu quantum yang besar. (Nilai penuh: jika menyebutkan kelompok proses memerlukan scheduling yang berbeda, optimalisasi pemakaian CPU dan response sistim). 15. Terangkan perbedaan (kontras) semaphore dan monitor. Monitor membantu programmer dalam hal mencegah kesalahan yang timbul dalam menggunakan semaphore yang sulit di deteksi (seperti timing error, deadlock dll), karena operasi semaphore dapat tersebar pada seluruh section program, sedangkan monitor sinkronisasi dikendalikan oleh prosedur tertentu sedangkan shared data hanya dapat diakses melalui prosedur tersebut. 16. Terangkan satu cara untuk mencegah (prevention) terjadi deadlock. Terangkan dengan membatasi untuk tidak dilakukan hal sbb (pilih 1): mutual exclusion, hold-and wait, no premption, circular wait.
C. Soal: untuk mendapatkan nilai penuh, tulis tahapan/keterangan pekerjaan anda. 17. Terdapat beberapa proses concurrent yang mencoba mengakses file (share). Untuk mencapai mutual exclusion maka setiap proses diberikan struktur sbb: Lock adalah "shared" variabel bool (inisialisasi : Lock = false) <… code tidak ada hubungan dengan akses ke file > while Test-and-Set(Lock) do no-op; < .. code mengakses ke shared I/O devices> Lock := false; <… code tidak ada hubungan dengan akses ke I/O >
Instruksi Test-and-Set dapat dieksekusi secara atomik (dukungan hardware CPU). Buktikan bahwa solusi tersebut memenuhi solusi untuk critical section yakni: mutual exclusion dan progress.
Asumsikan code instruction Test-and-Set (Lock) akan return nilai dari Lock, dan set Lock true: boolean Test-and-Set(boolean Lock) { Test-and-Set = Lock; Lock = true; }
Page 3/JM – RMS -V1.1/2001
Mutual Exclusion: Untuk membuktikan mutual exclusion cukup dengan menunjukkan proses Pi masuk ke critical section (CS) hanya jika var. Lock mempunyai nilai “false”. Saat awal nilai Lock adalah false dan karena operasi Test-and-Set atomik, maka jika lebih dari satu proses serentak mengeksekusi Test-and-Set maka hanya satu instruksi yang dipilih (dilakukan secara serial). Jadi hanya ada satu proses, misalkan Pi yang sukses melihat/menguji nilai Lock adalah false dan set nilai Lock menjadi true. Proses selanjutnya akan mendapatkan nilai Lock adalah true dan loop busy waiting (no-op), menunggu sampai proses Pi keluar dari CS dan men-set Lock false, Progress: Sebab proses Pi yang keluar dari CS dijamin akan men-set Lock menjadi false, maka secara otomatis akan ada satu proses yang sedang busy waiting akan dipilih dan dapat masuk ke CS.
18. Misalkan terdapat resource printer dengan jumlah total 12 printer. Proses A memerlukan max. 10 printer, Proses B memerlukan max. 4 printer, dan proses C memerlukan max. 4 printer. Pada saat t1, telah dialokasikan (hold) untuk A sebanyak 7 printer, B sebanyak 1 printer dan C sebanyak 2 printer. Misalkan pada saat t2, ketiga proses tersebut secara bersamaan melakukan request 1 printer. Proses manakah yang akan diberikan printer tersebut, dan terangkan alasannya dengan menggunakan Dijkstra’s banker algorithm. [full credit jika ditulis juga iterasi algoritma]. Menjawab: printer diberikan ke proses C (Nilai 4) Mencoba menjawab banker algorithm: Membuat matrix (max, alloc), needs dan available (sisa resources) dan menulis algoritma dan safe sequence yang benar jika diberikan ke proses C (Nilai 4) Melakukan iterasi pemilihan pemberian resources dalam mencari terdapat, (Nilai 2) misalkan: Finish[3] = false; Work=2; Iterasi: Cari proses dimana Finish adalah false dan Need lebih kecil dari available. Need C <= Work; ... dst. 19. Terdapat 3 threads yakni B, C, dan D melakukan kerjasama untuk task: print (f(x,y); Shared data/var: int x, y int z; // hasil f(x,y) dan akan diprint. // tambahkan code untuk var. semaphore.
a) ..
Thread B x = ...; // hitung x b)..
Thread C ... d)..
Thread D f)..
print (z); // print z Page 4/JM – RMS -V1.1/2001
y = ...; // hitung y; c)..
z = f (x, y); // function call x,e).. y
...
Lengkapi kode semaphore (tanda kotak) cukup hanya untuk sinkronisasi saja antara ketiga thread tersebut. Jawab dalam bentuk a) sampai f). a)
Semaphore overX, overY, overZ; // Initialize semaphore => zero: overX = overY = overZ = 0; b). signal(overX); c). signal (overY); d). wait(overX); wait(overY); e). signal(overZ); f). wait(overZ);
20. Misalkan terdapat producer dan consumer melakukan pertukaran data melalui monitor bounded buffer. Producer dapat menyimpat data melalui prosedur mput(); sedangkan Consumer dapat mengambil data melalui prosedur mget(). Tulis secara lengkap (pseudo code) dari monitor tersebut dimana buffer dengan besar N merupakan bagian shared data dari monitor: Hint: di bawah ini diberikan deklarasi untuk shared data monitor, anda dapat menggunakan shared data tsb untuk menyusun pseudo code mget dan mput. Item buffer[N]; // shared buffer int in, out; // track index buffer untuk producer dan consumer, initialize 0; int count; // counter untuk informasi jumlah item di buffer; Condition mayInsert, mayRemove; // condition variable.
Untuk soal ini lihat contoh pada slides atau buku.
Untuk bagian C, anda dapat memilih 3 dari 4 soal. Jika mengerjakan semua soal dan benar diberikan bonus sebesar nilai 10.
Page 5/JM – RMS -V1.1/2001
