PENJADWALAN SISTEM OPERASI

Misalkan terdapat empat proses (P1, P2, P3 dan P4) yang meminta layanan dari CPU sebagai berikut, hitunglah AWT dari proses berikut dengan menggunakan algotiritma penjadwalan SRF, PS dan RR.


1. SRF

Gantt Chart

Waktu Tunggu
AWT = (4+0+11+18)/4 = 8,25 MS

2. PS

Gantt


Waktu Tunggu

AWT = (22+9+0+13)/4 = 11 MS

3. RR

Gantt Chart


Waktu tunggu
AWT = (22+12+19+19)/4 = 18 MS

State Proses Tiga Keadaan

Running : Pemroses sedang mengeksekusi intruksi proses itu.
Ready : Proses siap (ready) dieksekusi, tapi pemroses belum tersedia untuk mengeksekusi proses ini.
Blocked : Proses menunggu kejadian untuk melengkapi tugasnya.

Mutual Exclusion, Deadlock, Starvation

Mutual Exclusion adalah jaminan bahwa hanya ada satu proses yang mengakses semua sumber daya dalam satu waktu tertentu.

Deadlock adalah jika proses menunggu suatu kejadian yang tidak akan pernah terjadi.

Starvation adalah menunggu suatu kejadian yang entah kapan bisa terjadi.

PCB, Multiprocessing & Multiprogramming

PCB (Proses Control Block) untuk mempresentasikan masing-masing proses pada sistem operasi yang dijalankan oleh sistem operasi.

Multiprocessing System adalah system yang memiliki lebih dari 1 CPU (processor).

Multiprogramming adalah suatu sistem yang siap dieksekusi dimana dikumpulkan dalam sebuah partisi dam meletakkannya di memory dalam bentuk antrian, sesuai dengan urutannya.

Preemtive & Non-Preemtive

Strategi Preemtive adalah saat proses diberi jatah waktu pemroses maka pemroses dapat diambil alih proses lain sehingga proses disela sebelum selesai dan harus dilanjutkan menungguh jatah waktu pemroses tiba kembali pada proses itu.
Strategi Non-Preemtive adalah pada saat proses sementara berjalan maka proses tidak dapat diambil alih oleh proses yang lain sampai proses itu selesai.

Perbedaan generasi I dan generasi II

Generasi I Tahun 1940 – 1450an komponen utamanya berupa tabung hampa udara dan semua operasi komputer dilakukan secara manual melalui plugboards dan hanya bisa digunakan untuk menghitung (+. -, dan *). Sedangkan generasi ke II Tahun 1960-an komponen utamanya berupa transistor dan inputnya memakai punch card.

Definisi dan fungsi sistem operasi

Sistem Operasi adalah kumpulan program yang berisi perintah – perintah (command) dan bertindak sebagai interface (antarmuka) antara user dan komputer, sehingga komputer dapat bekerja sesuai dengan keinginan user.

Fungsi Sistem Operasi yaitu:

Pengelola seluruh sumber daya sistem komputer (resource manager), mengelola seluruh sumber daya yang terdapat pada sistem komputer.

Sistem operasi sebagai penyedia layanan (extended, virtual machine). Sistem operasi menyediakan sekumpulan layanan (system calls) kepemakai, sehingga memudahkan dan menyamankan penggunaan atau pemanfaatan sumber daya sistem komputer.

Contoh Sistem Operasi

WINDOWS

LINUX

UNIX

ALGORITMA PENJADWALAN

Pendahuluan

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. Bagian berikut ini akan memberikan ilustrasi beberapa algoritma penjadwalan.

Rujukan

[Silberschatz2005] Avi Silberschatz, Peter Galvin, dan Grag Gagne. 2005 . Operating Systems Concepts. Seventh Edition. John Wiley & Sons.

[Scheduling] Moonbase. 1991 . Scheduling– http://moonbase.wwc.edu/~aabyan/352/Scheduling.html. Diakses 20 Februari 2007.

FCFS (First Come First Served)

Algoritma ini merupakan algoritma penjadwalan yang paling sederhana yang digunakan CPU. Dengan menggunakan algoritma ini setiap proses yang berada pada status ready dimasukkan kedalam FIFO queue atau antrian dengan prinsip first in first out, sesuai dengan waktu kedatangannya. Proses yang tiba terlebih dahulu yang akan dieksekusi.

