Penjelasan Kongkurensi

Proses-proses disebut kongkuren jika proses-proses (lebih dari 1 proses) berada pada saat yang sama. Proses-proses kongkuren dapat sepenuhnya tak bergantung dengan lainnya tapi dapat juga saling berinteraksi/kerjasama. Proses-proses yang berinteraksi memerlukan sinkronisasi/koordinasi agar terkendali dengan baik.

Contoh Kasus :

Sambil menunggu selesainya layanan (misalnya transfer data oleh modem) pemakai dapat berinteraksi dengan aplikasi lain seperti aplikasi permainan game atau mengetikkan perintah pada text editor. Proses tersebut harus berjalan konkuren dan tidak terjadi deadlock (hang).

Kegiatan yang berhubungan dengan kongkurensi :

• Alokasi waktu pemroses untuk proses-proses yang aktif
• Pemakaian bersama & persaingan mendapatkan sumber daya
• Komunikasi antar proses
• Sinkronisasi aktivitas banyak proses

Kesulitan dalam Kongkurensi:

• Pemakaian bersama sumber daya global
• Pengelolaan sumber daya agar optimal 
• Pencarian kesalahan pemrograman 

Penanganan Kongkurensi:

• Mengetahui proses-proses yang aktif
• Mengatur alokasi dan dealokasi beragam sumber daya untuk tiap proses yang aktif
• Proteksi data dan sumber daya fisik proses
• Hasil-hasil proses harus independen

Persaingan dan Kerjasama Antar Proses

Persaingan antar proses terjadi ketika beberapa proses akan menggunakan sumber daya yang sama. Jika ada 2 proses yang akan mengakses ke suatu sumber daya tunggal, kemudian satu proses dialokasikan ke sumber daya tersebut oleh SO → proses yang lainnya akan menunggu. 

Pada kasus yang ekstrim, proses yang menunggu tersebut ada kemungkinan tidak akan pernah mendapatkan akses ke sumber daya sehingga tidak akan pernah selesai dengan sempurna. Hal ini juga terjadi akibat antar proses yang saling tidak peduli. Proses-proses yang mengalami kongkuren dapat berdiri sendiri (independen) atau dapat saling berinteraksi, sehingga membutuhkan sinkronisasi atau koordinasi proses yang baik. 

Meskipun proses-proses tidak bekerja bersama, SO perlu mengatur persaingan diantara proses-proses itu dalam memperoleh sumber daya yang terbatas

Contoh :

• Dua buah aplikasi (word & corel) berusaha mengakses printer yang sama.
• Bila kedua aplikasi mengakses printer yang sama benar-benar secara bersamaan maka kedua proses akan memperoleh hasil yang tidak di kehendaki.

Kondisi dan Masalah

Beberapa kondisi dan masalah yang dapat muncul pada kongkurensi antara lain :

• Mutual exclusion

Mutual exclusion adalah jaminan hanya satu proses yang mengakses sumber daya pada suatu interval waktu tertentu, sedangkan proses lain dilarang mengerjakan hal yang sama. Contoh : sumberdaya printer hanya bisa diakses 1 proses, tidak bisa bersamaan → sumber daya ini disebut sumber daya kritis

• Deadlock

Adalah banyak proses yang saling menunggu hasil dari proses yang lain untuk dapat melanjutkan atau menyelesaikan tugasnya.

Misal : 2 proses P0 dan P1 

2 sumber daya R0 dan R1 

P0 meminta sumberdaya R0. 

Sumber daya R1 dialokasikan ke P1. 

Skenario yang menimbulkan deadlock :

P0 dialokasikan R0

P1 dialokasikan R1

P0 sambil masih menggenggam R0, meminta R1

P1 sambil masih menggenggam R1, meminta R0

Terjadi deadlock karena sama-sama akan saling menunggu 

Starvation

Adalah suatu proses akan menunggu suatu kejadian atau hasil suatu proses lain, supaya dapat menyelesaikan tugasnya, tetapi kejadian yang ditunggu tidak pernah terjadi karena selalu diambil lebih dulu oleh proses yang lain.

Contoh :Terdapat tiga proses, yaitu P1, P2 dan P3. 

