Minggu, 23 April 2017

METODE SIKRONISASI


1.      Sikronissasi pada proses Critical ection

§  Masalah Critical Section
a)      n proses mencoba menggunakan shared data bersamaan
b)  Setiap proses mempunyai “code” yang mengakses/ manipulasi shared data tersebut => “critical section”
c)      Problem: Menjamin jika ada satu proses yang sedang
d)     “eksekusi” pada bagian “critical section” tidak ada proses lain yang diperbolehkan masuk ke “code” critical section dari proses tersebut.

§  Solusi “critical section problem” harus memenuhi:
1.   Mutual Exclusion: Jika proses Pi sedang “eksekusi” pada bagian “critical section” (dari proses Pi) maka tidak ada proses proses lain dapat “eksekusi” pada bagian critical section dari proses-proses tersebut.
2.     Progress: Jika tidak ada proses sedang eksekusi pada critical section-nya dan jika terdapat lebih dari satu proses lain yang ingin masuk ke critical section, maka pemilihan siapa yang berhak masuk ke critical section tidak dapat ditunda tanpa terbatas.
3.     Bounded Waiting: Terdapat batasan berapa lama suatu proses harus menunggu giliran untuk mengakses “critical section” – jika seandainya proses lain yang diberikan hak akses ke critical section.

2.      Metode Test-and-Set (mutual exclusion)
a.      Mutual exclusion dapat diterapkan:
b.      Gunakan shared data, variabel: lock: boolean (initially false)
c.       lock: menjaga critical section
d.      Process Pi:
do {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section
}

3.      Metode Semaphore
a.      Perangkat sinkronisasi yang tidak membutuhkan busy waiting
b.      Semaphore S – integer variable
Dapat dijamin akses ke var. S oleh dua operasi atomik:







  • Implementasi Semaphore

a.      Didefinisikan sebuah Semaphore dengan sebuah Record
 






b.      Diasumsikan terdapat 2 operasi sederhana :
§  block menhambat proses yang akan masuk
§  wakeup(P) memulai eksekusi pada proses P yang di block

4.      Metode Masalah Klasik Sinkronisasi

1)      Bounded-Buffer Problem
Produsen menghasilkan barang dan konsumen yang akan menggunakannya. Beberapa batasan yang harus dipenuhi, yaitu  :
§  Barang yang dihasilkan oleh produsen terbatas
§  Barang yang dipakai konsumen terbatas - Konsumen hanya boleh menggunakan barang yang dimaksud setelah produsen menghasilkan barang dalam jumlah tertentu
§  Produsen hanya boleh memproduksi barang jika konsumen sudah kehabisan barang
Pada penyelesaian permasalahan bounded buffer menggunakan semaphore berikut:




2)      Reader and Writer Problem
Pada masalah ini terdapat  dua variasi  yaitu :
1) seorang reader tidak perlu menuggu reader lain untuk selesai hanya karena ada writer menunggu (reader memiliki prioritas lebih tinggi disbanding dengan writer)
2)   Jika ada writer yang sedang menunggu, maka tidak boleh ada reader lain yang bekerja (writer memiliki prioritas yang lebih tinggi)
§   Jika terdapat writer dalam critical section dan terdapat n reader yang menunggu, maka satu reader akan antri di wrt dan n-1 reader akan antri di mutex.
§   Jika writer mengeksekusi signal(wrt), maka dapat disimpulkan bahwa eksekusi adalah menunggu reader atau menunggu satu writer. Variabel umum yang digunakan adalah




3)      DiningPhilosophers Problem


Permasalahan dining-philosophers pada gambar disamping terdapat 5 filosof yang akan makan. Di sana disediakan 5 supit. Jika filosof lapar, ia akan mengambil 2 supit yaitu di tangan kanan dan kiri. Namun adakalanya hanya diambil supit satu saja. Jika ada filosof yang mengambil 2 supit, maka ada filosof yang harus menunggu sampai supit tersebut diletakkan.
Hal ini dapat diimplementasikan dengan wait dan signal.


 



 









Referensi :
  1. http://webcache.googleusercontent.com/search?q=cache:http://july-indiarti fst13.web.unair.ac.id/artikel_detail-103493-Sistem%2520Operasi-Singkronisasi%2520Proses.html
  2. https://www.google.co.id/url Fridha.staff.gunadarma.ac.id




Kamis, 20 April 2017

Algoritma Penjadualan

Algoritma Penjadualan

1.      First-come, first-served (FCFS)

Algoritma:
a.       Proses yang request CPU pertama kali akan mendapatkan jatah CPU.
b.      algoritma maupun struktur data merupakan yang paling sederhana : menggunakan FIFO queue (ready queue).

Contoh :
Ada tiga buah proses yang datang secara bersamaan yaitu:

§    Process              Burst Time
    P1                        24
    P2                         3
    P3                         3

§  Diketahui proses yang tiba adalah P1, P2, P3. Gant chartnya  adalah :




§  Hitunglah waiting time ( burst time + waiting time) dari ketiga proses tersebut dengan menggunakan algoritma FCFS, Waiting time untuk P1 = 0; P2 = 24; P3 = 27
§  Average waiting time: (0 + 24 + 27)/3 = 17

Diketahui proses yang tiba adalah P2, P3, P1. Gant chart-nya adalah :
 


§  Waiting time untuk P1 = 6; P2 = 0; P3 = 3
§  Average waiting time: (6 + 0 + 3)/3 = 3  (Lebih baik dari kasus sebelumnya)
§  Convoy effect proses yang pendek diikuti proses yang panjang

2.      Shortest-Job-First (SJF)

Algoritma:
Penggabungan setiap proses merupakan panjang dari burst CPU  berikutnya. Panjang  tersebut digunakan untuk penjadualan proses pada waktu terpendek
    Shortest Job First memiliki  2 skema :
1.      nonpreemptive – CPU hanya satu kali diberikan pada suatu proses, maka proses tersebut tetap akan memakai CPU hingga proses tersebut melepaskannya
2.      preemptive –jika suatu proses tiba dengan panjang CPU burst lebih kecil dari waktu yang tersisa pada ekseksusi proses yang sedang berlangsung, maka dijalankan preemtive. Skema ini dikenal dengan Shortest-Remaining-Time-First (SRTF).

Contoh
a.       Process     Arrival Time   Burst Time
                     P1                0.0                     7
                     P2                2.0                     4
                     P3                4.0                     1
                     P4                5.0                     4


a.       SJF (non-preemptive)


     Average waiting time = (0 + 6 + 3 + 7)/4 - 4

b.      SJF (preemptive)


                        Average waiting time = (9 + 1 + 0 +2)/4 - 3

3.      Priority

Algoritma:
a.       Setiap proses akan mempunyai prioritas tertinggi  (bilangan integer).
b.      CPU diberikan ke proses dengan prioritas tertinggi (smallest integer ยบ highest priority).
c.       Preemptive: proses dapat di interupsi jika terdapat prioritas lebih tinggi yang memerlukan CPU.
d.      Nonpreemptive: proses dengan prioritas tinggi akan mengganti pada saat pemakain time-slice habis.
e.        SJF adalah contoh priority scheduling dimana prioritas ditentukan oleh waktu pemakaian CPU berikutnya.

Contoh permasalahan dalam sistem :

Setiap 10 menit, prioritas dari masing-masing proses yang menunggu dalam queue dinaikkan satu tingkat. Maka, suatu proses yang memiliki prioritas 127, setidaknya dalam 21 jam 20 menit, proses tersebut akan memiliki prioritas 0, yaitu prioritas yang tertinggi (semakin kecil angka menunjukkan bahwa prioritasnya semakin tinggi).

4.      Round-Robin (RR)

Algoritma:
Proses akan mendapat jatah sebesar time quantum. Jika time quantum-nya habis atau proses sudah selesai, CPU akan dialokasikan ke proses berikutnya. Jadi,,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.

Contoh RR (Q =20)

§  Process              Burst Time
       P1                       53
       P2                       17
      P3                        68 
      P4                        24

§  Gantt Chart



§  Tipikal: lebih lama waktu rata-rata turnaround dibandingkan SJF, tapi mempunyai response terhadap  user lebih cepat.

5.      Multilevel Queue

Algoritma:
§  proses sesuai dengan sifat dari : Interaktif (response cepat) dan Batch dll
§  Partisi “ready queue” dalam beberapa tingkat (multilevel) sesuai dengan proses:
a.       Setiap queue menggunakan algoritma schedule sendiri
b.       Foreground proses (interaktif, high prioritiy): RR
c.       Background proses (batch, low priority): FCFS
§  Setiap queue mempunyai prioritas yang fixed.

6.      Multilevel Feedback Queue

Algoritma:
§  Suatu proses dapat berpindah diantara beragam antrian
§  Perlu feedback untuk penentuan proses naik/turun prioritasnya (dinamis):
a.       Aging dapat diimplementasikan sesuai dengan lama proses pada satu queue.
b.      Suatu proses yang menggunakan CPU sampai habis (tanpa I/O wait) => CPU-bound (bukan proses interaktif) dapat dipindahk ke queue dengan prioritas lebih rendah

Contoh

Terdapat tiga antrian; Q1=10 ms, FCFS Q2=40 ms, FCFS Q3=FCFS proses yang masuk, masuk ke antrian Q1. Jika dalam 10 ms tidak selesai, maka proses tersebut dipindahkan ke Q2. Jika dalam 40 ms tidak selesai, maka dipindahkan lagi ke Q3. Berdasarkan hal-hal di atas maka algoritma ini dapat digunakan secara fleksibel dan diterapkan sesuai dengan kebutuhan sistem. Pada zaman sekarang ini algoritma multilevel feedback queue adalah salah satu yang paling banyak digunakan.