PENJADWALAN DISK

Penjadwalan FCFS

Bentuk algoritma penjadwalan disk yang paling sederhana adalah First Come First Served (FCFS). Sistem kerja dari algoritma ini adalah melayani permintaan yang lebih dulu datang di queue. Algoritma ini pada hakekatnya adil bagi permintaan M/K yang mengantri di queue karena penjadwalan ini melayani permintaan sesuai waktu tunggunya di queue. Tetapi yang menjadi kelemahan algoritma ini adalah bukan merupakan algoritma dengan layanan yang tercepat. Sebagai contoh, misalnya di queue disk terdapat antrian permintaan blok I/O di silinder

Gambar Penjadwalan FCFS

85, 35, 10, 90, 45, 80, 20, 50, 65 secara berurutan. Jika posisi head awal berada pada silinder 25, maka pertama kali head akan bergerak dari silinder 25 ke 85, lalu secara berurutan bergerak melayani permintaan di silinder 35, 10, 90, 45, 80, 20, 50, dan akhirnya ke silinder 65. sehingga total pergerakanhead-nya adalah 400 silinder.

Penjadwalan SSTF

Shortest-Seek-Time-First (SSTF) merupakan algoritma yang melayani permintaan berdasarkan waktu pencarian yang paling kecil dari posisi head terakhir. Sangat beralasan untuk melayani semua permintaan yang berada dekat dengan posisi head yang sebelumnya, sebelum menggerakan head lebih jauh untuk melayani permintaan yang lain.

Gambar Penjadwalan SSTF

Untuk contoh permintaan di queue kita, permintaan yang terdekat dari head awal (25) adalah permintaan silinder 20. maka silinder itu akan dilayani terlebih dahulu. Setelah head berada di silinder 20, maka permintaan yang terdekat adalah silinder 10. Secara berurutan permintaan silinder berikutnya yang dilayani adalah silinder 35, lalu 45, 50, 65, 80, 85, dan akhirnya silinder 90. dengan menggunakan algoritma ini, maka total pergerakan head-nya menjadi 95 silinder. Hasil yang didapat ternyata kurang dari seperempat jarak yang dihasilkan oleh penjadwalan FCFS

Penjadwalan SCAN dan C-SCAN

Pada algoritma SCAN, head bergerak ke silinder paling ujung dari disk. Setelah sampai disana maka headakan berbalik arah menuju silinder di ujung yang lainnya. Head akan melayani permintaan yang dilaluinya selama pergerakannya ini. Algoritma ini disebut juga sebagai Elevator Algorithm karena sistem kerjanya yang sama seperti yang digunakan elevator di sebuah gedung tinggi dalam melayani penggunanya. Elevator akan melayani pengguna yang akan menuju ke atas dahulu sampai lantai tertinggi, baru setelah itu dia berbalik arah menuju lantai terbawah sambil melayani penggunanya yang akan turun atau sebaliknya. Jika melihat analogi yang seperti itu maka dapat dikatakan head hanya melayani permintaan yang berada di depan arah pergerakannya. Jika ada permintaan yang berada di belakang arah geraknya, maka permintaan tersebut harus menunggu sampai head menuju silinder di salah satu disk, lalu berbalik arah untuk melayani permintaan tersebut.

Jika head sedang melayani permintaan silinder 25, dan arah pergerakan disk arm-nya sedang menuju ke silinder yang terkecil, maka permintaan berikutnya yang akan dilayani secara berurutan adalah 20 dan 10 lalu menuju ke silinder 0. Setelah sampai disini head akan berbalik arah menuju silinder yang terbesar yaitu silinder 99. Dan dalam pergerakannya itu secara berurutan head akan melayani permintaan 35, 45, 50, 65, 80, 85, dan 90. Sehingga total pergerakan head-nya adalah 115 silinder.

Salah satu behavior yang dimiliki oleh algoritma ini adalah, dia memiliki batas atas untuk total pergerakanhead-nya, yaitu 2 kali jumlah silinder yang dimiliki oleh disk. Jika dilihat dari cara kerjanya yang selalu menuju ke silinder terujung, maka dapat dilihat kelemahan dari algoritma ini yaitu ketidakefisienannya. Mengapa head harus bergerak ke silinder 0, padahal sudah tidak ada lagi permintaan yang lebih kecil dari silinder 10?. Bukankah akan lebih efisien jika head langsung berbalik arah setelah melayani permintaan silinder 10.

Penjadwalan SCAN

Kelemahan lain dari algoritma SCAN adalah dapat menyebabkan permintaan lama menunggu pada kondisi-kondisi tertentu. Misalkan penyebaran banyaknya permintaan yang ada di queue tidak sama. Permintaan yang berada di depan arah pergerakan head sedikit sedangkan yang berada di ujung satunya lebih banyak. Maka head akan melayani permintaan yang lebih sedikit (sesuai arah pergerakannya) dan berbalik arah jika sudah sampai di ujung disk. Jika kemudian muncul permintaan baru di dekat head yang terakhir, maka permintaan tersebut akan segera dilayani, sehingga permintaan yang lebih banyak yang berada di ujung silinder yang satunya akan semakin kelaparan. Jadi, mengapa head tidak melayani permintaan-permintaan yang lebih banyak itu terlebih dahulu? Karena adanya kelemahan inilah maka tercipta satu modifikasi dari algoritma SCAN, yaitu C-SCAN yang akan dibahas berikutnya.

Algoritma C-SCAN atau Circular SCAN merupakan hasil modifikasi dari SCAN untuk mengurangi kemungkinan banyak permintaan yang menunggu untuk dilayani. Perbedaan yang paling mendasar dari kedua algoritma ini adalah pada behavior saat pergerakan head yang berbalik arah setelah sampai di ujung disk. Pada C-SCAN, saat head sudah berada di silinder terujung disk, head akan berbalik arah dan bergerak secepatnya menuju silinder di ujung disk yang satu lagi, tanpa melayani permintaan yang dilalui dalam pergerakannya. Sedangkan pada SCAN akan tetap melayani permintaan saat bergerak berbalik arah menuju ujung yang lain.

Untuk contoh permintaan seperti SCAN, setelah head sampai di silinder 99 (permintaan silinder 35, 45, 50, 65, 80, 85 dan 90 telah dilayani secara berurutan), maka head akan secepatnya menuju silinder 0 tanpa melayani silinder 20 dan 10. Permintaan tersebut baru dilayani ketika head sudah berbalik arah lagi setelah mencapai silinder 0.

Penjadwalan C-SCAN

Pemilihan Algoritma Penjadwalan

Performa dari suatu sistem biasanya tidak terlalu bergantung pada algoritma penjadwalan yang kita pakai, karena yang paling mempengaruhi kinerja dari suatu sistem adalah jumlah dan tipe dari pemintaan. Dan tipe permintaan juga sangat dipengaruhi oleh metoda pengalokasian file, lokasi direktori dan indeks blok. Karena kompleksitas ini, sebaiknya algoritma penjadwalan disk diimplementasikan sebagai modul yang terpisah dari OS, sehingga algoritma tersebut bisa diganti dengan algoritma lain sesuai dengan jumlah dan tipe permintaan yang ada. Namun biasanya, OS memiliki algoritma default yang sering dipakai, yaitu SSTF.

Penerapan algoritma penjadwalan di atas berdasarkan hanya pada jarak pencarian saja. Tapi untuk diskmodern, selain jarak pencarian, rotation latency (waktu tunggu untuk sektor yang diinginkan untuk berrotasi di bawah disk head) juga sangat berpengaruh. Tetapi algoritma untuk mengurangi rotation latency tidak dapat diterapkan oleh OS, karena pada disk modern tidak dapat diketahui lokasi fisik dari blok-blok logikanya. Tapi masalah rotation latency ini dapat ditangani dengan mengimplementasikan algoritma penjadwalan disk pada hardware controller yang terdapat dalam disk drive, sehingga kalau hanya kinerja I/O yang diperhatikan, maka sistem operasi dapat menyerahkan algoritma penjadwalan diskpada perangkat keras itu sendiri.

Dari seluruh algoritma yang sudah kita bahas di atas, tidak ada algoritma yang tebaik untuk semua keadaan yang terjadi. SSTF lebih umum dan memiliki perilaku yang lazim kita temui. SCAN dan C-SCAN memperlihatkan kemampuan yang lebih baik bagi sistem yang menempatkan beban pekerjaan yang berat pada disk, karena algoritma tersebut memiliki msalah starvation yang paling sedikit. SSTF sering dipakai sebagai algoritma dasar dalam OS.