penjadualan cpu

Penjadwalan CPU
Penjadwalan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Penjadwalan CPU merupakan konsep dari multiprogramming, dimana CPU digunakan secara bergantian untuk proses yang berbeda. Suatu proses terdiri dari dua siklus yaitu Burst I/O dan Burst CPU yang dilakukan bergantian hingga proses selesai. Penjadwalan CPU mungkin dijalankan ketika proses:

1. running ke waiting time
2. running ke ready state
3. waiting ke ready state
4. terminates

Proses 1 dan 4 adalah proses Non Preemptive, dimana proses tersebut tidak bisa di- interrupt, sedangkan 2 dan 3 adalah proses Preemptive, dimana proses boleh di interrupt.
Pada saat CPU menganggur, maka sistem operasi harus menyeleksi proses-proses yang ada di memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm scheduler (CPU scheduler).
Komponen yang lain dalam penjadwalan CPU adalah dispatcher, Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling . Waktu yang diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai proses yang lain disebut dengan dispatch latency.
Jika dalam suatu proses Burst CPU jauh lebih besar daripada Burst I/O maka disebut CPU Bound. Demikian juga sebaliknya disebut dengn I/O Bound.

1. Penjadwalan Preemptive

Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. Penjadwalan ini bisa saja termasuk penjadwalan proses atau I/O. Penjadwalan Preemptive memungkinkan sistem untuk lebih bisa menjamin bahwa setiap proses mendapat sebuah slice waktu operasi. Dan juga membuat sistem lebih cepat merespon terhadap event dari luar (contohnya seperti ada data yang masuk) yang membutuhkan reaksi cepat dari satu atau beberapa proses. Membuat penjadwalan yang Preemptive mempunyai keuntungan yaitu sistem lebih responsif daripada sistem yang memakai penjadwalan Non Preemptive.

Dalam waktu-waktu tertentu, proses dapat dikelompokkan ke dalam dua kategori: proses yang memiliki Burst M/K yang sangat lama disebut I/O Bound, dan proses yang memiliki Burst CPU yang sangat lama disebut CPU Bound. Terkadang juga suatu sistem mengalami kondisi yang disebut busywait, yaitu saat dimana sistem menunggu request input(seperti disk, keyboard, atau jaringan). Saat busywait tersebut, proses tidak melakukan sesuatu yang produktif, tetapi tetap memakan resource dari CPU. Dengan penjadwalan Preemptive, hal tersebut dapat dihindari.

Dengan kata lain, penjadwalan Preemptive melibatkan mekanisme interupsi yang menyela proses yang sedang berjalan dan memaksa sistem untuk menentukan proses mana yang akan dieksekusi selanjutnya.

Lama waktu suatu proses diizinkan untuk dieksekusi dalam penjadwalan Preemptive disebut time slice/quantum. Penjadwalan berjalan setiap satu satuan time slice untuk memilih proses mana yang akan berjalan selanjutnya. Bila time slice terlalu pendek maka penjadwal akan memakan terlalu banyak waktu proses, tetapi bila time slice terlau lama maka memungkinkan proses untuk tidak dapat merespon terhadap event dari luar secepat yang diharapkan.

2. Penjadwalan Non Preemptive

Penjadwalan Non Preemptive ialah salah satu jenis penjadwalan dimana sistem operasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke proses yang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di- interupt.

Penjadwalan Non Preemptive terjadi ketika proses hanya:

1. Berjalan dari running state sampai waiting state.

2. Dihentikan.

Ini berarti CPU menjaga proses sampai proses itu pindah ke waiting state ataupun dihentikan (proses tidak diganggu). Metode ini digunakan oleh Microsoft Windows 3.1 dan Macintosh. Ini adalah metode yang dapat digunakan untuk platforms hardware tertentu, karena tidak memerlukan perangkat keras khusus (misalnya timer yang digunakan untuk meng interupt pada metode penjadwalan Preemptive).

Algoritma Penjadwalan CPU
Penjadwalan CPU terkait dengan bagaimana proses dikelola . Banyak algoritma yang digunakan  untuk penjadwalan proses. Beberapa algoritma yang digunakan antara lain :
1. First-Come First- Serve (FCFS)
Merupakan algoritma yang paling sederhana dalam penjadwalan proses. Proses yang melakukan request terhadap CPU akan diproses oleh CPU. Implementasinya dengan menggunakan algoritma First In First Out – FIFO.  FCFS bersifat non-preemptive yaitu proses yang dikerjakan oleh CPU tidak dapat diinterupsi oleh proses yang lainnya.
Sebagai contoh :

Proses	Burst
P1	10
P2	1
P3	2
P4	1
P5	5

Gant Chart :

Proses diasumsikan datang bersamaan dan masuk dalam antrian penggunaan CPU. Proses akan dikerjakan berdasarkan nomor urutan proses, sedangkan yang lainnya menunggu sampai proses diatasnya selesai dikerjakan.
Dari Gant Chart dapat diperoleh waktu tunggu proses dari CPU yang dapat diambil waktu rata-ratanya.
Waiting Time P1 = 0, Waiting Time P2 = 10, Waiting Time P3 = 11, Waiting Time P4 = 13, Waiting Time P5 = 14.
Avarage Waiting Time (AWT) =  (WT P1 + WT P2 + WT P3 + WT P4 + WT P5)/5
Avarage Waiting Time (AWT) =  (0 + 10 + 11 + 13 + 14)/5 = 9.6 ms

FCFS  dapat juga bekerja dengan adanya prioritas terhadap proses, prioritas dengan nilai terkecil akan diberi status sebagai prioritas tinggi dan akan dikerjakan terlebih dahulu.

Proses	Burst	Prioritas
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

Gant Chart :

Avarage Waiting Time (AWT) =  (0 + 1 + 6 + 16 + 18)/4 = 8.2 ms
Masalah utama pada FCFS adalah adanya antrian dari proses yang menjadi panjang karena waiting time yang rata-rata panjang. Proses-proses yang telah  berada dalam posisi ready akan tetapi CPU belum dapat memprosesnya. Hal ini yang disebut dengan starvation.
2. Shortest Job First (SJF)
Pendekatan  SJF berbeda dengan FCFS, algoritma SJF tergantung dengan panjang proses yang ada pada queue. Ketika CPU akan melakukan  proses, CPU akan memilik proses dengan CPU burst paling kecil. SJF dapat bekerja dengan mode preemptive maupun non-preemptive.

1. Non-preemptive

Proses	Burst
P1	6
P2	8
P3	7
P4	3

Gant chat :Waiting Time P1 = 3
Waiting Time P2 = 16
Waiting Time P3 = 9
Waiting Time P4 = 0
Avarage Waiting Time = (3 + 16 + 9 + 0)/4 = 7 ms
b. Preemptive
SJF dengan waktu kedatangan (arrival time) berbeda.

Proses	Arrival	Burst
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Proses akan di-preemptive jika ada proses masuk, dah penjadwalan dilakukan ulang dengan membandingkan proses yang masuk dengna proses yang sedang dijalankan. Sebaga contoh pada tabel ketika P1 dijalankan dengna membutuhkan 8 ms, akan tetapi datang burst dari proses P2 dengan burst time 4 ms pada deti ke-1. Proses akan berhenti pada detik 1 kemudian membandingkan proses P1 dengan P2. Karena P2 < P1 maka proses P1 akan dikembalikan ke ready queue dengan P1 = 7 dan memproses P2. Demikian seterusnya.
Gant chart :

Waiting Time P1 = 0 + (10-1) = 9
Waiting Time P2 = 1-1 = 0
Waiting Time P3 = 17-2 = 15
Waiting Time P4 =  5-3 = 2
Average Waiting Time = (9 + 0 + 15 + 2 )/4 =  6.5 ms
3. Round Robin (RR)
Round Robin hampir mirip dengan FCFS akan tetapi terdapat proses perpindahan antar proses dimana satu proses melakukan interupsi terhadap proses yang lainnya atau disebut juga dengan preemptive. Proses preemptive dengan menggunakan time quantum atau time slice.
Sebagai contoh :

Proses	Burst
P1	24
P2	3
P3	3

Dengan time slice sebesar 4 ms, penjadwalan yang terjadi adalah sebagai berikut:
P1 mendapatkan kesempatan pada 4 ms (time slice) pertama, karena P1 > time slice maka P1 hanya akan diproses selama time slice, sisa P1 sebesar P1 – time slice akan di preemptive-kan. Selanjutnya penjadwalan akan beralih ke P2, karena P2 < time slice maka P2 diproses hingga selesai, setelah itu penjadwalan beralih ke P3 dan seterusnya.

Waiting Time P1 = 0 + (10 – 4) = 6
Waiting Time P2 = 4
Waiting Time P3 = 7
Average Waiting Time = (6 + 4 + 7 )/3 = 5.66 ms
Pada algoritma RR, tidak ada proses yang dikerjakan dalam satu waktu lebih dari time slice yang disediakan. Jika terdapat n proses pada queue dengan time slice sebesar q, maka setiap proses akan mendapatkan waktu 1/n dengan masing-masing proses sebesar q .Setiap proses akan menunggu setidaknya sebanyak (n-1)x q untuk proses selanjutnya. Sebagai contoh terdapat 5 proses dengan time slice sebesar 20 ms maka masing-masing proses akan mendapatkan waktu sebanyak 20 ms setiap 100 ms.

