Priority

PRIORITY
Algoritma ini memberikan skala prioritas kepada tiap proses. Proses yang mendapat prioritas terbesar akan didahulukan. Skala diberikan dalam bentuk integer. Beberapa sistem menggunakan integer kecil untuk prioritas tertinggi, beberapa sistem menggunakan integer besar.

Algoritma ini dapat preemptive maupun nonpreeemptive. Jika preemptive maka proses dapat diinterupsi oleh proses yang prioritasnya lebih tinggi. Kelemahan dari algoritma ini adalah proses dengan prioritas kecil tidak akan mendapat jatah CPU. Hal ini dapat diatasi dengan aging, yaitu semakin lama menunggu, prioritas semakin tinggi.

Konsep prioritas sangat penting dalam penjadwalan prosesor jamak. Prioritas adalah tingkat kepentingan suatu proses yang ada di ready queue. Prioritas adalah suatu istilah yang digunakan untuk menentukan tingkat urutan atau hirarki suatu proses yang sedang masuk dalam ready queue.

Akan tetapi, ada kemungkinan proses yang mempunyai prioritas tinggi, memerlukan data yang sedang diakses oleh proses yang mempunyai prioritas lebih rendah. Maka, proses yang berprioritas tinggi harus menunggu dan membiarkan proses yang berprioritas rendah menyelesaikan eksekusinya. Situasi ini disebut pembalikan priority inversion.

Namun, pembalikan prioritas memungkinkan proses yang prioritasnya lebih rendah dapat terus menerus mengakses sumber daya yang sedang dibutuhkan oleh proses yang prioritasnya lebih tinggi.

Solusi untuk masalah ini adalah priority inheritance protocol, yaitu semua proses yang sedang mengakses sumber daya mendapat prioritas tinggi sampai selesai menggunakan sumber daya. Setelah selesai, prioritas proses ini dikembalikan menjadi seperti semula.

priority-inheritance protocol, yaitu semua proses yang sedang mengakses sumber daya mendapat prioritas tinggi sampai selesai menggunakan sumber daya. Setelah selesai, prioritas proses ini dikembalikan menjadi seperti semula.

Priority inversion adalah kejadian dimana sebuah Task dengan priority rendah.

(misalkan Task 2) dapat menunda eksekusi Task dengan priority yang lebih tinggi (misalkan Task 1).

Misalkan sebuah set 3 Task dengan urutan priority : Task 1 > Task 2 > Task 3.

Priority inversion dapat terjadi apabila Task 1 hendak mengakses unsharedable resource (contoh: penulisan data ke harddisk atau printing) yang kebetulan sedang digunakan oleh Task lain dengan priority yang lebih rendah (misalkan Task 3). Pada saat itu, Task 1 tidak dapat diteruskan dan Task 3 akan dilanjutkan. Pada saat Task 3 dilanjutkan, Task 2 dapat menginterupsi Task 3 (selama Task 2 tidak mengakses resource) karena priority Task 2 lebih tinggi dari Task 3.

Pada kejadian tersebut, Task 2 menunda eksekusi Task 1 secara tidak langsung dengan menginterupsi Task 3 yang sedang memegang unsharedable resource (dan dengan demikian Task 3 memblok Task 1 yang juga hendak memakai resource tersebut).

contoh yang diberikan :

Ø Pada saat t0, Task 3 mulai di-release dan dijalankan.

Ø Pada saat t1, Task 3 memasuki critical section dan mengakses unsharedable resource R.

Ø Pada saat t2, Task 1 di-release. Karena Task 1 memiliki priority yang lebih tinggi daripada Task 3 dan tidak membutuhkan resource R pada saat itu, maka Task 1 menginterupsi Task 3. Semaphore pada resource R diset untuk menandakan bahwa resource tersebut sedang dikontrol oleh Task 3.

Ø Pada saat t3, Task 1 memasuki critical section yang membutuhkan resource R. Karena resource R sedang dipegang oleh Task 3, maka Task 1 dihentikan dan eksekusi Task 3 dilanjutkan.

Ø Pada saat t4, Task 2 di-release. Karena Task 2 memiliki priority di atas Task 3 dan tidak membutuhkan resource R maka Task 2 menginterupsi Task 3. Pada saat ini, priority inversion terjadi dimana Task 2 dapat menunda eksekusi Task 1.

Ø Pada saat t5, Task 2 selesai dijalankan. Task 3 kembali dilanjutkan.

Ø Pada saat t6, Task 3 selesai menggunakan R. Task 3 melepaskan kontrol terhadap R. Task 1 dilanjutkan dan memegang kontrol atas R.

Ø Pada saat t7, Task 1 telah selesai menggunakan R dan melepaskan kontrol terhadapnya.

