INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1
SOLUSI QUIZ 2 SISOP CS3613
Soal-soal berikut ini berkaitan dengan topik: SINKRONISASI dan MUTUAL EXCLUTION (Total nilai = 110) 1.
Jelaskan pengertian critical section dan berikan contohnya (minimal 2) ! (Nilai 6) Jawab: Resource yang dalam satu saat hanya boleh diakses oleh satu proses saja Contoh: variabel global, printer, CPU, share memory, dll
2.
Jenis-jenis interaksi antar proses di dalam sebuah komputer adalah saling berkompetisi, saling bekerja sama melalui memori bersama, dan saling berkomunikasi dengan pesan. Jenis-jenis masalah yang bisa terjadi pada interaksi antar proses tersebut antara lain deadlock, data coherence, starvation, dan kegagalan mutual exclution. Tuliskan 2 jenis masalah yang bisa terjadi pada model interaksi antar proses melalui memori bersama, kemudian berikan contoh kasus yang bisa terjadi untuk setiap masalah ! (Nilai 12) Jawab: a. Mutual exclution gagal (Nilai 6) Contoh kasus: Dalam satu saat variabel global atau shared memory diakses oleh lebih dari satu proses b.
3.
Starvation (Nilai 6) Contoh kasus: Variabel global atau shared memory akan diakses oleh lebih dari satu proses. Salah satu proses mengakses variabel global atau shared memory terus menerus sehingga proses yang lain menunggu terus menerus
Selain tidak boleh terjadi deadlock, starvation, dan race condition, tuliskan 3 syarat lainnya yang harus dipenuhi untuk membentuk mutual exclution ! (Nilai 9) Jawab: a. Dalam satu saat hanya ada satu proses yang dapat mengakses critical section b. Proses yang sedang tidak mengakses critical section boleh melakukan aktifitas yang lain c. Proses yang akan mengakses critical section yang sedang tidak diakses tidak boleh ditunda d. Waktu pengaksesan critical section adalah terbatas
Oktober 2011/#1
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 4.
Perhatikan contoh program solusi kasus Producer-Consumer dengan ukuran buffer terbatas menggunakan semaphore. Jawablah pertanyaan-pertanyaan di bawah ini !
/* program boundedbuffer */ const int sizeofbuffer = 5; semaphore n = 1; semaphore s = 0; semaphore e = sizeofbuffer; void producer() { while(true) { 1 produce (); 2 semWait (e); 3 semWait (n); 4 append (); 5 semSignal (n); 6 semSignal (s); } }
5.
1 2 3 4 5 6
void consumer() { while (true) { semWait (s); semWait (n); take (); semSignal (n); semSignal (e); consume (); } } void main () { parbegin (producer, consumer); }
a.
Apa yang akan terjadi jika inisialisasi variabel semaphore s = 1 ? (Nilai 3) Jawab: Kondisi mutex gagal, karena dalam satu saat buffer (critical section) bisa diakses oleh 2 buah proses secara bersamaan
b.
Apa yang akan terjadi jika inisialisasi variabel semaphore n = 0 ? (Nilai 3) Jawab: Program tidak dapat berjalan, karena tidak ada proses yang dapat mengakses buffer
c.
Jika nilai sizeofbuffer = 1, tentukan apakah program bisa berjalan atau tidak, jika bisa berjalan tuliskan urut-urutan eksekusi Producer (P) dan Consumer (C) yang mungkin terjadi ! (Nilai 3) Jawab: Producer – Consumer – Producer – Consumer - dst
Tuliskan 2 kelebihan monitor dibanding penggunaan semaphore ! (Nilai 3) Jawab: a. Dapat mengurangi beban programmer dalam menangani sinkronisasi b. Pengecekan masalah yang berhubungan dengan mutex dapat terpusat hanya pada modul monitor, tidak tersebar di berbagai lokasi program c. Sekali program monitor telah benar, maka akses terhadap critical resource oleh berbagai proses akan selalu benar
Oktober 2011/#2
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 6.
1 2 3 4
Berikut ini merupakan program producer/consumer finite buffer dengan message passing.
/* program boundedbuffer */ const int capacity = 2; null = /*empty message*/ int i; void producer() { message pmsg; while(true) { receive (mayproduce, pmsg); pmsg = produce(); send (mayconsume, pmsg); } }
a.
b.
7.
void consumer() { message cmsg; 1 while (true) { 2 ??? 3 consume(cmsg); 4 send (mayproduce, null); } } void main() { 1 create_mailbox (mayproduce); 2 create_mailbox (mayconsume); 3 for (int i=1; i <= capacity; i++) 4 send(mayproduce, null); 5 parbegin (producer, consumer); } Baris program nomor 2 pada bagian consumer (tanda ???) seharusnya diisi dengan ... (Nilai 3) Jawab: receive (mayconsume, cmsg) Tuliskan semua urut-urutan eksekusi Producer (P) dan Consumer (C) yang mungkin terjadi ! (Nilai 3) Jawab: PPCC, PCPC
Di bawah ini merupakan contoh program reader/writer dengan semaphore dimana pembaca (reader) diutamakan. /* program readerswriters */ int readcount; semaphore x = 1, wsem = 1; void reader() { while (true) { 1: semWait (x); 2: readcount++; 3: if (readcount == 1) 4: semWait (wsem); 5: semSignal (x); 6: READUNIT(); 7: semWait (x); 8: readcount--; 9: if (readcount ==0) 10: semSignal (wsem); 11: semSignal (x); } }
void writer() { while (true) { 12: semWait (wsem); 13: WRITEUNIT(); 14: semSignal (wsem); } } void main() { 15: readcount = 0; 16: parbegin (reader, writer); }
Oktober 2011/#3
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 Terdapat 2 pembaca (R1 dan R2) dan 1 penulis (W) yang dieksekusi secara acak dengan urutan seperti pada tabel di bawah. Program dieksekusi pada sistem prosesor tunggal. Bagian program yang ditulis pada tabel hanya baris-baris program di dalam loop while (true). Tabel berikut berisi nilai dari beberapa variabel digunakan pada program di atas serta isi antrian yang digunakan untuk menampung proses yang ter-blok akibat memanggil prosedur semaphore. Lengkapilah titik-titik pada kolom variabel x, readcount, wsem, dan kolom Antrian Blok di bawah ini ! (Untuk setiap baris: benar semuanilai=4; total nilai = 20) Pembaca 1 (R1)
Pembaca 2 (R2)
Penulis (W)
x
read wsem count
Antrian Blok
Inisialisasi
1
0
1
-
semWait (x);
0
0
1
-
readcount++;
0
1
1
-
-1
1
1
R2
semWait (wsem);
-1
1
0
R2
WRITEUNIT();
-1
1
0
R2
-1
1
-1
R2
-1
1
0
R2
0
1
0
-
0
2
0
-
0
2
-1
W
semWait (x);
if(readcount == 1) semWait (wsem); semSignal (wsem); semSignal (x); readcount++; semWait (wsem);
Soal-soal berikut ini berkaitan dengan topik: MANAJEMEN MEMORI (Total nilai = 30) Setiap nomor soal pilihan ganda bernilai 3. 8. Sebuah memori berukuran 64 MB digunakan untuk menaruh sistem operasi 8 MB dan sisanya untuk menaruh program user. Ada 4 proses yang dieksekusi dengan urut-urutan kedatangan sbb: masuk proses A (25 MB), masuk proses B (15 MB), proses A selesai, masuk proses C (18 MB), masuk proses D (16 MB). Jika model manajemen memori yang digunakan adalah partisi dinamis, maka: a.
Terjadi fragmentasi internal sebesar 7 MB
b.
Terjadi fragmentasi eksternal sebesar 9 MB
c.
Terjadi fragmentasi eksternal sebesar 7 MB
d.
Terjadi fragmentasi internal sebesar 9 MB
e.
Tidak terjadi fragmentasi eksternal maupun internal
Oktober 2011/#4
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 9. Sebuah memori dipartisi secara dinamis dengan kondisi terakhir partisi seperti pada gambar di bawah ini dimana partisi A merupakan awal memori. Semua partisi kosong kecuali partisi D. Sebuah proses berukuran 8 MB akan ditaruh ke memori. Jika lokasi penempatan memori terakhir sebesar 25 MB ada di partisi D, pilihlah pernyataan di bawah ini yang paling benar ! 20 (A)
15 (B)
10 (C)
25 (D)
58 (E)
Jika algoritma penempatan yang digunakan adalah: a. Best-fit, maka proses tersebut akan ditempatkan pada lokasi B b. Next-fit, maka proses tersebut akan ditempatkan pada lokasi A c. First -fit, maka proses tersebut akan ditempatkan pada lokasi E d. First-fit, maka proses tersebut akan ditempatkan pada lokasi A e. Worst-fit, maka proses tersebut akan ditempatkan pada lokasi C
10. Misal dinotasikan alokasi memori sebesar x dinyatakan sebagai Ax dan dealokasi memori sebesar y dinotasikan Dy, dan algoritma alokasi yang digunakan adalah First Fit. Pada gambar di bawah ini partisi yang kosong adalah partisi A dan E. Jika urut-urutan operasi yang terjadi adalah D10, A8, A30, maka ruang kosong (dalam MB) yang terjadi adalah ... 20 (A)
15 (B)
10 (C)
25 (D)
58 (E)
a. 12, 10, dan 28
d. 20 dan 58
b. 20, 10, dan 58
e. tidak ada ruang kosong
c. 37 dan 28 11. Teknik untuk menempatkan bagian modul/program pada area memori yang sama secara bergantian, dimana main programlah yang bertanggungjawab untuk melakukan switching, disebut sebagai ... a.
Partisi tetap
d. Segmentasi sederhana
b.
Partisi dinamik
e. Overlay
c.
Paging sederhana
12. Buddy system digunakan untuk mengatur penggunaan memori sebesar 128 MB, dan urut-urutan alokasi proses adalah sbb: masuk proses A (35 MB), masuk proses B (25 MB), masuk proses C (5 MB), keluar proses B (25 MB), dan masuk proses D (35 MB). Gambarkan alokasi/dealokasi memori yang terjadi (tuliskan ukuran partisi dan proses yang menempatinya) ! (Nilai 12)
Jawab: masuk proses A (35 MB): 64 MB (A) masuk proses B (25 MB): 64 MB (A)
32 MB (B)
Oktober 2011/#5
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 masuk proses C (5 MB): 64 MB (A)
32 MB (B)
8 MB C)
keluar proses B (25 MB): 64 MB (A)
8 MB C)
masuk proses D (35 MB): Proses D tidak bisa dimasukkan ke memori karena partisi yang ada tidak mencukupi.
13. Manajemen memori dengan segmentasi sederhana yang memiliki tabel segmen sebagai berikut:
a.
Segment Starting Address Length(bytes) 0 660 248 1 1752 422 2 222 198 Untuk alamat lojik dengan segment = 2 dan offset = 198, tentukan apakah terjadi segment fault atau tidak. Jika tidak terjadi segment fault, tentukan alamat fisiknya (cara harus dituliskan) ? (Nilai 3) Jawab:
b.
Terjadi segment fault, karena offset yang valid untuk segmen 2 adalah 0 – 197. Sebuah komputer mengalokasikan 6 bit untuk nomor segmen dan 10 bit untuk offset. Jika data pada alamat relatif 352 akan diakses, tentukan apakah terjadi segment fault atau tidak. Jika tidak terjadi segment fault, tentukan alamat fisiknya dalam heksadesimal (cara harus dituliskan) ? (Nilai 3) Jawab: Alamat relatif 352 = 101100000 = 000001 0101100000 segmen = 1 dan offset = 352 Tidak terjadi segment fault karena offset (352) lebih kecil daripada length (422). Alamat fisik = 1752 + 352 = 2104 = 0000100000111000 = 0000 1000 0011 1000 = 0x0838
14. Sebuah memori menggunakan pengalamatan 32 bit dan dipartisi dengan model paging sederhana dimana ukuran setiap page adalah 4 kB. Jika isi tabel page suatu proses seperti pada tabel di bawah, maka jawablah pertanyaan-pertanyaan berikut dan tuliskan perhitungannya !
Oktober 2011/#6
INSTITUT TEKNOLOGI TELKOM FAKULTAS INFORMATIKA PROGRAM STUDI S1 a.
Berapakah jumlah bit offset-nya ? (Nilai 3) Jawab: 1 page = 4 kB = 212, maka jumlah bit offset = 12 bit
b.
Berapakah jumlah bit page-nya ? (Nilai 3) Jawab: Jumlah bit page = 32 – 12 = 20 bit
c.
Jika diberikan alamat relatif 3456 (desimal), berapakah nilai offset-nya (dalam desimal) ? (Nilai 3) Jawab: 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 0
1
1
0
1
1
0 0 0 0 0 0 0
3456 = 110110000000 Bit-bit offset (12 bit) = 110110000000 = 3456 (desimal) d.
Berdasarkan soal c di atas, berapa nomor page-nya (dalam desimal) ? (Nilai 3) Jawab: Bit-bit page (20 bit) = 00 ... 0 (20 bit), maka nomor page-nya = 0 (desimal)
e.
Berapakah alamat fisik (dalam heksa desimal) dari alamat relatif 3456 ? (Nilai 3) Jawab: Page 0 ditaruh pada frame 7 (111) Alamat fisik = gabungan bit-bit nomor frame dengan bit-bit offset = 00 ... 0111 (jumlah bit 0 = 17 bit) digabung dengan 110110000000 = 00 ... 0111 1101 1000 0000 (total 32 bit) = 0x00007B80
Oktober 2011/#7
