PEMODELAN CPU SCHEDULING DENGAN ALGORITMA ROUND ROBIN

Download mempercepat penjadwalan proses karena dua atau lebih core pada processor dapat dimanfaatkan untuk mengeksekusi proses. Namun, meskipun proc...
1 downloads 558 Views 891KB Size
Download PDF
Love PNG Images
1

Pemodelan CPU Scheduling dengan Algoritma Round Robin sebagai Media Pembelajaran Mata Kuliah Sistem Operasi TAN HANDOKO DHARMA SAPUTRO Program Studi Teknik Informatika, S1, Fakultas Ilmu Komputer, Universitas Dian Nuswantoro, Jl. Nakula 1 no 5-11 Semarang 5013, Telp. (024) 3517261, URL : http://dinus.ac.id/, [email protected] Abstract CPU Scheduling is one of the essential material in the operating system courses. Scheduler’s duty is to perform a process/job turnover that is being executed, and it is used when two or more processes sent a signal that indicates the process’ arrival, simultaneously. Round Robin algorithm implements preemptive system that allows switching among processes. This research aims to make a learning medium in the form of a modeling of CPU Scheduling, that simulates Round Robin algorithm. In addition to help operating system courses’ lecturer in teaching scheduling matter, it is also expected that students can comprehend these algorithm’s stages and outcomes. Index Terms—CPU Scheduling, Operating System, Learning Medium, Round Robin, Simulation

I. PENDAHULUAN1 Media pembelajaran merupakan salah satu komponen penting yang membantu proses belajar mengajar. Salah satu media pembelajaran yang ideal dalam mengevaluasi keluaran CPU Scheduling yaitu melalui pemodelan/simulasi [1]. Penjadwalan proses merupakan komponen penting pada sistem operasi, yang bertujuan untuk memaksimalkan penggunaan CPU dan meningkatkan produktivitas komputer. Penjadwalan bertugas melakukan pergantian proses yang dieksekusi, dan digunakan saat dua atau lebih proses mengirimkan sinyal yang menandakan kedatangan proses tersebut secara simultan. Pada processor yang berinti tunggal, sistem operasi menentukan proses yang dieksekusi terlebih dulu sesuai prioritasnya. Pengaturan proses ini ditangani oleh scheduler, dengan menggunakan suatu algoritma penjadwalan [3]. Dalam mengatur antrian proses yang akan dieksekusi, algoritma penjadwalan dibagi menjadi dua kategori utama, yaitu non-preemptive dan preemptive. Pada sistem non-preemptive, proses tidak dapat digantikan atau disebut juga independen. Proses dieksekusi hingga selesai, untuk selanjutnya CPU akan mengeksekusi proses lain yang telah menunggu. Sedangkan pada sistem preemptive, proses dapat digantikan atau bersifat kooperatif [4]. Di sini, terjadi interupsi pada proses yang sedang berjalan pada CPU, ketika proses lain yang memiliki prioritas lebih tinggi datang. Proses dengan prioritas yang lebih rendah ini akan diselesaikan ketika proses yang mendapat optimasi

penjadwalan sebelumnya telah berakhir, tanpa melakukan intervensi terhadap interupsi proses. Cara ini digunakan ketika sebuah sistem membutuhkan pemodelan sistem yang terdiri dari sejumlah aktivitas dengan prioritas yang berbeda-beda [5]. Algoritma Round Robin dirancang untuk sistem time-sharing (Contoh : UNIX) dan menerapkan sistem preemptive, sehingga memungkinkan sistem untuk melakukan pergantian antar proses [5]. Komponen yang membedakan algoritma Round Robin dengan algoritma yang lain adalah adanya slot waktu yang disebut quantum. Ketika sebuah proses ditangani CPU, waktu eksekusi akan diatur sesuai waktu yang telah ditentukan pada quantum. Kemudian, setelah melewati quantum, CPU mengeksekusi proses berikut [6]. Dalam membuat pemodelan penjadwalan proses dengan algoritma Round Robin, penulis menggunakan 2 cara masukan proses. Cara pertama, aplikasi menerima masukan/input untuk setiap proses berupa waktu kedatangan dan lama proses dari pengguna. Cara kedua, masukan variabel dari setiap proses akan dihasilkan secara acak oleh aplikasi. Selain itu, pada simulasi ini, komputer diasumsikan menggunakan processor berinti tunggal untuk penyederhanaan pemodelan. Kemudian dilakukan simulasi dari pemodelan tersebut untuk menjalankan hasil proses dalam pemodelan dan mengambil keputusan. Simulasi ini merupakan tiruan dari pendekatan Algoritma Round Robin, sehingga mempunyai karakteristik serupa dengan proses yang sesungguhnya, dan dimodelkan ke dalam bentuk aplikasi [7]. II. METODE YANG DIUSULKAN Terdapat