Ø Pada saat t8, Task 1 telah selesai dijalankan. Task 3 dilanjutkan.

Ø Pada saat t9, Task 3 selesai dijalankan.

è Priority Inheritance adalah teknik untuk mencegah priority inversion. Pada saat Task

dengan priority yang lebih tinggi (TH) diblok oleh Task dengan priority yang lebih rendah (TL) karena penggunaan unsharedable resource maka TL akan mewarisi priority TH. Setelah TL selesai menggunakan resource tersebut, priority TL dikembalikan ke asalnya.

Berikut ini adalah contoh penggunaan priority inheritance pada kasus priority inversion di atas :


Berikut ini adalah penjelasan dari gambar di atas :

Ø Pada saat t3, Task 1 diblok oleh Task 3 yang sedang mengontrol R. Task 3 mewarisi priority Task 1 (dalam set Task ini, priority tertinggi) dan eksekusinya diteruskan dengan priority yang baru. Pada saat ini terjadi priority inheritance.

Ø Pada saat t4, Task 2 di-release. Karena Task 2 memiliki priority yang lebih rendah daripada Task 3 pada saat ini, eksekusi Task 2 tertunda dan Task 3 dilanjutkan.

Ø Pada saat t5, Task 3 selesai menggunakan R. Karena Task 3 telah melepaskan kontrol atas R, maka blok terhadap Task 1 selesai. Pada saat ini, priority Task 3 dikembalikan menjadi priority asalnya. Task 1 kemudian menginterupsi Task 3 dan mulai menggunakan R.

Ø Pada saat t7, Task 1 selesai dijalankan. Task 2 mulai dieksekusi.

Ø Pada saat t8, Task 2 selesai dijalankan. Task 3 dilanjutkan.

Ø Pada saat t9, Task 3 selesai dijalankan.

Priority Inheritance
Priority inheritance is a protocol used to avoid the problem of priority inversion. When a lower priority task is blocking a higher priority task, it inherits the priority of the higher priority task. It gains its priority back when the blocking is over. The bad side of priority inversion is that it can lead to deadlock.

Untuk menghindari problem priority inversion maka digunakan priority inheritance. Dimana skema dari priority inheritance adalah jika task dengan prioritas lebih tinggi TH diblock oleh task dengan prioritas lebih rendah TL(karena TL sedang mengeksekusi critical section yang dibutuhkan oleh TH), task dengan prioritas lebih rendah secara temporary (sesaat) inherits(mewarisi) prioritas dari TH. Ketika blocking berhenti, TL kembali ke prioritas asalnya.













Protocol priority inheritance adalah sebagai berikut,
1. task dengan prioritas paling tinggi T ditentukan oleh processor. T melepaskan processor sewaktu-waktu ketika T bertemu dengan lock semaphore guarding sebuah critical section yang telah di lock oleh task lain
2. jika suatu task T1 diblock oleh task T2(karena adanya critical section) dan T1 memiliki prioritas lebih tinggi dibanding T2, T2 mewarisi(inherits) prioritas dari T1 selama T2 memblock T1. Ketika T2 keluar dari critical section yang telah menyebabkan pemblockan, T2 akan kembali ke prioritas semula dimana T1 > T2 (T1 lebih prioritas dibanding T2). operasi priority inheritance dan pembagian priority sebelumnya sudah tak berlaku lagi
3. priority inheritance bersifat transitive. Jika T3 memblock T2, yang memblock T1(T1 > T2 > T3), kemudian T3 mewarisi prioritas T1 melalaui T2
4. suatu task T1 dapat menginterupsi task lain T2, jika T1 tidak dblock dan jika prioritas T1 lebih besar dibanding prioritas T2

contoh2 untuk mengetahui bagaimana priority inheritance dapat mencegah terjadinya priority inversion, kita kembali analisis contoh1. pada saat t3, ketika T3 memblock T1, T3 mewarisi prioritas yang lebih besar dari T1. sehingga ketika T2 release pada t4, T2 tidak dapat menginterusi T3, karena pada t4 prioritas T3 lebih tinggi (mewarisi prioritas T1) disbanding T2. T3 terus berjalan menggunakan critical section S hingga selesai pada tx. Pada saat itu T3 melepas critical section S dan T1 dapat melanjutkan eksekusinya. Pada saat tx prioritas T3 telah kembali ke prioritas semula. Sehingga T1 dapat menginterupsi T3. Sebagai hasilnya, T1 tidak indirectly block oleh T2

sayangnya, priority inheritance dapat menyebabkan:
1) deadlock.
2) Timbul kemungkinan dimana task dengan prioritas paling tinggi dapat diblock sekali oleh setiap task yang dieksekusi oleh processor yang sama

