PENJADWALAN PROSES

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

1. Adil (fairness)
2. Efisiensi
3. Waktu Tanggap (response time)
4. Turn arround Time
5.  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 :

• Sistem interaktif

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

1. 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.
2. 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 :

1.  FIFO (First-In, First-Out) atau FCFS (First-Come, First-Serve)
2. SJF (Shortest Job First)

Algoritma-algoritma yang menerapkan strategi preemptive diantaranya :

1. RR (Round-Robin)
2. MFQ (Multiple Feedback Queues)
3. SRF (Shortest-Remaining-First)
4. HRN (Highest-Remaining-Next)
5. PS (Priority Schedulling)
6. GS (Guaranteed Schedulling)

Klasifikasi lain selain berdasarkan dapat/tidaknya suatu proses diambil alih secara paksa adalah klasifikasi yang berdasarkan adanya prioritas diproses-proses, yaitu :

1. Algoritma penjadwalan tanpa berprioritas
2. Algoritma penjadwalan berprioritas, terdiri dari :

• Algoritma penjadwalan berprioritas statis
• Algoritma penjadwalan berprioritas dinamis

Algoritma-Algoritma Penjadwalan Proses

1. Penjadwalan Round-Robin (RR)
2. Penjadwalan FIFO (FIFO)
3. Penjadwalan Berprioritas (PS)
4. Penjadwalan yang Terpendek yang Lebih Dahulu (SJF)
5. Penjadwalan dengan Banyak Antrian (MFQ)
6. Penjadwalan dengan Sisa Waktu Terpendek, Lebih Dahulu (SRF)
7. Penjadwalan Rasio Tanggapan Tertinggi, Lebih Dahulu(HRN)
8. 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 :

1. Jika kwanta habis dan proses belum selesai maka proses Runing menjadi Ready dan pemroses dialihkan ke proses lain
2. 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.
3. 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

Quantum 4 milidetik

-        P1 mendapat 4 milidetik pertama

-        20 milidetik berikutnya akan disela P2 dan P3

                              ii.            Gambar Gantt Chart 

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

1. Proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu yang lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu.
2. 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

Gantt Chart

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 :

1. 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.
2. 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).
3. 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.
4. 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

Company /developer	Oracle Corporation
Programmed in	C
OS family	Unix
Source model	Mixed open source / closed source
Initial release	1992
Latest stable release	10 10/09 / October 8, 2009; 10 months ago
Availablelanguage(s)	English
Availableprogramming languages(s)	C
Supported platforms	SPARC, IA-32, x86-64,PowerPC (Solaris 2.5.1 only)
Kernel type	Monolithic
Default user interface	Java Desktop System orCDE
License	Various
Official website	oracle.com/solaris

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:

1. 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.
2. 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).
3. 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.
4. 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:

1. Priority: prioritas berdasarkan kelas untuk time sharing dan interactive class. Nomor yang lebih tinggi menunjukkan prioritas yang lebih tinggi.

1. Time quantum: waktu kuantum untuk setiap prioritas. Dapat diketahui bahwa fungsi waktu kuantum berbanding terbalik dengan prioritasnya.

1. 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.

1. 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.

1. 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.
2. 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

Company /developer	Linus Torvalds and many others
Programmed in	Assembly, C
OS family	Unix-like
Working state	Current
Source model	Free and open source software
Latest stable release	2.6.35.3 (August 20, 2010; 3 days ago)[1] [+/−]
Latest unstable release	2.6.36-rc2 (August 23, 2010; 0 days ago)[2][+/−]
Marketing target	Desktops, servers, embedded devices
Availablelanguage(s)	Multi-lingual
Availableprogramming languages(s)	Assembly, C, C++
Supported platforms	IA-32, MIPS, x86-64, SPARC,DEC Alpha, Itanium, PowerPC,ARM, m68k, PA-RISC, s390,SuperH, M32R and more
Kernel type	Monolithic
Userland	GNU and others
Default user interface	Graphical (X Window System)
License	Various including GNU General Public License, BSD License, Apache License, MIT License, and others[3]
Officialwebsite	http://www.kernel.org

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	Closed source, Shared source[1]
License	Microsoft-EULA
Kernel type	Hybrid
Update method	Windows Update
Platform support	IA-32, x86-64, IA-64
Website	Windows XP: Homepage

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 .