beberapa

penelitian

yang

relevan

telah

dilakukan oleh peneliti sebelumnya. Penelitian yang dilakukan tahun 2011 oleh Hala ElAaraq, David Bauschlicher, dan Steven Bauschlicher dari Department of Mathematics and Computer Science, Stetson University, Florida dalam jurnal yang berjudul ‘Simulation-Based Comparison of Scheduling Techniques in Multiprogramming Operating Systems on Single and Multi-Core Processors” membahas tentang pemodelan CPU Scheduling menggunakan algoritma Round Robin, yang membandingkan penerapan manajemen proses antara processor berinti tunggal dan procesor multi-core. Penggunaan processor yang memiliki banyak core mempercepat penjadwalan proses karena dua atau lebih core pada processor dapat dimanfaatkan untuk mengeksekusi proses. Namun, meskipun processor berinti tunggal hanya dapat mengeksekusi satu proses pada satu waktu, hal ini akan memudahkan pemodelan untuk dipahami siswa [7]. Penelitian lainnya dilakukan pada tahun 1987 oleh James O. Henriksen yang berjudul “Alternatives for Modelling of Preemptive Scheduling”. Penelitiannya membahas kesulitan yang muncul ketika memodelkan Preemptive Scheduling. Pemodel harus melakukan penjadwalan ulang dan membatalkan eksekusi proses yang sedang berjalan melalui interupsi. Henriksen mengajukan gagasan mengenai pendekatan Optimistic Scheduling yang meminimalisir jeda yang muncul ketika terjadi pergantian proses [4]. William A. Shay dalam penelitian berjudul “A Project for Operating Systems Simulation” pada tahun 1986 membahas faktor-faktor yang perlu ada dalam membuat pemodelan CPU Scheduling, yaitu : jumlah proses, kebutuhan memori, waktu maksimal yang dibutuhkan suatu proses, penempatan proses pada suatu queue, dan pemanggilan proses pada awal queue jika terdapat ruang [6]. Wantah Satria dan Sri Handayaningsih pada tahun 2013 membuat penelitian berjudul “Pembuatan Media Pembelajaran untuk Proses Konversi pada Finite Automata Berbasis Multimedia” membahas keuntungan penggunaan metode pembelajaran dengan visual interaktif dapat membantu meningkatkan proses belajar dan mengajar dan meningkatkan hasil belajar siswa dan keaktifan siswa dalam mengembangkan potensi yang ada [2]. A. Algoritma Round Robin Salah satu algoritma penjadwalan yang banyak digunakan adalah Round Robin. Setiap proses mendapatkan slot waktu yang disebut dengan quantum, yang menginjinkan proses tersebut berjalan untuk selang waktu tertentu. Jika suatu proses tetap butuh berjalan hingga akhir quantum, CPU akan mendapatkan interupsi untuk menjalankan proses lainnya. Namun, ketika suatu proses telah diblok atau selesai dieksekusi sebelum quantum habis, CPU melakukan pergantian untuk proses lain. Scheduler selalu memeriksa queue berisi proses-proses yang siap dieksekusi. Ketika sebuah proses telah menyelesaikan suatu quantum, proses tersebut akan ditempatkan pada akhir queue [5].

