Sistem Operasi
Penjadwalan Proses: pemilihan proses selanjutnya yang akan dieksekusi.
Cara Kerja: Melakukan multiplexing CPU.
Penjadwalan dilakukan:
- Proses baru dibuat
- Proses selesai dieksekusi
- Proses yang selesai di eksekusi diblokir
- Terjadi I/O interrupt (mis. Proses yang di blokir siap untuk dieksekusi kembali)
- Terjadi clock interrupt (mis. Sekali 40 mdet).
Tujuan penjadwalan: Adil, Prioritas, Efisiensi, Mendukung beban yang berat, Beradaptasi dengan beragam lingungan (interaktif, realtime, multimuedia)
Kriteria performansi
- Keadilan
- Efisiensi: optimalisasi penggunaan sumberdaya
- Throughput: proses yang selesai dalam satuan waktu tertentu
- Waktu turnaround: waktu yang diperlukan proses untuk menunggu di antrian ready
- Waktu respon: jangka waktu sejak proses disubmit hingga memperoleh respon pertama
- Penerapan kebijakan: sesuai dengan kebijakan yang telah ditetapkan
- Proporsional: memenuhi keinginan user
- Memenuhi target
Focus penjadawalan pada system,
- Untuk semua: keadilan, penerapan kebijakan, pemerataan beban.
- System batch: maksimal troughput, minimal waktu turnaround, maksimal penggunaan CPU.
- System interaktif: minimal waktu respon, proporsionalitas.
- System realtime: dapat diprediksi, memenuhi tenggat.
Penjadwalan Preempitive VS Non Preemptive
- Penjadwalan Preemptive: proses yang sedang dieksekusi dapat diinterupsi dan dipaksa untuk menyerahkan CPU
- Penjadwalan Nonpreemptive: proses yang sedang dieksekusi menggunakan CPU hingga proses tersebut menyerahkan secara sukarela
Algoritma Penjadwalan Prosesor Tunggal
- System batch: first come first serve (FCFS), shortest job first (SJF).
- System interaktif: round robin, penjadwalan prioritas, mutli queue dan multi level feed back, shortest proses time, guaranteed scheduling, lottery scheduling, fair sharing scheduling.
First Come First Serve (FCFS)
- proses yang meminta CPU duluan yang dialokasikan CPU duluan.
- disebut juga FIFO
- nonpreemptive
- digunakan pada sistem batch
- analogi dunia nyata: restoran cepat saji.
- implementasi: antrian FIFO. Proses baru memasuki belakang antrian, scheduler memilih dari depan antrian.
- metrik performansi: waktu tunggu rata-rata.
- Parameter: burst time, waktu dan urutan kedatangan.
FCFS: Masalah
- Non-preemptive.
- AWT tidak optimal.
- Tidak bisa menggunakan sumberdaya secara pararel: Asumsi 1 proses CPU-bounded dan banyak proses I/O-bounded, Hasil convoy effect utilisasi CPU dan perangkat I/O sangat rendah.
Shortest Job First (SJF)
- Dahulukan job dengan waktu eksekusi tersingkat.
- Digunakan pada sistem batch.
- Ada 2 tipe: Non-preemptive, Preemptive.
- Kebutuhan: Waktu eksekusi harus diketahui terlebih dahulu.
- Optimal jika semua job tersedia pada waktu yang sama.
- Memberikan waktu tunggu rata-rata terbaik.
Masalah Pada SJF: Starvation (Pada kondisi tertentu, suatu job mungkin tidak pernah menyelasikan eksekusinya).
Algoritma Penjadwalan Interaktif
- Biasanya preemptive: waktu eksekusi dibagi dalam kuantum, Keputusan penjadwalan dibuat pada awal tiap kuantum.
- Kriteria performansi: Waktu respon minimnum, Proporsional terbaik.
- Algoritma: Berbasis prioritas, Round-robin, Multi Queue & Multi level feedback, Shortest process time, Guaranteed scheduling, Lottery scheduling, Fair sharing scheduling.
Penjadwalan Prioritas
- Tiap proses diberi prioritas
- Penjadwalan FCFS within each priority level
- Proses dengan prioritas lebih tinggi dijadwalkan duluan: Preemptive, Nonpreemptive.
- Masalah: Mungkin tidak menghasilkan waktu tunggu rata-rata yang baik, Dapat menyebabkan infite blocking atau starvation pada proses dengan prioritas rendah.
Penjadwalan Prioritas/Penentuan Prioritas
- Ada 2 pendekatan: Statis (untuk sistem dengan prilaku aplikasi yang teratur dan telah diketahui), Dinamis (sebaliknya).
- Prioritas dapat ditentukan berdasarkan: Biaya terhadap user, Tingkat kepentingn user, Umur proses (aging), persen waktu CPU yang telah digunakan pada kali jam terkhir.
Round Robin
- Tiap proses memperoleh alokasi waktu CPU dalam kuantum waktu biasanya 10-100ms.
- Setelah kuantum waktu lewat, proses di preempted dan dimasukan ke belakang antrian ready.
- Jika ada n proses pada antrian ready dan kuantum waktu=q maka: pada gilirannya tiap proses memperoleh 1/n waktu CPU selama q, Tidak ada proses yang menunggu lebih dari (n-1)q unit waktu.
- Performansi: q bsar FIFO, q kecil overhead untuk context switch sangat besar.
Sinkronisasi & Inter Process Communication (IPC)
- Critical Section: Mutual exclusion, Algoritma sincronisasi, Komunikasi antar proses, Permasalahan klasik.
Latar Belakang
- Akses konkuren terhadap data yang dipakai bersama dapat mengakibatkan inkonsistensi data.
- Akses memori bersama dapat mengakibatkan terjadinya kondisi berlomba (race condition).
- Pemeliharaan konsistensi data memerlukan mekanisme khusus untuk memjamin eksekusi antar proses yang bekerjasama dengan benar (terurut).
Critical Section
- Terjadi perlombaan beberapa proses untuk mengeksekusi critical section, hasil eksekusi tidak bisa diprediksi
- CS bisa berada pada kode & proses yang berbeda.
Persyaratan CS
- Mutual exclusion: Tidak ada proses lain yang boleh masuk ke CS selama masih ada proses lain di dalamnya.
- Prigres: Jika tidak ada proses yang sedang berada di CS dan ada proses yang mencoba masuk ke CS, maka proses tersebut harus diberi akses ke CS.
- Bounded Waiting: Proses yang menunggu akses ke CS tidak boleh menunggu dalam waktu yang tak terbatas.
- Kecepatan dan banyak CPU: tidak ada asumsi mengenai kecepatan atau banyaknya CPU.
Implementasi Mutex (busy waiting) kemungkinan solusi: Disabling Interrupts, Variabel Lock, Strict Alternation, Solusi Peterson, Instruksi TSL.
Disabling Interupt
- Cara kerja: Disable semua interupt tepat sebelum masuk ke CS dan di-enable kembali tepat sebelum keluar.
- Jika interrupt dalam keadaan disable, tidak ada clock interrupt yang akan terjadi tidak akan terjadi process switching.
- Hanya digunakan untuk internal OS.
Variable Lock: Menimbulkan permasalahan kondisi berlomba yang baru.
Overlay
- Program dibagi menjadi beberapa bagian -> overlay.
- Membagi program menjadi beberapa bagian dilakukan olehh programer->makan waktu dan membosankan.
- Overlay 0 akan diload pertamakali dan setelah selesai akan memanggil overlay yang lain.
- Overlay ditaruh di disk dan di swap in/out ke memory saat di utuhkan.
Virtual Memory
- Pemisahan memori lojik dari memori fisik.
- Hanya sebagian dari program yang perlu berada di memori untuk eksekusi.
- Ruang alamat lojik bisa lebih besar dari ruang alamat fisik.
- Perlu mekanisme untuk swap in/out pages.
Paging
- CPU akan meng generate virtual address mengirimkannya ke MMU (memory management unit).
- MMU bertugas memetakan virtual address ke physical address.
Demand Paging
- Periksa tabel internal
- Bila valid tapi belum ada maka di page-in.
- Jika invalid maka batalkan proses.
Dukungan Harware
- Page table: Table memiliki valid/invalid bit serta bit proteksi khusus.
- Secondary memory: Memori yang menyimpan seluruh page (dikenal sebagai swap device dan bagian disk yang digunakan untuk swap disebut swap space/backing store).
Apa yang terjadi jika tidak ada frame yg kosong: Page Replacement, temukan page dalam memory tetapi tidak sedang digunakan swap-out page tersebut.
Swap Space
- Aspek penting dalam demand paging adalah menangani penggunaan swap space .
- Suatu bagian dalam disk dijadikan swap space sebagai penyimpan/ virtual memory.
Over-Allocating Memory: peningkatan degree of multiprograming akan sampai pada situasi over allocating memory.
- Saat terjadi page-fault & hendak page-in ternyata tidak ada frame kosing tersedia.
- Solusi OS: Paging harus transparan bagi user.
Solusi
- Trashing: swap-out suatu proses.
- page replacement (mencari salah satu frame yang tidak sedang digunakan dan membebaskannya): Menuliskan isi sebelum ke swap-space, Mengubah page table dimana page tidak ada di memory.
Page Fault Service
- Menemukan lokasi dari page di dalam disk.
- Menemukan frame jika ada gunakan frame tersebut untuk page yang bersangkutan dan jika tidak ada: Mencari frame yang akan di-replace, Page-out frame tersebut ke swap-space dan ubah tabel oage & frame, Page-in page yang diminta ke frame kosing yang baru serta ubah table page & frame, Mulai kembali ke user proses.
Dirty Bit (modify-bit): saat tidak ditemukan frame kosong maka dilakukan dua kali page transfer in & out, untuk mengurangi overhaead operasi ini di gunakan dirty-bit pada setiap page/frame untuk menunjukkan perlu/tidaknya page dalam dinsk di update.
- modify bit di set ketika word/byte dalam page ditulis.
- ketika memilih page untuk di replace modify bit dibaca dulu.
- Jika bit tersebut di set maka page tersebut sudah dimodifikasi sejak dibaca di disk.
- Jika bit tersebut tidak di set maka page tersebut belum dimodifikasi sejak dibaca .
Frame Allocation – Page Replacement
Pemilihan algoritma yang tepat sangat penting, karena pemrosesan pada disk I/O costnya mahal.
Frame Allocation Alghoritme: Menentukan berapa banyak frame dialokasikan untuk suatu/setiap proses.
Page Replacement Algorithm: Menentukan frame mana yang dipilih untuk di page-out.
- Terdapat banyak skema/algorimta.
- Kriteria pemilihan algoritma yang sesuai dapat meminimalisasi page-fault rate.
- Evaluasi dengan string (string dari aktifitas memori reference): String dari memori reference dinamakan reference string, Secara empiris direkam dari referensi yang terjadi pada running program, Secara hipotesis digenerate secara acak, Menghitung jumlah page fault pada string tersebut.
Page Fault VS Jumlah Frame
- Bertambahnya jumlah frame akibat penambahan physical memory space dapat mengurangi FPR.
- Tanpa penambahan tersebut maka memperkecil ukuran frame/page yang akhirnya meningkatkan page fault.
Algoritma Pergantian Halaman (Page Replacement Policy): Ketika terjadi page fault OS harus mencari page mana yang harus dibuang dari memori agar tersedia ruangan bagi page yang lain.
Beberapa algorimta pergantian halaman:
- Algoritma FIFO: Page yang di replace adalah yang paling lama berada di memori secara teus menerus, Realisasinya setiap page menyimpan data waktu page yang bersangkutan di page-in atau menggunakan struktur queue, Mudah di implementasikan tapi performance tidak baik.
- Algoritma Optimal (OPT): Jika diketahui page mana yang berikutnya akan di akses maka page yang tidak akan digunakan dalam waktu dekat yang direplace, Secara teoritis paling optimal tapi dalam kenyataannya sulit di implementasikan.
- Algoritma Least Recently Used (LRU perpaduan FIFO & OPT): Perkiraan akses ayng akan datang diestimasi dengan menggunakan informasi akses yang lalu, Page dalam memori yang paling lama tidak diakses yang direplace.
0 Comments