Kelemahan dari algoritma ini:

1. Waiting time rata-ratanya cukup lama.
2. Terjadinya convoy effect, yaitu proses-proses menunggu lama untuk menunggu 1 proses besar yang sedang dieksekusi oleh CPU. Algoritma ini juga menerapkan konsep non-preemptive, yaitu setiap proses yang sedang dieksekusi oleh CPU tidak dapat di-interrupt oleh proses yang lain.

Contoh:
Terdapat 3 proses seperti pada tabel berikut:
Hitunglah AWT menggunakan algoritma FCFS

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (0+23+29)/3 = 17,3 ms

SJF (Shortest Job First)

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.

Ada beberapa kekurangan dari algoritma ini yaitu:

1. Susahnya untuk memprediksi burst time proses yang akan dieksekusi selanjutnya.

2. Proses yang mempunyai burst time yang besar akan memiliki waiting time yang besar pula karena yang dieksekusi terlebih dahulu adalah proses dengan burst time yang lebih kecil.

Algoritma ini dapat dibagi menjadi dua bagian yaitu :

1. Preemptive . 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 (SRF).

2. Non-preemptive . CPU tidak memperbolehkan proses yang ada di ready queue untuk menggeser proses yang sedang dieksekusi oleh CPU meskipun proses yang baru tersebut mempunyai burst time yang lebih kecil.

Contoh:
Terdapat 4 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma SRF.

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (4+0+13+5)/4 = 5,5 ms

Priority Scheduling

Priority Scheduling merupakan algoritma penjadwalan yang mendahulukan proses yang memiliki prioritas tertinggi. Setiap proses memiliki prioritasnya masing-masing.

Prioritas suatu proses dapat ditentukan melalui beberapa karakteristik antara lain:

1. Time limit.
2. Memory requirement.
3. Akses file.
4. Perbandingan antara burst M/K dengan CPU burst.
5. Tingkat kepentingan proses.

Priority scheduling juga dapat dijalankan secara preemptive maupun non-preemptive. Pada preemptive, jika ada suatu proses yang baru datang memiliki prioritas yang lebih tinggi daripada proses yang sedang dijalankan, maka proses yang sedang berjalan tersebut dihentikan, lalu CPU dialihkan untuk proses yang baru datang tersebut. Sementara itu, pada non-preemptive, proses yang baru datang tidak dapat menganggu proses yang sedang berjalan, tetapi hanya diletakkan di depan queue.

Kelemahan pada priority scheduling adalah dapat terjadinya indefinite blocking( starvation). Suatu proses dengan prioritas yang rendah memiliki kemungkinan untuk tidak dieksekusi jika terdapat proses lain yang memiliki prioritas lebih tinggi darinya.

Solusi dari permasalahan ini adalah aging, yaitu meningkatkan prioritas dari setiap proses yang menunggu dalam queue secara bertahap.

Contoh:

Terdapat 5 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma PS.

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+22+19+2)/5 = 11 ms.

Round Robin

Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Tentu proses ini cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU yaitu (1/n), dan tak akan menunggu lebih lama dari (n-1)q dengan q adalah lama 1 quantum.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja dengan algoritma first come first served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga banyak waktu terbuang.

Permasalahan utama pada Round Robin adalah menentukan besarnya time quantum. Jika time quantum yang ditentukan terlalu kecil, maka sebagian besar proses tidak akan selesai dalam 1 quantum. Hal ini tidak baik karena akan terjadi banyak switch, padahal CPU memerlukan waktu untuk beralih dari suatu proses ke proses lain (disebut dengan context switches time). Sebaliknya, jika time quantum terlalu besar, algoritma Round Robin akan berjalan seperti algoritma first come first served. Time quantum yang ideal adalah jika 80% dari total proses memiliki CPU burst time yang lebih kecil dari 1 time quantum.

Contoh:

Terdapat 3 proses seperti pada tabel berikut:

Hitunglah AWT menggunakan algoritma RR dengan Q=3.

Maka gantt chart kedatangan proses:

Sehingga waktu tunggu untuk tiap-tiap proses terlihat pada tabel berikut:

AWT = (12+9+12)/3 = 11 ms.

KESIMPULAN

Dari beberapa contoh diatas, algoritma yang paling efisien untuk menyelesaikan proses adalah SRF karena memiliki AWT yang kecil.