Penjadwalan Proses dan Algoritma Penjadwalan Proses

Penjadwalan Proses

Deskripsi Penjadwalan Proses

Kumpulan kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan

kerja yang dilakukan sistem komputer.

·         Sistem Operasi modern umumnya merupakan sistem multitasking.

·         Pemanfaatan CPU maksimum diperoleh dengan multiprogramming

·         CPU-I/O Burst Cycle-Pelaksanaan proses terdiri dari suatu siklus tunggu I/O dan eksekusi CPU

Penjadwalan bertugas memutuskan hal-hal berikut :

·         Proses yang harus berjalan

·         Kapan dan selama berapa lama proses berjalan

Tujuan Utama Penjadwalan adalah Untuk mempunyai proses berjalan secara bersamaan, untuk memaksimalkan kinerja dari CPU.

Sasaran utama penjadwalan proses adalah Optimasi kinerja sistem komputer menurut kriteria tertentu.

Kriteria untuk mengukur dan optimasi kinerja penjadwalan

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.

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.

Tipe-Tipe Penjadwalan

Dapat terdapat 3 tipe penjadwal berada secara bersama-sama pada sistem operasi yang kompleks, yaitu :

1.     Penjadwal jangka pendek (short-term scheduller).

Penjadwalan jangka pendek bertugas menjadwalkan alokasi pemroses di antara proses-proses Ready yang berada di memori utama. sasaran utama penjadwal jangka pendek adalah memaksimumkan kinerja sistem untuk memenuhi satu kumpulan kriteria yang diharapkan. Penjadwal ini 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 ditunda karena permintaan layanan masukan/keluaran atau memanggil suatu system call. Proses-proses yang tertunda tidak dapat membuat suatu kemajuan untuk menuju selesai sampai ondisi yang menyebabkannya hilang. Agar ruang memori dapat bermanfaat maka proses dipindah dari memori utama ke memori sekunder sehingga tersedia ruang yang lebih besar untuk proses yang lain.

Kapasitas memori utama terbatas untuk sejumlah proses yang aktif. Aktivitas pemindahan proses yang tertunda dari memori utama ke memori sekunder disebut swapping. Penjadwal jangka menengah bertugas menangani proses swapping . Proses yang mempunyai kepentingan kecil saat itu adalah proses yang tertunda. Tetapi begitu kondisi yang membuat proses tertunda hilang dan proses dimasukkan kembali ke memori utama dan Ready.

Penjadwal jangka menengah mengendalikan transisi dari suspended ke ready (dari state suspend ke Ready dari proses yang mengalami swapping).

3.     Penjadwal jangka panjang (long-term scheduller).

Penjadwal jangka panjang bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi sistem. Batch biasanya berupa proses-proses dengan penggunaan sumber daya yang intensif (yaitu waktu pemroses, memori, perangkat masukan/keluaran), program ini mempunyai prioritas yang rendah, dan biasa digunakan sebagai pengisi (agar pemroses sibu) selama periode aktivitas proses-proses interaktif rendah. Sasaran utama penjadwal jangka panjang adalah memberi keseimbangan proses-proses campuran.

Tujuan Penjadwalan Proses

·         Supaya semua pekerjaan memperoleh pelayanan yang adil (fairness)

·         Supaya pemakaian prosesor dapat dimaksimumkan

·         Supaya waktu tanggap dapat diminimumkan, berupa waktu tanggap nyata dan waktu tanggap maya

·         Supaya pemakaian sumber daya seimbang

·         Turn arround time, waktu sejak program masuk ke sistem sampai proses selesai.

·         Efesien, proses tetap dalam keadaan sibuk tidak menganggur.

·         Supaya terobosan (thoughput) dapat dimaksimumkan

3 Istilah yang digunakan pada penjadwalan proses

1.      Antrian

Sejumlah proses yang menunggu menggunakan prosesor dan akan diproses sesuai dengan urutan antrian proses.

Proses berada dalam memori utama

2.      Prioritas

Mendahului pada antrian proses, jika proses berada di bagian belakang antrian, maka dengan pemberian prioritas, proses itu langsung berada di bagian paling depan pada antrian itu sambil menunggu sampai kerja prosesor selesai.

3.      Prempsi

Mendahului pada antrian proses, jika proses berada di bagian belakang antrian, maka dengan pemberian prempsi, proses itu langsung berada di bagian paling depan pada antrian itu bahkan akan memberhentikan kerja prosessor untuk mengerjakan proses yang prempsi tersebut.

PERHITUNGAN PADA CARA KERJA PROSESSOR

·         Lama proses (t) adalah lama waktu yang diperlukan untuk mengolah proses itu di dalam prosesor.

