194x 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.