SJF (Shortest Job First).

Ciri-ciri SJF:

@SJF merupakan  satu algorithme penjadwalan  Non Preepmtive.

@Penjadwalan ini mengasumsikan waktu layanan proses  diketahui sebelumnya.

@SJF tidak dapat dilaksanakan di tingkat penjadwalan CPU jangka pendek, karena tidak ada cara untuk mengetahui BT proses berikutnya. Sama halnya seperti FIFO,   SJF optimal diterapkan untuk penjadwalan CPU jangka panjang seperti dalam sistem Batch.

@Shortest Job First (SJF) merupakan algorithme penjadwalan layanan proses berdasarkan Burst Time terpendek(BT terkecil, tersingkat).

@Dari proses yang sudah tiba pada semua AT =0    scheduller memilih proses terpendek untuk pertama dilayani oleh processor hingga selesai kemudian urutan selanjutnya yang dijadwalkan untuk dilayani adalah proses yang memiliki BT terpendek dari semua proses yang tersisa ,  demikian prinsip layanan proses-prosesnya selanjutnya hingga semua proses dilayani  selesai.

@Jika proses tiba dengan waktu tiba(AT) yang berbeda maka proses yang awal dilayani awal adalah proses yang masuk di waktu tiba paling awal dan proses tersebut dilayani hingga selesai dengan tanpa melihat apakah proses yang tiba di waktu paling awal tersebut memiliki BT terpendek atau terpanjang,  urutan layanan selanjutnya barulah dilakukan layanan pada proses yang BT nya paling  terpendek dan demikian prinsip layanan proses yang selanjutnya dipilih BT terpendek dari semua proses yang ada hingga semua semua proses selesai dilayani.

@Jika terdapat 2 proses atau lebih yang memiliki BT sama terpendek maka penjadwalan ala FIFO dilaksanakan yaitu dari antara kedua proses yang memiliki BT sama terpendeknya yang duluan dilayani adalah proses yang duluan tiba dari keduanya .

@SJF dinilai sebgai algorithme yang memberikan efisiensi yang tinggi dan turn around time rendah dan penjadwalannya tak berprioritas.

@Algoritma SJF pada suatu kondisi dapat bersifat algorithme  pre-emptive  yang dikenal sebagai algorithme SRTF atau SRF yang insya Allah  akan penulis postingkan pada kesempatan  yang akan datang.

MASALAH PADA SJF
1) Starvation (adanya proses yang tidak dilayani)
dalam beberapa keadaan seperti BT terpendek yang panjang  mungkin dibelakang ada proses yang selamanya menunggu.
Misalnya proses A BT 1 jam tiba di AT = 0

***************************

Contoh 1 Algorithme SJF

Contoh SJF dengan Arrival Time =0

Terdapat proses dibawah ini dengan Arrival Time (waktu tiba) yang sama di  t=0

Jika ditanya :

1.kapankah proses mulai dilayani ?

2.kapankah proses selesai dilayani ?

3.berapa lama proses menunggu sebelum dilayani ? dan berapa rata-rata lama proses menunggu dilayani?

4.berapa waktu yang dihabiskan proses di dalam sistem ? dan berapa rata-rata waktu yang dihabiskan proses di dalam sistem?

maka jawaban pertanyaan di atas memerlukan langkah-langkah Penyelesaian:

Untuk mudah dapat menjawab pertanyaan maka sebagai Langkah 1.;

Membuat Gantt Chart Proses SJF nya.

Mungkin jika ukuran waktu prosesnya pendek dan rangkaian prosesnya sedikit maka dianggap  tidak memerlukan Gantt Chart , namun jika BT prosesnya bervariasi dan panjang serta rangkaian  prosesnya banyak maka Gantt Chart sangat membantu kita membahas mekanismenya.

Dalam membuat Gant Chart rangkaian proses digunakan prinsip SJF yaitu dengan 
mengingat bahwa  proses yang pertama dilayani yang punya BT terpendek yaitu proses A BT3 hingga selesai  di t =3, kemudian diikuti dengan terpendek berikutnya proses X BT6 dilayani hingga  selesai di t =9 dan kemudian terpendek berikutnya proses Z BT7 dilayani hingga selesai  di t =16  dan yang terakhir dilayani adalah proses Y BT8 dilayani selesai di t=24.  Sebagai  kontrol perlu memperhatikan Jumlah Burst Time sama dengan t terakhir pada Gantt Chart.

Meskipun di soal tidak diminta menggambarkan Gantt Chartnya, tetapi sudah lazim dalam menjawab soal algorithme penjadawalan .dilampirkan Gantt Chartnya pada bagian awal jawaban.

Gant Chart proses SJF nya:

Membuat  tabel  jawaban yaitu table dasar soal  ditambah dengan kolom-kolom komponen  pertanyaan seperti berikut:

Setiap hasil pembahasan nantinya  dituliskan sebagai jawaban di dalam tabel.

Langkah 2. Berdasarkan Gantt Chart dapat dimulai menjawab pertanyaan

1.Waktu Proses mulai dilayani (Start Time) dilihat dari Gantt Chart

X =3

Y=16

Z=9

A=0 ­.------masukkan jawaban di dalam tabel di kolom Start Time

2.Waktu Proses selesai  dilayani (Completion Time) dilihat dari Gantt Chart

X =9

Y=24

Z=16

A=3 ­.------masukkan jawaban di dalam tabel pada langkah 2 di kolom Completion Time

3.Waktu Proses menunggu dilayani (Waiting Time) dapat dilihat dari Gantt Chart:

X =3

Y=16

Z=9

A=0  ------masukkan jawaban di dalam tabel pada langkah 2 di kolom Completion Time

Jika diuji dengan Rumus perhitungan WT :

Waiting Time = Start Time – Arrival Time

Waiting Time = Completion Time – Burst Time – Arrival Time
Untuk AT = 0 ,  WT=ST  atau  WT = CT-BT

Maka hasilnya sama dengan pembacaan waktu tunggu dari Gantt Chart

  

Rata-rata lama waktu proses menunggu dilayani:

WT average = ∑ WT  / ∑P

WT average = (3+16+9+0)/4 = 7

4.Waktu yang dihabiskan Proses di dalam sistem adalah:

Turn Around Time =

Turn Around Time = Completion Time – Arrival Time

Atau

Turn Around Time = Waiting Time + Burst Time

X=3 +6 = 9

Y=16 +8 =24

Z=9 +7 =16

A=0  + 3 = 3 masukkan jawaban di dalam tabel pada langkah 2 di kolom Turn Around Time

Rata-rata waktu yang dihabiskan proses di dalam sistem  (Turn Around Time) adalah

TAT average = ∑ TAT  / ∑P

TAT average= (9 + 24 + 16 +3) / 4 = 13

********************************* 

Contoh 2 Algorithme SJF

Contoh SJF dengan Arrival Time berbeda

Pertanyaan:

1.Gambarkan Gantt Chart proses

2.Tentukan Lama Proses menunggu layanan

3.Hitung jumlah rata-rata waktu yang dihabiskan proses selama di dalam sistem

Pada rangkaian proses di bawah ini.

Pembahasan :

Pada t=0.0 P1(BT7)  tiba dilayani 7 ms selesai di t=7,sementara  itu semua proses sudah tiba.

Kemudian yang dilayani selanjutnya adalah proses yang dilayani berikutnya dari tiga proses yang tersisa adalah proses yang  paling pendek BTnya yaitu P3(BT1) dilayani 1ms selesai di t=8,  selanjutnya yang dilayani adalah P2(BT4) dilayani selesai di t=12 dan terakhir dilayani adalah P1(BT7) selesai di t=16

Jawaban 1.

Gant Chart pproses SJF nya:

Jawaban 2.

Sebelumnya ,buat tabel jawaban dari tabel dasar ditambah kolom Waiting Time dan kolom Turn Around Time

Mencari Waiting Time (WT) yang lebih memungkinkan digunakan rumus

WT = Start Time - Arrival Time , -------untuk ukuran Start Time lihat Gantt Chart

WT P1 =0-0 =0

WT P2 =8-2 =6

WT P3=7-4 =3

WT P4 =12-5 =7  -------------------isikan ke dalam kolom Waiting Time

Jawaban no 3

TAT= Waiting Time + Burst Time Mencari waktu yang dihabiskan proses selama di sistem (Turn Around Time)  yang lebih memungkinkan digunakan rumus

TAT P1 =0+7 =7

TAT P2 =6+4 =10

TAT P3 =3+1 =4

TAT P4 =7+4 =11  -------------------isikan ke dalam kolom  Turn Around Time di tabel

Tabel Jawaban Contoh 2 SJF:

Rata-rata Turn Around Time = ∑ Turn Around Time / ∑ Proses

Rata-rata Turn Around Time = (7+10+4+11) /4  = 32/4 = 8

**************************

Contoh 3 Algorithme SJF

Mencari Rata-rata waktu penyelesaian  dan rata-rata waktu tunggu dari proses dibawah :

Pembahasan:

Seperti biasanya , terutama untuk tampilan data proses yang demikian diperlukan Gantt Chart untuk

membahasnya. 

Proses yang pertama tiba  di t=1 adalah D4(BT5) dilayani  5ms hingga selesai  di t = 6, sementara itu semua proses  telah tiba. Proses selanjutnya yang memiliki BT terpendek ada dua yakni  D1 dan D6 maka kebijakan FIFO digunakan yaitu yang dilayani adalah D6 karena D6 tiba lebih awal daripada D1.

Setelah D6 maka dilayani berturut-turut adalah D1,D5,D2,D4, dan terakhir dilayani adalah D3,sehingga kronologis pelayanan prosesnya dapat digambarkan pada Gantt Chart sbb:

∑t = 19-1 =18

Untuk mencari waktu penyelesaian  proses  selama di sistem (Turn Around Time)  yang lebih memungkinkan digunakan rumus :

Turn Arround Time  = Completion Time  – Arrival Time yaitu

Lihat Completion Time dari Gantt Chart dan lihat Arival Time dari tabel dasar di atas,  maka didapat:

Waktu Penyelesaian D1 = 8 –  6 = 2

Waktu Penyelesaian D2 = 13 – 3 =10

Waktu Penyelesaian D3 = 19 – 4 =15

Waktu Penyelesaian D4 = 6 – 1 = 5

Waktu Penyelesaian D5 = 10 – 2 = 8

Waktu Penyelesaian D6 = 7 – 5 = 2 -------isikan hasilnya ke kolom Turn Around Time  pada tabel.

Rata-rata waktu penyelesaian maka

TAT =  ∑ Turn Around Time / ∑ Proses

TAT = (2+10+15+5+8+2)/6    =42/6  = 7

Untuk mencari waktu tunggu   proses  (Waiting Time)  yang lebih memungkinkan digunakan rumus

Yang berkaitan langsung dengan  TAT yaitu:

Waiting Time = Turn Around Time - Burst Time

WT D1  = 2–1 = 1

WT D2  = 10–3 = 7                                   

WT D3  = 15-6 = 11

WT D4  = 5-5 = 0

WT D5  = 8-2 = 6

WT D6  = 2-1 = 1--------------isikan hasilnya ke kolom  Waiting Time  pada tabel.

             

Tabel Jawaban Contoh 3 SJF :          

Demikian kiranya informasi SJF scheduling yang dapat penulis tampilkan di sini,  semoga bermanfaat .


Thanks for...

Daftar Referensi:

   http://inst.eecs.berkeley.edu/~cs162/sp11/sections/cs162-sp11-section5-answers.pdf

      http://siber.cankaya.edu.tr/OperatingSystems/ceng328/node123.html

http://web.cse.ohio-state.edu/~agrawal/660/Slides/jan18.pdf

https://www.cs.rutgers.edu/~pxk/416/notes/07-scheduling.html

Pasaribu.M.2015.Sistem Operasi