Algoritma Penjadwalan ( Schedulling Algorithm)



Filed under : Uncategorized

Tugas Sistem Operasi :

1. Merangkum Bab 9 (Scheduling) dengan bahasa sendiri

2. Menjelaskan apa itu yang disebut dengan:

   -clock driven
   -weighted round robin
   -priority driven

 

Prima Nur Pratama

115060807111070

TIF-G
 

 

Apa sih scheduling itu?

Dalam suatu sistem komputer scheduling merupakan pengaturan penggunaan waktu prosesor bagi sejumlah proses yang saling berkompetisi, dalam hal ini berkompetisi untuk mendapatkan resource yang dibutuhkan.

Mengapa harus ada scheduling?

- Agar setiap proses dapat dilayani secara seimbang / adil.

- Agar tidak terjadi starvation.

- Agar efisien dalam penggunaan waktu prosesor

- Agar dapat meminimalkan terjadinya overhead

- Supaya response time dapat terpenuhi

- Supaya dapat memaksimalkan throughput

Apa saja jenis-jenis scheduling?

- Penjadwalan Jangka Panjang (Long-Term)   

   yaitu adalah keputusan untuk menambah suatu proses kedalam kelompok proses yang akan dieksekusi.

- Penjadwalan Jangka Menengah (Medium-Term)

   adalah suatu keputusan untuk menambahkan sejumlah proses (sebagian atau seluruhnya) kedalam main memory.

- Penjadwalan Jangka Pendek (Short-Term)

   adalah suatu keputusan untuk memilih proses mana yang akan dieksekusi diantara sejumlah proses yang sudah siap dieksekusi.

- Penjadwalan I/O

   adalah suatu keputusan untuk memilih proses mana yang akan diberi kesempatan untuk menggunakan I/O device diantar sejumlah proses yang sama-sama akan menggunakan I/O device tersebut.

Penjadwalan Alternatif

Oke kali ini kita masuk ke bagian inti dari artikel yang saya susun ini. Terdapat beberapa jenis penjadwalan alternatif, diantaranya adalah:

- First Come First Serve (FCFS)

- Round Robin (RR)

- Shortest Process Next (SPN)

- Shortest Remaining Time (SRT)

- Highest Response Ratio Next (HRRN)

- Feedback (FB)

Oke sekarang kita bahas satu persatu ya..

1. First Come First Serve (FCFS)

Proses ini disebut juga dengan FIFO (First In First Out), dimana proses yang datang pertama akan dieksekusi terlebih dahulu.

Kelebihan dari proses ini adalah:

- Merupakan metode scheduling paling sederhana

- Overhead kecil

- Dapat mencegah starvation

Kekurangan :

- Proses yang pendek dapat dirugikan, bila urutan eksekusinya setelah proses yang panjang

Contoh :

- Terdapat 5 buah proses yang akan dieksekusi menggunakan algoritma schedulling FCFS. Waktu kedatangan dan waktu layanan untuk masing-masing proses seperti pada tabel dibawah ini.

Proses
Arival Time
Service Time
A
0
3
B
2
6
C
4
4
D
6
5
E
8
2

Gambarkan urutan eksekusi yang terjadi dan hitung finish time, TAT (Turn Around Time), dan NTAT (Normalized Turn Around Time) untuk masing-masing proses.

Solusi :

Process
A
B
C
D
E
Mean
Finsih Time
3
9
13
18
20
Arival Time
0
2
4
6
8
TAT
3
7
9
12
12
8.60
Service Time
3
6
4
5
2
NTAT
1.00
1.17
2.25
2.40
6.00
2.56

 

2. Round-Robin (RR)

Eksekusi proses dilakukan berdasarkan alokasi waktu tertentu yang diatur dengan clock interrupt.

Kelebihan :

- Dapat menghindari ketidakadilan layanan terhadap proses kecil seperti yang telah terjadi pada FCFS

- Response time lebih cepat untuk proses yang berukuran kecil

- Dapat mencegah starvation

- Overhead kecil, jika ukuran proses rata-rata lebih kecil dibandingkan quantum / slot

Kekurangan :

- Performa lebih buruk dibandingkan FCFS jika ukuran slot lebih besar daripada ukuran proses terbesar

- Dapat terjadi overhead berlebihan jika ukuran setiap slot terlalu kecil

- Proses I/O bound mendapatkan layanan lebih sedikit

Contoh :

Berikut adalah contoh kasus seperti pada FCFS namun diselesaikan dengan metode Round-Robin dengan quantum = 1

Process
A
B
C
D
E
Mean
Finsih Time
4
18
17
20
15
Arival Time
0
2
4
6
8
TAT
4
16
13
14
7
10.80
Service Time
3
6
4
5
2
NTAT
1.33
2.67
3.25
2.80
3.50
2.71

 

3. Shortest Process Next (SPN)

Eksekusi proses diatur berdasarkan perkiraan ukuran proses terkecil. Sehingga proses yang datang belakangan akan ditaruh didepan dan dieksekusi terlebih dahulu jika ukuran proses tersebut paling kecil diantara proses yang lain.

Kelebihan :

- Dapat mencegah kerugian proses kecil seperti yang dialami FCFS

- Throughput tinggi

- Proses kecil mempunyai response time kecil

Kekurangan :

- Scheduler harus mengetahui atau memperkirakan ukuran setiap proses yang akan dieksekusi.

- Proses besar dapat mengalami starvation