·         Lama tanggap (T) adalah Waktu yang diperlukan untuk proses sejak mulai sampai selesai diolah oleh prosesor.

Terdapat 2 macam lama tanggap :

1)      Turn around time, dengan memperhitungkan lama waktu yang digunakan untuk sebuah proses hingga keluaran.

2)      Respone time, tidak memperhitungkan lama waktu yang digunakan untuk sebuah proses hingga keluaran.

TEKNIK PENJADWALAN PROSESSOR

1)      Kategori penjadwalan prosessor

o   Tanpa prioritas tanpa prempsi

o   Dengan prioritas tanpa prempsi

o   Tanpa prioritas dengan prempsi

o   Dengan prioritas dengan prempsi

2)      Teknik penjadwalan prosessor

o   Penjadwalan satu tingkat

o   Penjadwalan multi tingkat

3)      Teknik penjadwalan satu tingkat

RUMUS PENJADWALAN

Jika terdapat N proses serentak, serta setiap proses memiliki lama tanggap sebesar T, maka rerata lama tanggap Tr adalah :

·         Tr = (jumlah Ti) / N

·         Waktu sia-sia (T – t), waktu yang terbuang dalam antrian atau selama terkena Prempsi.

o   Rasio tanggap (Rt), Perbandingan di antara lama proses terhadap lama tanggap

o   Rasio pinalti (Rp), Perbandingan diantara lama tanggap terhadap lama proses.

o   Rt = t/T dan

o   Rp = T/t

Strategi Penjadwalan
Terdapat 2 strategi penjadwalan, yaitu :

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

Ø  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 Penjadwalan Proses

Terdapat banyak algoritma penjadwalan, baik algoritma penjadwalan nonpreemptive maupun penjadwalan preemptive.
Algoritma-algoritma yang menerapkan strategi nonpreemptive diantaranya :

·         FIFO (First-In, First-Out) atau FCFS (First-Come, First-Serve)

·         SJF (Shortest Job First)

Algoritma-algoritma yang menerapkan strategi preemptive diantaranya :

·         RR (Round-Robin)

·         MFQ (Multiple Feedback Queues)

·         SRF (Shortest-Remaining-First)

·         HRN (Highest-Remaining-Next)

·         PS (Priority Schedulling)

·         GS (Guaranteed Schedulling)

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

a)      Algoritma penjadwalan tanpa berprioritas

b)      Algoritma penjadwalan berprioritas, terdiri dari :

·         Algoritma penjadwalan berprioritas statis

·         Algoritma penjadwalan berprioritas dinamis

Algoritma-Algoritma Penjadwalan Proses

o   Penjadwalan Round-Robin (RR)

o   Penjadwalan FIFO (FIFO)

o   Penjadwalan Berprioritas (PS)

o   Penjadwalan yang Terpendek yang Lebih Dahulu (SJF)

o   Penjadwalan dengan Banyak Antrian (MFQ)

o   Penjadwalan dengan Sisa Waktu Terpendek, Lebih Dahulu (SRF)

o   Penjadwalan Rasio Tanggapan Tertinggi, Lebih Dahulu(HRN)

o   Penjadwalan Terjamin (GS)

  

1.      Algoritma (PTPD/ FCFS/FIFO)

·        Merupakan algoritma penjadwalan CPU yang paling sederhana.

·        Proses yang tiba lebih dahulu akan dilayani lebih dahulu.

·        Jika ada proses tiba pada waktu yang sama, maka pelayanan mereka dilaksanakan berdasarkan urutan dalam antrian.

·        Proses di antrian belakang harus menunggu sampai semua proses di depannya selesai.

·        Setiap proses diberi jadwal eksekusi berdasarkan urutan waktu kedatangan.

·        FIFO jarang digunakan secara tersendiri tetapi dikombinasikan dengan algoritma lain karena:

o   Timbul masalah “waiting time” terlalu lama jika didahului oleh proses yang waktu selesainya lama.

o   Job yang pendek harus menunggu job yang panjang

o   Job yang penting harus menunggu job yang kurang penting.

Algoritma (PTPD/ FCFS/FIFO)

Berdasarkan kriteria penilaian penjadwalan:

1.      Fairness

Penjadwalan FCFS adil dalam arti semantiks (dalam arti antrian)

2.      Efesiensi

Penjadwalan FCFS sangat efisien dalam penggunaan pemroses

3.      Waktu Tanggap

Penjadwalan sangat tidak memuaskan, karena proses dapat menunggu lama

4.      Turn Arround Time

Penjadwalan FCFS tidak bagus

5.      Throughput

Penjadwalan FCFS tidak bagus.

Contoh soal :

Jika diketahui terdapat 4 macam antrian proses, yaitu A-B-C-D dengan waktu kedatangan 0-3-5-7. Lama proses berturut-turut antara lain: 7-3-4-8.

