Modul SO-1 [PDF]

Citation preview

Diktat Kuliah Sistem Operasi



1



Penjadwalan Sistem Interaktif 



Penjadwalan Round-Robin - Setiap proses diberi interval waktu, disebut quantum, waktu untuk run. - Pertukaran penggunaan CPU dari satu proses ke proses berikutnya membutuhkan waktu untuk tugas administrasi, yaitu : - saving dan loading registers dan memory map, updating beberapa tabel dan list, dll. Proses pertukaran ini disebut process-switch atau context-switch. Current process B



Next process



F



D



G



A



D



G



A



B



Current process F



1. Penjadwalan Prioritas - Proses dengan prioritas tertinggi di run terlebih dulu. - Untuk mencegah proses dengan prioritas tertinggi di run tanpa batas, maka digunakan clock-interrupt untuk menurunkan prioritas proses yang sedang run. - Penjadwalan prioritas di lakukan dalam kelas-kelas. Queue headers priority 4



Runable processes Highest Priority



priority 3 priority 2 priority 1



   



Lowest Priority



Shortest Process Next Guaranteed Scheduling Lottery Scheduling Fair-Share Scheduling



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



2



Penjadwalan Sistem Real-Time - m periodic events. - event i terjadi dalam periode Pi dan membutuhkan Ci detik. m



Ci ≤ 1 ∑ Pi i= 1 Policy Versus Mechanism - Pemisahan antara Mekanisme dan Policy. Penjadwalan Thread



(a) Kemungkinan penjadwalan User-Level Threads dengan proses quantum 50-msec dan thread run 5-msec per CPU burst.



(b) Kemungkinan penjadwalan Kernel-Level Threads dengan karakteristik yang sama seperti (a).



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



3



DEADLOCK Situasi Deadlock terjadi, jika: - Proses diberi akses eksklusif ke device. - Device ini juga disebut resource/ sumber daya. - Contoh: dua proses hendak merekam dokumen yang di scan kedalam sebuah CD. Resources - Preemptable. - Non Preemptable. Urutan langkah untuk menggunakan resource: 1. Request resource 2. Use resource 3. Release resource Perolehan Resource - menggunakan semaphore untuk setiap resource Syarat Kondisi Deadlock : 1. Kondisi mutual exclusion 2. Kondisi hold and wait 3. Kondisi No Preemption 4. Kondisi circular wait Pemodelan Deadlock - Model Holt ( 1972 ) (a) Proses A menggunakan resource R. (b) Proses B meminta/menunggu resource S. (c) Deadlock, proses C dan D meminta resource T dan U. Strategi untuk menghadapi Deadlock : 1. Ignore ( abaikan ) 2. Detection and Recovery 3. Dynamic avoidance, dengan cara mengalokasikan resource secara berhati - hati 4. Prevention, dengan cara menghilangkan salah satu kondisi Deadlock



Teknik Informatika Unindra



Versi 1.0



A



B



C



Diktat Kuliah Sistem Operasi



4



⇒ Algoritma Ostrich - “Stick your head in the sand and pretend there is no problem at all” (menganggap tidak ada masalah). - Layak, jika: - deadlock jarang terjadi - biaya pencegahan (prevention) sangat mahal. •



Deteksi Deadlock dan Pemulihan (Deadlock Detection and Recovery)



•



Deteksi deadlock dengan satu resource untuk setiap jenis.



-



Contoh: sebuah sistem dengan 7 proses (A – G) dan 6 resource (R – W), dengan status pemilikan dan permintaan resource sbb : 1. A holds R, wants S 2. B holds nothing, wants T 3. C holds nothing, wants S 4. D holds U, wants S and T 5. E holds T, wants S and T 6. F holds W, wants S 7. G holds V, wants U



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



-



5



Algoritma pendeteksian siklus (cycle) Tanda panah akan diberi tanda untuk mengetahui sudah dilewati dan menggunakan struktur data, L, daftar simpul:



1. Untuk setiap simpul / node, N dalam graph, kerjakan 5 langkah berikut dengan N sebagai simpul awal.



2. Inisialisasi L menjadi daftar kosong, dan semua tanda panah belum ditandai. 3. Tambahkan simpul yang dikunjungi ke daftar L dan periksa apakah simpul muncul dua kali dalam daftar L. Jika ya, maka dalam graph terdapat siklus dan algoritma selesai. 4. Dari simpul yang sudah anda tentukan, ikuti jika ada tanda panah keluar yang belum di-tandai. Jika ada, kerjakan langkah 5; jika tidak kerjakan langkah 6. 5. Pilih sebuah tanda panah keluar secara acak dan beri tanda. Kemudian ikuti ke simpul berikutnya dan kerjakan langkah 3. 6. Kita sampai ke jalan buntu. Kembali ke simpul sebelumnya dan kerjakan langkah 3. Jika simpul ini adalah simpul awal maka graph tidak terdapat siklus dan algoritma selesai. •



Deteksi deadlock dengan banyak resource untuk setiap jenis - Existing resource vector



-



Available resource vector Current allocation matrix Request matrix



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



6



Empat struktur data yang diperlukan untuk algoritma deteksi deadlock Algoritma deteksi deadlock sbb:



1. Cari proses Pi yang belum di-tandai, dimana baris ke-i mempunyai R ≤ A. 2. Jika proses yang dicari ditemukan, tambahkan C dari baris ke-i ke A, tandai proses dan kembali ke langkah 1. 3. Jika proses yang dicari tidak ada, algoritma selesai. Contoh:



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



•



7



Pemulihan dari Deadlock Jika deadlock terjadi, apa yang harus dilakukan agar sistem bekerja kembali? -



Pemulihan melalui preemption Pemulihan melalui rollback Pemulihan melalui killing process



Menghindari Deadlock (Deadlock Avoidance) Lintasan Resource (Resource Trajectories) - Algoritma untuk menghindari deadlock bekerja berdasarkan “status aman” (safe state). - Contoh: Lintasan resource yang terdiri dari dua proses dan dua resource.



⇒ Status Aman dan Tidak Aman -



Contoh status (a) adalah aman, dimana terdapat total 10 buah resource. A B C



Teknik Informatika Unindra



HAS 3 2 2 Free : 3 (a)



MAX 9 4 7



A B C



HAS 3 4 2 Free : 1 (b)



MAX 9 4 7



Versi 1.0



Diktat Kuliah Sistem Operasi



A B C



A B C



8



HAS 3 0 2 Free : 5 (c)



MAX 9 7



HAS 3 0 0 Free : 7 (e)



MAX 9 -



A B C



HAS 3 0 7 Free : 0 (d)



MAX 9 7



HAS 4 2 2



MAX 9 4 7



- Status (b) adalah tidak aman. A B C



A B C



HAS 3 2 2 Free:3 (a)



MAX 9 4 7



HAS 4 4 2 Free:0 (c)



MAX 9 4 7



A B C Free:2



(b) A B C Free:4



HAS 4 2



MAX 9 7



(d)



⇒ Algoritma Banker untuk satu jenis resource A B C D



A B C D



Teknik Informatika Unindra



HAS 0 0 0 0 Free : 10 (a)



MAX 6 5 4 7



HAS 1 2 2 4 Free : 1 (c)



MAX 6 5 4 7



A B C D



HAS 1 1 2 4 Free : 2 (b)



MAX 6 5 4 7



Versi 1.0



Diktat Kuliah Sistem Operasi



9



⇒ Algoritma Banker dengan banyak jenis resource Proce ss A B C D E



Tape Plotte Printe Drive rs rs 3 0 1 0 1 0 1 1 1 1 1 0 0 0 0 resources assigned



CD ROM 1 0 0 1 0



Proce Tape Plotte Printe ss Drive rs rs A 1 1 0 B 0 1 1 C 3 1 0 D 0 0 1 E 2 1 1 resources still needed



CD ROM 0 2 0 0 0



E = ( 6342 ) P = ( 5322 ) A = ( 1020 ) Pencegahan Deadlock (Deadlock Prevention) ⇒ Menghilangkan kondisi mutual exclusion - Printer dapat di-spool. - Tidak semua alat dapat di-spool. - Prinsip: - Hindari pemberian resource yang tidak perlu. - Proses yang meng-claim resource diusahakan seminimal mungkin. ⇒ Menghilangkan kondisi hold dan wait - Proses mendapat semua resource-nya sebelum di-run. - Masalah: - Proses tidak mengetahui kebutuhannya. - Penggunaan resource yang tidak optimal. ⇒ Menghilangkan kondisi no preemption - tidak dapat dilakukan. - Contoh: printer tidak dapat diambil dengan paksa saat sedang bekerja. ⇒ Menghilangkan kondisi circular wait - Menentukan aturan, satu proses hanya dapat menggunakan satu resource (masalah: tidak dapat diterima semua proses). - Memberikan nomor dan meng-urutkan semua resource serta menetapkan aturan dalam meminta resource.



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