B. Pseudo-code Algoritma Round Robin memiliki pseudo-code sebagai berikut : 1. Lakukan pengecekan kosong tidaknya queue yang digunakan. 2. Jika queue kosong, semua proses ditempatkan ke queue. 3. Process Scheduler memilih proses pertama. a) Atur timer sesuai waktu quantum b) Alokasi sumber daya CPU 4. Jika Burst Time masih tersisa ketika quantum habis : a) Proses dihentikan dan ditempatkan pada akhir queue (tail) b) Informasi Burst Time disimpan di PCB (Process Control Block). 5. Jika Burst Time < Waktu Quantum : a) Proses selesai : alokasi sumber daya dilepaskan dan proses dikembalikan ke user. b) Interupsi permintaan oleh I/O : informasi disimpan di PCB dan dihubungkan ke queue I/O 6. Ketika permintaan I/O telah terpenuhi : a) Proses akan ditempatkan di tail queue.

Gambar 1: Algoritma Round Robin C. Keluaran Ada tiga parameter yang dihasilkan dari perhitungan selama menjadwalkan proses, yaitu : 1. Turn Around Time : selisih antara waktu ketika sebuah proses memasuki sistem, dengan waktu sebuah proses selesai dieksekusi seluruhnya. 2. Waiting Time : Jumlah waktu yang dihabiskan sebuah proses ketika menunggu di queue. 3. Response Time : Selisih antara waktu kedatangan proses dengan waktu proses tersebut pertama kali dipanggil ke sistem untuk dieksekusi.

III. METODE PENELITIAN A. Metode Pengumpulan Data Teknik Pengumpulan Data yang digunakan dalam penelitian ini adalah :

3 1. Eksperimental Aplikasi pemodelan CPU Scheduling ini menggunakan teknik eksperimental, yang mengumpulkan data melalui pencatatan langsung dari percobaan/pengukuran, yaitu melalui masukan dari pengguna dan dihasilkan secara acak dari komputer. 2. Studi Pustaka Metode studi pustaka digunakan penulis dalam mencari informasi mengenai CPU Scheduling, sistem operasi, dan pemrograman Java, baik dari buku, jurnal, laporan penelitian, dan sumber elektronik dari internet. B. Arsitektur Sistem Penulis membuat arsitektur yang memberikan gambaran alur kerja aplikasi dari tahapan input, proses, hingga output, yang ditunjukkan oleh Gambar 2.

Gambar 2: Arsitektur Sistem C. Metode Pengembangan Sistem Perancangan sistem dalam penelitian ini akan menggunakan model Waterfall atau Classic Life Cycle, yang menggunakan pendekatan sekuensial untuk pembangunan atau pengembangan perangkat lunak melalui analisis, desain, implementasi, pengujian, dan dukungan. Berikut merupakan tahapan pengembangan sistem model Waterfall menurut Roger S. Pressman pada Gambar 3[8]:

Gambar 3: Model Waterfall IV. HASIL & PEMBAHASAN Aplikasi pemodelan CPU Scheduling akan diimplementasikan dan diberi nama SPARR (Simulasi Penjadwalan Algoritma Round Robin). A. Hasil 1. Class InputPanel Class InputPanel merupakan form tempat pengisian data proses, dengan beberapa method sebagai berikut : No Method Deskripsi 1. ambilNilai Method ini digunakan untuk mengambil nilai dari textfield pada form Parameter Statis 2. setData Method ini digunakan untuk mengambil nilai dari textfield pada form Data Proses 3. replace Method ini digunakan untuk melakukan pengecekan agar data yang diterima hanya berupa bilangan integer. 4. showGanttChart Method ini menampilkan pemodelan penjadwalan proses berdasarkan data proses dan parameter statis yang ada. Tabel 1: Method pada Class InputPanel 2. Class RRQueueAppletRand Class RRQueueAppletRand berisi pembentukan penjadwalan dengan masukan data yang dihasilkan secara acak, dengan beberapa method sebagai berikut : No Method Deskripsi 1. init Method ini digunakan untuk melakukan inisialisasi data dengan memanggil fungsi pada class RRQueueMethod 2. paint Method ini digunakan untuk melakukan penggambaran setiap node proses sesuai urutan eksekusi yang terjadi selama penjadwalan Tabel 2: Method pada Class RRQueueAppletRand

3. Class RRQueueAppletMF

