Sistem Operasi 5 “Process Schedulling” Antonius Rachmat C, C S.Kom, S Kom M.Cs
B i C Basic Concept • Tujuan Utama : agar proses-proses berjalan secara konkuren dan untuk memaksimalkan kinerja dari CPU. p • Pemanfaatan CPU maksimum diperoleh dengan multiprograming – Proses dieksekusi secara bergantian g
• CPU-I/O Burst Cycle adalah pelaksanaan proses yg terdiri dari suatu siklus tunggu I/O dan eksekusi CPU
Alternating Sequence of CPU And I/O Bursts
Histogram of CPUCPU-burst Times Ti
CPU Scheduler S h d l • Short term scheduler memilih dari sekian proses yang ada di ready queue yang sudah siap dieksekusi, dan mengalokasikan CPU untuk k kepadanya d • Penjadwalan CPU akan terjadi perubahan state: 1. 2. 3. 4.
Berubah dari running g ke waiting g state. Berubah dari running ke ready state. Berubah dari waiting ke ready. Terminates.
• Penjadwalan 1 dan 4 adalah non preemptive; sekali CPU telah dialokasikan untuk sebuah proses,, maka tidak bisa di ganggu, p g gg , – contoh pada windows 3.x dan DOS
• Selain itu bersifat preemptive (> win 95 dst)
Di Dispatcher h • Merupakan modul pemberi kontrol CPU kepada proses, yg fungsinya : – switching context – switching to user mode – Lompat dari suatu bagian di progam user untuk mengulang progam.
• Dispatch Latency: waktu yang dibutuhkan untuk menstop satu proses dan menjalankan proses lainnya – Sebisa mungkin g secepat-cepatnya. p p y
S h d li Scheduling C Criteria i i • CPU utilization tili ti – keep k the th CPU as busy b as possible (ideal: 40-90%) • Throughput g p – # of p processes that complete p their execution per time unit – Rata-rata untuk proses yang sebentar 10 proses per dtk
• Turnaround time – amount of time to execute a particular process – dibawa ke memori, menunggu di ready queue, eksekusi di CPU CPU, dan I/O
• Waiting time – amount of time a process has been waiting in the ready queue • Response time – amount of time it takes from when a request was submitted until the first response p is p produced,, not output p (for ( timesharing environment)
O i i Optimization i C Criteria i i • Max CPU utilization • Max throughput • Min turnaround time • Min waiting time • Min response time
S h d li Scheduling Al Algorithm ih • First-Come, First-Served • Shortest Shortest-Job-First Job First • Priority • Round-Robin • Multilevel Queue • Multilevel Feedback Queue
FCFS
FCFS (2)
Bersifat non preemptive
Sh Shortest Job J b First Fi • M Mendahulukan d h l k proses dengan d b burstt ti time terkecil t k il (shortest next CPU burst) • Avg waiting time terkecil (optimal) • Sulit menentukan panjang CPU burst (prediksi) • Two schemes: – Non preemptive – once CPU given to the process it cannot be preempted until completes its CPU burst – preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)
Prediction of the Length of the N t CPU B Next Burstt
SJF non preemptive i
SJF preemptive i
P i i S Priority Schedulling h d lli • Tiap Ti proses diberikan dib ik skala k l prioritas i it • Skala bisa ditentukan secara i t internal/eksternal l/ k t l • Preemptive or not. • Non preemptive = FCFS berprioritas • Preemptive = SJF berprioritas
• Problem: Starvation - low priority processes may p y never execute • Solution: Aging – as time progresses p g increase the p priority y of the process
R Round dR Robin bi • Digilir Di ili selama l time quantum q ant m (q) ( ) • Sekitar 10-100ms
• Performa tergantung besar time quantum. • Adil, Adil semua proses mendapat jatah CPU 1/n, dan tidak akan menunggu lebih dari (n-1)/q • Jika time quantum sangat besar (infinite), akan seperti FCFS. • Kalau K l tterlalu l l k kecil, il context t t switch it h (perpindahan) terlalu banyak
RR with i h time i quantum= 20
RR with Time Quantum = 4 Process P ocess P1 P2 P3 The Gantt chart is: P1 0
P2 4
P3 7
P1 10
P1 14
P1 18 22
Burst B st Time 24 3 3
P1 26
P1 30
Time Q Quantum and Context Switch Time
M l i llevell queue Multi • Terdiri dari beberapa antrian (queue): – foreground (interactive) – background (batch)
• Tiap bagian antrian mempunyai skala prioritas • Antrian tidak akan mendapat jatah CPU, selama masih ih ada d antrian t i dg d prioritas i it lebih l bih tinggi ti i yg belum mendapat jatah • Time slice – each queue gets a certain amount of CPU time – 80% to foreground in RR, and 20% to background in FCFS
• Each queue has its own scheduling algorithm – foreground – RR – background – FCFS
M l il Multilevel lQ Queue S Scheduling h d li
M l i llevell ffeedback Multi db k queue • Proses bisa pindah antar antrian • Dengan metode Aging gg untuk p proses y yang g CPU burstnya y • Prioritas tertinggi terkecil
• Umumnya antrian high priority menggunakan RR, yang y g rendah FCFS • Lebih mendukung interaktivitas • Parameternya – – – –
Jumlah l h antrian Algoritma tiap antrian Antrian mana yg g akan dimasukki oleh proses Kapan menaikkan proses ke prioritas yg lebih tinggi dan menurunkan proses ke prioritas yg lebih rendah
Example of Multilevel Feedback Queue • Ex: in three queues: – Q0 – RR with time quantum 8 milliseconds – Q1 – FCFS time quantum 16 milliseconds – Q2 – FCFS
• Scheduling
– 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. milliseconds, job is moved to queue Q1. g served FCFS and receives 16 – At Q1 jjob is again additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.
M l il Multilevel lF Feedback db k Q Queues
Th Thread dS Scheduling h d li • Distinction between user-level and kernel-level kernel level threads • Many-to-one and many-to-many models, thread library y schedules user-level threads to run on LWP (Light Weight Process) – Known as process-contention scope (PCS) since scheduling competition is within the process
• Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system
R l Ti Real Time S Schedulling h d lli • Asumsi: – Ada batasan waktu: ada deadline – Semua kejadian dapat diprediksi – Jika ada banyak proses terjadi bersamaan, maka semua deadline harus terpenuhi. terpenuhi
R l time Real i schedulling h d lli • Hard-Real H d R l Time Ti – Menjamin proses dapat diselesaikan dengan tepat waktu. • Biasanya <= 100 mikro detik
– Pada saat proses dikirim, terdapat statement yang menyatakan jumlah waktu yang diperlukan untuk menyelesaikan proses tersebut. – Setelah deadline, proses langsung berhenti. – Scheduler memainkan peranan yang penting. penting – Jika permintaan alokasi waktu terlalu besar (atau tidak dapat diprediksi), maka scheduler akan menolaknya. – Contoh: pengkontrol pesawat terbang
Real R l time i schedulling h d lli (2) • Soft-Real S ft R l Ti Time
– Memiliki keterbatasan yang lebih rendah dari hard-time hard time system. (lebih longgar) – Setelah deadline, proses langsung berhenti bertahap. – Critical C iti l task t k dib diberikan ik prioritas i it yang lebih l bih tinggi dari yang lainnya. – Memerlukan desain scheduler y yang g lebih cermat, karena harus men-set prioritas. – Dapat menyebabkan pembagian resource yang kurang adil adil, delay yang lama, lama sampai terjadinya starvation. – Contoh: alat penjual / pelayanan otomatis.
H d vs S Hard Soft f Graphics G hi
Multiple--Processor Scheduling Multiple - CPU scheduling more complex when multiple CPUs are available - Homogeneous processors within a multiprocessor lti - Asymmetric multiprocessing – only one processor accesses the system data structures (sharing) - Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes
Windows XP Priorities
Linux Priorities: tthe he Relationship Between Priorities and TimeTime-slice length
NEXT • Process Synchronization
