KONSEP
DASAR
Pada
sistem multiprogramming, selalu terjadi beberapa proses yang berjalan dalam
suatu waktu. Sedangkan pada uniprogramming hal ini tidak akan terjadi, karena
hanya ada satu proses yang berjalan pada saat tertentu. Sistem multiprogramming
diperlukan untuk memaksimalkan utilitas CPU.
Pada saat
proses dijalankan terjadi siklus eksekusi CPU dan menunggu I/O yang disebut
dengan siklus CPU-I/O burst. Eksekusi proses dimulai dengan CPU burst dan
dilanjutkan dengan I/O burst, diikuti CPU burst lain, kemudian I/O burst lain
dan seterusnya
Pada saat
suatu proses dieksekusi, terdapat banyak CPU burst yang pendek dan terdapat
sedikit CPU burst yang panjang. Program I/O bound biasanya sangat pendek CPU
burst nya, sedangkan program CPU bound kemungkinan CPU burst nya sangat lama.
Oleh karena itu sangat penting pemilihan algoritma penjadwalan CPU.
CPU Scheduler
Pada saat
CPU menganggur, maka sistem operasi harus menyeleksi proses-proses yang ada di
memori utama (ready queue) untuk dieksekusi dan mengalokasikan CPU untuk salah
satu dari proses tersebut. Seleksi semacam ini disebut dengan shortterm
scheduler (CPU scheduler). Keputusan untuk menjadwalkan CPU mengikuti 4
keadaan:
·
Apabila proses berpindah dari keadaan running
ke waiting
·
Apabila proses berpindah dari keadaan running
ke ready
·
Apabila proses berpindah dari keadaan waiting
ke ready
·
Apabila proses berhenti
Apabila
model penjadwalan yang dipilih menggunakan keadaan 1 dan 4, maka penjadwakan
semacam ini disebut non-peemptive. Sebaliknya, jika 2 dan 3, maka disebut
dengan preemptive. Pada non-preemptive, jika suatu proses sedang menggunakan
CPU, maka proses tersebut akan tetap membawa CPU sampai proses tersebut
melepaskannya (berhenti atau dalam keadaan waiting). Preemptive scheduling
memiliki kelemahan, yaitu biaya yang dibutuhkan sangat tinggi. Antara lain,
harus selalu dilakukan perbaikan data. Hal ini terjadi jika suatu proses
ditinggalkan dan akan segera dikerjakan proses yang lain.
Dispatcher
Dispatcher
adalah suatu modul yang akan memberikan kontrol pada CPU terhadap penyeleksian
proses yang dilakukan selama short-term scheduling. Fungsi-fungsi yang
terkandung di dalam-nya meliputi:
·
Switching context
·
Switching ke user-mode
· Melompat ke lokasi tertentu pada user program
untuk memulai program.
Waktu yang
diperlukan oleh dispatcher untuk menghentikan suatu proses dan memulai untuk menjalankan
proses yang lainnya disebut dispatch latency.
KRITERIA PENJADWALAN
Algoritma
penjadwalan CPU yang berbeda akan memiliki perbedaan properti. Ada beberapa kriteria
yang digunakan untuk melakukan pembandingan algoritma penjadwalan CPU, antara
lain:
·
CPU utilization. Diharapkan agar CPU selalu dalam
keadaan sibuk. Utilitas CPU dinyatakan dalam bentuk prosen yaitu 0-100%. Namun
dalam kenyataannya hanya berkisar antara 40-90%.
·
Throughput. Adalah banyaknya proses yang selesai
dikerjakan dalam satu satuan waktu.
·
Turnaround time. Banyaknya waktu yang diperlukan
untuk mengeksekusi proses, dari mulai menunggu untuk meminta tempat di memori
utama, menunggu di ready queue, eksekusi oleh CPU, dan mengerjakan I/O.
·
Waiting time. Waktu yang diperlukan oleh suatu
proses untuk menunggu di ready queue. Waiting time ini tidak mempengaruhi
eksekusi proses dan penggunaan I/O.
·
Response time. Waktu yang dibutuhkan oleh
suatu proses dari minta dilayani hingga ada respon pertama yang menanggapi
permintaan tersebut.
·
Fairness. Meyakinkan bahwa tiap-tiap proses
akan mendapatkan pembagian waktu penggunaan CPU secara terbuka (fair).
First-Come First-Served Scheduling (FCFS)
Proses
yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani
terlebih dahulu. Misalnya terdapat tiga proses yang dapat dengan urutan P1, P2,
dan P3 dengan waktu CPU-burst dalam milidetik yang diberikan sebagai berikut :
Gant Chart
dengan penjadwalan FCFS adalah sebagai berikut :
Waktu
tunggu untuk P1 adalah 0, P2 adalah 24 dan P3 adalah 27 sehingga rata-rata waktu
tunggu adalah (0 + 24 + 27)/3 = 17 milidetik. Sedangkan apabila proses dating dengan
urutan P2, P3, dan P1, hasil penjadwalan CPU dapat dilihat pada gant chart berikut
:
Waktu
tunggu sekarang untuk P1 adalah 6, P2 adalah 0 dan P3 adalah 3 sehingga
ratarata waktu tunggu adalah (6 + 0 + 3)/3 = 3 milidetik. Pada penjadwalan CPU dimungkinkan
terjadi Convoy effect apabila proses yang pendek berada pada proses yang
panjang.
Algoritma
FCFS termasuk non-preemptive. karena, sekali CPU dialokasikan pada suatu
proses, maka proses tersebut tetap akan memakai CPU sampai proses tersebut
melepaskannya, yaitu jika proses tersebut berhenti atau meminta I/O.
Shortest Job First Scheduler (SJF)
Pada
penjadwalan SJF, proses yang memiliki CPU burst paling kecil dilayani terlebih
dahulu. Terdapat dua skema :
·
Non preemptive, bila CPU diberikan pada
proses, maka tidak bisa ditunda sampai CPU burst selesai.
·
Preemptive, jika proses baru datang dengan
panjang CPU burst lebih pendek dari sisa waktu proses yang saat itu sedang
dieksekusi, proses ini ditunda dan diganti dengan proses baru. Skema ini
disebut dengan Shortest-Remaining- Time-First (SRTF).
SJF adalah
algoritma penjadwalan yang optimal dengan rata-rata waktu tunggu yang minimal.
Misalnya terdapat empat proses dengan panjang CPU burst dalam milidetik.
CPU burst
berikutnya biasanya diprediksi sebagai suatu rata-rata eksponensial yang
ditentukan dari CPU burst sebelumnya atau “Exponential Average”.
τ n+1 = panjang CPU burst yang
diperkirakan
τ 0 = panjang CPU burst
sebelumnya
τ n = panjang CPU burst yang
ke-n (yang sedang berlangsung)
α = ukuran pembanding antara τ n+1
dengan τ n (0 sampai 1)
Priority Scheduling
Algoritma
SJF adalah suatu kasus khusus dari penjadwalan berprioritas. CPU dialokasikan
untuk proses yang memiliki prioritas paling tinggi. Jika beberapa proses
memiliki prioritas yang sama, maka akan digunakan algoritma FCFS. Penjadwalan
berprioritas terdiri dari dua skema yaitu non preemptive dan preemptive. Jika
ada proses P1 yang datang pada saat P0 sedang berjalan, maka akan dilihat
prioritas P1. Seandainya prioritas P1 lebih besar dibanding dengan prioritas P0,
maka pada non-preemptive, algoritma tetap akan menyelesaikan P0 sampai habis CPU
burst-nya, dan meletakkan P1 pada posisi head queue. Sedangkan pada preemptive,
P0 akan dihentikan dulu, dan CPU ganti dialokasikan untuk P1. Misalnya terdapat
lima proses P1, P2, P3, P4 dan P5 yang datang secara berurutan dengan CPU burst
dalam milidetik.
Penjadwalan
proses dengan algoritma priority dapat dilihat pada gant chart berikut :
Waktu
tunggu untuk P1 adalah 6, P2 adalah 0, P3 adalah 16, P4 adalah 18 dan P5 adalah
1 sehingga rata-rata waktu tunggu adalah (6 + 0 +16 + 18 + 1)/5 = 8.2
milidetik.
Round-Robin Scheduling
Konsep
dasar dari algoritma ini adalah dengan menggunakan time-sharing. Pada dasarnya
algoritma ini sama dengan FCFS, hanya saja bersifat preemptive. Setiap proses
mendapatkan waktu CPU yang disebut dengan waktu quantum (quantum time) untuk
membatasi waktu proses, biasanya 1-100 milidetik. Setelah waktu habis, proses ditunda
dan ditambahkan pada ready queue. Jika suatu proses memiliki CPU burst lebih kecil
dibandingkan dengan waktu quantum, maka proses tersebut akan melepaskan CPU
jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses
selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar
dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan
sementara jika sudah mencapai waktu quantum, dan selanjutnya mengantri kembali
pada posisi ekor dari ready queue, CPU kemudian menjalankan proses berikutnya. Jika
terdapat n proses pada ready queue dan waktu quantum q, maka setiap proses
mendapatkan 1/n dari waktu CPU paling banyak q unit waktu pada sekali penjadwalan
CPU. Tidak ada proses yang menunggu lebih dari (n-1)q unit waktu. Performansi
algoritma round robin dapat dijelaskan sebagai berikut, jika q besar, maka yang
digunakan adalah algoritma FIFO, tetapi jika q kecil maka sering terjadi
context switch. Misalkan ada 3 proses: P1, P2, dan P3 yang meminta pelayanan
CPU dengan quantum-time sebesar 4 milidetik
Penjadwalan
proses dengan algoritma round robin dapat dilihat pada gant chart berikut :
Waktu
tunggu untuk P1 adalah 6, P2 adalah 4, dan P3 adalah 7 sehingga rata-rata waktu
tunggu adalah (6 + 4 + 7)/3 = 5.66 milidetik. Algoritma Round-Robin ini di satu
sisi memiliki keuntungan, yaitu adanya keseragaman waktu. Namun di sisi lain,
algoritma ini akan terlalu sering melakukan switching. Semakin besar
quantum-timenya maka switching yang terjadi akan semakin sedikit.
Waktu
turnaround juga tergantung ukuran waktu quantum. Secara umum, rata-rata waktu
turnaround dapat ditingkatkan jika banyak proses menyelesaikan CPU burst
berikutnya sebagai satu waktu quantum. Sebagai contoh, terdapat tiga proses
masing-masing 10 unit waktu dan waktu quantum 1 unit waktu, rata-rata waktu
turnaround adalah 29. Jika waktu quantum 10, sebaliknya, rata-rata waktu
turnaround turun menjadi 20.
Multilevel Queue Scheduling
Algoritma ini membagi beberapa antrian yang
akan diberi prioritas berdasarkan tingkatan. Tingkatan lebih tinggi menjadi
prioritas utama.
eady queue dibagi menjadi queue yang terpisah
yaitu foreground
(interaktif) dan background (batch). Setiap queue mempunyai algoritmanya masing - masing. Foreground
queue memakai algoritma penjadwalan round robin sedangkan background
queue memakai algoritma penjadwalan FCFS.
Multilevel Feedback Queue Scheduling
Algoritma ini mengizinkan proses untuk pindah
antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan
dipindahkan ke antrian yang lebih rendah. Hal ini menguntungkan proses
interaksi karena proses ini hanya memakai waktu CPU yang sedikit. Demikian pula
dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan
tingkatannya. Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil,
dengan begitu CPU akan terutilisasi penuh dan I/O dapat terus sibuk. Semakin
rendah tingkatannya, panjang CPU burst proses juga semakin besar.
Multilevel
feedback queue akan diterapkan
dengan mendefinisikan terlebih dahulu parameter-parameternya, yaitu:
- Jumlah antrian.
- Algoritma internal tiap queue.
- Aturan sebuah proses naik ke antrian yang lebih tinggi.
- Aturan sebuah proses turun ke antrian yang lebih rendah.
- Antrian yang akan dimasuki tiap
proses yang baru datang.
Multiple-Processor Scheduling
Pada prosesor jamak, penjadwalannya jauh lebih
kompleks daripada prosesor tunggal karena pada prosesor jamak memungkinkan
adanya load
sharing antar prosesor yang menyebabkan penjadwalan menjadi lebih
kompleks namun kemampuan sistem tersebut menjadi lebih baik.
Approaches to Multiple-Processor Scheduling
Pendekatan
pertama untuk penjadwalan prosesor jamak adalah penjadwalan asymmetric
multiprocessing atau bisa disebut juga sebagai penjadwalan master/slave.
Dimana pada metode ini hanya satu prosesor(master) yang menangani semua keputusan penjadwalan,
pemrosesan I/O, dan aktivitas sistem lainnya dan prosesor lainnya (slave)
hanya mengeksekusi proses. Metode ini sederhana karena hanya satu prosesor yang
mengakses struktur data sistem dan juga mengurangi data sharing.
Penjadwalan
SMP (Symmetric
multiprocessing) adalah pendekatan kedua untuk penjadwalan prosesor
jamak. Dimana setiap prosesor menjadwalkan dirinya sendiri (self
scheduling). Semua proses mungkin berada pada ready queue yang
biasa, atau mungkin setiap prosesor memiliki ready queue tersendiri.
Bagaimanapun juga, penjadwalan terlaksana dengan menjadwalkan setiap prosesor
untuk memeriksa antrian ready dan memilih suatu proses untuk dieksekusi.
Processor Affinity
Afinitas prosesor
(processor affinity) adalah pencegahan migrasi proses antar prosesor
sehingga menjaga proses tersebut tetap berjalan di prosesor yang sama.
Ada dua jenis
afinitas prosesor, yakni:
- Soft affinity yang memungkinkan proses berpindah dari satu prosesor ke prosesor yang lain, dan
- Hard affinity yang menjamin bahwa suatu proses akan berjalan pada prosesor yang sama dan tidak berpindah. Contoh sistem yang menyediakan system calls yang mendukung hard affinity adalah Linux.
Load Balancing
Load balancing adalah usaha untuk menjaga workload terdistribusi
sama rata untuk semua prosesor dalam sistem SMP. Load balancing hanya
perlu untuk dilakukan pada sistem dimana setiap prosesor memiliki antrian
tersendiri(private queue) untuk proses-proses yang akan dipilih untuk
dieksekusi.
Ada dua jenis load
balancing, yakni:
- Push migration, pada kondisi ini ada suatu task spesifik yang secara berkala memeriksa load dari tiap-tiap prosesor. Jika terdapat ketidakseimbangan, maka dilakukan perataan dengan memindahkan (pushing) proses dari yang kelebihan muatan ke prosesor yang idle atau yang memiliki muatan lebih sedikit.
- Pull migration, kondisi ini terjadi saat prosesor yang idle menarik (pulling) proses yang sedang menunggu dari prosesor yang sibuk.
Operating System Examples
Solaris
Solaris menggunakan penjadwalan berdasarkan
prioritas dimana yang mempunyai prioritas yang lebih tinggi dijalankan terlebih
dahulu.
Terbagi dalam 4 kelas penjadwalan yang berbeda:
•
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.
•
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).
•
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.
•
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.
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.
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.
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.
Windows XP
scheduling
Windows XP menggunakan algoritma, prioritas
penjadwalan quantum-based yang berbasis reemptive priority scheduling. Terdapat
6 kemungkinan state dari sebuah thread, yaitu ready, standby, running, waiting,
transition dan terminated. Ready state yaitu thread yang siap untuk dieksekusi.
Thread yang berada pada ready state dengan prioritas tertinggi akan berpindah
menjadi standby state. Ketika thread dieksekusi, thread tersebut berada pada
running state. State waiting dimasuki thread ketika thread menunggu untuk
dijadwalkan ulang. Ketika thread akan dieksekusi tetapi sumber daya yang
diperlukan belum tersedia, maka thread tersebut akan berpindah pada state
transition. Terminated state dimasuki thread ketika thread selesai dieksekusi.
Linux
Scheduling
Dua masalah dengan penjadwal UNIX tradisional
adalah bahwa hal itu tidak memberikan dukungan yang cukup untuk sistem SMP dan
bahwa hal itu tidak cocok pada sistem. Dengan Versi 2,5, scheduler itu
dirombak, dan kernel sekarang menyediakan algoritma penjadwalan yang berjalan
dalam waktu konstan-dikenal sebagai O (1)-terlepas dari jumlah tugas pada
sistem. The scheduler baru juga memberikan peningkatandukungan untuk SMP,
termasuk afinitas prosesor dan load balancing, serta memberikan keadilan dan
dukungan untuk tugas-tugas interaktif.
The scheduler Linux adalah, preemptive
prioritas berbasis algoritma dengan dua rentang prioritas yang terpisah:
berbagai real-time 0-99 dan nilai yang bagus antara 100 sampai 140. Kedua
rentang peta ke dalam skema prioritas global dimana nilai-nilai numerik yang
lebih rendah menunjukkan prioritas yang lebih tinggi.
Tidak seperti penjadwal untuk sistem lain,
termasuk Solaris dan Windows XP, Linux memberikan prioritas lebih tinggi lagi
tugas kuanta waktu dan lebih rendah-prioritas tugas quanta waktu yang lebih
singkat. Hubungan antara prioritas dan waktu-slice panjang ditunjukkan pada
Sebuah tugas runnable dianggap memenuhi syarat
untuk eksekusi pada CPU asalkan memiliki waktu tersisa dalam irisan waktu.
Ketika tugas telah habis irisan waktu, itu
dianggap kadaluarsa dan tidak memenuhi syarat untuk eksekusi lagi sampai semua
tugas-tugas lain juga telah habis quanta waktu mereka.
Kernel menyimpan daftar semua tugas runnable
dalam struktur data runqueue. Karena dukungan untuk SMP, setiap prosesor
mempertahankan runqueue sendiri dan jadwal dirinya sendiri secara mandiri.
Runqueue masing-masing berisi dua array prioritas: aktif dan kadaluarsa. Array
aktif berisi semua tugas dengan waktu yang tersisa di iris waktu mereka, dan
array berakhir berisi semua tugas kedaluwarsa. Masing-masing array prioritas
berisi daftar tugas diindeks sesuai dengan prioritas The scheduler memilih
tugas dengan prioritas tertinggi dari array aktif untuk eksekusi pada CPU. Pada
mesin multiprosesor, ini berarti bahwa setiap prosesor adalah penjadwalan
tertinggi-prioritas tugas dari struktur runqueue sendiri. Ketika semua tugas
telah kehabisan waktu mereka irisan (yaitu, array aktif kosong), dua array
prioritas dipertukarkan, array berakhir menjadi array aktif, dan sebaliknya.
Linux mengimplementasikan real-time
penjadwalan seperti yang didefinisikan oleh POSIX.1b. Real-time tugas
ditugaskan prioritas statis. Semua tugas-tugas lain memiliki prioritas dinamis
yang didasarkan pada nilai-nilai mereka bagus plus atau minus nilai 5.
Interaktivitas dari tugas menentukan apakah
nilai 5 akan ditambahkan atau dikurangi dari nilai yang bagus. Interaktivitas
Sebuah tugas yang ditentukan oleh berapa lama telah tidur sambil menunggu I /
O. Tugas yang lebih interaktif biasanya memiliki waktu tidur lebih lama dan
karena itu lebih mungkin untuk memiliki penyesuaian lebih dekat ke -5, sebagai
scheduler tugas interaktif. Hasil dari penyesuaian tersebut akan menjadi
prioritas yang lebih tinggi untuk tugas-tugas. Sebaliknya, tugas dengan waktu
tidur pendek sering lebih CPU-terikat dan dengan demikian akan memiliki
prioritas mereka diturunkan.
Prioritas dinamis Sebuah tugas ini dihitung
ulang ketika tugas yang telah habis waktu kuantum dan akan dipindahkan ke array
expired. Dengan demikian, ketika dua array dipertukarkan,
semua tugas dalam array aktif baru telah ditetapkan prioritas baru dan irisan
waktu yang sesuai.
thanks gan sudah share
BalasHapusisolasi double tape