PENJADWALAN
PROSES(SISTEM OPERASI)
Tujuan
Penjadwalan Proses
Tujuan dari multiprogramming adalah untuk memiliki sejumlah
proses yang berjalan pada sepanjang waktu, untuk memaksimalkan penggunaan
CPU. Tujuan dari pembagian waktu adalah
untuk mengganti CPU diantara proses-proses yang begitu sering sehingga pengguna
dapat berinteraksi dengan setiap program sambil CPU bekerja. Untuk sistem uniprosesor, tidak akan ada
lebih dari satu proses berjalan. Jika ada proses yang lebih dari itu, yang
lainnya akan harus menunggu sampai CPU bebas dan dapat dijadualkan kembali
Deskripsi
Penjadwalan Proses
Penjadwalan proses
Merupakan kumpulan
kebijaksanaan dan mekanisme di sistem operasi yang berkaitan dengan urutan
kerja yang dilakukan sistem komputer.
Sedangkan proses sendiri merupakan unit kerja terkecil yang secara
individu memiliki sumberdaya atau unit pemilikan sumberdaya.
Tugas
Penjadwalan
• Memutuskan proses yang harus berjalan
• Memutuskan kapan dan selama berapa lama
proses itu berjalan
Konsep Dasar Penjadwalan Proses.
Preemptive & Non-Preemtive Scheduling.
NON-PREEMPTIVE algoritma didesain agar setelah proses yang
sedang berjalan memasuki negara (adalah proses diperbolehkan), tidak dihapus
dari prosesor sampai selesai dengan waktu layanan (secara eksplisit atau hasil
prosesor).
Bila CPU telah dialokasikan (schedule) ke suatu proses,
maka proses tersebut dapat menggunakan CPU tersebut sampai proses tersebut
block karena request I/O atau terminate. context_switch () dipanggil hanya
ketika proses dihentikan atau blok.
Preemptive: algoritma Preemptive digerakkan oleh konsep
diprioritaskan komputasi. Jika proses saat ini menggunakan prosesor baru dan
proses dengan prioritas yang lebih tinggi masuk, yang siap daftar, proses pada
prosesor harus dihapus dan kembali ke daftar siap sampai sekali lagi adalah
yang tertinggi-prioritas dalam proses sistem.selain scheduling dapat dilakukan
pada dua event di atas, maka scheduling dapat terjadi jika proses sedang run
(interrupt karena waktu quantum / time slice habis) dan diganti proses lain, atau
status dari wait menjadi ready (misalkan proses prioritas lebih tinggi, dapat
langsung mendapatkan jatah CPU setelah selesai I/O request).
Dispatcher
Adalah Sebuah operator penerbangan (juga dikenal sebagai
operator pesawat, maskapai operator, pengikut penerbangan atau petugas operasi
penerbangan) membantu dalam jalur perencanaan penerbangan, dengan arah angin
akun dan kecepatan, cuaca, badai, kinerja pesawat dan pemuatan, kondisi
mendarat di tempat tujuan atau mengubah bandara, dan kondisi lain. Dispatcher
menyediakan penerbangan layanan berikut dan menyarankan pilot jika kondisi atau
jalur berubah. Mereka biasanya bekerja di operasi atau kontrol pusat maskapai.
Di Amerika Serikat dan Kanada, operator penerbangan berbagi tanggung jawab hukum
dengan komandan pesawat (tanggung jawab bersama sistem pengiriman).
Algoritma
Penjadwalan.
FCFS (First Come First Server)
Scheduling.
FCFS - kadang-kadang
pertama-in, pertama-dilayani dan pertama datang, pertama pilihan adalah kebijakan layanan dimana
permintaan dari pelanggan atau klien yang
dalam urutan bahwa mereka tiba, tanpa lainnya bias atau
preferensiFestival duduk (juga dikenal sebagai tempat duduk umum dan stadion
tempat duduk) adalah tempat duduk dilakukan secara FCFS. (Lihat The Who bencana
konser untuk rincian pada Desember 1979 bencana yang melibatkan "festival
tempat duduk" di konser The Who di Cincinnati, Ohio di Riverfront
Coliseum.) Praktek ini juga umum di antara beberapa penerbangan yang tidak
mengizinkan pemesanan kursi baik di maju atau di check-in. Maskapai penerbangan
ini memungkinkan penumpang untuk naik dalam kelompok kecil berdasarkan pesanan
mereka check-in dan duduk di kursi di pesawat mereka ingin apa pun. Atas dasar
pertama datang, pertama dilayani, sebelumnya mereka check-in, sebelumnya mereka
naik pesawat untuk mendapatkan kursi yang mereka inginkan. Penumpang yang
berurutan (pada datang pertama, pertama dilayani) ditugaskan ke salah satu dari
beberapa "kelompok asrama." Para penumpang kemudian naik ke pesawat
agar kelompok.
SJF
(Shortest Job First) Scheduling
Adalah hortest-Job-First (SJF) adalah disiplin
non-preemptive dimana pekerjaan tunggu (atau proses) dengan terkecil
diperkirakan selesai run-time-to-dijalankan berikutnya. Dengan kata lain,
ketika CPU tersedia, ditugaskan untuk proses yang memiliki CPU burst terkecil
berikutnya.
Penjadwalan SJF terutama cocok untuk
pekerjaan batch yang kali run dikenal di muka. Karena algoritma penjadwalan SJF
memberikan waktu rata-rata minimum untuk himpunan proses, mungkin optimal.
Algoritma SJF nikmat pekerjaan singkat (atau prosesor) dengan mengorbankan
orang-orang lagi.
Masalah yang jelas dengan skema SJF
adalah bahwa hal itu membutuhkan pengetahuan yang tepat dari berapa lama
pekerjaan atau proses akan berjalan, dan informasi ini biasanya tidak tersedia. Algoritma SJF terbaik dapat Anda lakukan
adalah untuk mengandalkan perkiraan pengguna dari menjalankan kali.
Priority Scheduling.
Ide dasarnya adalah sederhana: setiap proses diberikan
prioritas, dan prioritas diperbolehkan untuk menjalankan. Proses yang
sama-Prioritas dijadwalkan agar FCFS. Terpendek-Job-First (SJF) algoritma
adalah kasus khusus dari algoritma penjadwalan prioritas umum. Sebuah algoritma
SJF hanyalah sebuah algoritma prioritas mana prioritasnya adalah kebalikan dari
(diprediksi) berikutnya CPU burst. Artinya, semakin lama meledak CPU, semakin
rendah prioritas dan sebaliknya. Prioritas dapat didefinisikan baik secara
internal maupun eksternal. Prioritas yang ditetapkan secara internal
menggunakan beberapa jumlah terukur atau kualitas untuk menghitung prioritas
dari sebuah proses.
Contoh prioritas
Internal
Batas waktu.
Persyaratan memori.
Persyaratan berkas,
misalnya, jumlah file yang terbuka.
CPU Vs persyaratan I / O.
Prioritas yang
ditetapkan secara eksternal ditetapkan dengan kriteria yang eksternal untuk
sistem operasi seperti :
1.
Pentingnya proses.
Jenis atau jumlah dana yang dibayar
untuk penggunaan komputer.
Departemen mensponsori pekerjaan.
2.
Politik.
Penjadwalan prioritas
dapat berupa preemptive atau non preemptive
Algoritma prioritas preemptive akan
preemptive CPU jika prioritas dari proses yang baru tiba lebih tinggi dari
prioritas dari proses yang sedang berjalan.
algoritma prioritas
non-preemptive hanya akan menempatkan proses baru di kepala antrian siap.
Masalah utama dengan penjadwalan prioritas adalah pemblokiran terbatas atau
kelaparan. Sebuah solusi untuk masalah penyumbatan terbatas dari proses
prioritas rendah adalah penuaan.
Round
Robin Scheduling.
round robin adalah algoritma penjadwalan yang digunakan
oleh CPU selama eksekusi dari proses. Round robin dirancang khusus untuk sistem
pembagian waktu. Hal ini mirip dengan yang pertama datang pertama melayani algoritma
penjadwalan tapi preemption adalah fungsionalitas tambahan untuk beralih antara
proses.
Sebuah unit kecil waktu
juga dikenal sebagai irisan waktu atau quantum diatur / ditentukan. Antrian
siap bekerja seperti antrian melingkar .Semua proses dalam algoritma ini
disimpan dalam antrian melingkar juga dikenal sebagai antrian siap. Setiap
proses baru ditambahkan ke ekor siap / antrian melingkar.
Dengan menggunakan
algoritma ini, CPU memastikan, irisan waktu (setiap nomor alam) yang ditugaskan
untuk setiap proses dalam porsi yang sama dan dalam rangka melingkar, berurusan
dengan semua proses tanpa prioritas apapun.
Hal ini juga dikenal
sebagai eksekutif siklik.
Keuntungan utama dari
algoritma round robin lebih pertama datang pertama melayani algoritma adalah
bahwa itu adalah kelaparan gratis. Setiap proses akan dieksekusi oleh CPU untuk
interval waktu yang tetap (yang ditetapkan sebagai irisan waktu). Jadi dengan
cara ini tidak ada proses kiri menunggu giliran untuk dieksekusi oleh CPU.
Algoritma round robin
sederhana dan mudah diimplementasikan. Nama round robin berasal dari prinsip
yang dikenal sebagai round robin dimana setiap orang mengambil bagian yang sama
dari sesuatu pada gilirannya.
Kriteria Penjadwalan.
Kriteria
Penjadwalan proses
Algoritma penjadwalan CPU yang berbeda akan memiliki
perbedaan properti. Sehingga untuk memilih algoritma ini harus dipertimbangkan
dulu properti-properti algoritma tersebut. Ada beberapa kriteria yang digunakan
untuk melakukan pembandingan algoritma penjadwalan CPU, antara lain:
1. 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%.
2. Throughput: throughput Adalah banyaknya
proses yang selesai dikerjakan dalam
satu satuan waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah proses user yang dapat
dieksekusi dalam interval waktu tertentu.
Ktiteria-kriteria
tersebut saling tergantung dan dapat saling bertentangan sehingga tidak
dimungkinkan optimasi semua criteria secara simultan
Preetive
dan Non-Preemtive Schedulling
Penjadwalan Non Preemptive
Pada strategi
ini, begitu proses telah berjalan maka sistem operasi maupun proses lain tidak
dapat mengambil alih eksekusi prosesor. Pengalihan hanya dapat terjadi jika
proses yang running sudah selesai, baik secara normal maupun abnormal.
Penjadwalan Preemptive
Pada strategi ini, sistem operasi dan proses lain dapat
mengambil alih eksekusi prosesor tanpa harus menunggu proses yang sedang
running menyelesaikan tugasnya. Penjadwalan preemptive merupakan fitur yang
penting, terutama pada sistem dimana proses-proses memerlukan tanggapan
prosesor secara cepat.
Dispatcher
Dispatcher adalah
suatu modul yang akan memberikan kontrol secepat mungkin pada CPU terhadap
penyeleksian proses.
1. Alih Konteks
2. Switching to user mode.
3. Lompat dari suatu bagian di progam user untuk
mengulang progam.
Dispatch Latency adalah waktu yang dibutuhkan untuk
menghentikan suatu proses dan
menjalankan proses yang lain.
Scheduling
Criteria
Adil, proses-proses diperlakukan sama, dalam artian adil.
Adil disini tidak berarti terdapat perlakuan yang sama kepada setiap process,
melainkan terdapat beberapa variabel seperti prioritas, dll yang akan
dipelajari nanti.
CPU
Utilization, diharapkan agar CPU selalu dalam keadaan sibuk, sehingga
penggunaan CPU lebih optimal.
Throughput, adalah
banyaknya proses yang selesai dikerjakan dalam satu satuan waktu. Sasaran
penjadwalan adalah memaksimalkan jumlah job yang diproses dalam satu satuan
waktu
Turn
Around Time, adalah 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.
Turn Around Time =
waktu eksekusi + waktu tunggu.
Sasaran Penjadwalan adalah meminimalkan waktu
Turn Around Time.
Waiting-Time, adalah
waktu yang diperlukan oleh suatu proses untuk menunggu di ready queue. Sasaran
Penjadwalan : meminimalkan waiting time.
Response-Time, adalah waktu yang diperlukan
oleh suatu proses dari minta dilayani hingga ada respon pertama menanggapi
permintaan tersebut . Sasaran penjadwalan : meminimalkan waktu tanggap
Scheduling
Algorithm
Algoritma – algoritma yang menerapkan strategi
nonpreemptive :
·
FIFO
(First-in, First-out)
·
FIFO
(First-in, First-out) adalah FIFO
adalah akronim yang paling umum adalah singkatan pertama keluar pertama. Dua
konteks umum untuk ini adalah:
·
FIFO dan LIFO akuntansi, akuntansi
FIFO (komputasi dan elektronik), metode
antrian atau manajemen memori
·
FIFO dapat berdiri untuk kata lain:
Cocok atau bercinta
off, ekspresi sumber daya manusia tidak resmi digunakan
dalam organisasi
Fly-in fly-out, strategi sumber daya manusia
untuk penyebaran personil ke lokasi
terpencil
·
SJF
(Shortest Job First).
Adalah
hortest-Job-First (SJF) adalah disiplin non-preemptive dimana pekerjaan tunggu (atau proses) dengan terkecil
diperkirakan selesai run- time-to-dijalankan
berikutnya. Dengan kata lain, ketika CPU tersedia, ditugaskan untuk proses yang memiliki CPU burst terkecil
berikutnya.
Penjadwalan SJF
terutama cocok untuk pekerjaan batch yang kali run dikenal di muka. Karena
algoritma penjadwalan SJF memberikan waktu rata-rata minimum untuk himpunan
proses, mungkin optimal.
Algoritma SJF nikmat
pekerjaan singkat (atau prosesor) dengan mengorbankan orang-orang lagi.
Masalah yang jelas
dengan skema SJF adalah bahwa hal itu membutuhkan pengetahuan yang tepat dari
berapa lama pekerjaan atau proses akan berjalan, dan informasi ini biasanya
tidak tersedia.
·
HRN (Highest Ratio Next).
Tertinggi Rasio Response Berikutnya (HRRN) penjadwalan
adalah disiplin non-preemptive, mirip dengan Shortest Job Berikutnya (SJN), di
mana prioritas setiap pekerjaan tergantung pada perkiraan waktu menjalankan
nya, dan juga jumlah waktu yang telah dihabiskan menunggu. Jobs mendapatkan
prioritas yang lebih tinggi semakin lama mereka menunggu, yang mencegah
penundaan tak terbatas (proses kelaparan).
Bahkan, pekerjaan yang
telah menghabiskan waktu tunggu bersaing terhadap mereka diperkirakan memiliki
jangka waktu pendek.
Prioritas = \ frac
{menunggu \ waktu + perkiraan waktu \ run \} {perkiraan waktu \ run \} = 1 + \
frac {menunggu waktu \} {perkiraan waktu \ run \}
Dikembangkan oleh
Brinch Hansen untuk memperbaiki kelemahan tertentu dalam SJN termasuk kesulitan
dalam memperkirakan waktu berjalan.
Ø MFQ (Multiple Feedback Queues).
Dalam ilmu komputer, antrian umpan balik bertingkat adalah
algoritma penjadwalan. Solaris 2.6 Time-Sharing (TS) scheduler
mengimplementasikan algoritma ini [1] The Mac OS X dan Microsoft Windows
penjadwal keduanya dapat dianggap sebagai contoh dari kelas yang lebih luas
dari multilevel penjadwalan antrian umpan balik.. [2] Algoritma penjadwalan ini
dimaksudkan untuk memenuhi persyaratan desain berikut untuk sistem multimode:
·
Memberikan preferensi pekerjaan singkat.
·
Memberikan preferensi untuk I / O proses
terikat.
·
Proses terpisah ke dalam kategori
berdasarkan kebutuhan mereka untuk prosesor.
Multi-level Feedback
Queue scheduler pertama kali dikembangkan oleh Fernando J. Corbató dkk. pada
tahun 1962, dan pekerjaan ini, bersama dengan pekerjaan lain pada Multics,
memimpin ACM untuk penghargaan Corbató Turing Award
Algortima – algoritma
yang menerapkan strategi preemptive :
RR (Round-Robin).
Secara umum, round-robin mengacu pada pola atau memesan
dimana item yang ditemui atau diproses secara berurutan, sering dimulai lagi
pada awal secara melingkar.
ü SRF
(Shortest-Remaining-First).
Terpendek waktu, juga dikenal sebagai waktu terpendek yang
tersisa pertama (SRTF) yang tersisa, adalah metode penjadwalan yang merupakan
versi preemptive pekerjaan terpendek penjadwalan berikutnya. Dalam algoritma
penjadwalan ini, proses dengan jumlah terkecil waktu yang tersisa sampai
selesai dipilih untuk mengeksekusi. Karena proses yang sedang dijalankan adalah
salah satu dengan jumlah waktu terpendek yang tersisa dengan definisi, dan
sejak saat itu seharusnya hanya mengurangi sebagai eksekusi berlangsung, proses
akan selalu berjalan sampai mereka lengkap atau proses baru ditambahkan yang
membutuhkan jumlah yang lebih kecil dari waktu.
Waktu yang tersisa terpendek adalah menguntungkan karena
proses singkat ditangani sangat cepat. Sistem ini juga memerlukan sangat
sedikit overhead karena hanya membuat keputusan ketika proses selesai atau
proses baru ditambahkan, dan ketika proses baru ditambahkan algoritma hanya
perlu membandingkan proses yang sedang dijalankan dengan proses baru,
mengabaikan semua proses lainnya saat menunggu untuk mengeksekusi.
Seperti terpendek pekerjaan pertama, ia memiliki potensi
untuk proses kelaparan; proses panjang dapat menahan tanpa batas waktu jika
proses pendek terus ditambah. Ancaman ini bisa menjadi minimal ketika kali
proses mengikuti distribusi berat ekor.
ü PS
(Priority Scheduling ).
Ide dasarnya adalah sederhana: setiap proses diberikan
prioritas, dan prioritas diperbolehkan untuk menjalankan. Proses yang
sama-Prioritas dijadwalkan agar FCFS. Terpendek-Job-First (SJF) algoritma
adalah kasus khusus dari algoritma penjadwalan prioritas umum.
Sebuah algoritma SJF
hanyalah sebuah algoritma prioritas mana prioritasnya adalah kebalikan dari
(diprediksi) berikutnya CPU burst. Artinya, semakin lama meledak CPU, semakin
rendah prioritas dan sebaliknya.
Prioritas dapat
didefinisikan baik secara internal maupun eksternal. Prioritas yang ditetapkan
secara internal menggunakan beberapa jumlah terukur atau kualitas untuk
menghitung prioritas dari sebuah proses.
Contoh prioritas
Internal
ü Batas
waktu.
ü Persyaratan
memori.
ü Persyaratan
berkas,
misalnya, jumlah file yang terbuka.
CPU
Vs persyaratan I / O.
Prioritas yang
ditetapkan secara eksternal ditetapkan dengan kriteria yang eksternal untuk
sistem operasi seperti
Pentingnya proses.
Jenis atau jumlah dana yang dibayar untuk
penggunaan komputer.
Departemen mensponsori pekerjaan.
Politik.
Penjadwalan
prioritas dapat berupa preemptive atau non preemptive
Algoritma prioritas
preemptive akan preemptive CPU jika prioritas dari proses yang baru tiba lebih
tinggi dari prioritas dari proses yang sedang berjalan.
Algoritma prioritas non-preemptive hanya
akan menempatkan proses baru di kepala antrian siap.
Masalah utama dengan
penjadwalan prioritas adalah pemblokiran terbatas atau kelaparan. Sebuah solusi
untuk masalah penyumbatan terbatas dari proses prioritas rendah adalah penuaan.
Penuaan adalah teknik secara bertahap meningkatkan prioritas proses yang
menunggu dalam sistem untuk jangka waktu yang panjang.
Klasifikasi lain selain
berdasarkan dapat/tidaknya suatu proses diambil secara paksa adalah klasifikasi
berdasarkan adanya prioritas di proses-proses, yaitu :
1. Algoritma penjadwalan tanpa berprioritas.
2. Algoritma penjadwalan berprioritas, terdiri
dari :
a. Berprioritas static
Intisari Makalah ini
membahas penerapan
algoritma tabu search
(TS) dalam penyelesaian masalah penjadwalan job shop
statik. Implementasi
dalam bentuk perangkat lunak membuktikan bahwa algoritma
ini dapat menghasilkan
jadwal job shop yang valid. Kualitas jadwal diukur
dengan kriteria
completion time atau makespan, dan dibandingkan dengan hasil
dari algoritma
simulated annealing (SA) dan perangkat lunak penjadwalan Quant
System. Disimpulkan
bahwa algoritma TS mengungguli algoritma SA dan Quant System
dalam hal kualitas
solusi,
b.Berprioritas dinamis
Untuk permasalahan
dinamis, setelah dilakukan percobaan perhitungan, maka dapat disimpulkan kondisi dinamis pada
dasarnya dengan menggunakan sistem lelang ini adalah dengan melakukan
perhitungan pada tiap slot waktu kritis.