Fenomena deadlock dapat diilustrasikan dengan contoh berikut
contoh3 terdapat 2 task T1 dan T2, dimana menggunakan 2 critical section S1 dan S2. task-task ini memerlukan critical section dalam urutan sebagai berikut:
T1 : lock S1 . lock S2 . unlock S2 . unlock S1
T2 : lock S2 . lock S1 . unlock S1 . unlock S2

Dengan T1 > T2, dan kita asumsikan T2 mulai eksekusi pada t0. pada saat t1, T2 locks S2. pada saat t2, T1 mulai dan menginterupsi T2 berdasarkan prioritasnya yang lebih tinggi. Pada saat t3, T1 locks S1. pada saat t4, T1 berusaha untuk lock S2, tetapi diblock karena T2 belum selesai menggunakan S2 ini. T2, dimana mewarisi prioritas dari T1 mulai eksekusi. Pada saat t5, T2 berusaha untuk lock S1, tetapi tidak bisa karena T1 sudah me-lock S1. sekarang T1 dan T2 saling menunggu resource yang masing-masing masih di lock oleh task lain. T1 menunggu S2 yang masih di lock oleh T2, sedang T2 menunggu S1 yang masih di lock oleh T1. sehingga terjadilah deadlock.




Priority
Algoritma ini memberikan skala prioritas kepada tiap proses. Proses yang mendapat prioritas terbesar akan didahulukan. Skala diberikan dalam bentuk integer. Beberapa sistem menggunakan integer kecil untuk prioritas tertinggi, beberapa sistem menggunakan integer besar.
Algoritma ini bisa preemptive maupun nonpreeemptive . Jika preemptive maka proses bisa diinterupsi oleh proses yang prioritasnya lebih tinggi.
Kelemahan dari algoritma ini adalah proses dengan prioritas kecil bisa-bisa tidak akan mendapat jatah CPU. Hal ini bisa diatasi dengan aging , yaitu semakin lama menunggu, prioritas semakin tinggi.
5)PreemptivePriority.
Harus diperhatikan bahwa penjadwalan selalu dikelola dengan prioritas, baik rendah ataupun tinggi. Job dengan prioritas yang sama ada dalam penjadwalan FCFS. Algoritma penjadwalan Shortest Job First adalah bentuk khusus dari penjadwalan Prioritas yang umum karena SJF dapat dijalankan dengan prioritas menurut nilai yang dihitung dari kebalikan (perkirakan) waktu penyelesaian job.
Prioritas-prioritas biasanya dalam bentuk bilangan yang telah ditetapkan sebelumnya. Walaupun demikian masih belum ada kesepakatan apakah suatu angka kecil memang menunjukkan prioritas yang rendah. Prioritas dapat dihitung baik secara ienternal maupun eksternal. Prioritas yang terdefinisi secara internal menggunakan ukuran kuantitas, seperti batas waktu, kebutuhan memori, jumlah file yang dibukanya, ataupun perbandingan antara waktu I/O dengan waktu CPU, dan lain-lain. Prioritas eksternal ditentukan oleh kriteria di luar sistem operasi, misalnya jumlah iuran yang dibayar untuk pemakaian komputer, bagian yang mensponsori kerja, bahkan mungkin saja faktor-faktor politis juga.
Masalah utama dengan algoritma penjadwalan Prioritas adalah penahanan (blocking) takterbatas atau lebih dikenal starvation. Starvation muncul jika suatu job telah siap untuk dijalankan (sedang menunggu CPU) tetapi tidak pernah diberi kesempatan untuk menyelesaikan jobnya karena prioritasnya rendah. Pemecahan masalah ini adalah Aging (untuk selanjutnya disebut pemetaan). Pemetaan adalah teknik yang menaikkan secara berkala prioritas job yang sudah lama menunggu di dalam sistem. Misalnya untuk kisaran prioritas antara 0 (rendah) sampai 127 (tinggi), prioritas job yang menuggu dapat dinaikkan 1 setiap 15 menit . Sehingga walaupun prioritas job semula adalah 0, namun suatu saat mampu pula mencapai prioritas tertinggi dan akhirnya dijalankan oleh CPU.
Walaupun sesungguhnya suatu sistem dapat memiliki beberapa buah CPU, dalam pembahasan selanjutnya untuk penyederhanaan hanya akan disediakan satu CPU untuk pengerjaan beberapa job.
Priority Scheduling
Algoritma SJF adalah suatu kasus khusus dari penjadwalan berprioritas. Tiaptiap
proses dilengkapi dengan nomor prioritas (integer). CPU dialokasikan untuk proses
yang memiliki prioritas paling tinggi (nilai integer terkecil biasanya merupakan prioritas
terbesar). Jika beberapa proses memiliki prioritas yang sama, maka akan digunakan
algoritma FCFS. Penjadwalan berprioritas terdiri dari dua skema yaitu non preemptive
dan preemptive. Jika ada proses P1 yang datang pada saat P0 sedang berjalan, maka
akan dilihat prioritas P1. Seandainya prioritas P1 lebih besar dibanding dengan prioritas
P0, maka pada non-preemptive, algoritma tetap akan menyelesaikan P0 sampai habis
CPU burst-nya, dan meletakkan P1 pada posisi head queue. Sedangkan pada
preemptive, P0 akan dihentikan dulu, dan CPU ganti dialokasikan untuk P1.
Misalnya terdapat lima proses P1, P2, P3, P4 dan P5 yang datang secara
berurutan dengan CPU burst dalam milidetik.
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
Penjadwalan proses dengan algoritma priority dapat dilihat pada gant chart berikut :
BAB 4 PENJADWALAN CPU
59
Waktu tunggu untuk P1 adalah 6, P2 adalah 0, P3 adalah 16, P4 adalah 18 dan P5 adalah
1 sehingga rata-rata waktu tunggu adalah (6 + 0 +16 + 18 + 1)/5 = 8.2 milidetik.

