Proses dan Penjadwalan Proses

PENGERTIAN PENJADWALAN PROSES

Penjadwalan proses merupakan kumpulan kebijaksanaan dan mekanisme disistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer.

Adapun penjadwalan bertugas memutuskan : 

a. Proses yang harus berjalan 

b. Kapan dan selama berapa lama proses itu berjalan 

TUJUAN PENJADWALAN PROSES

1. Supaya semua pekerjaan memperoleh pelayanan yang adil (fairness)

2. Supaya pemakaian prosesor dapat dimaksimumkan

3. Supaya waktu tanggap dapat diminimumkan, berupa waktu tanggap nyata dan waktu tanggap maya

4. Supaya pemakaian sumber daya seimbang

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

6. Efesien, proses tetap dalam keadaan sibuk tidak menganggur.

7. Supaya terobosan (thoughput) dapat dimaksimumkan 

 

TIPE - TIPE PENJADWALAN PROSES

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) 

     Setelah eksekusi selama suatu waktu, proses mungkin menunda sebuah eksekusi karena membuat permintaan layanan masukan/keluaran atau memanggil suatu system call. Proses-proses tertunda tidak dapat membuat suatu kemajuan menuju selesai sampai kondisi-kondisi yang menyebabkan tertunda dihilangkan. Agar ruang memori dapat bermanfaat, maka 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. Proses-proses 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.  

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, perangkat masukan/keluaran), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas job-job interaktif rendah.

 

PENJADWALAN PROSES

3 Istilah yang digunakan pada penjadwalan proses, yaitu: 

1. Antrian

    merupakan Sejumlah proses yang menunggu menggunakan prosesor dan akan diproses sesuai dengan urutan antrian proses. Proses berada dalam memori utama

2. Prioritas

    merupakan 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

    merupakan 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

1. Lama proses (t) adalah lama waktu yang diperlukan untuk mengolah proses itu di dalam prosesor.
2. Lama tanggap (T) adalah Waktu yang diperlukan untuk proses sejak mulai sampai selesai diolah oleh prosesor.

Terdapat 2 macam lama tanggap :

• Turn around time, dengan memperhitungkan lama waktu yang digunakan untuk sebuah proses hingga keluaran.
• Respone time, tidak memperhitungkan lama waktu yang digunakan untuk sebuah proses hingga keluaran

TEKNIK PENJADWALAN PROSESSOR

1. Kategori penjadwalan prosessor
• Tanpa prioritas tanpa prempsi
• Dengan prioritas tanpa prempsi
• Tanpa prioritas dengan prempsi
• Dengan prioritas dengan prempsi
2. Teknik penjadwalan prosessor
• – Penjadwalan satu tingkat
• – 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.

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

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

– Rt = t/T dan

– Rp = T/t

 
MACAM-MACAM ALGORITMA PENJADWALAN PROSES

1. Algortima First Come First Served (FCFS)/FIFO (First In First Out)

2. Algortima PTD/SJF (Shortest Job First)

3. Algoritma PTDP (Penjadwalan proses terpendek dipertamakan prempsi )

4. Algoritma RPTD (Ratio penalti tertinggi dipertamakan)

5. Algoritma Roun Robin

 

PENJELASAN ALGORITMA PENJADWALAN PROSES

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:

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

– Job yang pendek harus menunggu job yang panjang

– Job yang penting harus menunggu job yang kurang penting.

Contoh :

Misalkan ada tiga proses P1, P2, P3 yang dating dengan lama waktu kerja CPU (CPU Waiting time) masing-masing sebagai berikut :

• Proses           Waiting time

• P1                 24

• P2                 3

• P3                 3

Jika proses datang dengan urutan P1, P2, P3 dan dilayani dengan algoritma FIFO, maka dapat digambarkan Gantt Chart-nya :

• Dari Gantt Chart dapat diambil kesimpulan waktu tunggu untuk P1 adalah 0 milidetik, waktu tunggu untuk P2 adalah 24 milidetik, waktu tunggu P3 adalah 27 milidetik.

• Jadi rata-rata waktu tunggu (Average Waiting Time/AWT) adalah (0+24+27)/3 = 17 milidetik.

• Kemudian jika waktu kedatangan proses adalah P3, P2, P1 maka Gantt Chartnya adalah

• Turn around time (waktu penyelesaian) P3 adalah 0, P2 = 3, P1 = 6, Maka rata-rata turn around time

= (0+3+6)/3 = 3 milidetik

 

Contoh lain :

Diketahui 3 buah proses sebagai berikut:

·         Gantt chart

·         Waiting Time

 

·         AWT

Contoh soal 1:

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

Pertanyaan:

o    Kapan dimulainya eksekusi dari tiap-tiap antrian proses tsb?

o    Kapan selesai eksekusinya?

o    Hitung Turn Arround Time (TA)-nya?

o    Berata rata-rata TA?

Rumus

1.      TA = Waktu Tunggu + Lama Eksekusi

2.      Rata-rata TA = ∑TA / ∑Job

3.      Waktu Tunggu = Mulai Eksekusi – Waktu Tiba

4.      Selesai Eksekusi = Mulai Eksekusi + Lama Eksekusi

 

Jawaban:

Berdasarkan kriteria penilaian penjadwalan:

·         Fairness, Penjadwalan FCFS adil dalam arti semantiks (dalam arti antrian)

·         Efesiensi, Penjadwalan FCFS sangat efisien dalam penggunaan pemroses

·         Waktu Tanggap, Penjadwalan sangat tidak memuaskan, karena proses dapat menunggu lama

·         Turn Arround Time, Penjadwalan FCFS tidak bagus

·         Throughput, Penjadwalan FCFS tidak bagus.

 

2. Algoritma (PTD/ SJF/SJN)

Algoritma Shortest Job First, Dasar prioritas adalah pendeknya proses. Makin pendek/singkat proses makin tinggi prioritasnya

Langkah I : tentukan urutan prioritas berdasarkan pendeknya proses yang dilayani

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

 

 

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

·         Penjadwalan dengan prioritas dengan prempsi

Beberapa ketentuan :

1. Prioritas berdasarkan pendeknya sisa proses

2. Diperhatikan saat proses tiba atau saat proses selesai

3. Menghitung lama sisa proses dari semua proses yang ada

4. Jika proses dengan sisa proses yang lebih pendek dari proses yang sedang dikerjakan, maka atas dasar prempsi proses yang sedang dikerjakan akan dikeluarkan dari prosesor

Contoh Algoritma Penjadwalan Proses Terpendek Dipertamakan Prempsi  (PTDP / PSPN / SRT)

Penyelesaian Algoritma PTDP / PSPN / SRT

sisa                  A=5                 A=5                 A=5

B=2                 B=1                 B=0

C=9                 C=9

D=4

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

Penjadwalan dengan prioritas tanpa prempsi

Ketentuan Prioritas berdasarkan besarnya nilai ratio pinalti : 

Rumus ratio pinalti = Rp = ( s + t ) / t

s = waktu sia-sia (Saat selesai – Saat tiba)

t = lama proses

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

Contoh Algoritma Penjadwalan Ratio Pinalti Tertinggi Dipertamakan (RPTD/ HPRN)

Penyelesaian Algoritma RPTD/ HPRN

Penjelasan Step 1

Pada saat 0 : hanya ada A, A diolah

Pada saat 4 : A rampung, B, C, D, E telah tiba

Penjelasan Step 2

Pada saat 6 : A dan B telah rampung

Penjelasan Step 3

Pada saat 11 : A, B, dan C telah rampung

Pada saat 15 : A, B, C, dan E telah rampung D diolah

 

3.5. Algoritma Penjadwalan Penjadwalan Putar Gelang (Roun Robin/ Time Slice)

Penjadwalan tanpa prioritas dengan prempsi

Beberapa ketentuan :

• Kuantum waktu , waktu yang digunakan oleh prosesor untuk melayani setiap proses

• Prosesor akan melayani setiap proses berdasarkan antrian

• Prosesor akan melayani sesuai dengan Kuantum waktu yang sudah ditentukan.

Pada penjadwalan RR ini Eksekusi dijalankan secara giliran berdasarkan antrian (Non – Preemptive), prosesor mengerjakan sesaat setiap proses secara berturut-turut. Proses yang telah dieksekusi tapi belum selesai akan kembali ke antrian terakhir.

CONTOH SOAL I

Jika diketahui waktu tiba proses sama yaitu 0, dengan Quantum (Q) = 2.

Hitunglah waktu Turn Arround (TA) untuk tiap-tiap proses, Total TA dan Rata-rata TA-nya?

 

JAWAB SOAL I

CONTOH SOAL II:

Misal kumpulan proses datang pada waktu 0 dengan spesifikasi :

Jika digunakan quantum time 4 milidetik, maka proses P1 mendapat 4 milidetik yang pertama, 20 milidetik berikutnya akan disela oleh proses P2 dan P3 secara bergantian, sehingga Gantt Chart-nya dapat digambarkan sbb:

Waktu tunggu untuk tiap-tiap proses :

AWT yang terjadi adalah (6+4+7)/3 = 5,66 ms

 

Contoh Algoritma Penjadwalan Penjadwalan Putar Gelang (Roun Robin/ Time Slice)

Penyelesaian Algoritma Roun Robin/ Time Slice