PENJADWALAN PROSES (Sistem Operasi)

MENGENAL PENJADWALAN PROSES

Pengertian  Penjadwalan  Proses

Penjadwalan proses Merupakan kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer.         Sedangkan proses sendiri merupakan unit kerja terkecil yang secara individu memiliki sumberdaya  atau  unit  pemilikan  sumberdaya.

Tugas Penjadwalan Proses :

•    Memutuskan proses yang harus berjalan
•    Memutuskan kapan dan selama berapa lama proses 

      itu berjalan

Tujuan  Penjadwalan Proses

Tujuan dari multiprogramming adalah untuk memiliki sejumlah proses yang berjalan pada sepanjang waktu, untuk memaksimalkan penggunaan CPU. Pada sistem multiprogramming, selalu akan terjadi beberapa proses berjalan dalam suatu waktu. Sedangkan pada uniprogramming hal ini tidak akan terjadi, karena hanya ada satu proses yang  berjalan  pada  saat  tertentu. Sistem multiprogramming

Diperlukan  untuk  memaksimalkan  utilitas  CPU.

Tujuan dari pembagian waktu adalah untuk mengganti CPU diantara proses-proses yang begitu sering sehingga pengguna dapat berinteraksi dengan setiap program sambil CPU bekerja.

Untuk sistem uniprosesor, tidak akan ada lebih dari satu proses berjalan. Jika ada proses yang lebih dari itu, yang lainnya akan harus menunggu sampai CPU bebas dan dapat dijadualkan kembali.

Elemen Utama Penjadwalan Proses / Strategi Penjadwalan Proses

Konsep Dasar Penjadwalan Proses

Terdapat banyak algoritma penjadwalan ,baik nonpreemptive maupun preemptive :

• Preemptive Scheduling Atau Penjadwalan Preemtive yaitu dimana Saat proses diberi jatah waktu pemproses boleh diambil alih oleh proses yang lain, sehingga proses dapat disela sebelum proses itu selesai. Pada strategi ini, sistem operasi dan proses lain dapat mengambil alih eksekusi prosesor tanpa harus menunggu proses yang sedang running menyelesaikan tugasnya. Penjadwalan preemptive merupakan fitur yang penting, terutama pada sistem dimana proses-proses memerlukan tanggapan prosesor secara cepat.

• Non-Preemtive Scheduling Atau Penjadwalan Nonpreemtive Begitu proses diberi jatah waktu pemproses maka pemproses tidak dapat diambil alih oleh proses lain sampai proses itu selesai. Pada strategi ini, begitu proses telah berjalan maka sistem operasi maupun proses lain tidak dapat mengambil alih eksekusi prosesor. Pengalihan hanya dapat terjadi jika proses yang running sudah selesai, baik secara normal maupun abnormal.
  
  
• Dispatcher adalah suatu modul yang akan memberikan kontrol secepat mungkin pada CPU terhadap penyeleksian proses.
  

-Alih Konteks

-Switching to user mode.

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

    Dispatch Latency adalah waktu yang dibutuhkan untuk menghentikan suatu proses dan menjalankan proses yang lain.

Algoritma  Penjadwalan Proses yang menerapkan strategi Non  Preemptive  diantaranya:

– FIFO (First In First Out) Atau FCFS (First Come First Served)

Algoritma FIFO adalah sebuah algoritma yang mempunyai cara kerja mengganti page yang menempati memory paling lama. Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga. Algoritma ini menggunakan struktur data stack.

Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu. Pada skema ini, proses yang meminta CPU pertama kali akan dialokasikan ke CPU pertama kali.

Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2, dan P3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :

Process             Burst Time

P1                             24

P2                             3

P3                             3

– SJF (Shortest Job First)

Penjadwalan ini mengasumsikan waktu jalan proses sampai selesai diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

Contoh :

Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Untuk menghitung rata-rata turn around time seluruh proses adalah dengan menggunakan rumus : ( 4a + 3b + 2c + 1d ) / 4 Dengan menggunakan rumus, maka dapat dihitung turn around time-nya sebagai berikut (belum memperhatikan shortest job first, lihat gambar a) :

= ( 4a + 3b + 2c + 1d ) / 4

= ( 4x8 + 3x4 + 2x4 + 1x4 ) / 4

= ( 32 + 12 + 8 + 4 ) / 4

= 56 / 4

