Penjadual CPU

Siklus Burst CPU-I/O

Keberhasilan dari penjadual CPU tergantung dari beberapa properti prosesor. Proses eksekusi mengandung siklus CPU ekskusi dan I/o Wait. Proses hanya akan bolak-balik dari dua state ini. Poses eksekusi dimulai dengan CPU Burst, setelah itu dikikuti oleh I/O burst, dan dilakukan secara bergiliran.

Durasi dari CPU bust ini ditelah diukur secara ekstensif, walau pun mereka sangat berbeda dari proses ke proses. Mereka mempunyai frekeunsi kurva yang sama seperti yang diperlihatkan gambar dibawah ini.

Penjadual CPU

Kapan pun CPU menjadi idle, sistem opersai harus memilih salah satu proses untuk masuk kedalam antrian ready (siap) untuk dieksekusi. Pemilihan tersebut dilakukan oleh penjadual short term. Penjadual memilih dari sekian proses yang ada di memori yang sudah siap dieksekusi, den mengalokasikan CPU untuk mengeksekusinya

Penjadual CPU mungkin akan dijalankan ketika proses:

1. Berubah dari running ke waiting state.

2. Berubah dari running ke ready state.

3. Berubah dari waiting ke ready.

4. Terminates.

Penjadual dari no 1 sampai 4 non premptive sedangkan yang lain premptive. Dalam penjadual nonpreemptive sekali CPU telah dialokasikan untuk sebuah proses, maka tidak bisa di ganggu, penjadual model seperti ini digunakan oleh Windows 3.x; Windows 95 telah menggunakan penjadual preemptive.

Dispatcher

Komponen yang lain yang terlibat dalam penjadual CPU adalan dispatcher. Dispatcher adalah modul yang memberikan kontrol CPU kepada proses yang fungsinya adalah:

1. Switching context.

2. Switching to user mode.

3. Lompat dari suatu bagian di progam user untuk mengulang progam.

Dispatcher seharusnya secepat mungkin,

Kriteria Penjadual

Algoritma penjadual CPU yang berbeda mempunyai property yang berbeda. Dalam memilih algoritma yang digunakan untuk situasi tertentu, kita harus memikirkan properti yang berbeda untuk algoritma yang berbeda. Banyak kriteria yang dianjurkan utnuk membandingkan penjadual CPU algoritma. Kritria yang biasanya digunakan dalam memilih adalah:

1. CPU utilization: kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0 ke 100 persen. Di sistem yang sebenarnya seharusnya ia mempunyai range dari 40 persen samapi 90 persen.

2. Throughput: jika CPU sibuk mengeksekusi proses, jika begitu kerja telah dilaksanakan. Salah satu ukuran kerja adalah banyak proses yang diselesaikan per unit waktu, disebut througput. Untuk proses yang lama mungkin 1 proses per jam; untuk proses yang sebentar mungkin 10 proses perdetik.

3. Turnaround time: dari sudur pandang proses tertentu, kriteria yang penting adalah berapa lama untuk mengeksekusi proses tersebut. Interval dari waktu yang diizinkan dengan waktu yang dibutuhkan untuk menyelesaikan sebuah prose disebut turn-around time. Trun around time adalah jumlah periode untuk menunggu untuk bisa ke memori, menunggu di ready queue, eksekusi di CPU, dan melakukan I/O.

4. Waiting time: algoritma penjadual CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut atau I/O; itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time adalah jumlah periode menghabiskan di antrian ready.

5. Response time: di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria. Sering sebuah proses bisa memproduksi output diawal, dan bisa meneruskan hasil yang baru sementara hasil yang sebelumnya telah diberikan ke user. Ukuran yang lain adalah waktu dari pengiriamn permintaan sampai respon yang pertama di berikan. Ini disebut response time, yaitu waktu untuk memulai memberikan respon, tetapi bukan waktu yang dipakai output untu respon tersebut.

Biasanya yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan minimalkan turnaround time, waiting time, dan response time dalam kasus tertentu kita mengambil rata-rata.

First Come, First Served

Ini merupakan algoritma yang paling sederhana, dengan skema proses yang meminta CPU mendapat prioritas. Implementasi dari FCFS mudah diatasi dengan FIFO queue.

Contoh:

misal urutan kedatangan adalah P1, P2, P3 Gantt Chart untuk ini adalah:

misal proses dibalik sehingga urutan kedatangan adalah p3,p2,p1.

Gantt chartnya adalah:

Dari dua contoh diatas bahwa kasus kedua lebih baik dari kasus pertama, karena pengaruh kedatangan disamping itu FCFS mempunyai kelemahan yaitu convoy effect dimana seandainya ada sebuah proses yang kecil tetapi dia mengantri dengan proses yang membutuhkan waktu yang lama mengakibatkan proses tersebut akan lama dieksekusi.

