Filetype PDF | Posted on 06 Feb 2023 | 3 years ago
Authentication
digital resources
411x Filetype PDF File size 0.35 MB Source: informatika.stei.itb.ac.id
Implementasi CPU Scheduling dalam
Multiprogramming dengan Pendekatan Greedy
Amar Fadil - 13520103
Program Studi Teknik Informatika
Sekolah Teknik Elektro dan Informatika
Institut Teknologi Bandung, Jalan Ganesha 10 Bandung
E-mail: 13520103@std.stei.itb.ac.id
Abstract—Dalam multiprogramming, utilisasi CPU diharapkan setiap proses. Pada penjadwalan real-time, penjadwalan dengan
selalu tinggi. Dibutuhkan sebuah algoritma penjadwalan program priority scheduling dapat dilakukan dengan rate monotonic
sehingga CPU memiliki utilisasi penuh setiap saat. Strategi greedy shceduling untuk soft real-time system yang tidak memiliki
dapat digunakan dalam menjadwalkan program secara efisien deadline pengerjaan proses dan earliest deadline first (EDF)
yang biasa disebut sebagai priority scheduling. Shortest first job untuk hard real-time system yang mewajibkan proses harus
merupakan salah satu algoritma priority scheduling non- diproses sehingga tidak boleh melewati deadline [1].
preemptive. Diharapkan dengan priority scheduling, kriteria CPU Dalam makalah ini, akan dibahas penggunaan strategi
scheduler yang bagus terpenuhi dengan baik. greedy dalam mengimplementasikan priority scheduling seperti
Keywords—multiprogramming; greedy; cpu scheduling; SJF, terutama pada kasus non-preemptive. Implementasi ini
shortest job first dapat digunakan dalam level sistem operasi. Selain itu, juga akan
dibahas perbandingan antara shortest job first pada kasus non-
I. PENDAHULUAN preemptive dengan penjadwalan non-preemptive lainnya seperti
Multiprogramming mengharuskan utilisasi CPU yang tinggi FCFS.
setiap saat sehingga tidak terdapat waktu CPU untuk II. TEORI DASAR
mengganggur. Dibutuhkan sebuah penjadwalan yang disebut
sebagai CPU scheduling. Beberapa kriteria dalam menilai CPU A. Algoritma Greedy
scheduling yang bagus, diantaranya utilisasi CPU maksimum,
throughput maksimum, turnaround time minimum, waiting time Algoritma greedy merupakan salah satu cara untuk
minimum, dan response time minimum [1]. Sebuah job memecahkan masalah pada suatu permasalahan. Algoritma ini
seringkali disebut sebagai proses. Penjadwalan proses dapat cukup populer dan mengandalkan pendekatan yang sederhana
dijalankan secara preemptive, yakni penyerobotan paksa proses untuk persoalan optimalisasi, yakni masalah mengenai
sedang berjalan oleh proses yang baru muncul, atau secara non- pencarian maksimasi dan minimasi. Banyak sekali contoh
preemptive, yakni proses yang berjalan harus diselesaikan permasalahan yang dapat diselesaikan dengan algoritma greedy,
terlebih dahulu sebelum memproses proses baru. akan tetapi greedy mempunyai kelemahan yakni hanya
Secara sederhana, pembagian penjadwalan proses dapat mendapatkan local optimum alih-alih global optimum yang
dilaksanakan dengan FCFS (First Come, First Served), yakni sebenarnya diinginkan.
proses yang pertama kali masuk akan diproses pertama kali juga. Prinsip kerja dari algoritma ini adalah “take what you can get
Pembagian penjadwalan dengan FCFS ini bersifat non- now”, yaitu mencari solusi optimal pada setiap langkah. Jika
preemptive, sehingga dapat terjadi convoy effect berupa solusi yang ingin dicari adalah nilai maksimal, algoritma greedy
fenomena proses baru menunggu proses yang sedang dikerjakan akan mengambil nilai maksimal saat itu tanpa memikirkan
dalam waktu sangat lama. Hal ini dapat diselesaikan dengan konsekuensi pada langkah berikutnya. Sebaliknya, jika solusi
round robin, yakni algoritma penjadwalan yang bersifat pre- yang diinginkan adalah solusi dengan nilai minimal, nilai
emptif dalam satuan waktu yang disebut time quantum. Time minimal akan diambil. Nilai maksimal atau minimal sementara
quantum harus dibuat sedemikian rupa sehingga tidak terlalu ini disebut local optimum. Pada langkah berikutnya, algoritma
kecil (banyak overhead akibat context switching) dan tidak greedy akan kembali mencari local optimum. Pencarian local
terlalu besar (bekerja layaknya FCFS) yang biasanya berkisar optimum ini terus diulang hingga langkah terakhir. Pada langkah
antara 10-100ms. terakhir, algoritma greedy diharapkan dapat menemukan solusi
Selain FCFS dan round robin, terdapat algoritma yang optimal dari permasalahan dengan solusinya disebut sebagai
memakai strategi greedy, seringkali disebut sebagai priority global optimum. Meskipun begitu, sebagian permasalahan yang
scheduling karena mengurutkan proses pengerjaan berdasarkan ada tidak dijamin ditemukan solusi optimalnya dengan
prioritas setiap proses. Salah satu algoritma prority scheduling algoritma greedy, atau dengan kata lain local optimumnya
adalah Shortest Job First (SJF) yang mengurutkan proses berbeda dengan global optimum.
pengerjaan berdasarkan prediksi CPU burst selanjutnya dari
Makalah IF2211 Strategi Algoritma, Semester II Tahun 2021/2022
Supaya strategi greedy yang dipakai efektif dan efisien eksekusi CPU dengan I/O wait yang saling bergantian. Untuk
dalam menyelesaikan masalah secara akurat, diperlukan mencapai multiprogramming, dibutuhkan sebuah CPU
perencanaan fungsi seleksi yang baik. Akan tetapi, sulit untuk Scheduling yang efektif dan efisien, sehingga proses yang
membuktikan bahwa sebuah strategi greedy dengan fungsi menunggu I/O wait memberikan bagiannya kepada proses lain
seleksi yang dipilih pasti merupakan global optimum. Untuk yang membutuhkan.
membuktikan fungsi seleksi konvergen menuju global optimum,
harus dilakukan pembuktian dengan induksi matematika, yang C. CPU Scheduling
tentunya sulit untuk dilakukan. Meski begitu, kita juga dapat CPU scheduling merupakan sebuah algoritma yang dapat
membuktikan bahwa suatu strategi greedy bukan merupakan menjadwalkan proses sedemikian rupa untuk dijalankan secara
global optimum hanya dengan memberikan instansi berurutan. Hal ini biasanya diimplementasikan dalam level
permasalahan yang menunjukkan hasil local optimum berbeda sistem operasi. Tujuan utama CPU Scheduling adalah
dengan global optimum. tercapainya multiprogramming. Dalam mencapai
Terdapat beberapa elemen greedy, yakni sebagai berikut: [2] multiprogramming, CPU Scheduling memiliki kriteria sebagai
1) Himpunan Kandidat, C: berisi kandidat yang akan dipilih berikut [1]:
pada setiap langkah (misalnya koin, job, benda, dsb). • Utilisasi CPU maksimum: penggunaan CPU secara
2) Himpunan Solusi, S: berisi kandidat yang sudah dipillih maksimum setiap waktu, dimana CPU akan selalu sibuk
dan akan menjadi solusi permasalahan. dalam mengerjakan proses
3) Fungsi Solusi: menentukan apakah himpunan kandidat • Throughput maksimum: banyaknya proses yang
yang dipilih sudah menjadi solusi permasalahan. diekseskusi dalam satuan waktu bernilai maksimum,
sehingga banyak proses yang dapat diproses dalam suatu
4) Fungsi Seleksi (selection function): memilih kandidat waktu.
berdasarkan strategi greedy tertentu. Strategi greedy ini bersifat • Turnaround time minimum: waktu total yang dibutuhkan
heuristik. untuk mengeksekusi proses, dimulai dari waktu
5) Fungsi Kelayakan (feasible): memeriksa apakah kedatangan hingga burst time proses, seminimum
kandidat yang dipilih dapat dimasukkan ke dalam himpunan mungkin sehingga proses dapat diselesaikan dengan
solusi (layak atau tidak). cepat.
6) Fungsi Obyektif: memaksimumkan atau • Waiting time minimum: waktu yang dibutuhkan proses
meminimumkan. dalam menunggu di ready queue seminimum mungkin.
Skema umum yang digunakan dalam strategi greedy adalah Sebuah penjadwalan dapat memiliki sifat preemptive, yakni
sebagai berikut: [2] penyerobotan paksa proses sedang berjalan oleh proses yang
baru muncul, atau secara non-preemptive, yakni proses yang
function greedy(C: himpunan_kandidat) → himpunan_solusi berjalan harus diselesaikan terlebih dahulu sebelum memproses
{ mengembalikan solusi dari persoalan optimasi dengan proses baru. CPU scheduling dapat dilakukan dalam beberapa
algoritma greedy } tempat, yaitu ketika proses dalam keadaan running menjadi
Deklarasi waiting (non-preemptive) atau ready (preemptive), ketika proses
x: kandidat dalam keadaan waiting menjadi ready (preemptive), dan ketika
S: himpunan_solusi proses diterminasi (non-preemptive). Context switching
merupakan tahap penggantian proses yang dikerjakan dengan
Algoritma proses lainnya yang akan dikerjakan. Terjadinya context
S {} { inisialisasi S kosong }
while ((not SOLUSI(S)) and (Q {})) do switching tentunya mengakibatkan overhead dalam membaca
x SELEKSI(C) { pilih sebuah kandidat dari C } process control block (PCB) dari proses yang akan dijalankan
C C – {i} { buang x dari C } dan menuliskan PCB dari proses yang sedang dikerjakan jika
if (LAYAK(S {x})) then { x memenuhi kelayakan } masih memiliki waktu burst.
S S {x} { masukkan x ke himp. solusi }
endif Beberapa contoh CPU scheduler adalah first-come first-
endwhile served (FCFS), round-robin (RR), dan shortest job first (SJF).
{ SOLUSI(S) or C = {} } Dalam kasus sistem real-time, terdapat pula rate monotonic
scheduling dan earliest deadline first (EDF). SJF dan CPU
if (SOLUSI(S)) then { solusi sudah lengkap }
return S scheduler untuk sistem real-time merupakan jenis priority
else scheduler, dimana penjadwalan dilakukan berdasarkan suatu
write(‘tidak ada solusi’) prioritas. Untuk SJF non-preemptive, proses diurutkan
endif berdasarkan prioritas prediksi CPU burst time selanjutnya
(biasanya prediksi dilakukan dengan exponential average), dan
B. Multiprogramming untuk SJF preemptive, juga disebut sebagai shortest remaining
Multiprogramming merupakan konsep yang menekankan time first (SRTF), proses diurutkan berdasarkan waktu CPU
penggunaan CPU semaksimal mungkin sehingga tidak burst yang tersisa. Sedangkan untuk rate-monotonic scheduling,
menganggur. Selama eksekusi proses, akan terjadi siklus proses diurutkan berdasarkan oleh inverse dari periodik, dengan
Makalah IF2211 Strategi Algoritma, Semester II Tahun 2021/2022
kata lain, periodik paling singkat mendapatkan prioritas paling
tinggi, dan periodik paling lama mendapatkan prioritas paling
rendah. Terakhir untuk EDF, proses diurutkan berdasarkan
deadline proses, sehingga tidak memerlukan periodik proses
layaknya rate monotonic scheduling.
(b)
Gambar II.2 (a) Multilevel queue scheduling dan (b) Multi-feedback
queue scheduling.
th
Sumber: S. Abraham, Operating System Concepts 10 ed., pp. 215-
216
III. APLIKASI STRATEGI GREEDY
A. Mapping Elemen Greedy
Dalam penjadwalan menggunakan shortest job first, terdapat
beberapa identifikasi elemen-elemen dari suatu masalah yang
dapat diselesaikan secara sistematis menggunakan strategi
greedy:
1) Himpunan Kandidat, C: merupakan beberapa proses
Gambar II.1 Contoh penjadwalan non-preemptive SJF dan yang tersedia dalam ready queue. Dalam kasus non-preemptive,
preemptive SJF (SRTF). setiap proses hanya dapat dijalankan sekali hingga selesai.
th Meski begitu, pada kasus preemptive, setiap proses mungkin
Sumber: S. Abraham, Operating System Concepts 10 ed., pp. 207- dijalankan beberapa kali hingga selesai. Proses biasanya
209 diidentifikasi dengan P , dengan subscript i merupakan indeks
i+1
proses pada ready queue dengan panjang n (P , P , …, P ).
Terdapat metode lain dalam menjadwalkan proses, yakni 1 2 n
multilevel queue scheduling yang membagi ready queue 2) Himpunan Solusi, S: merupakan himpunan yang
menjadi beberapa queue, dimana tiap queue memiliki algoritma berisikan anggota himpunan kandidat terurut berdasarkan
penjadwalan yang berbeda-beda (FCFS, RR, SJF, atau SRTF). proses mana yang dijalankan terlebih dahulu di CPU. Misalnya
Pada scheduling tersebut, queue dapat di-schedule kembali, untuk kasus non-preemptive, himpunan solusi S = {P , P , P }
biasanya dalam bentuk fixed priority scheduling dengan 2 1 3
prioritas absolut yang memungkinkan starvation. Untuk berarti CPU akan menjalankan proses kedua, dilanjutkan
mengatasi ini, queue dapat memiliki time-slice dengan cara dengan proses pertama, dan diakhiri dengan proses ketiga.
Untuk kasus preemptive, misalnya himpunan solusi S = {P , P ,
dibagi menjadi dua jenis: queue untuk proses background dan 3 1
P P , P }
untuk proses foreground dengan pembagian prioritas 20% dan 3, 2 1
80% terurut. 3) Fungsi Solusi: merupakan fungsi yang mengembalikan
benar jika semua proses pada ready queue telah dijalankan
Selain multilevel queue scheduling, juga terdapat multilevel (ready queue kosong), dan salah jika sebaliknya.
feedback queue scheduling dimana proses dapat dipindahkan 4) Fungsi Seleksi: merupakan strategi greedy yang
dalam beberapa queue. Hal ini mempermudahkan dalam digunakan dalam memilih proses pada ready queue (himpunan
mengimplementasikan aging untuk menghilangkan starvation. kandidat). Hasil dari fungsi seleksi adalah proses terpilih dari
Parameter yang digunakan dalam penjadwalan ini adalah himpunan kandidat yang kemudian menjadi anggota himpunan
banyaknya queue, algoritma yang dipakai untuk setiap queue, solusi. Pada shortest job first non-preemptive, strategi greedy
metode untuk upgrade/demote suatu proses, dan metode untuk yang digunakan adalah mengambil proses dengan next burst
menentukan queue yang dipakai untuk proses baru. time paling kecil.
5) Fungsi Kelayakan: merupakan fungsi yang
mengembalikan benar jika proses yang dipilih, sebelumnya
berada pada ready queue, dan salah jika sebaliknya. Secara
teknis, fungsi ini selalu mengembalikan nilai benar, sehingga
dalam skema algoritma SJF, hasil fungsi seleksi tidak perlu
diperiksa (langsung dimasukkan kedalam himpunan solusi).
6) Fungsi Objektif: terdiri dari beberapa kriteria yang harus
diminimumkan atau dimaksimumkan, seperti pada kriteria
CPU scheduling di teori dasar (memaksimumkan utilisasi CPU,
(a) memaksimumkan throughput, meminimumkan turnaround
Makalah IF2211 Strategi Algoritma, Semester II Tahun 2021/2022
time, meminimumkan waiting time, dan memnimumkan Setelah diurutkan, penjadwalan dapat dilakukan dengan tahapan
response time). berikut:
1) Inisialisasi himpunan solusi kosong.
B. Algoritma Penjadwalan SJF Non-preemptive 2) Inisialisasi t = waktu kedatangan proses pertama (paling
Untuk menjadwalkan proses dengan shortest job first awal muncul). Variabel ini digunakan untuk mencari proses
scheduling pada kasus non-preemptive, dapat dilakukan dengan yang tersedia hingga pada saat t.
tahapan berikut: 3) Selama ready queue belum kosong, lakukan tahapan
berikut:
1) Inisialisasi himpunan solusi kosong. a.) Cari proses yang memiliki next burst time terkecil
2) Selama ready queue belum kosong, lakukan tahapan dengan syarat waktu kedatangan sama atau lebih
berikut: kecil daripada t.
a.) Cari proses yang memiliki next burst time terkecil. b.) Hapus proses hasil tahapan 2.a. pada ready queue.
b.) Hapus proses hasil tahapan 2.a. pada ready queue. c.) Tambahkan proses hasil tahapan 2.a. ke dalam
c.) Tambahkan proses hasil tahapan 2.a. ke dalam himpunan solusi.
himpunan solusi. d.) Jika ready queue masih belum kosong, assign t
3) Kembalikan himpunan solusi. dengan nilai maksimum (mana yang paling besar)
antara t + next burst time dari proses hasil tahapan
Secara algoritmik, shortest job first scheduling untuk kasus 2.a dan arrival time proses pertama di ready queue
non-preemptive dapat dilakukan sebagai berikut: (setelah proses hasil tahapan 2.a. dihapus dari ready
queue).
function SJFNonPreemptive(Q: himpunan_kandidat) → 4) Kembalikan himpunan solusi.
himpunan_solusi Secara algoritmik, generalisasi shortest job first scheduling
{ mengembalikan urutan penjadwalan proses dengan untuk kasus non-preemptive, yakni waktu kedatangan proses
algoritma SJF untuk kasus non-preemptive } diketahui, dapat dilakukan sebagai berikut:
Deklarasi
S: himpunan_solusi function SJFNonPreemptive2(Q: himpunan_kandidat)
p: Process → himpunan_solusi
{- type Process { { mengembalikan urutan penjadwalan proses dengan
burst: integer algoritma SJF untuk kasus non-preemptive dan
} -} arrival time diketahui (proses dianggap datang
tidak bersamaan). Asumsi Q tidak kosong dan
Algoritma dimulai dari indeks 0. }
S {}
while (Q {}) do Deklarasi
p proses dengan next burst time S: himpunan_solusi
terkecil p: Process
Q Q – {i} {- type Process {
S S {i} arrival: integer,
endwhile burst: integer
return S } -}
t: integer
Analisis kompleksitas algoritma tersebut membutuhkan satu Algoritma
loop utama, yakni ketika Q tidak kosong, dan membutuhkan S {}
loop untuk mencari proses dengan next burst time terkecil. Jika t Q[0].arrival
diketahui panjang Q adalah N, maka total operasi perbandingan while (Q {}) do
yang dilakukan adalah (N+1) + (N) + (N-1) + … + 3 + 2 = p proses dengan next burst time terkecil
2 dan waktu arrival ≤ t
N(N+1)/2 + N = O(N ). Kompleksitas ini dapat dioptimasi Q Q – {i}
dengan mengurutkan proses dari next burst time paling kecil S S {i}
terlebih dahulu, sehingga untuk mencari proses dengan next if (Q {}) then
burst time terkecil cukup hanya mengambil elemen pertama dari t max(t + p.burst, Q[0].arrival)
ready queue yang telah terurut. Jika proses diurutkan terlebih endif
dahulu, maka total operasi perbandingan yang dilakukan adalah endwhile
sebanyak panjang elemen Q, yaitu O(N). return S
Secara umum, jika diketahui arrival time dari masing- Analisis kompleksitas algoritma tersebut mirip seperti
masing proses (proses datang tidak secara bersamaan), maka algoritma SJFNonPreemptive, dimana algoritma ini
proses terlebih dahulu diurutkan mulai dari kedatangan paling membutuhkan satu loop utama, yakni ketika Q tidak kosong, dan
cepat hingga paling lama (bisa menggunakan priority queue).
Makalah IF2211 Strategi Algoritma, Semester II Tahun 2021/2022
no reviews yet
Please Login to review.
