Penjadwalan
Proses
Ø Definisi
Kumpulan
kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan
kerja yang dilakukan sistem komputer.
Penjadwalan
bertugas memutuskan hal-hal berikut :
- Proses yang harus berjalan
- Kapan dan selama berapa lama
proses berjalan
Sasaran
atau tujuan utama penjadwalan proses optimasi kinerja menurut kriteria
tertentu. dimana kriteria untuk mengukur dan optimasi kerja penjadwalan antara
lain :
- Agar semua pekerjaan memperoleh
pelayanan yang adil (firness).
- Agar pemakaian prosesor dapat
dimaksimumkan.
- Agar waktu tanggap dapat
diminimumkan.
- Agar pemakaian sumber daya
seimbang.
- Turn arround time, waktu sejak
program masuk ke system sampai proses selesai.
- Efesien, proses tetap dalam
keadaan sibuk tidak menganggur.
- Agar terobosan (thoughput)
dapat dimaksimumkan.
Ø Kriteria untuk
mengukur dan optimasi kinerja penjadwalan
- Adil (fairness)
- Efisiensi
- Waktu Tanggap (response time)
- Turn arround Time
- Troughput
1.
Adil(fairness)
Proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan pemroses
yang sama dan tidak ada proses yang tidak kebagian layanan pemroses sehingga
mengalami startvation.
Startvation
adalah kondisi bahwa proses tidak pernah berjalan karena tidak dijadwalkan
untuk berjalan. Sasaran penjadwalan seharusnya menjamin setiap proses mendapat
pelayanan dari pemroses secara adil.
2.
Efisiensi
Efisiensi atau utilisasi pemroses dihitung dengan perbandingan (rasio) waktu
sibuk pemroses dengan total waktu operasi sistem komputer secara keseluruhan.
Sasaran penjadwalan adalah menjaga agar pemroses tetap dalam keadaan sibuk
sehingga efisiensi sistem komputer mencapai nilai maksimum. Keadaan sibuk
berarti pemroses tidak menganggur. Layanan pemroses termasuk waktu yang
dihabiskan untuk mengeksekusi program pemakai dan layanan sistem operasi secara
efektif, bukan untuk melakukan penjadwalan itu sendiri.
3.
Waktu tanggap ( response time)
Waktu
tanggap berbeda untuk :
Waktu
yang dihabiskan dari saat karakter terakhir dari perintah dimasukkan oleh
program atau transaksi sampai hasil pertama muncul di jperangkat masukan
keluaran seperti layar (terminal).Waktu tanggap untuk sistem interaktif biasa
disebut terminal responce time.
- Sistem waktu nyata (real
time)
Pada
sistem waktu nyata, waktu tanggap didefinisikan sebagai waktu dari saat
kemunculan suatu kejadian (internal/eksternal) sampai instruksi pertama rutin
layanan terhadap kejadian dieksekusi. Waktu untuk sistem waktu nyata biasa
disebut event response time.
Sasaran penjadwalan adalah meminimalkan waktu tanggap sehingga menghasilkan
sistem yang responsif.
4.
Turn arround
Time
Waktu yang dihabiskan dari saat proses atau job mulai masuk ke sistem sampai
proses itu diselesaikan sistem.Waktu yang dimaksud adalah waktu yang dihabiskan
proses berada di sistem, diekspresikan sebagai penjumlahan waktu eksekusi
(waktu layanan proses/job) dan waktu menunggu dari proses itu, yaitu :
Turn
arround time = waktu eksekusi + waktu menunggu.
Sasaran
penjadwalan adalah meminimalkan turn arround time.
5.
Troughput
Troughput adalah jumlah kerja yang dapat diselsesaikan selama satu
selang/ unit waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah
proses/job pemakai yang dapat dieksekusi dalam satu unit/ interval waktu
tertentu.
Sasaran penjadwalan adalah memaksimalkan jumlah job/ proses yang dilayani per
satu interval waktu. Lebih tinggi angka througput maka lebih banya kerja yang
dilakukan sistem.
Kriteria tsb saling bergantung dan dapat saling bertentangan sehingga tidak
dimungkinkan optimasi semua kriteria secara simultan.
Ø Tipe – Tipe Penjadwalan
1)
Penjadwal jangka
pendek (short term scheduller)
Bertugas
menjadwalkan alokasi pemroses di antara proses-proses ready di memori utama
Penjadwalan dijalankan setiap terjadi pengalihan proses untuk memilih proses
berikutnya yang harus dijalankan.
2)
Penjadwal jangka
menengah (medium term scheduller)
Setelah eksekusi
selama suatu waktu, proses mungkin menunda sebuah eksekusi karena membuat
permintaan layanan masukan/keluaran atau memanggil suatu system call.
Proses-proses tertunda tidak dapat membuat suatu kemajuan menuju selesai sampai
kondisi-kondisi yang menyebabkan tertunda dihilangkan. Agar ruang memori dapat
bermanfaat, maka proses dipindah dari memori utama ke memori sekunder agar
tersedia ruang untuk proses-proses lain. Kapasitas memori utama terbatas untuk
sejumlah proses aktif. Aktivitas pemindahan proses yang tertunda dari memori
utama ke memori sekunder disebut swapping. Proses-proses mempunyai kepentingan
kecil saat itu sebagai proses yang tertunda. Tetapi, begitu kondisi yang
membuatnya tertunda hilang dan dimasukkan kembali ke memori utama dan ready.
3)
Penjadwal jangka
panjang (long term scheduller)
Penjadwal ini
bekerja terhadap antrian batch dan memilih batch berikutnya yang harus
dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya
yang intensif (yaitu waktu pemroses, memori, masukan/keluaran), program-program
ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama
periode aktivitas job-job interaktif rendah.
Ø
Strategi Penjadwalan
- Penjadwalan nonpreemptive
(run-to-completion). Begitu proses diberi jatah layanan pemroses
aka pemroses tidak dapat diambil alih oleh proses lain sampai proses itu
selesai. Non-preemptive juga disebut run-to-completion karena
proses yang telah dijadwalkan akan dijalankan sampai selesainya atau
proses tersebut meminta layanan masukan/keluaran.
- Penjadwalan preemptive. Saat
proses diberi jatah layanan pemroses maka pemroses dapat diambil alih
proses lain yang mempunyai prioritas lebih tinggi berdasarkan kriteria
sistem itu. Pada penjadwalan preemptive, proses dapat disela oleh proses
lain sebelumnya selesainya dan harus dilanjutkan menunggu jatah waktu
layanan pemroses tiba kembali pada proses itu. Proses yang disela berubah
menjadi state Ready.
Penjadwalan
preemptive berguna pada sistem yakni proses-proses yang perlu mendapat
perhatian/ tanggapan pemroses secara cepat. Misalnya :
- Pada sistem-sistem waktu
nyata, kehilangan interupsi (yaitu interupsi tidak segera dilayani) dapat
berakibat fatal
- Pada sistem-sistem interatif
timesharing, penjadwalan preemptive penting agar dapat menjamin waktu
tanggap yang memadai.
Peralihan
proses (yaitu layanan pemroses dari satu proses beralih ke proses lain)
memerlukan overhead (karena banya tabel yang dikelola). Agar penjadwalan
preemptive menjadi efektif, banyak proses harus berada di memori utama
sehingga proses-proses tersebut dapat segera Running begitu diperlukan.
Menyimpan banyak proses yang tidak Running di memori utama merupakan
suatu overhead tersendiri.
Ø
ALGORITMA
PENJADWALAN PROSES
Algoritma-algoritma
yang menerapkan strategi nonpreemptive diantaranya :
- FIFO (First-In, First-Out) atau FCFS (First-Come,
First-Serve)
- SJF (Shortest Job First)
Algoritma-algoritma
yang menerapkan strategi preemptive diantaranya :
- RR (Round-Robin)
- MFQ (Multiple Feedback Queues)
- SRF (Shortest-Remaining-First)
- HRN (Highest-Remaining-Next)
- PS (Priority Schedulling)
- GS (Guaranteed Schedulling)
Klasifikasi
lain selain berdasarkan dapat/tidaknya suatu proses diambil alih secara paksa
adalah klasifikasi yang berdasarkan adanya prioritas diproses-proses, yaitu :
- Algoritma penjadwalan tanpa berprioritas
- Algoritma penjadwalan berprioritas, terdiri dari :
- Algoritma penjadwalan berprioritas statis
- Algoritma penjadwalan berprioritas dinamis
Algoritma-Algoritma
Penjadwalan Proses
- Penjadwalan Round-Robin (RR)
- Penjadwalan FIFO (FIFO)
- Penjadwalan Berprioritas (PS)
- Penjadwalan yang Terpendek yang Lebih Dahulu (SJF)
- Penjadwalan dengan Banyak Antrian (MFQ)
- Penjadwalan dengan Sisa Waktu Terpendek, Lebih Dahulu
(SRF)
- Penjadwalan Rasio Tanggapan Tertinggi, Lebih
Dahulu(HRN)
- Penjadwalan Terjamin (GS)
a.
Penjadwalan FIFO
Penjadwalan FIFO merupakan :
- Penjadwalan non preemptive (run-to-completion)
- Penjadwalan tidak berprioritas
Penjadwal FIFO adalah penjadwalan
dengan ketentuan-ketentuan paling sederhana, yaitu :
- Proses-proses diberi jatah
waktu pemroses diurutkan berdasarkan waktu kedatangan proses-proses itu ke
sistem.
- Begitu proses mendapat jatah waktu pemroses, proses
dijalankan sampai selesai
Penjadwalan
ini dikatakan adil dalam arti resmi, tapi dikatakan tidak adil karena proses
yang memerlukan waktu lama membuat proses pendek menunggu. Proses tidak penting
dapat membuat proses penting menjadi menunggu.
FIFO jarang digunakan secara mandiri tapi dikombinasikan dengan skema lain,
misalnya keputusan berdasarkan prioritas proses, sedangkan untuk proses
berprioritas sama diputuskan berdasarkan FIFO.
Berdasarkan
kriteria penilaian penjadwalan :
- Fairness,
penjadwalan FIFO adil dalam arti resmi
- Efisiensi, FIFO sangat efisien dalam penggunaan
pemroses
- Waktu tanggap, penjadwalan sangat tidak memuaskan
karena proses dapat menunggu lama. Tidak cocok untuk sistem interaktifTurn
arround time, penjadwalan FIFO tidak bagus
- Throughput, penjadwalan FIFO tidak bagus.
Contoh : ada 3 proses P1, P2, P3 dengan
lama waktu kerja CPU (CPU Burst-time) masing-masing sbb
PROSES
|
BUST-TIME
|
P1
|
24
|
P2
|
3
|
P3
|
3
|
i) Jika proses datang dengan urutan P1, P2, P3
dan dilayani dengan algoritma FIFO maka dapat digambarkan Gantt Chart-nya :
Waktu
tunggu P1 : 0 milidetik, P2 : 24, P3: 27
Rata-rata
waktu tunggu (Average Waiting Time / AWT) : (0+24+27)/3 = 17 milidetik
ii)
Jika
waktu kedatangan proses adalah P3, P2, P1 maka Gantt Chartnya adalah :
AWT
= (0+3+6)/3 = 3 milidetik
iii) Menentukan Turn Around Time
Turn
around time (waktu penyelesaian) P1 adalah 24, P2 = 27, P3 = 30, maka rata-rata
turn around time = (24+27+30)/3 = 27 milidetik
b. Penjadwalan
SJF
Penjadwalan
SJF ini merupakan
- Penjadwalan non preemptive
- Penjadwalan dapat dikatakan sebagai berprioritas. Di
SJF, prioritas diasosiasikan dengan masing-masing proses dan pemroses
dialokasikan ke proses dengan prioritas tertinggi. Proses-proses dengan
prioritas yang sama akan dijadwalkan secara FIFO.
Penjadwalan
ini mengasumsikan waktu jalan proses (sampai selesai) atau waktu lamanya proses
diketahui sebelumnya. Mekanisme penjadwlan SJF adalah lebih dulu menjadwalkan
proses dengan waktu jalan terpendek sampai selesai. Setelah proses itu selesai,
maka proses dengan waktu jalan terpendek berikutnya dijadwalkan. Demikian
seterusnya.
Keunggulan : penjadwalan SJF mempunyai efisiensi tinggi dan turn arround time
rendah.
Contoh
: Terdapat 4 proses A,B,C,D dengan waktu jalan selama 8,7,6,5 kwanta.
Gambar (a) menunjukkan penjadwalan cara I, dengan proses-proses dijadwalkan
berurutan sebagai A,B,C,D. Gambar (b) menujukkan bila proses dijadwalkan secara
SJF yaitu berurutan D,C,B,A.
Kedua
cara menghasilkan turn arround time yang ditunjukkan pada gambar (c).
Cara I turn arround time rata-rata adalah 17,5 kwanta, sedangkan cara II
adalah 15 kwanta
Walaupun mempunyai turn arround yang bagus, SJF mempunyai masalah, yaitu
- Tidak dapat mengetahui ukuran proses saat proses masuk
- Proses tidak datang bersamaan sehingga penetapannya
harus dinamis
Untuk
mengetahui ukuran lama proses agar dapat ditetapkan yang terpendek, biasanya
dilakukan dengan cara pendekatan. Pendekatan yang biasa dilakukan adalah dengan
membuat estimasi berdasarkan perilaku historis sistem. Merupakan kajian
teoritis untuk pembandingan dalam pembandingan turn arround time.
Contoh :
PROSES
|
BUST-TIME
|
P1
|
6
|
P2
|
8
|
P3
|
7
|
P4
|
3
|
i)
Gantt Chart :
Nilai waktu tunggu : P1 = 3 milidetik, P2 = 16 milidetik, P3
= 9 milidetik, P4 = 0 milidetik
AWT : (3+16+9+0) / 4 = 7 milidetik
ii)
Contoh menentukan Turn Around Time
iii)
Contoh menentukan AWT untuk SJF
nonpreemptive:
A = 0 milidetik
B = waktu mulai dilayani – waktu saat tiba = 8-2 = 6
milidetik
C = waktu mulai dilayani – waktu saat tiba = 7-4 = 3 milidetik
D = waktu mulai dilayani – waktu saat tiba = 12-5 = 7
milidetik
AWT : (0+6+3+7) / 4 = 4 milidetik
iv)
Contoh menentukan AWT untuk SJF
preemptive
A = 0 + (11-2) = 9 milidetik
B = 0 + (5-4) = 1 milidetik
C = 0 milidetik
D = 7-5 = 2 milidetik
AWT : (9+1+0+2) / 4 = 3 milidetik.
v)
Menentukan Turn Around Time
Penjadwalan Round Robin
Penjadwalan Round Robin merupakan
- Penjadwalan Preemptive, namun
proses tidak di-preempt secara langsung oleh proses lain, namun oleh
penjadwal berdasarkan lama waktu berjalannya suatu proses. Maka
penjadwalan ini disebut preempt-by-time
- Penjadwalan tanpa prioritas
Semua
proses dianggap penting dan diberi jumlah waktu pemroses yang disebut kwanta (quantum)
atau time-slice tempat proses tsb berjalan. Proses berjalan selama 1
kwanta, kemudian penjadwal akan mengalihkan kepada proses berikutnya juga untuk
berjalan satu kwanta, begitu seterusnya sampai kembali pada proses pertama dan
berulang.
Ketentuan
algoritma round robin adalah sbb :
- Jika kwanta habis dan proses
belum selesai maka proses Runing menjadi Ready dan pemroses dialihkan ke
proses lain
- Jika kwanta belum habis dan
proses menunggu suatu kejadian (misalnya menunggu selesainya suatu operasi
I/O), maka proses Running menjadi Blocked dan pemroses dialihkan ke proses
lain.
- Jika kwanta belum habis tapi
proses telah selesai maka proses Running itu diakhiri dan pemroses
dialihkan ke proses lain
Algoritma
penjadwalan ini dapat diimplementasi sbb :
- Sistem mengelola senarai proses
Ready sesuai urutan kedatangannya
- Sistem mengambil proses yang
berada di ujung depan antrian Ready menjadi Running
- Bila kwanta belum habis dan
proses selesai maka sistem mengambil proses di ujung depan antrian proses
Ready
- Jika kwanta habis dan proses
belum selesai maka ditempatkan proses Running ke ekor antrian proses Ready
dan sistem mengambil proses di ujung depan antrian proses Ready
Masalah
penjadwalan ini adalah dalam hal menentukan besar kwanta, yaitu :
- Kwanta terlalu besar menyebabkan waktu tanggap besar
dan turn arround time rendah
- Kwanta terlalu kecil
mengakibatkan peralihan proses terlalu banyak sehingga menurunkan
efisiensi pemroses
Harus
diterapkan besar kwanta waktu yang optimal berdasarkan kebutuhan sistem,
terutama dari hasil percobaan atau data historis dari sistem. Besar kwanta
waktu beragam yang bergantung beban sistem.
Berdasarkan kriteria penilaian penjadwalan
- Fairness, penjadwalan RR adil bila dipandang dari
persamaan pelayanan oleh pemroses
- Efisiensi, penjadwalan ini cenderung efisien pada
sistem interatif
- Respons Time(waktu
tanggap), penjadwalan ini memuaskan untuk sistem interaktif, tidak memadai
untuk sistem waktu nyata.Turn arround Time, penjadwalan RR cukup
bagus
- Throughput, penjadwlan RR cukup bagus
i.
Contoh : kumpulan proses datang pada
waktu 0
-
P1 mendapat 4 milidetik pertama
-
20 milidetik berikutnya akan disela
P2 dan P3
Waktu
tunggu tiap proses
AWT
: (6+4+7)/3 = 5,66 milidetik
iii.
Contoh : Menentukan Turn Around Time
untuk quantum waktu (q) = 3
Penjadwal dengan Banyak Antrian
(MFQ)
Penjadwalan MFQ ini merupakan
- Penjadwalan preemptive
- Penjadwalan berprioritas dinamis
Sasaran
penjadwalan ini adalah untuk mencegah banyaknya aktivitas swapping. Cara yang
dilakukan adalah dengan
- Proses-proses yang sangat
banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu
yang lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu
waktu.
- Penjadwalan ini menghendaki
kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama
satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya
lagi berjalan empat kwanta, kelas berikutnya-berikutnya lagi berjalan
delapan kwanta dan seterusnya.
Ketentuan
yang berlaku adalah sebagai berikut :
- Jalankan proses-proses yang berada pada kelas prioritas
tertinggi
- Jika proses telah menggunakan seluruh kwanta yang
dialokasikan maka proses itu diturunkan kelas prioritasnya
- Proses yang masuk untuk pertama kali ke sistem langsung
diberi kelas tertinggi
Penjadwalan dengan Sisa Waktu
Terpendek, Lebih Dahulu (SRF)
Penjadwalan ini merupakan
- Penjadwalan preemptive
- Penjadwalan berprioritas dinamis
Penjadwalan
SRF merupakan perbaikan dari SJF, SJF merupakan penjadwalan nonpreemptive
sedang SRF adalah preemptive yang dapat digunakan untuk sistem timesharing.
Pada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan,
termasuk proses-proses yang baru tiba.
Perbedaan
SRF dengan SJF
- Pada SJF, begitu proses dieksekusi, proses dijalankan
sampai selesai
- Pada SRF proses yang sedang berjalan (Running) dapat
diambil alih oleh proses baru dengan sisa waktu jalan yang diestimasi
lebih rendah
SRF
mempunyai overhead yang lebih besar dibanding SJF. SRF memerlukan penyimpanan
waktu layanan yang telah dihabiskan proses dan kadang-kadang harus menangani
peralihan.
- Tibanya proses-proses kecil akan segera dijalankan
- Proses-proses lebih lama berarti dengan lama dan
variasi waktu tunggu lebih lama dibanding dengan SJF
Secara
teoretis, SRF memberi waktu tunggu minimum tapi karena adanya overhead
peralihan, maka pada situasi tertentu SJF bisa memberi kinerja yang lebih baik
dibanding SRF.
Penjadwalan Rasio Tanggapan
Tertinggi, Lebih Dahulu (HRN)
Penjadwalan HRN ini merupakan :
- Penjadwalan non preemptive
- Penjadwalan berprioritas dinamis
Penjadwalan
ini juga untuk mengkoreksi kelemahan SJF. HRN adalah strategi penjadwalan non
preemptive dengan prioritas proses tidak hanya merupakan fungsi dari waktu
layanan, tapi juga jumlah waktu tunggu proses. Prioritas dinamis HRN dihitung
berdasarkan rumus berikut :
Prioritas
= (waktu tunggu + waktu layanan) / waktu layanan
Karena
waktu layanan muncul sebagai pembagi maka proses yang lebih pendek mempunyai
prioritas yang lebih baik. Karena waktu tunggu sebagai pembilang maka proses
yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus untuk
memperoleh layanan pemroses.
Disebut HRN (High respons next) karena waktu tanggap adalah (waktu
tunggu + waktu layanan). Ketentuan HRN berarti agar memperoleh waktu tanggap
tertinggi yang harus dilayani.
Penjadwalan Berprioritas (ps)
Gagasan penjadwalan adalah masing-masing proses diberi prioritas dan proses
berprioritas tertinggi menjadi Running (yaitu mendapat jatah waktu pemroses).
Prioritas dapat diberikan secara
- Prioritas statis (static priorities), prioritas tak
berubah.
keunggulan
: Mudah diimplementasikan dan mempunyai overhead relatif kecil
kelemahan : penjadwalan prioritas statis tidak tanggap perubahan lingkungan
yang mungkin menghendaki penyesuaian prioritas
- Prioritas dinamis (dynamic
priorities), mekanisme menanggapi perubahan lingkungan sistem saat
beroperasi di lingkungan nyata. Prioritas awal yang diberikan ke proses
mungkin hanya berumur pendek. Dalam hal ini sistem dapat menyesuaikan
nilai prioritasnya ke nilai yang lebih tepat sesuai lingkungan.
keunggulan
:
keunggulan : waktu system yang bagus
kelemahan : implementsi mekanisme prioritas dinamis lebih kompleks dan
mempunyai overhead yang lebih besar dibanding mekanisme prioritas
statik.
Contoh penjadwalan berprioritas
Proses-proses yang sangat banyak operasi masukan/keluaran dan menghabiskan
kebanyakan waktu proses untuk menunggu selesainya operasi masukan/ keluaran.
Proses demikian disebut I/O bound process. Proses-proses ini dapat diberi
prioritas sangat tinggi sehingga begitu proses-proses memerlukan pemroses,
segera saja diberikan dan proses akan segera memulai permintaaan
masukan/keluaran berikutnya sehingga menyebabkan proses Blocked menunggu
selesainya operasi masukan/keluaran. Dengan demikian pemroses segera dialihkan,
dapat dipergunakan oleh proses lain tanpa mengganggu proses I/O bound.
Proses I/O bound berjalan paralel bersama proses lain yang benar-benar
memerlukan pemroses.
Proses-proses
yang sangat banyak operasi masukan/keluaran jika harus menunggu lama untuk
memakai pemroses(karena diberi prioritas rendah) hanya akan membebani memori,
karena sistem harus menyimpan tanpa perlu proses-proses itu di memori karena
tidak selesai-selesai menunggu operasi masukan/keluaran dan menunggu jatah
pemroses.
Algoritma
Prioritas Dinamis
Algoritma ini dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu
yang menjadi tujuan sistem komputer.
Algoritma sederhana yang memberi layanan yang baik adalah dengan menge-set
proses dengan prioritas berdasarkan rumus nilai 1/f bahwa f adalah rasio kwanta
terakhir yang digunakan proses.
- Proses yang menggunakan 2 milidetik, kwanta 100 ms maka
prioritasnya 50
- Proses yang berjalan selama 50 milidetik sebelum
Blocked berprioritas 2
- Proses yang menggunakan seluruh kwanta berprioritas 1
Kebijaksanaan
yang diterapkan adalah jaminan proses-proses mendapat layanan yang adil dari
pemroses dalam arti jumlah waktu pemroses yang sama untuk masing-masing
pemroses pada satu waktu.
Biasanya memenuhi kebijaksanaan yang ingin mencapai level maksimal berdasarkan
suatu kriteria tertentu di sistem.
Algoritma
penjadwalan berprioritas dapat dikombinasikan yaitu dengan mengelompokkan
proses-proses menjadi kelas-kelas prioritas. Penjadwalan berprioritas
diterapkan antar kelas- kelas proses itu. Penjadwlan round-robin atau
penjadwalan FIFO diterapkan pada proses-proses di dalam satu kelas.
=====================================================================
Contoh
: ada 5 proses P1,P2,P3,P4,P5
Waktu
tunggu untuk tiap tiap prose :
proses
|
Waiting
time
|
P1
|
6
|
P2
|
0
|
P3
|
16
|
P4
|
18
|
P5
|
1
|
AWT
= (6+0+16+18+1) = 8,2 ms
Penjadwalan Terjamin (GS)
Penjadwal GS ini adalah
- Penjadwalan preemptive
- Penjadwalan berprioritas dinamis
Penjadwalan
ini berupaya memberi masing-masing pemakai daya pemroses yang sama. Jika
terdapat N pemakai maka tiap pemakai diupayakan mendapat 1/N daya pemroses.
Sistem merekam banyak waktu pemroses yang telah digunakan proses sejak login
dan jumlah waktu proses yang digunakan seluruh proses.
Karena
jumlah waktu pemroses tiap pemakai dapat diketahui, maka dapat dihitung rasio
antara waktu pemroses yang sesungguhnya harus diperoleh yaitu 1/N waktu
pemroses seluruhnya dan waktu pemroses telah diperuntukkan proses itu.
Penjadwal akan menjalankan proses dengan rasio terendah sampai rasio proses
diatas pesaing terdekatnya.
Evaluasi
Algoritma
Bagaimana memilih algoritma penjadwalan untuk sistem tertentu? Masing-masing
algoritma mempunyai parameter-parameter tersendiri. Pemilihan algoritma
penjadwalan merupakan hal yang sulit. Persoalan pertama adalah mendefinisikan
kriteria untuk pemilihan algoritma.
Kriteria-kriteria yang sering digunakan adalah fairness (keadilan), efisiensi,
waktu tanggap, turn arround time dan throughput. Kriteria kemudian dapat
menjadi :
- Memaksimumkan utilisasi
pemroses dengan konstrain waktu tanggap maksimum adalah 500 milidetik,
atau
- Memaksimumkan throughput bahwa
turn arround time adalah berbanding linier dengan waktu eksekusi total.
Begitu
kriteria pemilihan telah didefinisikan, kita dapat mengeveluasi beragam
algoritma. Terdapat sejumlah metode evaluasi untuk melakukan hal ini, yaitu :
- Pemodelan deterministis,
merupakan evaluasi analitis. Evaluasi analitis menggunakan algoritma dan
beban kerja sistem untuk menghasilkan satu rumus atau angka yang
menunjukkan kinerja algoritma untuk beban kerja itu. Pemodelan
deterministik menggunakan suatu beban kerja tertentu yang telah ditentukan
dan mendefinisikan kinerja algoritma untuk beban kerja itu.
- Pemodelan antrian, sistem
komputer dipandang sebagai satu jaringan pelayanan (server). Masing-masing
pelayan mempunyai satu antrian dari proses-proses yang menunggu layanan.
Pemroses adalah satu pelayan dengan satu antrian proses yang siap menerima
layanan, begitu juga perangkat I/O adalah antrian perangkat. Dengan
mengetahui rate kedatangan dan rate layanan, maka kita dapat mengkomputasi
utilisasi, panjang antrian rata-rata, waktu tunggu rata-rata dsb. Bidang
studi ini adalah analisis jaringan antrian (queueing network analys).
- Simulasi, simulasi dapat
memberikan evaluasi algoritma penjadwalan dengan lebih akurat. Simulasi
melibatkan pemrograman model sistem komputer. Dengan simulasi akan
diperoleh statistik yang menyatakan kinerja algoritma.
- Implementasi, simulasi pun
hanya memberikan akurasi yang terbatas. Satu-satunya cara paling akurat
dalam mengevaluasi algoritma penjadwalan adalah mengimplementasikannya,
menjalankannya pada sistem nyata dan melihatnya bekerja. Pendekatan ini
adalah menjalankan algoritma nyata di sistem nyata untuk keperluan
evaluasi pada beban atau kondisi operasi yang nyata.
Pembentukan Proses
Saat komputer berjalan, terdapat banyak proses yang berjalan secara bersamaan.
Sebuah proses dibuat melalui system call create-process membentuk proses
turunan (child process) yang dilakukan oleh proses induk parent process. Proses
turunan tersebut juga mampu membuat proses baru sehingga kesemua proses-proses
ini pada akhirnya membentuk pohon proses.
Ketika sebuah proses dibuat maka proses tersebut dapat memperoleh sumber-daya
seperti ”waktu CPU”, ”memori”, ”berkas” atau perangkat ”M/K”. Sumber daya ini
dapat diperoleh langsung dari Sistem Operasi, dari Proses Induk yang
membagi-bagikan sumber daya kepada setiap proses turunannnya, atau proses
turunan dan proses induk berbagi sumber-daya yang diberikan Sistem Operasi.
Ada dua kemungkinan bagaimana jalannya (running) proses induk dan turunan
berjalan (running). Proses-proses tersebut berjalan secara konkuren atau proses
induk menunggu sampai beberapa/seluruh proses turunannya selesai berjalan
Terminasi Proses
Suatu proses
diterminasi ketika proses tersebut telah selesai mengeksekusi perintah terakhir
serta meminta sistem operasi untuk menghapus perintah tersebut dengan
menggunakan system call exit. Pada saat itu, proses dapat mengembalikan data
keluaran kepada proses induk-nya melalui system call wait. Semua sumber-daya
yang digunakan oleh proses akan dialokasikan kembali oleh system operasi agar
dapat dimanfaatkan oleh proses lain. Suatu proses juga dapat diterminasi dengan
sengaja oleh proses lain melalui system call abort. Biasanya proses induk
melakukan hal ini pada turunannya. Alasan terminasi tersebut seperti:
- Turunan melampaui penggunaan sumber-daya yang telah
dialokasikan. Dalam keadaan ini, proses induk perlu mempunyai mekanisme
untuk memeriksa status turunannya-nya.
- Task yang ditugaskan kepada turunan tidak lagi
diperlukan.
- Proses induk selesai, dan sistem operasi tidak
mengizinkan proses turunan untuk tetap berjalan.
Jadi,
semua proses turunan akan berakhir pula. Hal ini yang disebut cascading
termination.
Process Control Block (PCB)
Proses Control Block adalah bentuk informasi-informasi lain yang diperlukan
sistem operasi untuk mengendalikan dan mengoordinasikan beragam proses aktif
dalam suatu proses. Dalam kenyataannya, proses banyak mengalami gangguan dalam
menjalankan tugasnya oleh karena itu ada PCB (Proses Control Block) untuk
membantu dan memberikan dukungan kepada proses itu.
Setiap proses digambarkan dalam sistem operasi oleh sebuah process control
block(PCB), juga disebut sebuah control block. PCB berisikan banyak bagian dari
informasi yang berhubungan dengan sebuah proses yang spesifik, seperti status
proses, program counter, CPU register, Informasi manajemen memori, informasi
pencatatan, informasi status I/O. Berikut adalah gambar diagram PCB.
PENJADWALAN PROSES SISTEM OPERASI
SOLARIS
|
|
|
|
Programmed in
|
|
OS family
|
|
Source model
|
|
Initial release
|
1992
|
|
|
10 10/09 / October 8, 2009; 10
months ago
|
|
|
|
|
|
|
Supported platforms
|
|
|
|
|
|
|
|
|
|
Various
|
|
|
|
Solaris menggunakan penjadwalan
berdasarkan prioritas dimana yang mempunyai prioritas yang lebih tinggi
dijalankan terlebih dahulu. Informasi tentang penjadwalan kernel thread
dapat dilihat dengan ps -elcL. Kernel Solaris adalah fully
preemtible, artinya semua thread, termasuk thread
yang mendukung aktifitas kernel itu sendiri dapat ditunda untuk
menjalankan thread dengan prioritas yang lebih tinggi.
Gambar penjadwalan solaris
Solaris mengenal 170 prioritas yang berbeda, 0-169. Terbagi dalam 4 kelas
penjadwalan yang berbeda:
- Real time (RT). Thread di kelas RT memiliki prioritas yang tetap dengan waktu
kuantum yang tetap juga. Thread ini memiliki prioritas yang
tinggi berkisar antara 100-159. Hal inilah yang membuat proses waktu nyata
memiliki response time yang cepat. Proses waktu nyata akan
dijalankan sebelum proses-proses dari kelas yang lain dijalankan sehingga
dapat menghentikan proses di system class. Pada umumnya, hanya
sedikit proses yang merupakan real time class.
- System (SYS). Solaris
menggunakan system class untuk menjalankan kernel proses,
seperti penjadwalan dan paging daemon. Threads di
kelas ini adalah “bound” threads, berarti bahwa mereka akan
dijalankan sampai mereka di blok atau prosesnya sudah selesai. Prioritas
untuk SYS threads berkisar 60-99. Sekali dibangun, prioritas
dari sistem proses tidak dapat dirubah. System classdialokasikan
untuk kernel use( user proses berjalan di
kernel mode bukan di system class).
- Time Sharing (TS). Time sharing class
merupakan default class untuk proses dan kernel thread
yang bersesuaian. Time slices masing-masing proses dibagi
berdasarkan prioritasnya. Dalam hal ini, prioritas berbanding terbalik
dengan time slices-nya. Untuk proses yang prioritasnya tinggi
mempunyai time-slices yang pendek, dan sebaliknya proses
dengan prioritas yang rendah mempunyai time slices yang lebih
panjang. Besar prioritasnya berada antara 0-59. Proses yang interaktif
berada di prioritas yang tinggi sedangkan proses CPU-bound
mempunyai prioritas yang rendah. Aturan penjadwalan seperti ini
memberikan response time yang baik untuk proses yang
interaktif, dan troughput yang baik untuk proses CPU-bound.
- Interactive (IA). Kelas
Interaktif menggunakan aturan yang sama dengan aturan dengan kelas
kelas time sharing, tetapi kelas ini memberikan prioritas yang
tinggi untuk aplikasi jendela ( windowing application)
sehingga menghasilkan performance yang lebih baik. Seperti
TS, range IA berkisar 0-59.
Tabel . Solaris dispatch table
for interactive and time sharing threads
Priority
|
Time quantum
|
Time quantum expired
|
return from sleep
|
0
|
200
|
0
|
50
|
5
|
200
|
0
|
50
|
10
|
160
|
0
|
51
|
15
|
160
|
5
|
51
|
20
|
120
|
10
|
52
|
25
|
120
|
15
|
52
|
30
|
80
|
20
|
53
|
35
|
80
|
25
|
54
|
40
|
40
|
30
|
55
|
45
|
40
|
35
|
56
|
50
|
40
|
40
|
58
|
55
|
40
|
45
|
58
|
59
|
20
|
49
|
59
|
Keterangan:
- Priority:
prioritas berdasarkan kelas untuk time sharing dan interactive
class. Nomor yang lebih tinggi menunjukkan prioritas yang lebih
tinggi.
- Time quantum:
waktu kuantum untuk setiap prioritas. Dapat diketahui bahwa fungsi waktu
kuantum berbanding terbalik dengan prioritasnya.
- Time quantum expired:
Prioritas terbaru untuk thread yang telah habis time
slices-nya tanpa diblok. Dapat dilihat dari tabel bahwa thread
yang CPU-bound tetap mempunyai prioritas yang rendah.
- Return from sleep:
Prioritas thread yang kembali dari sleeping(misalnya
menunggu dari M/K). Seperti yang terlihat dari tabel ketika M/K berada di waiting
thread, prioritasnya berada antara 50-59, hal ini menyebabkan response
time yang baik untuk proses yang interaktif.
- Fixed Priority (FX). Thread
di kelas fixed priority memiliki range prioritas
(0-59) yang sama seperti di time-sharing class; tetapi,
prioritas mereka tidak akan berubah.
- Fair Share Scheduler (FSS). Thread yang diatur oleh FSS dijadwalkan berdasar
pembagian sumber daya dari CPU yang tersedia dan dialokasikan untuk
himpunan proses-proses (yang dikenal sebagai project). FS juga
berkisar 0-59. FSS and FX baru mulai diimplementasikan di Solaris 9.
Seperti yang telah diketahui, setiap
kelas penjadwalan mempunyai himpunan dari prioritas-prioritas. Tetapi,
penjadwal mengubah class-specific priorities menjadi global
priorities kemudian memilih threaddengan prioritas paling
tinggi untuk dijalankan. Thread yang dipilih tersebut jalan di CPU
sampai thread tersebut (1) di- block, (2) habis time
slices-nya, atau (3) dihentikan oleh thread dengan prioritas
yang lebih tinggi. Jika ada beberapa thread dengan prioritas yang
sama, penjadwal akan menggunakan Round-Robin queue. Seperti yang pernah
dijelaskan sebelumnya, Solaris terdahulu menggunakan many-to-many model
tetapi solaris 9 berubah menggunakan one-to-one model.
PENJADWALAN PROSES SISTEM OPERASI LINUX
|
|
|
|
Programmed in
|
|
OS family
|
|
Working state
|
Current
|
Source model
|
|
|
|
|
|
|
|
Marketing target
|
Desktops, servers, embedded
devices
|
|
|
Multi-lingual
|
|
|
|
Supported platforms
|
IA-32, MIPS, x86-64, SPARC,DEC Alpha, Itanium, PowerPC,ARM, m68k, PA-RISC, s390,SuperH, M32R and more
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mulai di versi 2.5, Kernel linux
dapat berjalan di berbagai algoritma penjadwalan UNIX tradisional. Dua masalah
dengan penjadwal UNIX tradisional adalah tidak disediakannya dukungan yang
cukup untuk SMP (symmetric multiprocessor) sistem dan tidak
diperhitungkan dengan baik jumlah tasks pada sistem yang
berkembang. Dalam versi 2.5, penjadwal memeriksa dengan teliti hal tersebut,
dan sekarang kernel juga menyajikan algoritma penjadwalan yang dapat run
dalam waktu yang konstan tidak tergantung dari jumlah tasks dalam
sistem. Penjadwal yang baru juga menyediakan peningkatan dukungan untuk SMP,
termasuk processor affinity dan load balancing, sebaik
dalam menyediakan keadilan dan dukungan terhadap interactive tasks.
Penjadwal linux adalah preemptive, algoritmanya berdasarkan
prioritas dengan dua range prioritas yang terpisah: real-time
range dari 0-99 dan nice value berkisar dari 100-140. Dua range
ini dipetakan menjadi global priority scheme dimana nilai yang
lebih rendah memiliki prioritas yang lebih tinggi. Tidak seperti penjadwal yang
lain, Linux menetapkan prioritas yang lebih tinggi memiliki waktu kuantum yang
lebih panjang dan prioritas yang lebih rendah memiliki waktu kuantum yang lebih
pendek.
Linux mengimplementasikan real time scheduling seperti yang
didefinisikan oleh POSIX 1.b: First Come First Served dan Round
Robin. Sistem waktu nyata( real time)diberikan untuk task
yang prioritasnya tetap. Sedangkan task yang lainnya memiliki
prioritas yang dinamis berdasakan nice values ditambah atau dikurangi
dengan 5. Interaktifitas sebuah task menentukan apakah nilai 5 tersebut akan
ditambah atau dikurangi dari nice value. Task yang lebih interaktif
mempunyai ciri khas memiliki sleep times yang lebih lama dan karena
itu maka ditambah dengan -5, karena penjadwal lebih menyukaiinteractive task.
Hasil dari pendekatan ini akan membuat prioritas untuk interactive task
lebih tinggi. Sebaliknya, task dengan sleep time yang
lebih pendek biasanya lebih CPU-bound jadi prioritasnya lebih
rendah.
Gambar . Hubungan antara prioritas
dan waktu kuantum
Task yang berjalan memenuhi syarat untuk dieksekusi oleh CPU
selama time slice-nya masih ada. Ketika sebuah task
telah kehabisan time slice-nya, maka task tersebut akan expired
dan tidak memenuhi syarat untuk dieksekusi lagi sampai semua task
yang lain sudah habis waktu kuantumnya. Kernel mengatur daftar semua task
yang berjalan di runqueue data structure. Karena dukungan Linux
untuk SMP, setiap prossesor mengatur runqueue mereka sendiri dan
penjadwalan yang bebas. Setiap runqueue terdiri dari dua array
prioritas – active dan expired. Active array
terdiri dari semua task yang mempunyai sisa waktu time
slices, dan expired array terdiri dari task yang
telah berakhir. Setiap array prioritas ini memiliki daftar task indexed
berdasakan prioritasnya. Penjadwal memilih task dengan prioritas
paling tinggi di active array untuk dieksekusi dalam CPU. Di mesin
multiprossesor, ini berarti setiap prossesor menjadwalkan prioritas paling
tinggi dalam runqueue structure masing-masing. Ketika semua tasktelah
habis time slices-nya (dimana, active array-nya sudah
kosong), dua array prioritas bertukar; expired array menjadi active
array, dan sebaliknya.
Gambar . Daftar task indexed
berdasarkan prioritas
Penghitungan ulang dari task yang memiliki prioritas yang dinamis
berlangsung ketika task telah menyelesaikan waktu kuantumnya dan
akan dipindahkan ke expired array. Jadi, ketika ada dua larik
( array) ditukar, semua task di array aktif
yang baru ditentukan prioritasnya yang baru dan disesuaikan juga time
slices-nya.
PENJADWALAN PROSES SISTEM OPERASI WINDOWS XP
|
Developer
|
Microsoft Corporation
|
Release date
|
RTM:
August 24, 2001
Retail: October 25, 2001 (info)
|
Current version
|
5.1.2600.5512 Service Pack 3 (x86
SP3) (21 April 2008; 2 years ago) (info)
|
Source model
|
|
|
|
|
|
|
|
Update method
|
|
|
|
|
Website
|
|
Windows XP menggunakan algoritma,
prioritas penjadwalan quantum-based berbasis reemptive priority
scheduling .
Gambar Proses Pada Windows Xp
Threads dijadwalkan dalam proses, Karena prioritas preemptive algoritma
diimplementasikan dengan beberapa queue, dapat dianggap sebagai algoritma
multiple feedback-queue . Namun, masing-masing Threads biasanya terbatas
pada kelompok kecil dari 5 level prioritas,
Preemption dapat terjadi karena salah satu dari 4 alasan:
·
- thread menjadi prioritas lebih tinggi-siap
- thread berakhir
- kuantum habis waktu
- thread melakukan panggilan sistem pemblokiran, seperti
untuk I / O, dalam hal ini meninggalkan keadaan ready menjadi keadaan
menunggu.
Gambar Quatum pada windows XP
32 tingkat prioritas digunakan, di mana prioritas 31 merupakan prioritas
tertinggi dan prioritas 0 adalah prioritas terendah
·
- memori manajemen thread: prioritas 0
- variabel kelas
prioritas (1-15)
- real-time kelas
prioritas (16-31)
- Threads di kelas real-time telah tetap prioritasnya.
- Threads yang berjalan selalu dengan tingkat prioritas
tertinggi.
- Jika tidak ada thread yang ready, Threads idle
dijalankan.
- Ketika waktu quantum thread habis, prioritasnya
diturunkan, tetapi prioritasnya tidak pernah diturunkan terlalu jauh.
Ketika
Threads menjadi ready setelah keadaan menunggu, maka diberikan prioritas
tertinggi setiap threads dari proses yang terkait dengan program yang saat ini
pengguna gunakan diberikan prioritas lebih .