Priority Inheritance –Protocol
Prioritas ditukar hanya sementara. Setelah keperluan selesai, prioritas diganti kembali.

Priority
Algoritma ini memberikan skala prioritas kepada tiap proses. Proses yang mendapat prioritas
terbesar akan didahulukan. Skala diberikan dalam bentuk integer. Beberapa sistem
menggunakan integer kecil untuk prioritas tertinggi, beberapa sistem menggunakan integer
besar.
Algoritma ini dapat preemptive maupun nonpreeemptive. Jika preemptive maka proses dapat
diinterupsi oleh proses yang prioritasnya lebih tinggi.
Kelemahan dari algoritma ini adalah proses dengan prioritas kecil tidak akan mendapat jatah
CPU. Hal ini dapat diatasi dengan aging, yaitu semakin lama menunggu, prioritas semakin
tinggi.

Priority
Algoritma ini memberikan skala prioritas kepada tiap proses. Proses yang mendapat prioritas
terbesar akan didahulukan. Skala diberikan dalam bentuk integer. Beberapa sistem
menggunakan integer kecil untuk prioritas tertinggi, beberapa sistem menggunakan integer
besar.
Algoritma ini dapat preemptive maupun nonpreeemptive. Jika preemptive maka proses dapat
diinterupsi oleh proses yang prioritasnya lebih tinggi.
Kelemahan dari algoritma ini adalah proses dengan prioritas kecil tidak akan mendapat jatah
CPU. Hal ini dapat diatasi dengan aging, yaitu semakin lama menunggu, prioritas semakin
tinggi.

3. Priority Scheduling

Priority Scheduling merupakan algoritma penjadwalan yang
mendahulukan proses yang memiliki prioritas tertinggi.
Setiap proses memiliki prioritasnya masing-masing.

Prioritas suatu proses dapat ditentukan melalui beberapa
karakteristik antara lain:

1. Time limit
2. Memory requirement
3. Akses file
4. Perbandingan antara I/O Burst dengan CPU Burst
5. Tingkat kepentingan proses

Priority Scheduling juga dapat dijalankan secara
preemptive maupun non-preemptive.

Pada preemptive, jika ada suatu proses yang baru datang
memiliki prioritas yang lebih tinggi daripada proses
yang sedang dijalankan, maka proses yang sedang berjalan
tersebut dihentikan, lalu CPU dialihkan untuk proses yang
baru datang tersebut.

Sementara itu, pada non-preemptive, proses yang baru datang
tidak dapat menganggu proses yang sedang berjalan, tetapi
hanya diletakkan di depan queue.

Kelemahan pada priority scheduling adalah dapat terjadinya
indefinite blocking (starvation). Suatu proses dengan prioritas
yang rendah memiliki kemungkinan untuk tidak dieksekusi jika
terdapat proses lain yang memiliki prioritas lebih tinggi darinya.

Solusi dari permasalahan ini adalah aging, yaitu meningkatkan
prioritas dari setiap proses yang menunggu dalam queue secara
bertahap.

Contoh:
Setiap 10 menit, prioritas dari masing-masing proses yang
menunggu dalam queue dinaikkan satu tingkat.
Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam
21 jam 20 menit, proses tersebut akan memiliki prioritas 0,
yaitu prioritas yang tertinggi. (semakin kecil angka menunjukkan
bahwa prioritasnya semakin tinggi)

Priority Scheduling
■ Algoritma:
■ 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
■ low priority processes may never execute.
■ Solution = Aging
• Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU.