TEKNIK PENJADWALAN PROSESOR

1. Istilah-istilah dan Konsep-konsep Penjadwalan

• Bagian sistem operasi yang mengatur penjadwalan eksekusi proses-proses disebut scheduler.
• Algoritma yang digunakan disebut algoritma penjadulan (scheduling algorithm).
• Kriteria baik tidaknya suatu algoritma penjadwalan ditentukan oleh:

1. Fairness
2. Efficiency
3. Response Time
4. Turnaround Time
5. Throughput

• Penjadwalan Proses

–      Antrian
–      Prioritas
–      Preempsi

• Jangka penjadwalan

–      pendek
–      madya
–      panjang

• Tujuan penjadwalan:

–       pelayanan yang adil untuk semua pekerjaan
–       memaksimumkan throughput
–       memaksimumkan pemakaian prosesor
–       meminimumkan waktu tunggu (overhead)
–       pemakaian sumber daya seimbang
–       tidak terjadi penundaan waktu tak hingga
–       kegiatan sumber daya dapat dideteksi terlebih dahulu

• Perhitungan kerja prosesor

t       = lama proses pada prosesor
T      = lama tanggap pada prosesor
Waktu sia-sia (waktu antri) = T – t
Rasio tanggap Rt = t / T
Rasio Penalti Rp = T/t

Penjadwalan Prosesor

• Penjadwalan satu tingkat

–       Pertama Tiba Pertama Dilayani (PTPD)
–       Proses Terpendek Dipertamakan (PTD)
–       Proses Terpendek Dipertamakan Preempsi (PTDP)
–       Rasio Penalti Tertinggi Dipertamakan (RPTD)
–       Putar Gelang (PG)
–       Putar Gelang Prioritas Berubah (PGPB)

• Penjadwalan multi tingkat

–       Antrian multitingkat
–       Antrian multitingkat berbalikan

2.     Penjadwalan Satu Tingkat

• Pertama Tiba Pertama Dilayani (PTPD)

First Come First Served (FCFS)
Penjadualan ini murni antrian.

Nama Proses	Saat Tiba	Lama Proses	Saat Mulai	Saat Rampung	Lama Tanggap
A	0	9	0	9	9
B	0	30	9	39	39
C	0	4	39	43	43
D	0	8	43	51	51
E	0	12	51	63	63
				Jumlah	205
				Rerata	41

• Pertama Tiba Pertama Dilayani (PTPD)
  First Come First Served (FCFS)

Nama Proses	Saat Tiba	Lama Proses	Saat Mulai	Saat Rampung	Lama Tanggap
A	0	4	0	4	4
B	1	7	4	11	10
C	3	3	11	14	11
D	7	8	14	22	15
				Jumlah	40
				Rerata	10

• Proses Terpendek Dipertamakan (PTD)
  Shortest Job First (SJF)

Penjadualan ini adalah antrian dengan prioritas, yang menjadi prioritas adalah proses yang terpendek (tersingkat).

Nama Proses	Saat Tiba	Lama Proses	Nama Proses	Saat Tiba	Lama Proses
A	0	8	C	6	3
B	4	5	E	14	4
C	6	3	B	4	5
D	9	8	A	0	8
E	14	4	D	9	8

• Proses Terpendek Dipertamakan (PTD)
  Shortest Job First (SJF)

Nama Proses	Saat Tiba	Lama Proses	Lama Mulai	Saat Rampung	Lama Tanggap
A	0	8	0	8	8
C	6	3	8	11	5
B	4	5	11	16	12
E	14	4	16	20	6
D	9	8	20	28	19
				Jumlah	50
				Rerata	10

• Proses Terpendek Dipertamakan Preempsi (PTDP) Preemptive Shortest Job First (PSJF)

Penjadualan ini dengan prioritas dan preempsi
Proses yang terpendek bisa didahulukan dengan cara membandingkan sisa waktu proses yang sedang dilaksanakan dengan proses yang tiba, dan dapat menyebabkan proses yang sedang berjalan terhenti untuk melaksanakan proses yang lebih pendek/singkat.

Nama Proses	Saat Tiba	Lama Proses
A	0	8
B	2	5
C	4	7
D	5	1

Barisan saat
daftar Proses

Proses	Tiba	Proses	Mulai	Rampung	Tanggap
A	0	8	0	14	14
B	2	5	2	8	6
C	4	7	14	21	17
D	5	1	5	6	1
				Jumlah	38
				Rerata	9.5

• Rasio Penalti Tertinggi Dipertamakan (PTD)

Highest Penalti Ratio Next (HPRN)
Tetap mendahulukan proses pendek ditambah dengan mempertimbangkan rasio penaltinya, yang ditentukan berdasarkan lama waktu antriannya.
t = lama proses

T = lama tanggap

s = waktu sia sia (waktu antri)
s = (T-t)
R_p= (s+t)/t

Nama Proses	Saat Tiba	Lama Proses
A	0	4
B	1	2
C	2	5
D	3	8
E	4	4

Nama Proses	Tiba Selama	Rasio Penalti
B	4 – 1 = 3	(3 + 2) / 2 = 2,5
C	4 – 2 = 2	(2 + 5) / 5 = 1,4
D	4 – 3 = 1	(1 + 8) / 8 = 1,125
E	4 – 4 = 0	(0 + 4) / 4 = 1

Nama Proses	Tiba Selama	Rasio Penalti
C	6 – 2 = 4	(4 + 5) / 5 = 1,8
D	6 – 3 = 3	(3 + 8) / 8 = 1,375
E	6 – 4 = 2	(2 + 4) / 4 = 1,5

Nama Proses	Tiba Selama	Rasio Penalti
D	11 – 3 = 8	(8 + 8) / 8 = 2
E	11 – 4 = 7	(7 + 4) / 4 = 2,75

Daftar Proses

Nama Proses	Saat Tiba	Lama Proses	Lama Mulai	Saat Rampung	Lama Tanggap
A	0	4	0	4	4
B	1	2	4	6	5
C	2	5	6	11	9
D	3	8	15	23	20
E	4	4	11	15	11
				Jumlah	49
				Rerata	9.8

• Putar Gelang (PG)
  Round Robin (RR)

Penjadualan ini tanpa prioritas & preempsi
Setiap proses dilayani selama quantum waktu tertentu secara bergiliran.

Nama Proses	Saat Tiba	Lama Proses
A	0	5
B	1	3
C	5	7
D	6	1
E	7	6

Kuantum waktu (q) = 2
Barisan saat
Daftar Proses

Nama Proses	Saat Tiba	Lama Proses	Lama Mulai	Saat Rampung	Lama Tanggap
A	0	5	0	11	11
B	1	3	2	7	6
C	5	7	7	22	17
D	6	1	9	10	4
E	7	6	11	21	14
				Jumlah	52
				Rerata	10.4

• Penjadwalan dengan prioritas berubah-ubah
  Putar Gelang Prioritas Berubah (PGPB)
  Selfish Round Robin (RR)

Penjadualan yang menggunakan proiritas dapat diubah-ubah menjadi prioritas lainnya.
p = prioritas              a = koefisien untuk lama
s = waktu sia sia       b = koefisien untuk proses baru
t = waktu proses       b/a = 1 => prioritas sama
u = tarif sewa            b/a = 0 => prioritas lama +
p = f ( s, t, u )            b/a < 1 => prioritas baru < lama
b/a > 1 => prioritas baru > lama

3.     Penjadwalan Multitingkat

v Proses dibedakan tingkatnya berdasarkan kepentingannya.
v Penjadualan pada tiap tingkat dapat bermacam-macam.
v Pada antrian multitingkat berbalikan, tingkat satu dan lainnya saling berhubungan.

• Antrian Multitingkat (Multilevel queue)

• Antrian Multitingkat Berbalikan
  Feedback multilevel queue

4.     Metoda Evaluasi Penjadwalan
–       evaluasi analitik

• pemodelan deterministik
• analisis model antrian

–       simulasi
–       implementasi
¨   Metode Pemodelan Deterministik
Pekerjaan sudah ditetapkan terlebih dahulu, menerapkan berbagai penjadualan dan dievaluasi hasilnya.
Kelemahan: Hanya tepat untuk model yang sudah dicoba,
untuk model yang lain belum tentu.
¨   Metode Analisis Model Antrian
Dengan menganggap sistem komputer sebagai suatu jaringan alat layanan.
Dianalisa berdasarkan model (rumus) yang diambil untuk tiap penjadualan.
Kelemahan: Pengambilan model cukup rumit untuk sistem tertentu dan model tidak selalu cocok dengan keadaan yang sebenarnya.
¨   Metode Simulasi
Metode ini berdasarkan sejumlah variabel yang disimulasikan sistem komputer yang digunakan.
¨   Metode Implementasi
Metode ini bekerja dengan cara mengamati hasil dari implementasi setiap penjadualan.