Performance dari RR tergantung pada ukuran time slice. Jika time slice terlalu besar maka RR akan sama atau mendekati performance FCFS. Akan tetapi jika time slice kecil maka muncul problem context switch yang terlalu banyak, yaitu proses perpindahan dari satu proses ke proses lain yang akan menimbulkan permasalahan. Hal ini terjadi karena perbedaan kecepatan processor dan memori, dengan terjadinya perpindahan yang terlalu sering proses pembacaan CPU ke memori dan sebaliknya akan membebani sistem.

LATAR BELAKANG

CPU merupakan komponen yang sangat penting, demikian juga dengan penjadwalannya. Algoritma penjadwalan CPU dan dampaknya cukup sulit dipelajari karena butuh menguji dan memodifikasi kernel sistem operasi dan mengukur beban kinerja yang digunakan ketika membuka aplikasi. Tujuan pembuatan jurnal ini adalah membandingkan antar algoritma penjadwalan CPU (single Processor) dan menunjukkan algoritma mana yang terbaik dalam keadaan tertentu. Dengan sudut pandang ini, akan lebih mudah untuk memahami apa yang terjadi dalam sistem dan memahami mengapa proses-proses memiliki sistem alokasi CPU pada waktu yang berbeda.

IMPLEMENTASI

CPU memiliki beberapa tipe dan strategi penjadwalan, oleh karean itu dapat dimanfaatkan untuk melihat strategi penjadwalan atau algoritma mana yang dapat dijalankan dengan baik. PENJADWALAN PADA CPU 3 tipe penjadwalan CPU, yaitu:

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)

 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

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.

Gambar di bawah ini menunjukkan contoh penjadwalan CPU

1 . Ketika sebuah proses beralih dari keadaan running ke keadaan waiting . 2 . Ketika sebuah proses beralih dari keadaan running ke status ready. 3 . Ketika sebuah proses beralih dari waiting untuk ready. 4 . Ketika proses berakhir .

ALGORITMA PENJADWALAN 1.

First Come First Serve 2.

Shortest Job First Scheduling

k r kteristik

 

->Kurangnya prioritas tidak mengizinkan setiap proses untuk menyelesaikan, maka tidak terjadi kasus kelaparan/starving. ->Turnaround waktu , menunggu waktu dan waktu respon yang tinggi . ->Proses dengan waktu besar terpanjang dapat memonopoli CPU

k r kteristik

-> Kesulitan sesungguhnya dengan algoritma SJF adalah, untuk mengetahui panjang permintaan CPU berikutnya . ->SJF meminimalkan waktu tunggu rata-rata karena layanan proses kecil sebelum yang besar . Sementara itu meminimalkan rata-rata waktu tunggu , mungkin layanan besar cenderung tertinggal dalam daftar.

 

3.

Round Robin 4.

Priority Scheduling

PERBANDINGAN ANTAR ALGORITMA PENJADWALAN

Dari tabel di atas dapat disimpulkan bahwa First Come First Serve (FCFS) dan Shortest Job First merupakan algoritma penjadwalan yang baik pada sistem operasi batch dan Round Robin serta Priority Scheduling cocok untuk sistem pembagian waktu.

k r kteristik

->Membuatkuantum terlalu pendek menyebabkan terlalu banyak switch konteks dan menurunkan efisiensi CPU . ->Mengatur kuantum terlalu lama dapat menyebabkan waktu respon kecil dan mendekati FCFS . ->Karena waktu tunggu tinggi , tenggat waktu jarang bertemu dalam sistem RR murni.

k r kteristik

proses prioritas yang sama. gi memiliki waktu menunggu dan waktu respon yang lebih kecil.

 

KESIMPULAN

Penjadwalan dengan algoritma Shortest Job First akan meningkatkan waktu tunggu untuk proses yang besar. Dengan SJF juga memungkinkan proses yang besar tidak dapat dijalankan. Maka dari itu diperlukan sebuah perlakuan khusus untuk setiap algoritma penjadwalan CPU terhadap keakuratan proses yang dijalankan. Caranya adalah dengan memasukkan kode atau proses ke dalam sebuah sistem operasi dan menemukan kinerja yang tepat oleh suatu algoritma secara langsung atau real time