Scheduling
Behaviour
of Process
- Process-bound : dilihat dari
proses itu sendiri
- I/O bound : dilihat dari input dan output
CPU
Scheduler()
- Algoritma scheduling:
Memilih dari proses-proses yang berada di memori (ready to execute)
dan memberikan jatah CPU ke salah satu proses tersebut.
- CPU Scheduler berfungsi untuk
menampilkan proses-proses didalam sebuah memori yang sudah siap untuk
dieksekusi, dan dialokasikan ke dalam CPU.
- CPU scheduling mempunyai 4
keputusan :
- berubah dari running ke waiting
state
- berubah dari running ke ready
state
- berubah dari waiting ke ready
state
- terminate/mengakhiri
- Scheduling nomor 1 dan 4 adalah
non-preemptive
- Scheduling nomor 2 dan 3 adalah
preemptive
Types
of Scheduler
- Long-term scheduling ->
Menyeleksi proses-proses mana yang harus dimasukkan ke dalam ready queue
dan membawanya ke memori untuk dieksekusi .
- Medium-term scheduling ->
Menentukan apakah menambah sebagian jumlah proses atau seluruhnya dalam
memori utama
- Short-term -> Menentukan proses
mana yang selanjutnya akan dieksekusi dan mengalokasikan CPU untuk proses
tersebut, dimana pemilihan proses barunya dialokasikan sesering mungkin.
- I/O scheduling -> I/O device
yang tersedia akan menghandle proses I/O yang tertunda
Dispatcher
Dispatcher
mengatur dan memberikan kontrol CPU kepada proses yang dipilih oleh “short-term
scheduler”. Dispatcher melibatkan :
- perubahan konteks
- perubahan ke mode user
- melompat ke lokasi yang salah
dalam program user
Dispatcher
latency adalah waktu yang dibutuhkan oleh dispatcher untuk menyelesaikan 1
proses dan memulai proses yang lainnya.
Scheduling
Criteria :
- CPU utilization : untuk
menjaga agar CPU tetap dalam keadaan sibuk/bekerja (menggunakan CPU
semaksimal mungkin).
- Throughput : maksimalkan
jumlah proses yang selesai dijalankan (per satuan waktu).
- Turnaround time : meminimalkan
waktu selesai eksekusi suatu proses (sejak di submit sampai selesai).
- Waiting time : meminimalkan
waktu tunggu proses (jumlah waktu yang dihabiskan menunggu di ready
queue).
- Response time : meminimalkan
waktu respon dari sistem terhadap user (interaktif, time-sharing system),
sehingga interaksi dapat berlangsung dengan cepat.
Optimization
Criteria :
- Max CPU utilization : Penggunaan
CPU secara maksimal
- Max throughput : Penyelesaian
jumlah proses yang maksimal
- Min turnaround time : Waktu yang
diperlukan semakin cepat semakin baik
- Min waiting time : Waktu menunggu
seminimal mungkin
- Min response time : Waktu untuk
merespon secepat mungkin
Goal
of Scheduling
- All system
– Fairness : mengatur proses dalam penggunaan bersama sumber daya CPU secara adil
– Policy enforcement : memastikan kebijakan yang diterapkan berjalan
– Balance : menjaga semua bagian sistem dalam keadaan sibuk - Batch system
– Throughput : memaksimalkan jumlah job per jam (jobs per hour)
– Turn around time : meminimalkan waktu dari mulai (submission) hingga berakhir (termination)
– CPU utilization : mengupayakan CPU selalu sibuk sepanjang waktu - Interactive system
– Response time : merespon permintaan (request) dengan cepat
– Proportionallity : memenuhi harapan pengguna (user’s expectation) - Real time system
– Meeting deadlines : menghindari kehilangan data
– Predictability : menghindari penurunan kualitas dalam sistem multimedia
Batch
Scheduling Algorithms
Ada
beberapa metode dalam scheduling :
1.
First-Come First-Serve
Proses diassign ke dalam CPU secara urut.
Proses diassign ke dalam CPU secara urut.
Keuntungan : Mudah
dimengerti dan mudah diprogram
Kelemahan
: Pekerjaan yang lebih singkat tetap harus menunggu meskipun ada
pekerjaan yang lebih lama berada di depannya
.
2.
Shortest Job First
Pekerjaan
yang lebih ringan akan dikerjakan terlebih dahulu.
Shortest
Job First mempunyai 2 skema yaitu Preemptive dan Non Preemptive.
- Non preemptive : saat CPU
diberi proses maka harus menunggu proses tersebut sampai selesai terlebih
dahulu.
- Preemptive : Jika ada proses
baru yang datang dengan jumlah CPU burst time nya lebih sedikit
dibandingkan dengan sisa CPU burst time proses yang sedang berjalan maka
proses yang baru datang tersebut dapat dijalankan terlebih dahulu.
Skema ini juga dikenal sebagai Shortest-Remaining-Time-First
(SRTF).
–
Shortest Job First – Non Preemptive
–
Shortest Job First – Preemptive
Contoh
soal :
Tugas
dari Buku Operating Systems: Internals and Design
Principles: International Edition,7th Edition Halaman 447 nomor
9.2
Process
|
Arrival Time
|
Processsing Time
|
A
|
0
|
3
|
B
|
1
|
5
|
C
|
3
|
2
|
D
|
9
|
5
|
E
|
12
|
5
|
Jawab :
1. First-Come
First-Serve
Seperti
yang telah dijelaskan diatas, FCFS menggunakan prinsip FIFO yaitu First In
First Out.
Waktu
menunggu A = 0 detik karena tidak ada proses yang berjalan
sebelumnya pada saat proses A datang oleh karena itu proses A bisa
langsung dikerjakan.
Waktu
menunggu B = 2 detik karena arrival time proses B=1 sedangkan proses A baru
selesai pada detik ke 3. Jadi waktu menunggunya adalah 3-1=2.
Waktu
menunggu C = 5 detik karena arrival time proses C=3 sedangkan proses B baru
selesai pada detik ke 8. Jadi waktu menunggunya adalah 8-3=5.
Waktu
menunggu D = 1 detik karena arrival time proses D=9 sedangkan proses C baru
selesai pada detik ke 10. Jadi waktu menunggunya adalah 10-9=1.
Waktu
menunggu E = 3 detik karena arrival time proses E=12 sedangkan proses D baru
selesai pada detik ke 15. Jadi waktu menunggunya adalah 15-12=3.
Jadi ..
Waktu
menunggu untuk A=0, B=2, C=5, D=1, E=3
Rata-rata
waktu menunggu = (0+2+5+1+3)/5 = 2,2 detik
2.
Shortest Job First – Non Preemptive
Pada
Non Preemptive proses yang waktu pengerjaanya lebih cepat bisa dikerjakan
terlebih dahulu dengan catatan proses yang sebelumnya harus diselesaikan
terlebih dahulu.
Seperti
biasa proses A dijalankan terlebih dahulu karena tidak ada proses yang berjalan
sebelumnya dan waktu menunggunya adalah 0 detik.
Nah
sekarang proses yang dijalankan selanjutnya adalah proses C. kenapa tidak
proses B terlebih dahulu? bukannya proses B yang datang lebih dulu dibandingkan
proses C? Seperti yang telah dijelaskan sebelumnya proses yang waktu
pengerjaannya lebih cepat maka dijalankan terlebih dahulu. Proses C memiliki
processing tme = 2 , sedangkan proses B memiliki processing time = 5. Jadi
waktu menunggu proses c adalah 0 karena saat datang langsung dikerjakan.
Proses
selanjutnya adalah B. Mengapa harus B? padahal proses B,D dan E memiliki
processing time yang sama? alasannya adalah karena proses B datang terlebih
dahulu, selanjutnya baru proses D dan E yang dijalankan.
Waktu
menunggu proses B = 4, karena proses B baru dijalankan pada detik ke 5
sedangkan proses B datang pada detik ke 1. Jadi 5-1=4 detik.
Waktu
menunggu proses D = 1, karena proses D baru dijalankan pada detik ke 10
sedangkan proses D datang pada detik ke 9. Jadi 10-9=1 detik
Waktu
menunggu proses E = 1, karena proses D baru dijalankan pada detik ke 15
sedangkan proses D datang pada detik ke 12. Jadi 15-12=3 detik
Waktu
menunggu untuk A=0, B=4, C=0, D=1, E=3
Rata-rata
waktu menunggu = (0+4+0+1+3)/5 = 1,6 detik
3.
Shortest Job First – Preemptive
Kebetulan
jawaban Preempive pada soal ini sama persis dengan jawaban non-preemptive,
namun secara teknik pengerjaan tentu ada yang berbeda. Yang membedakan adalah
pada preemptive kita bisa menghentikan proses yang sedang berjalan jika ada
proses yang datang pada waktu tersebut dengan processing time yang lebih
rendah.
Misalnya
pada detik ke 0 datang proses A dengan processing time 4, lalu pada detik ke 2
ada proses C datang dengan processing time 1, yang dilakukan pada preemptive
ini adalah menjalankan proses C terlebih dahulu dengan kata lain proses A di delay waktu pengerjaannya. Setelah proses C
selesai pada detik ke 3 maka proses A bisa dilanjutkan kembali dengan waktu
menunggunya adalah 1 detik (3-2=1). Namun jika ada proses baru lagi yang datang
dengan processing time nya lebih rendah dari A , maka proses A bisa tertunda
lagi sampai proses tersebut selesai dijalankan. Begitu juga dengan
proses-prosess selanjutnya.
Jadi
untuk jawaban preemptive adalah :
Waktu
menunggu untuk A=0, B=4, C=0, D=1, E=3
Rata-rata
waktu menunggu = (0+4+0+1+3)/5 = 1,6 detik
Tidak ada komentar:
Posting Komentar