Pertanyaan :

Kapan dimulainya eksekusi dari tiap-tiap antrian proses tsb?

Kapan selesai eksekusinya?

Hitung Turn Arround Time (TA)-nya?

Berata rata-rata TA?

Rumus :

TA = Waktu Tunggu + Lama Eksekusi

Rata-rata TA = ΣTA / ΣJob

Waktu Tunggu = Mulai Eksekusi – Waktu Tiba

Selesai Eksekusi = Mulai Eksekusi + Lama Eksekusi

Jawaban:

2.      Algoritma (PTD/ SJF/SJN)

·         Algoritma Shortest Job First

·         Dasar prioritas adalah pendeknya proses.

·         Makin pendek/singkat proses makin tinggi prioritasnya

o   Langkah I : tentukan urutan prioritas berdasarkan pendeknya proses yang dilayani

o   Langkah II : penentuan proses mana yang dilayani oleh pemroses

·         Setiap proses yang ada dalam ready queue akan dieksekusi berdasarkan burst time terkecil

·         Hal ini mengakibatkan waiting time yang pendek untuk setiap proses, maka rerata waiting time (AWT) juga menjadi pendek

·         Algoritma ini dikatakan optimal

Contoh soal :

Jika diketahui terdapat 4 macam antrian proses, yaitu A-B-C-D dengan waktu kedatangan 0-3-5-7. Lama proses berturut-turut antara lain: 7-4-8-3..

Pertanyaan :

Kapan dimulainya eksekusi dari tiap-tiap antrian proses tsb?

Kapan selesai eksekusinya?

Hitung Turn Arround Time (TA)-nya?

Berata rata-rata TA?

Rumus :

TA = Waktu Tunggu + Lama Eksekusi

Rata-rata TA = ΣTA / ΣJob

Waktu Tunggu = Mulai Eksekusi – Waktu Tiba

Selesai Eksekusi = Mulai Eksekusi + Lama Eksekusi

Jawaban:

3.      Algoritma Penjadwalan Proses Terpendek Dipertamakan Prempsi (PTDP atau PSPN)

Pada penjadwalan ini, prioritas dan prempsi diberlakukan namun dengan beberapa ketentuan, yaitu:

1. Prioritas berdasarkan pendeknya sisa proses;
2. Perhatikan saat proses tiba dan atau saat proses selesai;
3. Menghitung lama sisa proses dari semua proses yang ada; dan
4. Jika proses dengan sisa proses yang lebih pendek dari proses yang sedang dikerjakan, maka akan dikeluarkan dari prosesor.

Contoh :

4.      Algoritma Penjadwalan Ratio Pinalti Tertinggi Dipertamakan (RPTD atau HPRN)

Penjadwalan ini dilakukan dengan prioritas namun tanpa menggunakan prempsi. Dengan ketentuan Prioritas berdasarkan besarnya nilai ratio pinalti.

Tetap mendahulukan proses terpendek, namun prioritas proses panjang akan turut meningkat melalui peningkatan ratio pinaltinya.

Contoh :

5.      Algoritma Penjadwalan Putar Gelang (Round Robin atau Time Slice)

Penjadwalan pada algoritma ini dapat menggunakan prempsi namun tidak dengan prioritas. Berikut ketentuannya:

1. Kuantum Waktu, Waktu yang digunakan oleh prosesor untuk melayani setiap proses.
2. Prosesor akan melayani setiap proses berdasarkan antrian.
3. Prosesor akan melayani sesuai dengan Kuantum Waktu yang sudah ditentukan.

Contoh :

Nah terakhir dari pembahasan kali ini, Jadi Kesimpulannya...

Penjadwalan adalah sekumpulan mekanisme dan kebijaksanaan pada OS yang bersangkutan dengan urutan kerja yang dilakukan sistem pada komputer. dan Penjadwalan memiliki 2 tugas, yaitu:

1. Kapan dan berapa lama proses itu berjalan; dan
2. Proses harus berjalan.

Penjadwalan bertujuan untuk mengoptimalkan kinerja sistem komputer sesuai dengan kriteria yang telah ditentukan.

Selain itu ada beberapa macam Algoritma Penjadwalan Proses, yaitu:

1. Algoritma Pertama Tiba Pertama Di Layani (PTPD atua FCFS)
2. Algoritma Proses Terpendek Dipertamakan (PTD atau SJF)
3. Algoritma Proses Terpendek Dipertamakan Prempsi (PTDP atau PSPN)
4. Algoritma Penjadwalan Ratio Pinalti Tertinggi Dipertamakan (RPTD atau HPRN)
5. Algoritma Penjadwalan Putar Gelang (Round Robin atau Time Slice)