- Overhead bisa tinggi

Contoh :

Contoh kasus seperti pada FCFS yang diselesaikan dengan metode SPN

Process
A
B
C
D
E
Mean
Finsih Time
3
9
15
20
11
Arival Time
0
2
4
6
8
TAT
3
7
11
14
3
7.60
Service Time
3
6
4
5
2
NTAT
1.00
1.17
2.75
2.80
1.50
1.84

 

4. Shortest Remaining Time

Eksekusi proses diatur berdasarkan perkiraan sisa waktu terkecil , proses yang masuk dapat langsung dieksekusi bila total waktu eksekusinya lebih kecil daripada sisa waktu proses yang sedang running.

Kelebihan :

- Kualitas layanan rata-rata yang diterima proses lebih baik (jumlah proses yang memperoleh nilai NTAT = 1 lebih banyak)

- Throughput tinggi

- Response time cepat

Kekurangan :

-Terjadi overhead akibat scheduler harus menghitung / memperkirakan sisa waktu eksekusi setiap proses untuk menentukan sisa waktu yang terkecil

- Dapat terjadi starvation pada proses yang panjang

- Proses yang panjang dikalahkan oleh proses yang kecil

Contoh :

Solusi masalah seperti pada FCFS menggunakan metode SRT

Process
A
B
C
D
E
Mean
Finsih Time
3
15
8
20
10
Arival Time
0
2
4
6
8
TAT
3
13
4
14
2
7.20
Service Time
3
6
4
5
2
NTAT
1.00
2.17
1.00
2.80
1.00
1.59

 

5. Highest Response Ratio Next (HRRN)

Pemilihan proses didasarkan pada rasio response tertinggi. Rasio response diperoleh dari perbandingan jumlah waktu tunggu (w) ditambah perkiraan service time (s) dengan perkiraan service time (s)

R = w+s / s

Keuntungan :

- Dapat mencegah starvation

- Setiap proses akan mendapatkan layanan proses yang seimbang

- Response time cepat

- Throughput tinggi

Kekurangan :

- Terjadi overhead akibat scheduller harus mengetahui service time dari proses-proses yang akan dieksekusi.

Contoh :

Solusi untuk menyelesaikan kasus seperti pada FCFS tetapi menggunakan HRRN

Process
A
B
C
D
E
Mean
Finsih Time
3
9
13
20
15
Arival Time
0
2
4
6
8
TAT
3
7
9
14
7
8.00
Service Time
3
6
4
5
2
NTAT
1.00
1.17
2.25
2.80
3.50
2.18

 

6. Feedback

Setiap proses yang datan glangsung masuk pada antrian prioritas tertinggi, sehingga langsung dieksekusi selama satu slot atau satu kuantum. Bila proses tersebut ter-preempt oleh proses lain atau jatah waktunya habis selanjutnya dimasukkan kedalam antrian prioritas lebi rendah (teknik ini disebut multilevel feedback).

Kelebihan :

- Dapat digunakan pada kondisi diman ainformasi tentang panjang proses atau perkiraan waktu eksekusi tidak diketahui

Kekurangan :

- Turn around time (TAT) proses yang panjang dapat semakin lama

- Proses yang panjang dapat mengalami starvatio nbila terus menerus datang proses yang baru

- overhead tinggi

Contoh :

 

Process
A
B
C
D
E
Mean
Finsih Time
4
20
16
19
11
Arival Time
0
2
4
6
8
TAT
4
18
12
13
3
10.00
Service Time
3
6
4
5
2
NTAT
1.33
3.00
3.00
2.60
1.50
2.29

 

Real Time Scheduling

Penjadwalan real-time dapat diartikan dengan penjadwalan yang benar-benar valid, yang ditentukan oleh hasil logika dan waktu hasil diperoleh.

Berdasarkan tugas-tugas yang dikerjakan Real-Time dibagi menjadi dua , yaitu hard real-time dan soft real-time. Hard Real-Time adalah proses yang harus diselesaikan pada saat itu juga untuk menghindari error. Soft Real-Time adalah proses yang dikerjakan berdasarkan prioritas dan terdapat toleransi waktu untuk pengeksekusian proses tersebut.

Real-Time Scheduling juga memiliki beberapa algoritma penjadwalan, adapun algoritmanya adalah sbb:

1. Clock-driven

pada clock-driven scheduling ini terdapat bagian yang menunjuk waktu penjadwalan yang disebut  “scheduling desicion time”  fungsingya untuk menentukan prioritas dalan suatu proses, penjadwalan dilakukan secara langsung dan pada waktu tertentu. Clock-driven biasanya digunakan pada hard real-time sistem.

2. Weighted round-robin

merupakan algoritma kelanjutan dari algoritma round robin ( RR ). Fungsinya untuk penjadwalan real – time traffic berkecepatan tinggi. Contohnya yaitu pada algoritma penjadwalan jaringan.

3. Priority driven

adalah yang menggunakan priority-driven (algoritma yang mengutamakan prioritas untuk menyelesaikan suatu proses yang dieksekusi). Dalam sistem non real time, berbagai faktor dapat digunakan untuk menentukan prioritas. Dalam sistem real time , prioritas tugas terkait dengan kendala waktu terkait dengan tiap tugas. Biasanya digunakan untuk dinamis real-time sistem.

 

RSS feed for comments on this post. TrackBack URI

Leave a reply


CAPTCHA Image
*