Session 9 – Scheduling

Behaviour of Process

1. Process-bound : dilihat dari proses itu sendiri
2. 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 :

1. berubah dari running ke waiting state
2. berubah dari running ke ready state
3. berubah dari waiting ke ready state
4. 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

1. 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
2. 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
3. Interactive system
   – Response time : merespon permintaan (request) dengan cepat
   – Proportionallity : memenuhi harapan pengguna (user’s expectation)
4. 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.

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

 

www.binus.ac.id

www.skyconnectiva.com