10



Isu-isu lain dalam Deadlock: -



Two phase locking Phase satu: - proses melakukan lock pada data yang akan digunakan. Phase dua: - data di-update. - lock dilepaskan.



-



Non-resource Deadlock Deadlock juga dapat terjadi jika kita menuliskan urutan yang salah dalam operasi “down” untuk dua semaphore.



-



Starvation Memilih algoritma alokasi resource yang tidak menyebabkan starvation. Algoritma FCFS menghindari terjadinya starvation.



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



11



Pengaturan Memori (Memory Management) 1. Teknik Dasar Pengaturan Memori 2. Swapping 3. Virtual memory 4. Page Replacement Algorithms 5. Modeling Page Replacement Algorithms 6. Isu Perancangan untuk Sistem Paging 7. Isu Implementasi 8. Segmentation



1. Teknik Dasar Pengaturan Memori •



Monoprogramming tanpa Swapping atau Paging



Tiga Cara Pengorganisasian Memori dengan Sistem Operasi dan Satu Proses Pemakai



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



12



Tiga Cara Pengorganisasian Memori dengan Sistem Operasi dan Satu Proses Pemakai •



Multiprogramming dengan Fixed Partitions



•



Modeling Multiprogramming • Utilisasi CPU = 1 - pn



Degree of multiprogramming



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



•



13



Analisa Unjuk Kinerja Sistem Multiprogramming



• •



Job 1 – 4 : 80 % I/O Wait



Relokasi dan Proteksi • Relokasi: o Address o User-Written Procedures o Library Procedures o Contoh Masalah • •



Teknik Informatika Unindra



Proteksi: o Contoh Masalah Solusi: o Base Register o Limit Register



Versi 1.0



Diktat Kuliah Sistem Operasi



14



Swapping



Pengaturan Memori dengan Bitmaps dan Link Lists



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



•



15



Kombinasi Posisi Proses dan Holes



Algoritma Pengalokasian Memori • First Fit • Next Fit • Best Fit • Worst Fit • Quick Fit 2. Virtual Memori • Paging • Memory Management Unit (MMU)



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



• • •



16



Page Table Virtual Memory Address Physical Memory Address



TLBs – Translation Lookaside Buffer



•



Inverted Page Table



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



17



Page Replacement Algorithms • Page Fault • Pemilihan Page • Pertukaran Page • Contoh Permasalahan Optimal Page Replacement Algorithm • Memilih Page yang berada pada posisi terjauh • Optimal tetapi tidak mungkin di implementasi Not recently Used Page Replacement Algorithm • Reference Bit • Modified Bit • Klasifikasi Page • Random FIFO Page Replacement Algoritma • Membuat Daftar Page sesuai urutan masuk • Memilih Page yang Pertama Masuk • Terjadi Kelemahan Second Chance Page Replacement Algorithm • FIFO Order • R Bit



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



18



The Clock Page Replacement Algorithm



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



19



Least Recently Used (LRU) Page Replacement Algorithm •



• •



Memilih Page yang Paling Lama Tidak Terpakai Membuat Daftar Page Update Page



LRU using a matrix – pages referenced in order 0,1,2,3,2,1,0,3,2,3



Simulating LRU in Software



• The aging algorithm simulates LRU in software • Note 6 pages for 5 clock ticks, (a) – (e)



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



20



The Working Set Page Replacement Algorithm



• The aging algorithm simulates LRU in software • Note 6 pages for 5 clock ticks, (a) – (e)



The working set algorithm



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



21



The WSClock Page Replacement Algorithm



The working set algorithm



Review Page Replacement Algorithm Algorithm 1. Optimal



Comment



2. NRU



Tidak dapat diimplementasi tetapi berguna sebagai Benchmark Tidak optimal



3. FIFO



Sering mengganti Page yang penting



4. Second Chance



Modifikasi dari FIFO



5. Clock



Realistis



6. LRU 7. Aging



Bagus tetapi sulit untuk diimplementasi Efisien dalam mengimplementasi LRU



8. Working Set



Mahal untuk diimplementasi



9. WSClock



Cukup Efisien



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



22



Modeling Page Replacement Algorithms •



Belady’s Anomaly o Reference Pages: 0 1 2 3 0 1 4 0 1 2 3 4