= 14 menit

Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt (lihat gambar b), maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D adalah 12 dan untuk A adalah 20, sehingga rata-rata turn around timenya adalah sebagai berikut :

= ( 4a + 3b + 2c + 1d ) / 4

= ( 4x4 + 3x4 + 2x4 + 1x8 ) / 4

= ( 16 + 12 + 8 + 8 ) / 4

= 44 / 4

= 11 menit

Tidak memperhatikan SJF Memperhatikan SJF

Posisi : a b c d a b c d

Priority : 4 3 2 1 4 3 2 1

Job : A B C D B C D A

+-----------------+ +-----------------+

: 8 : 4 : 4 : 4 : : 4 : 4 : 4 : 8 :

+-----------------+ +-----------------+

(a)      (b)

Jelas bahwa a memberikan nilai kontribusi yang besar, kemudian b, c dan d. Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, menjalankan perintah, menunggu perintah dan menjalankan perintah, begitu seterusnya. Masalah yang muncul adalah :

• Tidak mengetahui ukuran job saat job masuk. Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya.
• Proses yang tidak datang bersamaan, sehingga penetapannya harus dinamis.

Penjadwalan ini jarang digunakan, karena merupakan kajian teoritis untuk pembandingan turn around time.

– HRN (Highest Ratio Net)

Merupakan penjadwalan berprioritas dinamis. Penjadwalan untuk mengoreksi kelemahan SJF. Adalah strategi penjadwalan dengan prioritas proses tidak hanya merupakan Fungsi waktu layanan tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, proses berjalan sampai selesai.

Prioritas dinamis HRN dihitung berdasarkan rumus : Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus.Disebut HRN, karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani.

Penjadwalan ini mengasumsikan waktu berjalannya proses sampai selesai telah diketahui sebelumnya. Mekanismenya adalah menjadwalkan proses dengan waktu jalan terpendek lebih dulu sampai selesai, sehingga memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

Contoh :

Terdapat empat proses (job) yaitu A,B,C,D dengan waktu jalannya masing-masing adalah 8,4,4 dan 4 menit. Apabila proses-proses tersebut dijalankan, maka turn around time untuk A adalah 8 menit, untuk B adalah 12, untuk C adalah 16 dan untuk D adalah 20. Apabila keempat proses tersebut menggunakan penjadwalan shortest job fisrt, maka turn around time untuk B adalah 4, untuk C adalah 8, untuk D adalah 12 dan untuk A adalah 20.

Karena SJF selalu memperhatikan rata-rata waktu respon terkecil, maka sangat baik untuk proses interaktif. Umumnya proses interaktif memiliki pola, yaitu menunggu perintah, menjalankan perintah, menunggu perintah dan menjalankan perintah, begitu seterusnya. Masalah yang muncul adalah tidak mengetahui ukuran job saat job masuk.

Untuk mengetahui ukuran job adalah dengan membuat estimasi berdasarkan kelakukan sebelumnya. Prosesnya tidak datang bersamaan, sehingga penetapannya harus dinamis. Penjadwalan ini jarang digunakan karena merupakan kajian teoritis untuk pembandingan turn around time.

– MFQ (Multiple Feedback Queues)

Merupakan penjadwalan berprioritas dinamis. Penjadwalan ini untuk mencegah (mengurangi) banyaknya swappingdengan proses-proses yang sangat banyak menggunakan pemroses (karena menyelesaikan tugasnya memakan waktu lama) diberi jatah waktu (jumlah kwanta) lebih banyak dalam satu waktu.

 Penjadwalan ini juga menghendaki kelas-kelas prioritas bagi proses-proses yang ada. Kelas tertinggi berjalan selama satu kwanta, kelas berikutnya berjalan selama dua kwanta, kelas berikutnya berjalan empat kwanta, dan seterusnya. Ketentuan yang berlaku adalah sebagai berikut :

• Jalankan proses pada kelas tertinggi.
• Jika proses menggunakan seluruh kwanta yang dialokasikan, maka diturunkan kelas prioritasnya.
• Proses yang masuk untuk pertama kali ke sistem langsung diberi kelas tertinggi.

Mekanisme ini mencegah proses yang perlu berjalan lama swapping berkali-kali dan mencegah proses-proses interaktif yang singkat harus menunggu lama.

Algoritma  Penjadwalan Proses yang menerapkan strategi Preemptive diantaranya:

      -  RR (Round Robin)

