CPU Scheduler Ch. 5. SISTIM OPERASI (Operating System) IKI Johny Moningka

CPU Scheduler – Ch. 5 SISTIM OPERASI (Operating System) IKI-20230 Johny Moningka ([email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001

Chapter 5: CPU Scheduling n n n n n n

Basic Concepts Scheduling Criteria Scheduling Algorithms Multiple-Processor Scheduling Real-Time Scheduling Algorithm Evaluation

OS Processes JM-2000/v1.1/2

Basic Concepts n

n

n

Pemakaian CPU secara maksimum dengan multiprogramming => makin banyak jobs/task yang dijalankan makin baik CPU–I/O Burst Cycle – Eksekusi proses terdiri dari siklus instruksi-instruksi CPU dan I/O request/wait. Bagaimana prilaku CPU-burst? n n

Karakteristik dan berapa lama (tergantung profile program?) Distribusi lamanya CPU-brust (histogram-frekwensi) • Mayoritas proses => CPU-burst pendek (2 s/d 4 milidetik). • Sedikit menggunakan waktu CPU yang lama (lebih dari 8 milidetik). OS Processes JM-2000/v1.1/3

Sequence of CPU And I/O Bursts


Histogram of CPU-burst Times


CPU Scheduler n

Algoritma scheduling: n

n

Memilih dari proses-proses yang berada di memori (ready to execute) dan memberikan jatah CPU ke salah satu proses tersebut.

Kapan keputusan untuk algoritma dilakukan: n

Saat suatu proses: 1.Switches from running to waiting state. 2.Switches from running to ready state. 3.Switches from waiting to ready. 4.Terminates.


Types of Scheduling n

Bagaimana pemilihan dilakukan oleh Scheduler? n

n

n

Preemptive: OS dapat mengambil (secara interrupt, preempt) CPU dari satu proses setiap saat. Non-preemptive: setiap proses secara sukarela (berkala) memberikan CPU ke OS.

Contoh: n

n

Scheduling untuk switch dari running ke wait atau terminate: non-preemptive. Scheduling proses dari running ke ready: pre-emptive. • Prasyarat untuk OS real-time system.


Dispatcher n

Modul Dispatcher: mengatur dan memberikan kontrol CPU kepada proses yang dipilih oleh “short-term scheduler”: n n n

n

switching context switching to user mode jumping to the proper location in the user program to restart that program

Dispatch latency – terdapat waktu yang terbuang (CPU idle) dimana dispatcher menghentikan satu proses dan menjalankan proses lain. n

Save (proses lama) dan restrore (proses baru). OS Processes JM-2000/v1.1/8

Scheduling Criteria n n n n n

Utilisasi CPU: menjadikan CPU terus menerus sibuk (menggunakan CPU semaksimal mungkin). Throughput: maksimalkan jumlah proses yang selesai dijalankan (per satuan waktu). Turnaround time: minimalkan waktu selesai eksekusi suatu proses (sejak di submit sampai selesai). Waiting time: minimalkan waktu tunggu proses (jumlah waktu yang dihabiskan menunggu di ready queue). Response time: minimalkan waktu response dari sistim terhadap user (interaktif, time-sharing system), sehingga interaksi dapat berlangsung dengan cepat.


Scheduling Algorithms n n n n n n

First-come, first-served (FCFS) Shortest-Job-First (SJF) Priority Round-Robin (RR) Multilevel Queue Multilevel Feedback Queue


First-Come, First-Served (FCFS) n

Algoritma: n

n

n

Proses yang request CPU pertama kali akan mendapatkan jatah CPU. Sederhana – algoritma maupun struktur data: menggunakan FIFO queue (ready queue).

FIFO: Non preemptive n

Timbul masalah “waiting time” terlalu lama jika didahului oleh proses yang waktu selesainya lama. • Tidak cocok untuk time-sharing systems. • Digunakan pada OS dengan orientasi batch job.


FCFS: too long to wait n Example:

Process Burst Time P1 24 P2 3 P3 3 n Suppose that the processes arrive in the order: P1 , P2 , P3 : The Gantt Chart for the schedule is: P1 0

P2 24

P3 27

30

n Waiting

time for P1 = 0; P2 = 24; P3 = 27 n Average waiting time: (0 + 24 + 27)/3 = 17 OS Processes JM-2000/v1.1/12

FCFS Scheduling (Cont.) Suppose that the processes arrive in the order P2 , P3 , P1 . n The Gantt chart for the schedule is: P2 0 n n

P3 3

P1 6

30

Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 • Much better than previous case.

n

Convoy effect short process behind long process OS Processes JM-2000/v1.1/13

SJF Scheduling n

Algoritma: n n n

n

Alokasikan CPU kepada proses dengan waktu pemakaian CPU terpendek. Menghasilkan solusi optimal untuk: minimum. average waiting time. Prasyarat terdapat informasi awal lamanya suatu jobs (dari programmer atau log) => valid untuk batch jobs (long term scheduler).

Secara umum: sulit untuk melakukan prediksi pemakaian CPU untuk suatu proses (short term scheduler). OS Processes JM-2000/v1.1/14

Shortest-Job-First (SJR) n

Prediksi suatu proses dengan panjang waktu CPU burst yang akan digunakan (CPU intensive atau I/O intensive). n

n

Two schemes: n

n

n

Gunakan “panjang waktu pemakaian CPU kelak” akan sama dengan waktu pemakaina CPU-burst sebelumnya. Nonpreemptive – sekali CPU diberikan ke proses maka proses tersebut tidak dapat disingkirkan sampai CPU burst selesai. Preemptive – jika terdapat proses baru dengan CPU burst lebih kecil dibandingkan sisa waktu CPU proses “running” saat ini – maka preempt proses tersebut => Shortest-Remaining-Time-First (SRTF).

SJF is optimal – gives minimum average waiting time for a given set of processes. OS Processes JM-2000/v1.1/15

SJF: min turnaround time Process

CPU Time

P0 P1 P2

x y z

P0 0

P1 x

P2 x+y

x+y+z

Avg. turnaround time = [ x + (x+y) + (x+y+z) ] / 3 To minimize:

x
Priority Scheduling n

Algoritma: n n n n n

n

Setiap proses akan mempunyai prioritas (bilangan integer). CPU diberikan ke proses dengan prioritas tertinggi (smallest integer ≡ highest priority). Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis. SJF adalah contoh priority scheduling dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya.

Problem ≡ Starvation n n

low priority processes may never execute. Solution ≡ Aging • Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU. OS Processes JM-2000/v1.1/17

Round Robin (RR) n

Setiap proses mendapat jatah waktu CPU (time slice/quantum) tertentu misalkan 10 atau 100 milidetik. n

n

n

Jika terdapat n proses di “ready queue” dan waktu quantum q (milidetik), maka: n n

n

Setelah waktu tersebut maka proses akan di-preempt dan dipindahkan ke ready queue. Adil dan sederhana.

Maka setiap proses akan mendapatkan 1/n dari waktu CPU. Proses tidak akan menunggu lebih lama dari: (n-1)q time units.

Performance n n

q large ⇒ FIFO q small ⇒ q must be large with respect to context switch, otherwise overhead is too high. OS Processes JM-2000/v1.1/18

Example: RR (q=20) Process P1 P2 P3 P4

Burst Time 53 17 68 24

Gantt chart: P1 0

P2 20

P3 37

P4 57

P1 77

P3 97

117

P4

P1 121 134

P3

P3 154 162

Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response OS Processes JM-2000/v1.1/19 terhadap user lebih cepat.

Time Quantum vs Context Switches


Varying The Quantum n n

n

Assuming context switch time is 3 msec For a short quantum, Q = 15 msec: overhead = 3 / (3 + 15) = 16.67 % For a long quantum, Q = 97 msec: overhead = 3 / (3 + 97) = 3 %


Multilevel Queues Scheduling n

Kategori proses sesuai dengan sifat proses: n n

n

Partisi “ready queue” dalam beberapa tingkat (multilevel) sesuai dengan proses: n

n n

n

Interaktif (response cepat) Batch dll

Setiap queue menggunakan algoritma schedule sendiri Foreground proses (interaktif, high prioritiy): RR Background proses (batch, low priority): FCFS

Setiap queue mempunyai prioritas yang fixed. OS Processes JM-2000/v1.1/22

Multilevel Queue Scheduling


Mutlilevel scheduling n

Scheduling must be done between the queues. n

n

Fixed priority scheduling; i.e., serve all from foreground then from background. Possibility of starvation. Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., • 80% to foreground in RR • 20% to background in FCFS

n

Proses kemungkinan dapat berpindah secara dinamik dari satu queue ke queue lain. n

Faktor yang mepengaruhi perpindahan tsb? OS Processes JM-2000/v1.1/24

Multilevel Feedback Queue n n

A process can move between the various queues; Perlu feedback untuk penentuan proses naik/turun prioritasnya (dinamis): n

n

Aging dapat diimplementasikan sesuai dengan lama proses pada satu queue. Suatu proses yang menggunakan CPU sampai habis (tanpa I/O wait) => CPU-bound (bukan proses interaktif) dapat dipindahk ke queue dengan prioritas lebih rendah


Multilevel Feedback Queues


Example: Multilevel Feedback n

Three queues: n n n

n

Q0 – time quantum 8 milliseconds Q1 – time quantum 16 milliseconds Q2 – FCFS

Scheduling n

n

A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1. At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2. OS Processes JM-2000/v1.1/27

Multiple-Processor Scheduling n n n n

CPU scheduling more complex when multiple CPUs are available. Homogeneous processors within a multiprocessor. Load sharing Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing.


Real-Time Scheduling n

Hard real-time scheduling: n n

Task kritis harus selesai dengan garansi waktu tertentu OS akan melacak lamanya task tersebut dieksekusi (real time): • Mengetahui lama waktu system call, fungsi dan response dari hardware • Melakukan prediksi apakah task tersebut dapat dijalankan.

n

n

Mudah dilakukan untuk OS khusus pada peralatan/pemakaian khusus (single task: control system) Sulit untuk time-sharing sistim, virtual memory (faktor latency sebagian program aktif ada di disk). OS Processes JM-2000/v1.1/29

Dispatch Latency


Soft Real-Time Computing n

Soft real-time scheduling: n n n n

requires the use of a priority scheme multimedia, highly interactive graphics priority must not degrade over time small dispatch latency • insert preemption points in long duration system calls • make the entire kernel preemptable


CPU Scheduler Ch. 5. SISTIM OPERASI (Operating System) IKI Johny Moningka

Recommend Documents