Pengertian dan Contoh Kasus FIFO dan SJF dalam Penjadwalan Proses

Assalamualaikum sahabat blogger, sudah lama yah kita tak berjumpa …

Oia, Kalian pernah g berfikir tentang bagaimana sebuah proses di jalankan dalam sebuah mesin elektronik yang sering kita sebut dengan komputer.??? kita tinggal klik sana klik sini ,, semua yang kita ingin kan sudah di proses.. Komputer juga sama seperti kita.. jika kita memiliki tugas yang banyak atau kegiatan yang banyak kita bisa membuat jadwal yang membantu kita dalam mengatur waktu. Komputer juga seperti itu memutuhkan penjadwalan pada saat kita menjalankan beberapa program dalam satu waktu. play music, ngegame , ngerjain tugas dll, Mau tahu pengetian penjadwalan serta algoritma penjadwalan computer seperti apa??? Langsung saja chekidot...

PENJADWALAN PROSES

Deskripsi

·         Kumpulan kebijaksaanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer

Tugas :

•         Memastikan proses harus berjalan

•         Kapan dan berapa lama proses berjalan

Sasaran Utama

•         Optimasi kinerja sistem komputer menurut kriteria tertentu

Kriteria untuk mengukur dan optimasi kinerja penjadwalan

•         Adil (fairness)

–        Proses-proses diberlakukan sama, mendapatkan jatah waktu layanan pemroses yang sama dan tidak ada yang tidak kebagian layananan pemroses sehingga mengalami STARTVATION (proses tidak pernah berjalan karena tidak dijadwalkan untuk berjalan)

–        Sasaran

•         Menjamin setiap proses mendapat pelayanan dari pemroses secara adil

•         Efisiensi

–        Perbandingan waktu sibuk pemroses dengan total waktu operasi sistem komputer secara keseluruhan

–        Sasaran

•         Menjaga agar pemroses tetap dalam keadaan sibuk sehingga efisiensi sistem komputer mencapai nilai maksimum

•         Waktu tanggap (response time)

–        Waktu tanggap sistem interaktif (terminal response time)

•         Waktu yang dihabiskan dari saat karakter terakhir perintah dimasukkan oleh program atau transaksi sampai hasil pertama muncul diperangkat masukan keluaran seperti layar (terminal).

–        Waktu tanggap pada sistem waktu nyata (event response time)

•         Waktu dari saat kemunculan suatu kejadian (internal atau eksternal) sampai instruksi pertama rutin layanan terhadap kejadian dieksekusi

–        Sasaran

•         Meminimalkan waktu tanggap sehingga menghasilkan sistem yang resonsif

•         Turn around time

–        Waktu yang dihabiskan dari saat proses atau job mulai masuk kedalam sistem sampai proses tersebut diselesaikan oleh sistem

Turn arround time = waktu eksekusi + waktu menunggu

–        Sasaran

•         Meminimalkan turn arround time

•         Throughputt

–        Jumlah kerja yang dapat diselesaikan selama satu selang/unit waktu

–        Sasaran

•         Memaksimalkan jumlah job /proses yang dilayani per satu interval tertentu, lebih tinggi angka throughput maka lebih banyak kerja yang dilakukan oleh sistem

Algoritma-Algoritma Penjadwalan Proses

–        Algortima yang menerapkan nonpreemptive

–        FIFO (first-in, first-out)

–        SJF (Shortest Job First)

–        Algoritma yang menerapkan preemptive

–        RR (Round Robin)

–        MFQ (Multiple Feedback Queues)

–        SRF (shortest-remaining-first)

–        HRN (Highest-ratio next)

–        PS (Priority Scheduling)

–        GS (Guaranteed Scheduling)

1. FIFO (FIRST-IN, FIRST-OUT)

FIFO adalah akronim untuk First In, First Out (Pertama Masuk, Pertama Keluar), sebuah abstraksi yang berhubungan dengan cara mengatur dan memanipulasi data relatif terhadap waktu dan prioritas, atau lebih sederhananya FIFO salah satu teknik pengelolaan queue atau penanganan tugas yang bertumpuk, yaitu item yang pertama akan dikerjakan lebih dahulu. Ungkapan ini menggambarkan prinsip teknik pengolahan antrean atau melayani permintaan yang saling bertentangan dengan proses pemesanan berdasarkan perilaku : di mana orang-orang meninggalkan antrean dalam urutan mereka tiba, atau menunggu giliran satu di sebuah sinyal kontrol lalu lintas.FCFS juga merupakan Jargon istilah untuk sistem operasi penjadwalan algoritma FIFO, yang memberikan setiap proses CPU waktu sesuai dengan urutan mereka datang.