Merupakan Penjadwalan yang paling tua, sederhana, adil,banyak digunakan algoritmanya dan mudah diimplementasikan. Penjadwalan ini bukan dipreempt oleh proses lain tetapi oleh penjadwal berdasarkan lama waktu berjalannya proses (preempt by time). Penjadwalan tanpa prioritas. Berasumsi bahwa semua proses memiliki kepentingan yang sama, sehingga tidak ada prioritas tertentu.

Semua proses dianggap penting sehingga diberi sejumlah waktu oleh pemroses yang disebut kwanta (quantum) atau time slice dimana proses itu berjalan. Jika proses masih running sampai akhir quantum, maka CPU akan mempreempt proses itu dan memberikannya ke proses lain. Penjadwal membutuhkannya dengan memelihara daftar proses dari runnable.

 Algoritma penjadwalan ini mirip dengan algoritma First Come FirstServed, tetapi proses ini memberi suatu batasan waktu untuk setiap proses yang disebut dengan time quantum. Time quantum adalah suatu satuan waktu yang kecil.Jika proses yang sedang dieksekusi selesai dalam waktu kurang dari 1 time quantum, tidak ada masalah. Tetapi jika proses berjalan melebihi 1 time quantum, maka proses tersebut akan dihentikan,lalu digantikan oleh proses yang berikutnya. Proses yang ihentikan tersebut akan diletakkan di queue di urutan paling belakang.(Perhatikan gambar 15-4).

Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil,maka sebagian besar proses tidak akan selesai dalam 1 time quantum.Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma First Come First Served.

Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

-SRF (Shortest Remaining First)

Merupakan :

• Penjadwalan berprioritas.dinamis.
• Adalah preemptive untuk timesharing
• Melengkapi SJF

Pada SRF, proses dengan sisa waktu jalan diestimasi terendah dijalankan,

termasuk proses-proses yang baru tiba.

• Pada SJF, begitu proses dieksekusi, proses dijalankan sampai selesai.
• Pada SRF, proses yang sedang berjalan (running) dapat diambil alih proses baru dengan sisa waktu jalan yang diestimasi lebih rendah.

Kelemahan :

• Mempunyai overhead lebih besar dibanding SJF. SRF perlu penyimpanan waktu layanan yang telah dihabiskan job dan kadang-kadang harus menangani peralihan.
• Tibanya proses-proses kecil akan segera dijalankan.
• Job-job lebih lama berarti dengan lama dan variasi waktu tunggu lebih lama dibanding pada SJF.

SRF perlu menyimpan waktu layanan yang telah dihabiskan , menambah overhead. Secara teoritis, SRF memberi waktu tunggu minimum tetapi karena overhead peralihan, maka pada situasi tertentu SFJ bisa memberi kinerja lebih baik disbanding SRF.

-PS (Priority Schedulling)

Adalah tiap proses diberi prioritas dan proses yang berprioritas tertinggi mendapat jatah waktu lebih dulu (running). Berasumsi bahwa masing-masing proses memiliki prioritas tertentu, sehingga akan dilaksanakan berdasar prioritas yang dimilikinya.

 Ilustrasi yang dapat memperjelas prioritas tersebut adalah dalam komputer militer, dimana proses dari jendral berprioritas 100, proses dari kolonel 90, mayor berprioritas 80, kapten berprioritas 70, letnan berprioritas 60 dan seterusnya. Dalam UNIX perintah untuk mengubah prioritas menggunakan perintah nice.

Pemberian prioritas diberikan secara :

a. Statis (static priorities)

yaitu Berarti prioritas tidak berubah.

Keunggulan :

• Mudah diimplementasikan.
• Mempunyai overhead relatif kecil.

Kelemahan :

• Tidak tanggap terhadap perubahan lingkungan yang mungkin menghendaki
• penyesuaian prioritas.

b. Dinamis (dynamic priorities)

Merupakan mekanisme untuk menanggapi perubahan lingkungan system beroperasi. Prioritas awal yang diberikan ke proses mungkin hanya berumur pendek setelah disesuaikan ke nilai yang lebih tepat sesuai lingkungan.

Kelemahan :

• Implementasi mekanisme prioritas dinamis lebih kompleks dan mempunyai overhead lebih besar. Overhead in diimbangi dengan peningkatan daya tanggap sistem.

Contoh penjadwalan berprioritas :

