Evaluasi dan Ilustrasi

April 12, 2011 at 8:22 am (Sistem Operasi)

Pendahuluan

Seperti yang sudah dijelaskan di bab sebelumnya, terdapat banyak algoritma penjadwalan CPU. Pertanyaan yang muncul selanjutnya adalah bagaimana memilih algoritma penjadwal untuk suatu sistem. Untuk memilihnya, pertama kita harus mengetahui kriteria algoritma penjadwal yang baik. Kriteria ini bisa mencakup hal berikut:

  • Memaksimalkan penggunaan CPU dengan batasan response time maksimum adalah satu detik.
  • Memaksimalkan throughput sehingga rata-rata turnaround time berbanding lurus dengan total waktu eksekusi.

Dengan mempertimbangkan kriteria itu, kita bisa mengevaluasi algoritma penjadwalan dengan berbagai metode-metode yang akan dijelaskan dalam bab ini.

Deterministic Modelling

Salah satu metode evaluasi adalah evaluasi analitik, yaitu menggunakan algoritma yang sudah ada dan workload dari sistem untuk menghasilkan suatu formula yang menggambarkan performance suatu algoritma. Salah satu tipe evaluasi analitik ini adalah deterministic modelling. Model ini menggunakan workload yang sudah diketahui dan melihat performance algoritma dalam menjalankan workload tersebut. Untuk dapat memahami deterministic modelling ini, kita gunakan sebuah contoh. Misalkan lima proses datang pada waktu yang bersamaan dengan urutan sebagai berikut:

Tabel 16.1. Contoh

Proses Burst Time
P1 10
P2 29
P3 3
P4 7
P5 12

Dengan deterministic modelling kita membandingkan performance algoritma dalam mengekseskusi proses-proses di atas. Eksekusi proses dengan algoritma First Come First Serve (FCFS), Shortest Job First (SJF), dan Round Robin (RR) digambarkan pada Gambar 16.1, “Perbandingan dengan Deterministic Modelling”.

Dari average waiting time-nya, dapat dilihat bahwa untuk kasus ini algoritma SJF memberikan hasil yang paling baik, yaitu average waiting time-nya paling kecil.

Deterministic modelling ini memungkinkan kita membandingkan performance algoritma dengan cepat dan sederhana karena kita bisa melihat perbandingannya langsung dari angka yang dihasilkan. Namun, model ini hanya berlaku untuk kasus tertentu dimana kita bisa mengetahui angka pasti dari workload yang akan dijadikan input dalam perhitungan. Model ini bisa digunakan untuk memilih algoritma terbaik dimana kita menjalankan program yang sama berulang-ulang dan kebutuhan untuk menjalankan program dapat diukur.

Gambar 16.1. Perbandingan dengan Deterministic Modelling

Perbandingan dengan Deterministic Modelling

Queueing Modelling

Pada kenyataanya, program atau proses yang dijalankan pada suatu sistem bervariasi dari hari ke hari. Untuk itu, kita tidak bisa menggunakan deterministic modelling untuk membandingkan performance algoritma dengan menentukan kebutuhan proses atau waktu eksekusinya. Yang bisa ditentukan adalah distribusi CPU dan I/O burst. Distribusi ini bisa diukur, lalu kemudian diperkirakan atau diestimasikan, sehingga bisa didapatkan formula yang menjelaskan probabilitas CPU burst. Kita juga bisa menentukan distribusi waktu kedatangan proses dalam sistem. Dua distribusi tersebut memungkinkan kita menghitung throughput rata-rata, penggunaan CPU, waiting time, dan lain-lain.

Salah satu pemanfaatan metode di atas dengan menggunakan queueing-network analysis dimana kita menganggap sistem komputer sebagai jaringan server-server. Setiap server memiliki antrian proses-proses. CPU adalah server yang memiliki ready queue, yaitu antrian proses-proses yang menunggu untuk diekseskusi dan sistem M/K adalah server yang memiliki device queue, yaitu antrian M/K device yang menunggu untuk dilayani.

Misalnya diketahui n sebagai panjang antrian rata-rata (banyaknya proses yang berada dalam antrian), W sebagai waktu tungggu rata-rata yang dialami proses dalam antrian, dan sebagai kecepatan rata-rata kedatangan proses baru ke antrian (banyaknya proses baru yang datang per detik). Pada sistem yang berada dalam ” steady state“, jumlah proses yang meninggalkan antrian pasti sama dengan yang proses yang datang. Dengan demikian, kita bisa gunakan persamaan yang dikenal dengan Formula Little berikut ini:

n= x W

n: panjang antrian

W: waktu tunggu rata-rata dalam antrian

: kecepatan rata-rata kedatangan proses baru

Formula Little ini valid untuk semua algoritma penjadwalan dan distribusi kedatangan proses. Sebagai contoh, jika kita mengetahui rata-rata 7 proses datang setiap detik, dan normalnya ada 14 proses dalam antrian, maka kita bisa menghitung waktu tunggu rata-rata proses dalam antrian(W) sebagai berikut: = 7 proses/detik n= 14 proses maka W= n/ = 14/7= 2 detik per proses.

Queueing analysis ini bisa digunakan untuk membandingkan algoritma penjadwalan, tapi memiliki beberapa keterbatasan. Jenis algoritma distribusi yang bisa ditangani model ini terbatas dan pada algoritma atau distribusi yang kompleks, akan sulit untuk menggunakan model ini. Karena perhitungannya akan sangat rumit dan tidak realistis. Selain itu, kita juga perlu menggunakan asumsi yang mungkin saja tidak akurat. Model ini seringkali hanya memberi perkiraan dan keakuratan hasil perhitungannya dipertanyakan.

Simulasi

Untuk mendapatkan hasil yang lebih akurat dari evaluasi algoritma penjadwalan, bisa digunakan simulasi. Simulasi ini dibuat dengan memprogram sebuah model dari sistem komputer. Simulatornya memiliki variabel yang merepresentasikan clock. Jika nilai dari variabel ini bertambah, simulator mengubah status dari sistem untuk menggambarkan aktivitas proses, device, dan penjadwal. Selama simulatornya berjalan, data-data statistik mengenai performance algoritma dikumpulkan dan dicetak.

Untuk menjalakan simulator ini diperlukan data yang merepresentasikan aktivitas sistem seperti proses, CPU burst, dan lain-lain. Biasanya data ini dibuat dengan random-number generator dengan memanfaatkan distribusi probabilitas seperti distribusi Poisson, eksponensial, dan lain-lain. Tapi menjalankan simulasi dengan data yang dihasilkan dari distribusi ini bisa saja tidak akurat, karena dari distribusi hanya diketahui frekuensi atau berapa kali suatu kejadian muncul. Distribusi ini tidak memperhatikan urutan kejadiannya. Untuk mengatasi masalah itu, digunakan trace tapes .

Cara membuat trace tapes adalah dengan mengamati dan merekam aktivitas sistem yang sesungguhnya. Dengan ini, kita bisa menjalankan simulator dengan urutan data dari events yang sebenarnya. Cara ini cukup efektif dan bisa memberikan hasil yang akurat.

Berikut ini adalah ilustrasi evaluasi algoritma penjadwalan dengan simulasi:

Gambar 16.2. Evaluasi Algoritma Penjadwalan dengan Simulasi

Evaluasi Algoritma Penjadwalan dengan Simulasi


Urutan eksekusi proses direkam dengan trace tapes, kemudian simulator menjalankan simulasi penjadwalan proses-proses tersebut dengan berbagai macam algoritma penjadwalan. Simulasi ini kemudian menghasilkan catatan mengenai performance dari setiap algoritma penjadwalan tersebut. Dengan membandingkan catatan performance itu, pengguna bisa mencari algoritma penjadwalan yang paling baik.

Meskipun memberikan hasil yang akurat, simulasi ini bisa saja memerlukan waktu yang besar dan biaya yang mahal. Trace tapes juga membutuhkan ruang penyimpanan yang besar di memori. Mendesain, memprogram, dan men- debug simulator juga adalah sebuah pekerjaan yang besar.

Implementasi

Simulasi bahkan memiliki keakuratan yang terbatas. Satu-satunya cara yang paling akurat untuk mengevaluasi algoritma penjadwalan adalah dengan langsung membuat programnya, masukkan ke dalam sistem operasi, dan lihat bagaimana ia bekerja. Dengan ini, algoritma yang akan dievaluasi ditempatkan dan dijalankan di sistem yang sebenarnya.

Implementasi ini membutuhkan biaya yang besar. Selain mahal, kesulitannya antara lain:

  • Memprogram algoritmanya.
  • Memodifikasi sistem operasi agar bisa mendukung algoritma tersebut.
  • Reaksi pengguna akan sistem operasi yang terus berubah secara konstan karena pengguna tidak peduli dengan pengembangan sistem operasi. Pengguna hanya ingin proses yang dijalankannya dapat diselesaikan dengan cepat.
  • Environment dimana program dijalankan akan berubah.

Perubahan environment ini bukan hanya perubahan wajar sebagaimana yang terjadi jika program baru ditulis dan tipe-tipe masalah berubah, tapi juga perubahan performance dari penjadwal. Pengguna (dalam hal ini programmer) bisa memodifikasi programnya untuk memanipulasi penjadwalan.

Misalnya sebuah komputer dikembangkan dengan pengklasifikasian proses menjadi interaktif dan non-interaktif berdasarkan jumlah terminal M/K yang digunakan proses. Jika dalam interval satu detik suatu proses tidak menggunakan terminal M/K untuk masukan atau keluaran, maka proses itu dikategorikan proses non-interaktif dan dipindahkan ke antrian yang prioritasnya lebih rendah. Dengan sistem seperti ini, bisa saja seorang programmer memodifikasi programnya -yang bukan program interaktif- untuk menulis karakter acak ke terminal dalam interval kurang dari satu detik. Dengan demikian, programnya akan dianggap program interaktif dan mendapat prioritas tinggi, meskipun sebenarnya output yang diberikan ke terminal tidak memiliki arti.

Bagaimanapun, algoritma penjadwalan yang paling fleksibel adalah yang bisa berganti-ganti atau diatur sesuai kebutuhan. Misalnya komputer yang memiliki kebutuhan grafis tinggi akan memiliki algoritma penjadwalan yang berbeda dengan komputer server. Beberapa sistem operasi seperti UNIX memungkinkan system manager untuk mengatur penjadwalan berdasarkan konfigurasi sistem tertentu.

Ilustrasi: Linux

Mulai di versi 2.5, Kernel linux dapat berjalan di berbagai algoritma penjadwalan UNIX tradisional. Dua masalah dengan penjadwal UNIX tradisional adalah tidak disediakannya dukungan yang cukup untuk SMP (symmetric multiprocessor) sistem dan tidak diperhitungkan dengan baik jumlah tasks pada sistem yang berkembang. Dalam versi 2.5, penjadwal memeriksa dengan teliti hal tersebut, dan sekarang kernel juga menyajikan algoritma penjadwalan yang dapat run dalam waktu yang konstan tidak tergantung dari jumlah tasks dalam sistem. Penjadwal yang baru juga menyediakan peningkatan dukungan untuk SMP, termasuk processor affinity dan load balancing, sebaik dalam menyediakan keadilan dan dukungan terhadap interactive tasks.

Penjadwal linux adalah preemptive, algoritmanya berdasarkan prioritas dengan dua range prioritas yang terpisah: real-time range dari 0-99 dan nice value berkisar dari 100-140. Dua range ini dipetakan menjadi global priority scheme dimana nilai yang lebih rendah memiliki prioritas yang lebih tinggi. Tidak seperti penjadwal yang lain, Linux menetapkan prioritas yang lebih tinggi memiliki waktu kuantum yang lebih panjang dan prioritas yang lebih rendah memiliki waktu kuantum yang lebih pendek.

Linux mengimplementasikan real time scheduling seperti yang didefinisikan oleh POSIX 1.b: First Come First Served dan Round Robin. Sistem waktu nyata( real time)diberikan untuk task yang prioritasnya tetap. Sedangkan task yang lainnya memiliki prioritas yang dinamis berdasakan nice values ditambah atau dikurangi dengan 5. Interaktifitas sebuah task menentukan apakah nilai 5 tersebut akan ditambah atau dikurangi dari nice value. Task yang lebih interaktif mempunyai ciri khas memiliki sleep times yang lebih lama dan karena itu maka ditambah dengan -5, karena penjadwal lebih menyukai interactive task. Hasil dari pendekatan ini akan membuat prioritas untuk interactive task lebih tinggi. Sebaliknya, task dengan sleep time yang lebih pendek biasanya lebih CPU-bound jadi prioritasnya lebih rendah.

Gambar 16.3. Hubungan antara prioritas dan waktu kuantum

Hubungan antara prioritas dan waktu kuantum

Task yang berjalan memenuhi syarat untuk dieksekusi oleh CPU selama time slice-nya masih ada. Ketika sebuah task telah kehabisan time slice-nya, maka task tersebut akan expired dan tidak memenuhi syarat untuk dieksekusi lagi sampai semua task yang lain sudah habis waktu kuantumnya. Kernel mengatur daftar semua task yang berjalan di runqueue data structure. Karena dukungan Linux untuk SMP, setiap prossesor mengatur runqueue mereka sendiri dan penjadwalan yang bebas. Setiap runqueue terdiri dari dua array prioritas – active dan expired. Active array terdiri dari semua task yang mempunyai sisa waktu time slices, dan expired array terdiri dari task yang telah berakhir. Setiap array prioritas ini memiliki daftar task indexed berdasakan prioritasnya. Penjadwal memilih task dengan prioritas paling tinggi di active array untuk dieksekusi dalam CPU. Di mesin multiprossesor, ini berarti setiap prossesor menjadwalkan prioritas paling tinggi dalam runqueue structure masing-masing. Ketika semua task telah habis time slices-nya (dimana, active array-nya sudah kosong), dua array prioritas bertukar; expired array menjadi active array, dan sebaliknya.

Gambar 16.4. Daftar task indexed berdasarkan prioritas

Daftar task indexed berdasarkan prioritas

Penghitungan ulang dari task yang memiliki prioritas yang dinamis berlangsung ketika task telah menyelesaikan waktu kuantumnya dan akan dipindahkan ke expired array. Jadi, ketika ada dua larik ( array) ditukar, semua task di array aktif yang baru ditentukan prioritasnya yang baru dan disesuaikan juga time slices-nya.

Ilustrasi: Solaris

Solaris menggunakan penjadwalan berdasarkan prioritas dimana yang mempunyai prioritas yang lebih tinggi dijalankan terlebih dahulu. Informasi tentang penjadwalan kernel thread dapat dilihat dengan ps -elcL.

Kernel Solaris adalah fully preemtible, artinya semua thread, termasuk thread yang mendukung aktifitas kernel itu sendiri dapat ditunda untuk menjalankan thread dengan prioritas yang lebih tinggi.

Gambar 16.5. Penjadwalan Solaris

Penjadwalan Solaris