Dalam arti yang lebih luas, abstraksi LIFO, atau Last-In-First-Out adalah kebalikan dari abstraksi organisasi FIFO. Bedanya mungkin adalah yang paling jelas dengan mempertimbangkan sinonim yang kurang umum digunakan dari LIFO, FILO (berarti First-In-Last-Out). Pada intinya, keduanya adalah kasus khusus dari daftar yang lebih umum (yang dapat diakses di mana saja). Perbedaannya adalah tidak ada dalam daftar (data), tetapi dalam aturan untuk mengakses konten. Satu sub-tipe menambah satu ujung, dan melepaskan dari yang lain, sebaliknya mengambil dan menempatkan sesuatu hanya pada salah satu ujungnya. Variasi bahasa populer pada pendekatan ad-hoc untuk menghapus item dari antrean telah diciptakan dengan nama OFFO, yang merupakan singkatan On-Fire-First-Out. Antrean Prioritas adalah variasi pada antrean yang tidak memenuhi syarat untuk nama FIFO, karena tidak secara akurat menggambarkan perilaku Struktur Data. Teori antrean mencakup konsep yang lebih umum dari antrean, serta interaksi antara ketat-antrean FIFO.

Penjadwalan FIFO ini merupakan penjadwalan tidak berprioritas, dan penjadwalan dengan ketentuan-ketentuan paling sederhana, yaitu: Proses-proses diberi jatah waktu pemroses diurutkan berdasarkan waktu kedatangan proses-proses itu ke system. Pada saat proses mendapat jatah waktu pemroses, proses dijalankan sampai selesai.

Penjadwalan ini dikatakan adil dalam arti resmi (dalam semantic/arti antrian, yaitu proses yang pertama datang, akan dilayani pertama juga), tapi dinyatakan tidak adil karena proses-proses yang perlu waktu lama membuat proses-proses pendek menunggu. Proses-proses tidak penting dapat membuat proses-proses penting menunggu.

Kelebihan FIFO

Dalam kriteria efisiensi, penjadwalan FIFO sangat efisien dalam penggunaan proses.
Algoritmanya cukup sederhana

Kelemahan FIFO

*Dalam kriteria adil, penjadwalan FIFO adil dalam arti resmi (dalam semantic/arti antrian) yaitu proses yang pertama datang, akan dilayani pertama juga), tapi dinyatakan tidak adil karena proses-proses yang perlu waktu lama membuat proses-proses pendek menunggu. Proses-proses tidak penting dapat membuat proses-proses penting menunggu.
*Penjadwalan sangat tidak memuaskan karena proses menunggu lama, aktu tanggapnya sangat jelek. *Tidak cocok untuk sistem interaktif.
*Turn around time tidak bagus.
*Throughtput tidak bagus.
*Tidak dapat digunakan untuk sistem waktu nyata

Penjadwalan ini :

a. Baik untuk sistem batch yang sangat jarang berinteraksi dengan pemakai.

   Contoh : aplikasi analisis numerik, maupun pembuatan tabel.

b. Sangat tidak baik (tidak berguna) untuk sistem interaktif, karena tidak

   memberi waktu tanggap yang baik.

c. Tidak dapat digunakan untuk sistem waktu nyata (real-time applications).

Contoh Aplikasi Penerapan Teknik Penjadwalan FIFO

 a.      Ketika mencetak (dokumen,foto dll) yang di tekan/diperintahkan mencetak pertama maka itulah yang akan dikerjakan atau dilaksanakan duluan yang lain mengantri didalam list. 

b.      Ketika membuka suatu jendela aplikasi, yang pertama dibuka maka aplikasi itu akan muncul duluan.

CONTOH KASUS :

 TABEL

Nama proses	Saat Tiba	Burst Time
P1	0	14
P2	0	10
P3	2	13
P4	3	8
P5	5	3

Dengan menggunakan algoritma First come, first served (fcfs) atau First In, First Out (FIFO) dan Shorted Job First Scheduller (SJF), carilah :

a. Rata-rata waktu tunggu 

b. Rata-rata waktu tanggap 

c. Turn arround time

Jawaban 1

Nama Proses	Saat Tiba	Burst Time	Saat Mulai	Saat selesai	Waktu Tunggu	Waktu Tanggap
P1	0	14	34	48
P2	0	10	0	10
P3	0	13	21	34
P4	0	8	13	21
P5	0	3	10	13

. Rata-rata waktu tunggu 

Nama proses	Saat Tiba	Burst Time	Waktu tunggu	Ratio
P2	1	2	5	(5+2)/2 =7/2 =3,5
P3	1	3	5	(5+3)/3=8/3=2,66
P4	2	4	4	(4+4)/4= 2
P5	3	1	3	(3+1)/1 = 4

Yang dikerjakan adalah P5

b. Rata-rata waktu tanggap 

Nama proses	Saat Tiba	Burst Time	Waktu tunggu	Ratio
P2	1	2	6	(6+2)/2 =8/2 =4
P3	1	3	6	(6+3)/3=9/3=3
P4	2	4	5	(5+4)/4= 2,

Yang dikerjakan adalah P2

c. Turn arround time

Nama proses	Saat Tiba	Burst Time	Waktu tunggu	Ratio
P3	1	3	8	(8+3)/3=11/3=3,66
P4	2	4	7	(7+4)/4= 11/4 =2,75

Yang dikerjakan adalah P3

Tabel Proses

Nama Proses	Saat Tiba	Burst Time	Saat Mulai	Saat selesai	Waktu Tunggu	Waktu Tanggap
P1	0	6	0	6	0	6
P2	1	2	7	9	6	2
P3	1	3	9	12	8	3
P4	2	4	12	16	10	4
P5	3	1	6	7	3	1

2. SJF (SHORTEST JOB FIRST)

Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek, sehingga dapat dikatakan bahwa algoritma ini adalah algoritma yang optimal.

Tabel Contoh Shortest Job First

Process	Arrival Time	Burst Time
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

CONTOH KASUS

1.   Ada 4 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 7 ms, P2 dengan arrival time pada 2.0 ms dan burst time 4 ms, P3 dengan arrival time pada 4.0 ms dan burst time 1 ms, P4 dengan arrival time pada 5.0 ms dan burst time 4 ms. Hitunglah waiting time rata-rata dan turnaround time dari keempat proses tersebut dengan mengunakan algoritma SJF.

Average waiting time rata-rata untuk ketiga proses tersebut adalah sebesar (0 +6+3+7)/4=4 ms.

Gambar 14.3. Shortest Job First (Non-Preemptive)

Average waiting time rata-rata untuk ketiga prses tersebut adalah sebesar (9+1+0+2)/4=3 ms.

2.      Misalnya ada 2 buah proses yang datang berurutan yaitu P1 dengan arrival time pada 0.0 ms dan burst time 10 ms, P2 dengan arrival time pada 2.0 ms dan burst time 2 ms.

Process	Arrival Time	Burst Time
P1	0.0	10
P2	2.0	2

3.     

waiting time PSJF nya :

P1 = 0 + ( 4 ms – 2 ms ) = 2 ms

P2 = 0

Average waiting time : (2 ms + 0 ms ) / 2 = 2 ms

Average turn around : (12 ms + 0 ) / 2 = 12 ms

Tabel Solusi

Process	Arrival Time	Burst Time	Waktu Mulai	Waktu selesai	Waiting Time		Turn Around
P1	0	10	0	12	2		12
P2	2	2	0	4	0		0
				Average	2	12

Ada beberapa kekurangan dari algoritma ini yaitu:

1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya.
2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

Algoritma ini dapat dibagi menjadi dua bagian yaitu :

1. Preemptive .�Jika ada proses yang sedang dieksekusi oleh CPU dan terdapat proses di ready queue dengan burst time yang lebih kecil daripada proses yang sedang dieksekusi tersebut, maka proses yang sedang dieksekusi oleh CPU akan digantikan oleh proses yang berada di ready queue tersebut. Preemptive SJF sering disebut juga Shortest-Remaining- Time-First scheduling.
2. Non-preemptive .�CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.