Class RRQueueAppletRand berisi pembentukan penjadwalan dengan masukan data yang berasal oleh pengguna, dengan beberapa method sebagai berikut : No Method Deskripsi 1. init Method ini digunakan untuk melakukan inisialisasi data dengan memanggil fungsi pada class RRQueueMethod 2. paint Method ini digunakan untuk melakukan penggambaran setiap node proses sesuai urutan eksekusi yang terjadi selama penjadwalan Tabel 3: Method pada Class RRQueueAppletMF 4. Class RRQueueMethods Class RRQueueMethods berisi fungsi-fungsi yang digunakan dalam menjadwalkan proses, yaitu : No Method Deskripsi 1. addProcess-M Method ini digunakan untuk anual melakukan penambahan proses dari class Input Panel ke dalam array 2 dimensi p 2. addArrivedTo Method ini digunakan untuk Queue memasukkan proses yang sampai saat AT ke queue 3. addExecutedMethod ini digunakan untuk ToQueue mencari proses yang belum selesai (AT
untuk setiap proses dari P1 hingga P7. Persebaran data untuk Burst Time dapat dilihat pada Grafik 1.

Grafik 1: Grafik Persebaran Elastis Sempurna Kemudian dilakukan penjadwalan dari persebaran data di atas dengan Burst Time proses yang sama semua, yaitu 30ms, dan quantum yang digunakan yaitu 10ms (Grafik 2), 20ms (Grafik 3), dan 30ms (Grafik 4). Dari data tersebut didapatkan hasil berupa Waiting Time, Turn-Around Time, dan Response Time. Waiting Time setiap proses digambarkan dengan garis berwarna biru, Response Time dengan garis berwarna merah, dan Turn-Around Time dengan garis berwarna hijau.

Grafik 2: Grafik Detail Proses Elastis Sempurna (Q=10ms)

Grafik 3: Grafik Detail Proses Elastis Sempurna (Q=20ms)

Grafik 4: Grafik Detail Proses Elastis Sempurna (Q=30ms) Kemudian berdasarkan data ketiga parameter keluaran

5 di atas, didapatkan rata-rata, nilai maksimum, minimum, dan standar deviasi yang ditunjukkan pada Tabel 5 (Q=10ms), Tabel 6 (Q=20ms), dan Tabel 7 (Q=30ms). Standar deviasi merupakan rata-rata jarak penyimpangan titik-titik diukut dari nilai rata-rata data tersebut. Standar deviasi memiliki rumus perhitungan sebagai berikut :

Gambar 4: Rumus Standar Deviasi Nilai rata-rata, maksimum, minimum, dan standar deviasi digunakan untuk membandingkan hasil pengujian antara persebaran data yang menggunakan quantum 10ms, 20ms, dan 30ms. Dengan membandingkan tabel data keluaran tersebut akan dapat disimpulkan hubungan antara Waiting Time, Turn-Around Time, dan Response Time dengan besar/kecilnya quantum yang digunakan. Turn-Aro Waiting Response und Time Time (ms) Time (ms) (ms) Max 174 54 204 Min 120 0 150 Standard 19.44 19.44 19.44 Deviation Average 147 27 177 Tabel 5: Tabel Data Keluaran Elastis Sempurna (Q=10ms)

Max

Waiting Time (ms)

Response Time (ms)

174

114

Turn-Aro und Time (ms) 204

120

0 150 Min Standard 19.44 41.04 19.44 Deviation 147 57 177 Average Tabel 6: Tabel Data Keluaran Elastis Sempurna (Q=20ms)

Max

Waiting Time (ms)

Response Time (ms)

174

114

Turn-Aro und Time (ms) 204

120 0 150 Min Standard 19.44 41.04 19.44 Deviation 147 57 177 Average Tabel 7: Tabel Data Keluaran Elastis Sempurna (Q=30ms) Dengan menggunakan aplikasi SPARR, didapatkan pula Gantt Chart dari kasus dengan Q=10ms (Gambar 5), Q=20ms (Gambar 6), dan Q=30ms (Gambar 7).

Gambar 5: Penjadwalan Elastis Sempurna dengan SPARR (Q=10ms)

Gambar 6: Penjadwalan Elastis Sempurna dengan SPARR (Q=20ms)

Gambar 7: Penjadwalan Elastis Sempurna dengan SPARR (Q=30ms) 2. Persebaran Elastis Naik Pengujian dilakukan menggunakan persebaran data yang bersifat elastis dan naik, dengan interval setiap proses 10ms dari P1 sampai P7. Persebaran data untuk Burst Time dapat dilihat pada Grafik 5.

Grafik 5: Grafik Persebaran Elastis Naik Kemudian dilakukan penjadwalan dari persebaran data di atas dengan quantum yang digunakan yaitu 10ms (Grafik 6), 20ms (Grafik 7), dan 30ms (Grafik 8). Dari data tersebut didapatkan hasil berupa Waiting Time, Turn-Around Time, dan Response Time. Waiting Time setiap proses digambarkan dengan garis berwarna biru, Response Time dengan garis berwarna merah, dan Turn-Around Time dengan garis berwarna hijau.

Grafik 6: Grafik Detail Proses Elastis Naik (Q=10ms)

Max

Time (ms)

Time (ms)

148

132

und Time (ms) 180

0 0 16 Min Standard 59.99 51.12 68.22 Deviation 93.86 63 120.14 Average Tabel 10: Tabel Data Keluaran Elastis Naik (Q=30ms) Dengan menggunakan aplikasi SPARR, didapatkan pula Gantt Chart dari kasus dengan Q=10ms (Gambar 5), Q=20ms (Gambar 6), dan Q=30ms (Gambar 10). Grafik 7: Grafik Detail Proses Elastis Naik (Q=20ms) Gambar 8: Penjadwalan Elastis Naik dengan SPARR (Q=10ms)

Gambar 9: Penjadwalan Elastis Naik dengan SPARR (Q=20ms)

Grafik 8: Grafik Detail Proses Elastis Naik (Q=30ms) Kemudian berdasarkan data ketiga parameter keluaran di atas, didapatkan rata-rata, nilai maksimum, minimum, dan standar deviasi yang ditunjukkan pada Tabel 8 (Q=10ms), Tabel 9 (Q=20ms), dan Tabel 10 (Q=30ms).

Max

Waiting Time (ms)

Response Time (ms)

132

54

Turn-Aro und Time (ms) 181

60 0 76 Min Standard 28.78 19.44 40.84 Deviation 100.43 27 126.71 Average Tabel 8: Tabel Data Keluaran Elastis Naik (Q=10ms)

Max

Waiting Time (ms)

Response Time (ms)

132

102

Turn-Aro und Time (ms) 181

0 0 16 Min Standard 52.23 37.69 62.78 Deviation 80.43 50.14 106.71 Average Tabel 9: Tabel Data Keluaran Elastis Naik (Q=20ms)

Waiting

Response

Turn-Aro

Gambar 10: Penjadwalan Elastis Naik dengan SPARR (Q=30ms) 3. Persebaran Normal Pengujian dilakukan menggunakan persebaran data yang bersifat normal. Persebaran data untuk Burst Time dapat dilihat pada Grafik 9.

Grafik 9: Grafik Persebaran Normal Kemudian dilakukan penjadwalan dari persebaran data di atas, dengan quantum yang digunakan yaitu 10ms (Grafik 10), 20ms (Grafik 11), dan 30ms (Grafik 12). Dari data tersebut didapatkan hasil berupa Waiting Time setiap proses yang digambarkan dengan garis berwarna biru, Response Time dengan garis berwarna merah, dan Turn-Around Time dengan garis berwarna hijau.

7

Max

Waiting Time (ms)

Response Time (ms)

132

102

Turn-Aro und Time (ms) 181

0 0 16 Min Standard 52.23 37.69 62.78 Deviation 80.43 50.14 106.71 Average Tabel 12: Tabel Data Keluaran Normal (Q=20ms) Grafik 10: Grafik Detail Proses Normal (Q=10ms) Max

Waiting Time (ms)

Response Time (ms)

148

132

Turn-Aro und Time (ms) 180

0 0 16 Min Standard 59.99 51.12 68.22 Deviation 93.86 63 120.14 Average Tabel 13: Tabel Data Keluaran Normal (Q=30ms) Dengan menggunakan aplikasi SPARR, didapatkan pula Gantt Chart dari kasus dengan Q=10ms (Gambar 11), Q=20ms (Gambar 12), dan Q=30ms (Gambar 13).

Grafik 11: Grafik Detail Proses Normal (Q=20ms) Gambar 11: Penjadwalan Elastis Naik dengan SPARR (Q=10ms)

Gambar 12: Penjadwalan Elastis Naik dengan SPARR (Q=20ms)

Grafik 12: Grafik Detail Proses Normal (Q=30ms) Kemudian berdasarkan data ketiga parameter keluaran di atas, didapatkan rata-rata, nilai maksimum, minimum, dan standar deviasi yang ditunjukkan pada Tabel 11 (Q=10ms), Tabel 12 (Q=20ms), dan Tabel 13 (Q=30ms). Turn-Aro Waiting Response und Time Time (ms) Time (ms) (ms) 132 54 181 Max Min

60

0

76

SD

28.78

19.44

40.84

100.43 27 126.71 Average Tabel 11: Tabel Data Keluaran Normal (Q=10ms)

Gambar 13: Penjadwalan Elastis Naik dengan SPARR (Q=30ms) C. Pembahasan Dari ketiga hasil pengujian di atas, dengan membandingkan setiap macam pengujian yang dijadwalkan dengan penggunaan quantum yang berbeda-beda, dapat diambil kesimpulan bahwa panjang quantum berpengaruh pada hasil penjadwalan. Semakin kecil nilai quantum yang diberikan, proses menjadi lebih sering dieksekusi. Sedangkan jika nilai quantum sama dengan/lebih besar dari Burst Time proses, maka penjadwalan akan berubah menjadi penjadwalan dengan algoritma FCFS, yang menjadwalkan suatu proses hingga selesai, kemudian baru dilanjutkan dengan proses selanjutnya, sesuai dengan prioritas/waktu kedatangan.

Response Time berbanding lurus dengan kenaikan nilai quantum, yaitu semakin besar quantum, maka semakin besar pula rata-rata Response Time seluruh proses. Dari sini dapat disimpulkan, Response Time cenderung memiliki persebaran data yang bersifat elastis dan naik. Sedangkan kurva Waiting Time dan Turn-Around Time yang dihasilkan memiliki kecenderungan berbentuk sama dengan kurva persebaran data Burst Time proses yang dijadwalkan. V. PENUTUP CPU Scheduling merupakan salah satu dasar penting dalam sistem operasi. Dalam penelitian ini, dilakukan pengujian dengan menggunakan berbagai quantum yang berbeda untuk melihat efek yang terjadi terhadap parameter keluaran algoritma Round Robin. Diharapkan siswa dapat memahami materi penjadwalan CPU di mata kuliah Sistem Operasi. REFERENCES [1] L. S. Tang, "A Cpu Scheduling Simulation from Structured Programming to Object-Oriented Design," SIGCSE '92 Proceedings of the twenty-third SIGCSE technical symposium on Computer science education , vol. 24, no. 1, p. 1, 1992. [2] P. B. Hansen, Operating System Principles, New Jersey: Prentice Hall, 2001. [3] A. Silberschatz, P. B. Galvin and G. Gagne, Operating System Concepts, Massachusetts: John Wiley & Sons, Inc, 2009. [4] W. A. Shay, "A Project for Operating Systems Simulation," SIGCSE '86 Proceedings of the seventeenth SIGCSE technical symposium on Computer science education , vol. 18, no. 1, pp. 1-2, 1986. [5] H. ElAaraq, D. Bauschlicher and S. Bauschlicher, "Simulation-based comparison of scheduling techniques in multiprogramming operating systems on single and multi-core processors," Journal of Computing Sciences in Colleges, vol. 27, no. 2, pp. 166-168, 2011. [6] W. Satria and S. Handayaningsih, "Pembuatan Media Pembelajaran untuk Proses Konversi pada Finite Automata Berbasis Multimedia," Jurnal Sarana Teknik Informatika, vol. 1, no. 1, pp. 1-2, 2013. [7] J. O. Henriksen, "Alternatives for Modelling Preemptive Scheduling," Proceedings of 1987 Winter Simulation, p. 1, 1987.