Solaris mengenal 170 prioritas yang berbeda, 0-169. Terbagi dalam 4 kelas penjadwalan yang berbeda:

  1. Real time (RT).  Thread di kelas RT memiliki prioritas yang tetap dengan waktu kuantum yang tetap juga. Thread ini memiliki prioritas yang tinggi berkisar antara 100-159. Hal inilah yang membuat proses waktu nyata memiliki response time yang cepat. Proses waktu nyata akan dijalankan sebelum proses-proses dari kelas yang lain dijalankan sehingga dapat menghentikan proses di system class. Pada umumnya, hanya sedikit proses yang merupakan real time class.
  2. System (SYS). Solaris menggunakan system class untuk menjalankan kernel proses, seperti penjadwalan dan paging daemon. Threads di kelas ini adalah “bound” threads, berarti bahwa mereka akan dijalankan sampai mereka di blok atau prosesnya sudah selesai. Prioritas untuk SYS threads berkisar 60-99. Sekali dibangun, prioritas dari sistem proses tidak dapat dirubah. System class dialokasikan untuk kernel use( user proses berjalan di kernel mode bukan di system class).
  3. Time Sharing (TS).  Time sharing class merupakan default class untuk proses dan kernel thread yang bersesuaian. Time slices masing-masing proses dibagi berdasarkan prioritasnya. Dalam hal ini, prioritas berbanding terbalik dengan time slices-nya. Untuk proses yang prioritasnya tinggi mempunyai time-slices yang pendek, dan sebaliknya proses dengan prioritas yang rendah mempunyai time slices yang lebih panjang. Besar prioritasnya berada antara 0-59. Proses yang interaktif berada di prioritas yang tinggi sedangkan proses CPU-bound mempunyai prioritas yang rendah. Aturan penjadwalan seperti ini memberikan response time yang baik untuk proses yang interaktif, dan troughput yang baik untuk proses CPU-bound.
  4. Interactive (IA). Kelas Interaktif menggunakan aturan yang sama dengan aturan dengan kelas kelas time sharing, tetapi kelas ini memberikan prioritas yang tinggi untuk aplikasi jendela ( windowing application) sehingga menghasilkan performance yang lebih baik. Seperti TS, range IA berkisar 0-59.
    Tabel 16.2. Solaris dispatch table for interactive and time sharing threads


    Priority Time quantum Time quantum expired return from sleep
    0 200 0 50
    5 200 0 50
    10 160 0 51
    15 160 5 51
    20 120 10 52
    25 120 15 52
    30 80 20 53
    35 80 25 54
    40 40 30 55
    45 40 35 56
    50 40 40 58
    55 40 45 58
    59 20 49 59

    Keterangan:

    • Priority: prioritas berdasarkan kelas untuk time sharing dan interactive class. Nomor yang lebih tinggi menunjukkan prioritas yang lebih tinggi.
    • Time quantum: waktu kuantum untuk setiap prioritas. Dapat diketahui bahwa fungsi waktu kuantum berbanding terbalik dengan prioritasnya.
    • Time quantum expired: Prioritas terbaru untuk thread yang telah habis time slices-nya tanpa diblok. Dapat dilihat dari tabel bahwa thread yang CPU-bound tetap mempunyai prioritas yang rendah.
    • Return from sleep: Prioritas thread yang kembali dari sleeping(misalnya menunggu dari M/K). Seperti yang terlihat dari tabel ketika M/K berada di waiting thread, prioritasnya berada antara 50-59, hal ini menyebabkan response time yang baik untuk proses yang interaktif.
  5. Fixed Priority (FX).  Thread di kelas fixed priority memiliki range prioritas (0-59) yang sama seperti di time-sharing class; tetapi, prioritas mereka tidak akan berubah.
  6. Fair Share Scheduler (FSS). Thread yang diatur oleh FSS dijadwalkan berdasar pembagian sumber daya dari CPU yang tersedia dan dialokasikan untuk himpunan proses-proses (yang dikenal sebagai project). FS juga berkisar 0-59. FSS and FX baru mulai diimplementasikan di Solaris 9.

Seperti yang telah diketahui, setiap kelas penjadwalan mempunyai himpunan dari prioritas-prioritas. Tetapi, penjadwal mengubah class-specific priorities menjadi global priorities kemudian memilih thread dengan prioritas paling tinggi untuk dijalankan. Thread yang dipilih tersebut jalan di CPU sampai thread tersebut (1) di- block, (2) habis time slices-nya, atau (3) dihentikan oleh thread dengan prioritas yang lebih tinggi. Jika ada beberapa thread dengan prioritas yang sama, penjadwal akan menggunakan Round-Robin queue. Seperti yang pernah dijelaskan sebelumnya, Solaris terdahulu menggunakan many-to-many model tetapi solaris 9 berubah menggunakan one-to-one model.

Rangkuman

Cara mengevaluasi algoritma:

  • Deterministic Modelling: menggunakan perhitungan matematika berdasarkan workload sistem. Sederhana, namun pemakaiannya terbatas.
  • Queueing Model: menggunakan perhitungan matematika berdasarkan waktu antrian dan waktu kedatangan proses.
  • Simulasi: membuat model sistem komputer. Cara ini mahal dan membutuhkan kerja besar dalam memprogram.
  • Implementasi: langsung mengimplementasi pada sistem sebenarnya. Paling efektif, namun mahal.
Tabel 16.3. Scheduling Priorities in Linux


Priorities Scheduling class
0-99 System Threads, Real time (SCHED_FIFO, SCHED_RR)
100-139 User priorities (SCHED_NORMAL)
Tabel 16.4. Scheduling Priorities in Solaris


Priorities Scheduling class
0-59 Time Shared, Interactive, Fixed, Fair Share Scheduler
60-99 System Class
100-159 Real-Time (note real-time higher than system threads)
160-169 Low level Interrupts


%d bloggers like this: