1. Konsep Penjadwalan Proses

 

Permasalahan  yang  menyebabkan  dibutuhkannya  penjadwalan  adalah  bila terdapat berbagai macam tugas (job) atau proses yang harus dilakukan, sedangkan sumber  daya  (waktu,  bahan  baku,  tenaga  kerja,  mesin,  modal,  dan  sebagainya) yang  dibutuhkan  untuk  menyelesaikan  tugas-tugas  atau  proses  tersebut  terbatas sehingga  diperlukan  suatu  pengaturan  atas  pelaksanaan  tugas-tugas  atau  prosesproses  tersebut.  Conway (1967)   mendefinisikan  penjadwalan  sebagai  berikut:

”Scheduling is the task of assigning each operation  to a specific position or the time  scale  of  the  specific  machine”.  Sedangkan  Fogarty (1991)  mengatakan bahwa  penjadwalan  mencakup  dua hal,  yaitu  scheduling dan  sequencing yang masing-masing didefinisisikan sebagai berikut:

”Scheduling  is  the  assigning  of  starting  and  completion  times  orders  (job)  and frequently  includes  the  times  when  orders  are  to  arrive  and  leave  each department”.

Scheduling (penjadwalan)  merupakan  proses  penugasan  kapan  pekerjaan  harus dimulai dan diselesaikan, sedangkan  sequencing  (pengurutan) merupakan proses pengaturan  urutan  atas  pekerjaan-pekerjaan  yang  harus  diselesaikan  tersebut. Karena  eratnya  hubungan  diantara  kedua  istilah  ini, maka  biasanya  dalam penggunaan kata scheduling (penjadwalan), pengertian sequencingsudah tercakup didalamnya.

Pada sistem komputer terdapat beberapa bentuk dari penjadwalan, admission (pintu masuk ke system), memory, dan CPU scheduler coba lihat gambar scheduler dari batch system berikut:

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. Pada saat proses dijalankan terjadi siklus eksekusi CPU dan menunggu I/O yang disebut dengan siklus CPU-I/O burst. Eksekusi proses dimulai dengan CPU burst dan dilanjutkan dengan I/O burst, diikuti CPU burst lain, kemudian I/O burst lain dan seterusnya seperti pada gambar berikut:

Pada saat suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat sedikit CPU burst yang panjang. Program yang I/O bound biasanya sangat pendek CPU burst nya, sedangkan program yang CPU bound kemungkinan CPU burst nya sangan lama. Hal ini dapat digambarkan dengan grafik yang eksponensial atau hiper eksponensial seperti pada gambar. Oleh karena itu sangat penting pemilihan algoritma penjadwalan CPU.

CPU Scheduler

Pada saat CPU menganggur, maka sistem operasiharus 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).

Keputusan untuk menjadwalkan CPU mengikuti empat keadaan di bawah ini :

1)  Apabila proses berpindah dari keadaan running ke waiting;

2)  Apabila proses berpindah darikeadaan running ke ready;

3)  Apabila proses berpindah dari keadaan waiting ke ready;

4)  Apabila proses berhenti.

Apabila model penjadwalan yang dipilih menggunakan keadaan 1 dan 4, maka penjadwakan semacam ini disebut non-peemptive. Sebaliknya, apabila yang digunakan adalah keadaan 2 dan 3, maka disebut dengan preemptive. Pada non-preemptive, jika suatu proses sedang menggunakan CPU, maka proses tersebut akan tetap membawa CPU sampai proses tersebut melepaskannya (berhenti atau dalam keadaan waiting). Preemptive scheduling memiliki kelemahan, yaitu biaya yang dibutuhkan sangat tinggi. Antara lain, harus selalu dilakukan perbaikan data. Hal ini terjadi jika suatu proses ditinggalkan dan akan segera dikerjakan proses yang lain.

Dispatcher

Dispatcher adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian proses yang dilakukan selama short-term scheduling. Fungsi-fungsi yang terkandung di dalamnya meliputi:

1.  Switching context;

2.  Switching ke user-mode;

3.  Melompat ke lokasi tertentu pada user program untuk memulai program. Waktu yang

diperlukan oleh dispatcher untuk menghentikan suatu proses dan  memulai untuk

menjalankan proses yang lainnya disebut dispatch latency.

  1. Perbedaan Penjadwalan Long Term, Medium Term, dan Short Term.

Short term scheduler : Mempunyai tugas untuk menjadwalkan alokasi pemroses di antara proses ready di memori utama. Penjadwalan dijalankan setiap terjadi di pengalihan proses untuk memilih proses berikut yang harus dijalankan.

– Di dalam short term ini digunakan untuk memilih diantara proses – proses yang siap dieksekusi & satu diantaranya dialokasikan ke CPU.

– Penjadwalan short term biasa digunakan untuk CPU, proses dieksekusi dan hanya beberapa milidetik saja sebelum menunggu I/O.

Medium term scheduler: Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder yang disebut swapping. Proses ini mempunyai kepentingan kecil saat itu sebagai proses yang tertunda. Tetapi, begitu kondisi yang membuatnya tertunda hilang dan proses dimasukkan kembali ke memori utama dan ready.

– Dalam penjadwalan medium term ini, beberapa OS seperti contoh time-sharing harus membutuhkan penjadwalan dengan level tambahan.

Long term scheduler: Penjadwalan ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses-proses dengan penggunaan sumber daya yang intensif, program ini berprioritas rendah, digunakan sebagai pengisi selama periode aktivitas job-job interaktif rendah.

– Jika pada long term ini tiding sering mengeksekusi, dan digunakan jika proses meninggalkan suatu sistem.

– Digunakan untuk memilih suatu proses dari pool & menyimpan pada memori.

  1. Parameter Dalam Penjadwalan Proses

Algoritma penjadwalan CPU yang berbeda akan memiliki perbedaan properti. Sehingga untuk memilih algoritma ini harus dipertimbangkan dulu properti-properti algoritma tersebut. Ada beberapa parameter yang digunakan untuk melakukan pembandingan algoritma penjadwalan CPU, antara lain:

  1. CPU utilization: Diharapkan agar CPU selalu dalam keadaan sibuk. Utilitas CPU dinyatakan dalam bentuk prosen yaitu 0-100%. Namun dalam kenyataannya hanya berkisar antara 40-90%.

  2. Throughput: throughput Adalah banyaknya proses yang selesai dikerjakan dalam satu satuan waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah proses user yang dapat dieksekusi dalam interval waktu tertentu. Sasaran penjadwalan adalah memaksimalkan jumlah proses yang dilayani per satu interval waktu. Lebih tinggi waktu throughput maka lebih banyak kerja yang dilakukan sistem. Kriteria-kriteria tersebut saling tergantung dan dapat saling bertentangan sehingga tidak dimungkinkan optimasi semua criteria secara simultan Contoh:

Untuk memberikan waktu tanggap kecil umumnya memerlukan penjadwalan yang sering beralih-alih di antara proses-proses yang ada. Cara ini meningkatkan overhead sistem sehingga menurunkan efisiensi. Kebijaksanaan perancangan penjadwalan melibatkan kompromi di antara kebutuhan-kebutuhan yang saling bertentangan. Kompromi ini tergantung sifat dan penggunaan sistem komputer.

  1. Turnaround time: Banyaknya waktu yang diperlukan untuk mengeksekusi proses, dari mulai menunggu untuk meminta tempat di memori utama, menunggu di ready queue, eksekusi oleh CPU, dan mengerjakan I/O  sampai semua proses-proses tersebut diselesaikan. Waktu yang dimaksud adalah waktu yang dihabiskan proses berada di sistem, atau juga bisa diekspresikan sebagai penjumlahan waktu eksekusi (waktu pelayanan proses) dan waktu menunggu dari porses tersebutatau bisa dirumuskan seperti:

Turn arround time = waktu eksekusi + waktu tunggu. Sasaran dari penjadwalan adalah meminimalkan turn arround time.

  1. Waiting time: Waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Waiting time ini tidak mempengaruhi eksekusi proses dan penggunaan I/O.

  2. Response time: Waktu yang dibutuhkan oleh suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi permintaan tersebut. Respon time berbeda untuk sistem interaktif dan sistem waktu nyata.

  • Respon time sistem interaktif: respon time dalam sistem interkatif didefinisikan sebagai waktu yang dihabiskan dari saat karakter terakhir dari perintah dimasukan oleh program atau transaksi sampai hasil pertama muncul di perangkat output seperti layar (terminal)

  • Respon time sistem waktu nyata: pada sistem waktu nyata (real time), respon didefinisikan sebagai waktu dari saat kemunculan suatu kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan terhadap kejadian dieksekusi.

  1. Fairness: adil adalah menyakinkan proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan CPU yang sama dan tidakada proses yang tidak kebagian layanan CPU sehingga mengalai starvation. Starvation merupakan suatu kondisi bahwa proses tidak pernah berjalan tidak dijadwalkan untuk berjalan.

  1. Konsep Penjadwalan Berdasarkan Prioritas

Penjadwalan prioritas 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. Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

a. Batas waktu

b. Kebutuhan Memori

c. Akses file

d. Perbandingan antara I/O Burst dengan CPU Burst

e. Tingkat kepentingan proses

Proses-proses yang sangat banyak operasi masukan/keluaran menghabiskan kebanyakan waktu menunggu selesainya operasinya masukan/keluaran. Proses-proses 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 proses-proses 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.

Penjadwalan  dengan  pendekatan  heuristic menggunakan  aturan  pengurutan  atau priority  dispatching,  pada  priority  dispatching ditentukan  aturan  prioritasnya untuk memilih suatu operasi diantara operasi-operasi yang mengalami gangguan. Penentuan prioritas bergantung pada tujuan  yang ingin dicapai. Beberapa aturan prioritas menutur Fogarty(1991), adalah:

1.  Random (R)

Pemilihan  operasi  secara  random  artinya  setiap  pekerjaan  yang  akan dikerjakan  diurutkan  secara  random (tiap  job mempunyai  kemungkinan yang sama untuk dipilih)

2.  Most Working Remaining (MWR)

Prioritas tertinggi diberikan pada operasi dengan sisa waktu proses terlama.

Aturan  prioritas  ini  cocok  digunakan  untuk  menghasilkan  jadwal  dengan

makespan terpendek.

3.  Least Working Remaining (LWR)

Prioritas  tertinggi  diberikan  pada  operasi  dengan  sisa  waktu  proses terpendek. Aturan ini biasanya meminimasi flow timerata-rata.

4.  Most Operation Remaining (MOR)

Prioritas tertinggi diberikan pada operasi dengan successor terbanyak.

5.  Fewest Operation (FO)

Prioritas tertinggi diberikan pada produk dengan sisa operasi paling sedikit. Aturan ini biasanya mengurangi WIP, waktu penyelesaian produk, dan rata-rata waktu keterlambatan.

6.  Shortest Processing Time (SPT)

Prioritas  tertinggi  diberikan  pada  operasi  dengan  waktu  proses  terpendek, aturan  ini  biasanya  meminimasi  WIP,  rata-rata  keterlambatan  (mean latenes) dan waktu penyelesaian rata-rata (mean flow time) produk.

7.  First Come First Serve (FCFS)

Prioritas tertinggi diberikan pada operasi yang masuk St (stasiun ke-t) lebih dahulu. Aturan  ini  cocok  untuk  tipe  organisasi  dimana  konsumen mementingkan waktu pelayanan.

8.  Earliest Due Date (EDD)

Prioritas  tertinggi  diberikan  pada  produk  dengan  due  date (batas  waktu penyelesaian) terpendek. Aturan ini berjalan dengan baik bila waktu proses job-job relatif sama.

9.  Critical Ratio (CR)

Urutkan job berdasarkan CR terkecil (mengurangi lateness)

10.  Slack Time (ST)

       Merupakan variasi dari EDD.

11.  Slack Per Remaining Operation (S/OPN)

   Merupakan variasi dari ST, urutkan job berdasarkan S/OPN terkecil (aturan ini mengurangi lateness).

12.  Least Setup (LSU)

Urutkan  job berdasarkan  waktu  setup  terkecil  (aturan  ini  mengurangi makespan).

Referensi

Anggota yang berkontribusi:

  1. Rhesa Fauzan H (1103120102)

  2. M. Taufik Wahdiat (1103120104)

  3. Rakhmad Indra Permadi (1103121281)