Proses-proses yang sangat banyak operasi masukan/keluaran menghabiskan kebanyakan waktu menunggu selesainya operasinya masukan/keluaran. Prosesproses ini diberi prioritas sangat tinggi sehingga begitu proses memerlukan pemroses segera diberikan, proses akan segera memulai permintaan masukan/keluaran berikutnya sehingga menyebabkan proses blocked menunggu selesainya operasi masukan/keluaran. Dengan demikian pemroses dapat dipergunakan proses-proses lain. Proses-proses I/O berjalan paralel bersama proses-proses lain yang benar-benar memerlukan pemroses, sementara prosesproses I/O itu menunggu selesainya operasi DMA.

Proses-proses yang sangat banyak operasi I/O-nya, kalau harus menunggu lama untuk memakai pemroses (karena prioritas rendah) hanya akan membebani memori, karena harus disimpan tanpa perlu proses-proses itu dimemori karena tidak selesai-selesai menunggu operasi masukan dan menunggu jatah pemroses. Dalam algoritma berprioritas dinamis dituntun oleh keputusan untuk memenuhi kebijaksanaan tertentu yang menjadi tujuan. Layanan yang bagus adalah mensetprioritas dengan nilai 1/f, dimana f adalah ration kwanta terakhir yang digunakan proses.

Contoh :

• Proses yang menggunakan 2 msec kwanta 100 ms, maka prioritasnya50.
• Proses yang berjalan selama 50 ms sebelum blocked berprioritas 2.
• Proses yang menggunakan seluruh kwanta berprioritas 1.

Kebijaksanaan yang diterapkan adalah jaminan proses-proses mendapat layanan adil dari pemroses dalam arti jumlah waktu pemroses yang sama. Keunggulannya penjadwalan berpriorita adalah memenuhi kebijaksanaan yang ingin mencapai maksimasi suatu kriteria diterapkan. Algoritma ini dapat dikombinasikan, yaitu dengan mengelompokkan proses-proses menjadi kelaskelas prioritas. Penjadwalan berprioritas diterapkan antar kelas-kelas proses itu.

-Guaranteed Scheduloing (GS)

Penjadwalan ini memberikan janji yang realistis (memberi daya pemroses yang sama) untuk membuat dan menyesuaikan performance adalah jika ada N pemakai, sehingga setiap proses (pemakai) akan mendapatkan 1/N dari daya pemroses CPU.

Untuk mewujudkannya, sistem harus selalu menyimpan informasi tentang jumlah waktu CPU untuk semua proses sejak login dan juga berapa lama pemakai sedang login. Kemudian jumlah waktu CPU, yaitu waktu mulai login dibagi dengan n, sehingga lebih mudah menghitung rasio waktu CPU. 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 yang telah diperuntukkan proses itu.

Rasio 0,5 berarti sebuah proses hanya punya 0,5 dari apa yang waktu CPU miliki dan rasio 2,0 berarti sebuah proses hanya punya 2,0 dari apa yang waktu CPU miliki.

Algoritma akan menjalankan proses dengan rasio paling rendah hingga naik ketingkat lebih tinggi diatas pesaing terdekatnya. Ide sederhana ini dapat diimplementasikan ke sistem real-time dan memiliki penjadwalan berprioritas dinamis.

Scheduling Criteria

Penilaian penjadwalan ini berdasarkan kriteria optimasi :

• Adil, dalam arti resmi (proses yang datang duluan akan dilayani lebih dulu), tapi dinyatakan tidak adil karena job-job yang perlu waktu lama membuat job-job pendek menunggu. Job-job yang tidak penting dapat membuat job-job penting menunggu lama. proses-proses diperlakukan sama, dalam artian adil. Adil disini tidak berarti terdapat perlakuan yang sama kepada setiap process, melainkan terdapat beberapa variabel seperti prioritas, dll yang akan dipelajari nanti.

• CPU  Utilization, diharapkan agar CPU selalu dalam keadaan sibuk, sehingga penggunaan CPU lebih optimal.

• Throughput, adalah banyaknya proses yang selesai dikerjakan dalam satu satuan waktu. Sasaran penjadwalan adalah memaksimalkan jumlah job yang diproses dalam satu satuan waktu.

• Efisiensi, sangat efisien dan efektivitas.

• Waiting-Time, adalah waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Sasaran Penjadwalan : meminimalkan waiting time.

• Response-Time, adalah waktu yang diperlukan oleh suatu proses dari minta dilayani hingga ada respon pertama menanggapi permintaan tersebut . Sasaran penjadwalan : meminimalkan waktu tanggap