Penjadual FCFS algoritma adalah nonpremptive. Ketika CPU telah dialokasikan untuk sebuah proses, proses tetap menahan CPU sampai selssai. FCFS algortima jelas merupakan masalah bagi sistem time-sharing, dimana sangat penting untuk user mendapatkan pembagian CPU pada regular interval. Itu akan menjadi bencana untuk megizinkan satu proses pada CPU untuk waktu yang tidak terbatas

Penjadual Shortest Job First

Salah satu algoritma yang lain adalah Shortest Job First. Algoritma ini berkaitan dengan waktu setiap proses. Ketika CPU bebas proses yang mempunyai waktu terpendek untuk menyelesaikannya mendapat prioritas. Seandainya dua proses atau lebih mempunyai waktu yang sama maka FCFS algoritma digunakan untuk menyelsaikan masalah tersebut.

Ada dua skema dalam SJFS ini yaitu:

1. nonpremptive — ketika CPU memberikan kepada proses itu tidak bisa ditunda hingga selesai.

2. premptive — bila sebuah proses datang dengan waktu prose lebih rendah dibandingkan dengan waktu proses yang sedang dieksekusi oleh CPU maka proses yang waktunya lebih rendah mendapatkan prioritas. Skema ini disebut juga Short - Remaining Time First (SRTF).

Contoh:

SJF algoritma mungkin adalah yang paling optimal, karena ia memberikan rata-rata minimum waiting untuk kumpulan dari proses yang mengantri. Dengan mengeksekusi waktu yang paling pendek baru yang paling lama. Akibatnya rata-rata waktu mnenuggu menurun.

Hal yang sulit dengan SJF algoritma adalah mengethaui waku dari proses berikutnya. Untuk penjadual long term (lama) di sistem batch, kita bisa menggunakan panjang batas waktu proses yang user sebutkan ketika dia mengirim pekerjaan. Oleh karena itu sjf sering digunakan di penjadual long term.

Walau pun SJF optimal tetapi ia tidak bisa digunakan untuk penjadual CPU short term. Tidak ada jalan untuk mengetahui panjang dari CPU burst berikutnya. Salah satu cara untuk mengimplementasikannya adalah dengan memprediksikan CPU burst berikutnya.

Contoh SJF premptive:

kita lihat bahwa dengan premptive lebih baik hasilnya daripada non preemptive

Penjadual Prioritas

Pendaualan SJF (Shortest Job First) adalah kasus khusus untuk algoritma penjadual Prioritas. Prioritas dapat diasosiasikan masing-masing proses dan CPU dialokasikan untuk proses dengan prioritas tertinggi. Untuk proritas yang sama dilakukan dengan FCFS.

Ada pun algoritma penjadual prioritas adalah sebagai berikut:

• Setiap proses akan mempunyai prioritas (bilangan integer). Beberapa sistem menggunakan integer dengan urutan kecil untuk proses dengan prioritas rendah, dan sistem lain juga bisa menggunakan integer urutan kecil untuk proses dengan prioritas tinggi. Tetapi dalam teks ini diasumsikan bahwa integer kecil merupakan prioritas tertinggi.

• CPU diberikan ke proses dengan prioritas tertinggi (integer kecil adalah prioritas tertinggi).

• Dalam algoritma ini ada dua skema yaitu:

  1. Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.

  2. Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.

• SJF adalah contoh penjadual prioritas dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya. Permasalahan yang muncul dalam penjadualan prioritas adalah indefinite blocking atau starvation.

• Kadang-kadang untuk kasus dengan prioritas rendah mungkin tidak pernah dieksekusi. Solusi untuk algoritma penjadual prioritas adalah aging

• Prioritas akan naik jika proses makin lama menunggu waktu jatah CPU.

Penjadual Round Robin

Algoritma Round Robin (RR) didisain untuk sistem time sharing. Algoritma ini mirip dengan penjadual FCFS, namun preemption ditambahkan untuk switch antara proses. Antrian ready diperlakukan atau dianggap sebagai antrian sirkular. CPU menglilingi antrian ready dan mengalokasikan masing-masing proses untuk interval waktu tertentu sampai satu time slice/ quantum.

Berikut algritma untuk penjadual Round Robin:

• Setiap proses mendapat jatah waktu CPU (time slice/ quantum) tertentu Time slice/quantum umumnya antara 10 - 100 milidetik.

  1. Setelah time slice/quantum maka proses akan di-preempt dan dipindahkan ke antrian ready.

  2. Proses ini adil dan sangat sederhana.

• Jika terdapat n proses di "antrian ready " dan waktu quantum q (milidetik), maka:

  1. Maka setiap proses akan mendapatkan 1/n dari waktu CPU.

  2. Proses tidak akan menunggu lebih lama dari: (n-1)q time units.

• Performance dari algoritma ini tergantung dari ukuran time quantum

  1. Time Quantum dengan ukuran yang besar maka akan sama dengan FCFS

  2. Time Quantum dengan ukuran yang kecil maka time quantum harus diubah ukurannya lebih besar dengan respek pada context switch sebaliknya akan memerlukan ongkos yang besar.

Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response terhadap user lebih cepat.

Time Quantum Vs Context Switch