1. P1, P2 dan P3 memerlukan pengaksesan sumber daya R secara periodik
2. Skenario berikut terjadi : 
3. P1 sedang diberi sumber daya R sedangkan P2 dan P3 diblocked menunggu sumber daya R. 
4. Ketika P1 keluar dari critical section, maka P2 dan P3 diijinkan mengakses R. 
5. Asumsi P3 diberi hak akses, kemudian setelah selesai, hak akses kembali diberikan ke P1 yang saat itu kembali membutuhkan sumber daya R. 
6. Jika pemberian hak akses bergantian terus-menerus antara P1 dan P3, maka P2 tidak pernah memperoleh pengaksesan sumber daya R. 
7. Dalam kondisi ini memang tidak terjadi deadlock, hanya saja P2 mengalami starvation (tidak ada kesempatan untuk dilayani).

Penjadwalan Proses

Penjadwalan CPU terjadi pada sistem operasi yang mempergunakan multiprogramming. Penjadwalan berupa kumpulan kebijakan untuk menentukan proses mana yang harus dikerjakan CPU dan berapa lama proses tersebut berjalan.

Tujuan penjadwalan adalah mengusahakan agar CPU tetap sibuk. Pada saat CPU menunggu operasi I/O, scheduler menyeleksi proses di main memory yang memiliki status ready untuk dieksekusi. Penjadwalan tipe ini disebut Short-term scheduller. Scheduler pada short-term ini dikenal dengan nama dispatcher

Tipe-tipe Penjadwalan

• Short-term scheduller : ready→ running
• Medium-term scheduller : suspended→ ready
• Long-term scheduller : batch (new)→ ready

Untuk mengukur kinerja scheduler digunakan beberapa kriteria :

• Fairness: Proses-proses diperlakukan sama yaitu setiap proses akan mendapatkan pembagian waktu secara adil
• CPU utilization: CPU dikondisikan agar tetap sibuk, yang dinyatakan dengan rasio waktu sibuk

• Throughput: Ini hanya terjadi pada saat CPU sibuk yaitu banyaknya job yang dikerjakan dalam satu satuan waktu

• Turnaround Time: Banyaknya waktu yang diperlukan untuk mengeksekusi proses sampai selesai, dari mulai menunggu untuk meminta tempat di main memory, menunggu di ready queue (waiting time), dieksekusi dan selesai. Sasaran dari scheduller adalah meminimalkan timearound time.

• Response Time: Waktu yang dibutuhkan oleh suatu proses dari minta dilayanai sampai ditanggapi.

Strategi Penjadwalan

• Penjadwalan nonpreemptive: Begitu diberi jatah waktu pemroses maka prosesor tidak dapat diambil alih oleh proses lain sampai proses itu selesai (run to completion)
• Penjadwalan Preemptive: Saat proses diberi jatah waktu pemroses maka pemroses dapat diambil alih oleh proses lain sehingga proses disela sebelum selesai dan akan dilanjutkan setelah jatah waktu pemroses kembali padanya.

Algoritma Penjadwalan

A. First Come First Served (FCFS)

Proses yang pertama kali meminta jatah waktu untuk menggunakan CPU akan dilayani terlebih dahulu.

Algoritma ini termasuk non-preemptive

Average Waiting Time (AWT) tinggi. AWT adalah  total waktu menunggu dari semua proses dibagi jumlah proses 

Misal ada 3 proses : P1, P2 dan P3 yang meminta layanan CPU

Jika urutan kedatangan P1, P2, P3

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT = (0+24+27)/3 = 17 ms

B. Short Job First Scheduling (SJF)

Proses yang memiliki CPU burst paling kecil dilayani terlebih dahulu

Misal ada 4 proses : P1, P2, P3 dan P4

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT=  (3+16+9+0)/4=  7 ms

Kelemahan SJF : sulitnya mengetahui CPU burst time berikutnya. Cara mengatasinya dengan memprediksi CPU Burst Time berikutnya menggunakan rata-rata eksponensial dari burst time sebelumnya.

Sebagai contoh α = 0,5

Pada awalnya t1 = 6 dan τ1 = 10 sehingga

τ2    = 0,5*6 + (1-0,5)*10 = 8

Nilai ini akan digunakan untuk mencari  τ3

τ3=(0.5)*4+ (1-0.5)*8=6

Strategi penjadwalan SJF adalah non-preemptive dan preemptive. Misal ada proses P1 yang datang pada saat P0 sedang berjalan. Pada Preemptive jika CPU burst P1 lebih kecil dari sisa waktu yang dibutuhkan P0 maka P0 akan diberhentikan dulu dan CPU dialokasikan untuk P1. 

Penjadwalan SJF secara Preemptive dikenal dengan shortest remaining time first scheduling

Contoh Preemptive penjadwalan SJF:

Misal terdapat 4 proses

Gant chart :

Proses yang lebih tiba dulu akan diproses, setelah itu lihat CPU burst paling kecil.

Waktu tunggu untuk tiap proses