• FIFO with 3 page frames • FIFO with 4 page frames • P's show which page references show page faults



• •



Stacks Algorithms Reference String terdiri dari 4 Pages: 0 2 1 3 5 4 6 3 7 4 7 3 3 5 5 3 1 1 1 7 2 3 4 1



7



Teknik Informatika Unindra



4



6 5



Versi 1.0



Diktat Kuliah Sistem Operasi



•



23



Distance String



Probability density functions for two hypothetical distance strings



•



Memprediksi Page Fault Rates



• Computation of page fault rate from distance string – the C vector – the F vector



Isu Perancangan untuk Sistem Paging • Local Vs Global Allocation Policies



• Original configuration • Local page replacement • Global page replacement



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



•



24



Page Fault Rates



Page fault rate as a function of the number of page frames assigned



•



Besar Page o Overhead = se/p + p/2 o –se/p2 + ½ = 0 o p = √ (2se)



Isu Implementasi   



10 Tahap Page Fault Handling Locking Pages in Memory Backing Store



(a) Paging to static swap area (b) Backing up pages dynamically



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



25



Segmentation



• One-dimensional address space with growing tables • One table may bump into another



Allows each table to grow or shrink, independently



I •



Implementasi Pure Segmentation



(a)-(d) Development of checkerboarding (e) Removal of the checkerboarding by compaction



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



•



26



Segmentation with Paging: MULTICS



• Descriptor segment points to page tables • Segment descriptor – numbers are field lengths •



Segmentation with Paging: The Intel Pentium



• Pentium code segment descriptor • Data segments differ slightly



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



27



INPUT / OUTPUT Salah satu fungsi dari Sistem Operasi adalah mengendalikan seluruh peralatan input/output komputer. Sistem operasi melakukan interupsi, menangani error, dan memberi instruksi ke peralatan I/O. Beberapa pokok bahasan tentang input / output antara lain : • Prinsip perangkat keras I/O • Prinsip perangkat lunak I/O • Layer perangkat lunak I/O • Clock • Disk • Character Oriented Terminal • Graphic User Interfaces • Network Terminals • Power Management PRINSIP PERANGKAT KERAS INPUT / OUTPUT 



Peralatan Input/Output (I/O DEVICES) Dua jenis Peralatan I/O : ♦ Block devices Data dikirim atau diterima dalam bentuk Block ( Disk, Pita magnetik). Peralatan ini menyimpan informasi dalam Block yang berukuran tetap, dan setiap block memiliki alamat sendiri. ♦ Character devices Data dikirim atau diterima dalam bentuk karakter ( Seperti : Line printer, Pita kertas, Punched card, Mouse, Network interface, dsb). Data pada peralatan ini tidak memiliki alamat, juga tidak ada operasi seek terhadap data.



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



28



DEVICE CONTROLLER Komponen yang membentuk I/O Device • Komponen mekanis • Komponen Elektronik Device Controller (adapter) adalah komponen elektronik, yang dapat menangani beberapa peralatan yang sejenis. Tugas Controller • Konversi rangakian bit serial menjadi Block data • Koreksi Error jika diperlukan • Menyediakan data di memory utama MEMORY-MAPPED I/O



(a). Separate I/O and memory space (b). Memory Mapped I/O (c). Hybrid



Single–bus Architecture Teknik Informatika Unindra



Dual–bus memory Architecture Versi 1.0



Diktat Kuliah Sistem Operasi



29



DIRECT MEMORY ACCESS (DMA) Cara kerja DMA : • Controller membaca block data dari drive secara serial, bit per bit, hingga block tersebut berada dalam buffer internal dari controller • Dilakukan perhitungan checksum untuk verifikasi bahwa tidak terjadi kesalahan pembacaan • Controller melakukan transfer data byte per byte dari buffer controller ke memory dengan menaikkan nilai address dan mengurangi nilai count dengan 1 • Controller menyebabkan interupsi • Pada saat Sistem Operasi mulai running, ia dapat langsung membaca data dari memory, tanpa harus mengeksekusi loop untuk membaca dari buffer controller



Operation of a DMA transfer INTERRUPT REVISITED Interupsi terjadi dengan koneksi antara peralatan I/O dengan Interrupt controller menngunakan interrupt line di bus, dan bukan dedicated wires



Teknik Informatika Unindra



Versi 1.0



Diktat Kuliah Sistem Operasi



Teknik Informatika Unindra



30



Versi 1.0