Algoritma Scheduling

Nama : Ni Kade Mega Handayani.
Nim : 1605551030.
Dosen : I Putu Agus Eka Pratama ST., MT.
Matakuliah : Network Operating System ( Pertemuan 4).
Universitas : Udayana, Fakultas Teknik, Program Studi Teknologi Informasi.

Algoritma Scheduling

Pada artikel scheduling sebelumnnya juga sudah dibahas mengenai algoritma penjadwalan pada sistem operasi, pada artikel akan dijelaskan algoritma penjadwalan lanjutan, ditambah dengan praktik uji coba tertait penjadwalan pada sistem operasi Linux. Sebelum kita mulai kita kan mengulas kembali apa itu algoritma?

“Algoritma adalah urutan logis langkah-langkah penyelesaian masalah. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.” (Rinaldi, 2001: 4).

Penjadwalan CPU menyangkut penentuan proses-proses yang ada dalam ready queue yang akan dialokasikan pada CPU. Penjadwalan berkaitan dengan permasalahan memutuskan proses mana yang akan dilaksanakan dalam suatu sistem. Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Algoritma penjadwalan berfungsi untuk menentukan proses manakah yang ada di ready queue yang akan dieksekusi oleh CPU. Terdapat beberapa algoritma penjadwalan CPU sebagai berikut.

Shortest Process Next (SPN)

Mengecek processing time (waktu pemrosesan/waktu eksekusi) setiap job, yang terpendek dimasukkan ke urutan antrian (queue) terdepan, yang terpanjang paling belakang. 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. Algoritma ini dapat dibagi menjadi dua bagian sebagai berikut.

Preemptive

Penjadwalan Preemptive mempunyai arti kemampuan sistem operasi untuk memberhentikan sementara proses yang sedang berjalan untuk memberi ruang kepada proses yang prioritasnya lebih tinggi. 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.

Non-preemptive

Penjadwalan NonPreemptive ialah salah satu jenis penjadwalan dimana sistemoperasi tidak pernah melakukan context switch dari proses yang sedang berjalan ke prosesyang lain. Dengan kata lain, proses yang sedang berjalan tidak bisa di-interupt CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser prosesyang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil. Ada beberapa kekurangan dari algoritma ini sebagai berikut.

Susahnya untuk memprediksi burst time (lama eksekusi) proses yang akan dieksekusi selanjutnya.
Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pulakarena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil

Feedback.

Fokusnya bukan pada waktu eksekusinya, tapi pada “berapa lama waktu yang dihabiskan untuk melakukan eksekusi”. job masuk ke sejumlah antrian (queue) dengan memfokuskan kepada berapa lama waktu yang dihabiskan dengan persamaan jika melebihi waktu = lepaskan (release) sampai semua proses selesai. bagaimana jika tidak selesai menggunakan solusi lain yaitu algoritma Round Robin (RR).

Gambar 1 Feedback Sceduling

Gambar 1 merupakan gambar alur feedback yang aka terjadi dalam penjadwalan, jika melebihi waktu maka processor akan melepaskan proses sampai selesai dan jika tidak selesai proses akan berlanjut dengan menggunakan solusi RR.

Highest Response Ratio Next (HRRN)

Penjadwalan Highest Response Ratio Next (HRRN) adalah disiplin non-preemptive. Ini dikembangkan oleh Brinch Hansen sebagai modifikasi dari SJF untuk mengurangi masalah kekurangan dalam proses. Di HRRN, pekerjaan berikutnya bukan dengan perkiraan waktu run time, tapi dengan rasio respon tertinggi yang didefinisikan sebagai berikut

Pilih job yang nilai Response Time-nya terbesar (R). Nilai R diperoleh dengan rumus (w+s)/s (di mana w = waiting time = waktu tunggu processor, s = service time)

Algoritma HRRN memiliki konsep dimana kita akan diberi daftar Linked Q, iterate melalui Q untuk menemukan rasio tertinggi dengan membandingkan setiap rasio dalam antrian. Setelah rasio elemen N lebih besar dari elemen M dengan rasio tertinggi ganti elemen M dengan elemen N sebagai elemen rasio tertinggi dalam daftar. Setelah akhir daftar tercapai dequeue elemen rasio tertinggi. Jika elemennya ada di awal daftar, dequeue dan tentukan daftar ke elemen berikutnya, kembalikan elemennya. Jika tetangga N diganti untuk mengidentifikasi satu sama lain sebagai tetangga mereka berikutnya dan sebelumnya, mengembalikan hasil N.

Shortest Remaining Time (SRT)

Shortest Remaining Time (SRT) adalah metode penjadwalan yang merupakan versi preemptive penjadwalan pekerjaan terpendek. Dalam algoritma penjadwalan ini, proses dengan jumlah waktu terkecil sampai selesai dipilih untuk dieksekusi. Karena proses eksekusi saat ini adalah yang paling singkat yang tersisa menurut definisi, Dan sejak saat itu seharusnya hanya mengurangi saat eksekusi berlangsung, proses akan selalu berjalan sampai selesai atau proses baru ditambahkan yang memerlukan jumlah waktu yang lebih kecil. Adapun cara kerja algoritma ini sebagai berikut.

Pilih yang waktu tunggunya lebih pendek → job yang masuk ke dalam queue memiliki waktu tunggu < job yang sedang diproses .SRT dengan job yang waktu tunggunya lama → menimbulkan starvation (kelaparan?) → waktu tunggu terlalu lama → mati.

Penjadwalan dan NOS

Berikut ini adalah beberapa peran penjadwalan (Schedulling) pada Network Operating System secara spesifk sebagai berikut.

Membantu penjadwalan dari semua service yang ada di dalam server.
Memanfaatkan cron, dapat menentukan penjadwalan terhadap suatu proses.
Dikaitkan dengan log dan cron, dapat membantu system administrator di dalam memperoleh data dan informasi mengenai sistem pada server (melalui bantuan sistem operasi.

Ex: user mana, kapan, berapa resource yang dihabiskan → terhadap process dan service yang ada

Praktik 1: Melihat Log Sistem

Praktik ini menggunakan sistem operasi linux ikuti langkah-langkah berikut.

Cek dan amati log di sistem operasi Linux anda sendiri (latihan untuk dapat mengamati log server di mesin remote via SSH nanti) :

1.Buka Terminal

2.Ketik nano varlog/syslog

3.Amati proses yang terjadi (catatan : jika menjadi root, jangan melakukan perubahan pada log) 4.Catatan : apabila nano belum terinstal, ketik sudo apt-get install nano

Praktek 2: Melihat Semua File Log

Praktik ini menggunakan sistem operasi linux ikuti langkah-langkah berikut.

Ketahui semua fle log yang ada di dalam sistem operasi Linux (bahan penting bagi Sysadmin Linux):

1.Buka Terminal

2.Ketik pwd, seharusnya ada di /home user-anda, jika belum ketik ~

3.Pindah ke lokasi /var/log dengan perintah cd /var/log

4.Lihat list semua fle yang ada dengan perintah ls -la (machine) atau ls -lah (human readable) 5.Amati setiap isi fle dengan perintah nano (namafle) atau apabila ada sub direktori, pindahlah ke sana lalu buka dengan nano

Daftar Pustaka

[1] Moh. Syahrul Ramadhan. 2013. “Implementasi Algoritma Round Robin Dan Fcfs (First Come First Serve) Pada Penjadwalan Proses Processor Tungga”. Tanjungpinang : Sekolah Tinggi Teknologi Indonesia.

[2] Abdur Rohman M. Algoritma Penjadwalan Proses Shortest Job First (SJF). Teknik Elektro : Universitas Brawijaya

[3] Wikipedia. Dikutip dari : https://en.wikipedia.org/wiki/Highest_response_ratio_next. (7 Maret 2018)

[4] Wikipedia. Dikutip dari : https://en.wikipedia.org/wiki/Shortest_remaining_time. (7 Maret 2018)
[5] I Putu Agus Eka Pratama. "PPT Network Operating System Pertemuan 4". 2018.

Algoritma Scheduling