AWT  = (9+0+15+2)/4 = 6,5 ms

C. Priority Scheduling
Pada strategi ini CPU akan dialokasikan untuk proses yang memiliki prioritas tertinggi. Jika beberapa proses memiliki prioritas yang sama maka akan digunakan algortima FCFS. Priority scheduling dapat bersifat preemptive maupun non preemptive
Contoh : terdapat 5 proses dengan CPU burst

Gant Chart

Waktu tunggu untuk tiap-tiap proses

AWT = (6+0+16+18+1)/5 = 8,2 ms

Prioritas biasanya menyangkut : waktu, memori yang dibutuhkan, banyaknya file   yang boleh dibuka, rasio antara rata-rata I/O burst dan rata-rata CPU/burst

D. Round-Robin Scheduling

Konsep dasar algoritma ini adalah time sharing

Digunakan quantum time untuk membatasi waktu eksekusi 

Bersifat preemptive, proses yang burst timenya melebihi quantum time akan mengantri di posisi ekor dari ready queue.

Misal quantum time 4 ms

Gant chart

AWT=(6+4+7)/3= 5.7 ms

Kelemahan Round-Robin
Semakin kecil quantum time maka switching akan sering terjadi

Penjelasan Graph

Graph dalam Bahasa Inggris memiliki arti yang sama dengan grafik. Graph atau Graf adalah suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat.

Dalam kehidupan sehari-hari, graf digunakaan untuk menggambarkan macam-macam struktur yang ada. Tujuannya adalah sebagai visualisasi objek-objek agar lebih mudah dimengeri.
Contoh graf :

• Struktur organisasi,
• Bagan alir pengambilan mata kuliah,
• Peta,
• Rangkaian listrik.

Tiap-tiap diagram memuat sekumpulan objek (kotak, titik dll) beserta garis-garis yang menghubungkan objek-objek tersebut (jarak, berat, dll). Garis bisa berarah ataupun tidak berarah. Garis yang berarah biasanya digunakan untuk menyatakan hubungan yang mementingkan urutan objek. Urutan objek akan mempunyai arti yang lain jika arah dirubah. Sedangkan garis yang tidak berarah digunakan untuk menyatakan hubungan antar objek-objek yang tidak mementingkan urutan.

Suatu Graf G terdiri dari 2 himpunan yang berhingga, yaitu himpunan titik-titik tidak kosong (symbol V(G)) dan himpunan garis-garis (symbol E(G)). Titik atau simpul atau point biasa disebut juga Vertex atau node. Garis atau rusuk atau sisi disebut edge

Istilah-Istilah dalam Graf.

1. Titik Ujung: Titik yang menghubungakan setiap garis.

2. Loop: Garis yang hanya berhubungan dengan satu titik ujung.

3. Garis Paralel: Dua garis berbeda yang menghubungakan titik yang sama

4. Adjacent (berhubungan): Dua titik dikatakan adjacent jika ada garis yang menghubungkan keduanya.

5. Titik Terasing (Isolating Point): Titik yang tidak mempunyai garis yang berhubungan dengannya 

6. Graf Kosong: Graf yang tidak mempunyai titik (sehingga tidak  mempunyai garis)

7. Graf Berarah (Directed Graph/Digraph): Jika semua garis pada graf tersebut memiliki arah.

8. Graf Tak Berarah (Undirected Graph): Jika dalam  graf tersebut semua garisnya tidak berarah.

Contoh Kasus Best First Seach

Contoh Kasus
Permasalahan mencari jarak terdekat antara kota Arad dengan Bucharest menggunakan metode Best First search.

Solusi
Best First search merupakan metode yang menggunakan nilai heuristic, pada permasalahan ini heuristik yang digunakan adalah jarak kota-kota terhadap kota Bucharest jika ditarik garis lurus yang jaraknya seperti yang tertera di atas dengan asumsi kota terhubung yang letaknya paling dekat dengan kota Bucharest adalah jalan yang paling optimal.
Diagram pohon langkah-langkah penelusuran dengan metode Best First Search adalah sebagai berikut :

Dari Langkah-langkah di atas, didapatkan kota-kota yang harus dilalui untuk mendapatkan jalan yang paling dekat jaraknya dari Arad ke Bucharest dengan metode Best First Search adalah : Arad – Sibiu – Fagaras – Bucharest. Dari peta di atas, panjang jalan yang dilalui adalah 140+99+211 = 450 km.

Referensi:

Russel, S and Novig, P.(2009). Artificial Intelligence: A Modern Approach, 3rd ed. Pp. 92-93