Penjelasan Parallel Processing dan Model Komputasi Taksonomi Flynn

Pengertian
Pemrosesan paralel (parallel processing) adalah penggunaan lebih dari satu CPU untuk menjalankan sebuah program secara simultan. Idealnya, paralel processing membuat program berjalan lebih cepat karena semakin banyak CPU yang digunakan. Tetapi dalam prakteknya, seringkali sulit membagi program sehinggadapat dieksekusi oleh CPU yang berbeda-beda tanpa berkaitan diantaranya.
Pemrosesan paralel dalam sebuah komputer dapat didefinisikan sebagai pelaksanaan instruksi-instruksi secara bersamaan waktunya. Hal ini dapat menyebabkan pelaksanaan kejadian-kejadian :

1. dalam interval waktu yang sama,
2. dalam waktu yang bersamaan atau
3. dalam rentang waktu yang saling tumpang tindih

Komputasi paralel

Salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer secara bersamaan. Biasanya diperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ataupun karena tuntutan proses komputasi yang banyak. Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi.

Parallel processing berbeda dengan multitasking

Multitasking adalah komputer dengan processor tunggal mengeksekusi beberapa tugas secara bersamaan. Sedangkan komputasi paralel menggunakan beberapa processor atau komputer. Parallel processing disebut juga Komputasi Paralel. Pada system komputasi Paralel terdiri dari beberapa unit prosesor dan beberapa unit memori.

Ada dua teknik yang berbeda untuk mengakses data di unit memori, yaitu shared memory address dan message passing.

Berdasarkan cara mengorganisasikan memori ini computer parallel dibedakan menjadi shared memory parallel machine dan distributed memory parallel machine.

Untuk lebih memperjelas lebih dalam mengenai perbedaan komputasi tunggal (menggunakan 1 processor) dengan komputasi paralel (menggunakan beberapa processor), maka kita harus mengetahui terlebih dahulu Arsitektur Komputer Pararel dan pengertian mengenai model pemrosesan pararel.

Arsitektur paralel komputer menurut Klasifikasi Taksonomi Flynn

Ada 4 model komputasi yang digunakan Taksonomi Flynn , yaitu:

1. SISD (Single Instruction, Single Data)

Komputer ini memiliki hanya satu prosesor dan satu instruksi yang dieksekusi secara serial.

Komputer ini adalah tipe komputer konvensional. Menurut mereka tipe komputer ini tidak ada dalam praktik komputer paralel karena bahkan mainframe pun tidak lagi menggunakan satu prosesor. Klasifikasi ini sekedar untuk melengkapi definisi komputer paralel.

Beberapa contoh komputer yang menggunakan model SISD adalah UNIVAC1, IBM 360, CDC 7600, Cray 1 dan PDP 1.

2. SIMD (Single Instruction, Multiple Data) 

Komputer ini memiliki lebih dari satu prosesor, tetapi hanya mengeksekusi satu instruksi secara paralel pada data yang berbeda pada level lock-step. 

Komputer vektor adalah salah satu komputer paralel yang menggunakan arsitektur ini. Beberapa contoh komputer yang menggunakan model SIMD adalah ILLIAC IV, MasPar, Cray X-MP, Cray Y-MP, Thingking Machine CM-2 dan Cell Processor (GPU).

3. MISD (Multiple Instruction, Single Data)

Teorinya komputer ini memiliki satu prosesor dan mengeksekusi beberapa instruksi secara paralel tetapi praktiknya tidak ada komputer yang dibangun dengan arsitektur ini karena sistemnya tidak mudah dipahami. Sampai saat ini belum ada komputer yang menggunakan model MISD.

MIMD ( Multiple Instruction, Multiple Data) Multiple Instructions – Multiple Data. 

Komputer ini memiliki lebih dari satu prosesor dan mengeksekusi lebih dari satu instruksi secara paralel. Tipe komputer ini yang paling banyak digunakan untuk membangun komputer paralel, bahkan banyak supercomputer yang menerapkan arsitektur ini. Beberapa komputer yang menggunakan model MIMD adalah IBM POWER5, HP/Compaq AlphaServer, Intel IA32, AMD Opteron, Cray XT3 dan IBM BG/L. 

Singkatnya untuk perbedaan antara komputasi tunggal dengan komputasi paralel, bisa digambarkan pada gambar di bawah ini:

Komputasi Tunggal dan Komputasi Paralel

Dari perbedaan kedua gambar di atas, kita dapat menyimpulkan bahwa kinerja komputasi paralel lebih efektif dan dapat menghemat waktu untuk pemrosesan data yang banyak dan besar daripada komputasi tunggal. Namun keefektifan akan hilang ketika kita hanya mengolah data dalam jumlah yang kecil, karena data dengan jumlah kecil atau sedikit lebih efektif jika kita menggunakan komputasi tunggal.

Teknik pemrograman komputer yang memungkinkan eksekusi perintah/operasi secara bersamaan baik dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan mesin paralel) CPU. Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan.

Komputasi paralel membutuhkan:·

• algoritma
• bahasa pemrograman
• compiler

Ada 2 tehnik pemrograman pararel : 

1. Message Passing Interface (MPI).

MPI adalah sebuah standard pemrograman yang memungkinkan pemrogram (programmer) untuk membuat sebuah aplikasi yang dapat dijalankan secara paralel. Proses yang dijalankan oleh sebuah aplikasi dapat dibagi untuk dikirimkan ke masing - masing compute node yang kemudian masing -masing compute node tersebut mengolah dan mengembalikan hasilnya ke komputer head node. Untuk merancang aplikasi paralel tentu membutuhkan banyak pertimbangan - pertimbangan diantaranya adalah latensi dari jaringan dan lama sebuah tugas dieksekusi oleh prosesor.

Kegunaan MPI yang lain adalah :

1. Menulis kode paralel secara portable,
2. Mendapatkan performa yang tinggi dalam pemrograman paralel,
3. Menghadapi permasalahan yang melibatkan hubungan data irregular atau dinamis yang tidak  begitu cocok dengan model data paralel.

2. PVM (Parallel Virtual Machine)

Paket software yang mendukung pengiriman pesan untuk komputasi parallel antara komputer.

PVM dapat berjalan diberbagai macam variasi UNIX atau pun windows dan telah portable untuk banyak arsitektur seperti PC, workstation, multiprocessor dan superkomputer.

Sistem Pendukung Keputusan

Sistem pendukung keputusan (Inggris: decision support systems disingkat DSS) adalah bagian dari sistem informasi berbasis komputer (termasuk sistem berbasis pengetahuan (manajemen pengetahuan)) yang dipakai untuk mendukung pengambilan keputusan dalam suatu organisasi atau perusahaan.

Dapat juga dikatakan sebagai sistem komputer yang mengolah data menjadi informasi untuk mengambil keputusan dari masalah semi-terstruktur yang spesifik.

Menurut Moore and Chang, SPK dapat digambarkan sebagai sistem yang berkemampuan mendukung analisis ad hoc data, dan pemodelan keputusan, berorientasi keputusan, orientasi perencanaan masa depan, dan digunakan pada saat-saat tidak biasa. Pembuatan keputusan merupakan bagian kunci kegiatan, eksekutif, manajer, karyawan, setiap manusia dalam kehidupannya.
A. Tipe-tipe keputusan
1. Keputusan terprogram (struktur)

• Dibuat menurut kebiasaan, aturan, prosedur; tertulis maupun tidak
• Bersifat rutin, berulang-ulang

2. Keputusan tak terprogram (tidak terstruktur)

• Mengenai masalah khusus, khas, tidak biasa
• Kebijakan yang ada belum menjawab 
• Misal: Pengalokasian sumber daya

B. Teknik Keputusan

1. Teknik Keputusan Terprogram

• Tradisional
• Kebiasaan
• Mengikuti prosedur baku
• Saluran informasi disusun dengan baik
• Modern

• Menggunakan teknik “operation research”:

• Formula matematika
• Simulasi komputer

• Berdasarkan pengolahan data berbantu komputer

2. Teknik Keputusan Tak Terprogram

• Tradisional
• Kebijakan intuisi berdasarkan kreativitas
• Coba-coba
• Seleksi dan latihan para pelaksana
• Modern

• Teknik pemecahan masalah yang diterapkan pada :

• Latihan pembuatan keputusan
• Penyusunan program komputer empiris

C. Proses pembuatan keputusan

1. Pemahaman dan perumusan masalah

• Identifikasi gejala yang muncul
• Cari penyebabnya/masalah utama
• Cari bagian-bagian yang perlu dipecahkan
• Pergunakan analisis sebab-akibat

2. Pengumpulan dan analisis data yang relevan

• Menentukan data yang relevan
• Mengumpulkan data
• Mencari pola dari data yang terkumpul

3. Pengembangan alternatif-alternatif

• Berdasarkan data, disusun beberapa alternatif
• Untuk setiap alternatif susun pro & kontra, konsekuensi, resiko
• Semua alternatif harus feasible

4. Evaluasi Alternatif-alternatif

• Nilai efektivitas dari setiap alternatif, tolok ukur
• Realistik bila dihubungkan dengan tujuan & sumber daya organisasi
• Seberapa jauh memecahkan masalah

5. Pemilihan alternatif terbaik

• Berdasarkan alternatif, alternatif terbaik dipilih atau pilih kompromi dari beberapa alternatif

6. Implementasi keputusan

• Susun rencana untuk menerapkan keputusan
• Disiapkan mekanisme laporan periodik
• Bila perlu bangun sistem peringatan dini

7. Evaluasi hasil keputusan

D. Keunggulan dan Kelemahan Pembuatan keputusan secara Kelompok

Keunggulan

• Adanya pengetahuan yang lebih luas
• Pencarian alternatif keputusan lebih luas
• Adanya kerangka pandangan yang lebar
• Resiko keputusan ditanggung kelompok
• Karena keputusan kelompok, setiap individu termotivasi untuk melaksanakan
• Dapat terwujudnya kreativitas yang lebih luas, karena adanya berbagai pandangan

Kelemahan

• Lempar tanggung jawab mudah terjadi
• Memakan waktu dan biaya lebih
• Efisiensi pengambilan keputusan menurun
• Keputusan kelompok dapat merupakan kompromi atau bukan sepenuhnya keputusan kelompok
• Bila ada anggota yang dominan, keputusan bukan mencerminkan keinginan kelompok

E. Alat bantu Pengambilan keputusan

• Decision Tree

• Metode operation research
1. Linear programming, queuing theory
2. Network analysis (ie. CPM)
• Bantuan komputer

1. Information System, Expert System, DSS, EIS

F. Decesion Support System Model

1. Model Keputusan

1. Model Fisik

• Model fisik adalah penggambaran entitas dalam bentuk tiga dimensi.
• Contoh: miniatur pusat pembelanjaan atau miniatur mobil baru

• Model Naratif
• Model naratif adalah jenis model yang digunakan oleh manajer setiap hari, yaitu menggambarkan dan menjelaskan suatu entitas secara langsung baik dalam bentuk lisan maupun tertulis.

• Model Grafik
• Adalah model yang sangat umum dan selalu digunakan karena merupakan model yang sangat efektif dalam menjelaskan suatu entitas. Model grafik menggambarkan entitasnya dengan sejumlah garis, simbol atau bentuk.

• Model Matematika
• Model matematika adalah semua rumus dan persamaan matematika yang digunakan oleh manajer untuk mengambil suatu keputusan

2. Keuntungan Pemodelan

• Proses pemodelan dapat menjadi sebuah pengalaman belajar bagi manajer
• Kecepatan proses simulasi memungkinkan sejumlah besar alternatif dimasukkan untuk dipertimbangkan karena simulasi memiliki kemampuan untuk mengevaluasi pengaruh dari sebuah keputusan dalam waktu singkat
• Model memiliki kemampuan untuk meramal atau memperkirakan masa depan. Kemampuan ini tidak dimiliki oleh metode-metode penghasil informasi lainnya
• Biaya penggunaan model jauh lebih murah daripada menggunakan  metode trial and error

3. Kerugian Pemodelan

• Kesulitan dalam pemodelan suatu sistem bisnis akan menghasilkan model yang tidak mampu menampung semua pengaruh terhadap entitas
• Diperlukan kemampuan yang tinggi dibidang matematika untuk menggunakan dan mengembangkan model yang lebih kompleks.

4. Artificial Intellegent

Adalah aktivitas dalam menyediakan alat atau mesin seperti komputer yang memiliki kemampuan untuk berperilaku cerdas dengan standar kecerdasan manusia

Operasi dan Hukum Himpunan Singkat

Operasi terhadap himpunan
1. Irisan

2. Gabungan

3. Komplemen

4. Selisih

5. Beda Setangkup

Hukum terhadap himpunan

Metoda Mengatasi Deadlock

Cara mengatasi deadlock :
A. Pencegahan deadlock (deadlock prevention)
1. Meniadakan mutual exclusion
Deadlock disebabkan terdapatnya  pengaksesan eksklusif sumber daya. Jika tidak ada sumber daya ekslusif ke satu proses tunggal, maka tidak pernah dijumpai deadlock. Cara yang ditempuh untuk mengganti pengaksesan eksklusif adalah dengan spooling sumber daya yaitu proses pengakesan sumber daya diantrikan di disk.

2. Mencegah hold and wait
Proses me-request seluruh sumber daya pada sekaligus dan proses terblock samapai seluruh permintaan terpenuhi. Proses ini tidak efisien karena :

• Proses menjadi lama karena menunggu semua  sumber daya yang diminta terpenuhi yang sebenarnya dapat dikerjakan hanya dengan beberapa sumber daya.
• Sumber daya yang sudah dialokasikan pada proses ini mungkin saja tidak langsung digunakan tetapi karena sudah dialokasikan tidak dapat dipakai oleh proses lain.

3. Mencegah no-preemption, dilakukan dengan alternatif:
Jika sebuah proses yang telah menggenggam (hold) sumber daya tidak diperbolehkan meminta (request) lagi sumber daya, proses harus melepaskan (release) sumber daya tersebut dulu jika diperlukan dapat juga meminta kembali sumber daya yang dilepaskan bersamaan dengan sumber daya tambahannya.
Jika proses meminta sumber daya yang sedang digenggam oleh proses lain, sistem operasi dapat menyela (preempt) proses yang menggenggam dengan meminta melepaskan sumber daya tersebut. Alternatif ini dapat dilakukan jika tidak ada dua proses yang memiliki prioritas yang sama. Contoh kasus ini adalah prosesor.

4. Mencegah Circular wait
Dapat dilakukan dengan mendefinisikan urutan linier dari jenis sumber daya. Jika proses telah dialokasikan pada sumber daya berjenis R maka urutan permintaan berikutnya dari proses tersebut adalah hanya yang berjenis R. Misal sumber daya Ri mendahului Rj dengan urutan i < j. Jika terdapat dua proses A dan B deadlock karena A telah memperoleh Ri dan meminta Rj dan B telah memperoleh Rj dan  meminta Ri. Kondisi ini tidak akan terjadi karena pada kasus ini  i < j dan juga j < I.

B. Pendeteksian dan pemulihan deadlock (deadlock detection and recovery)
Berbeda dengan Deadlock prevention, deadlock detection tidak membatasi akses sumber daya dan memberi larangan pada proses. Permintaan terhadap sumber daya akan diberikan jika memungkinkan

Pengecekan deadlock dilakukan setiap kali ada permintaan sumber daya. Pendeteksian deadlock ini menguntungkan karena algoritmanya mudah hanya  didasari perubahan state dan tidak mengkonsumsi waktu prosesor yang banyak.

Setelah dideteksi ada deadlock dilakukan beberapa strategi pemulihan berikut :

• Keluarkan seluruh proses yang mengalami deadlock.
• Salin setiap proses yang deadlock ke titik pengecekan yang telah didefinisikan sebelumnya dan mulai kembali dari awal seluruh proses. Resikonya deadlock bisa terjadi lagi tapi karena proses kongkurensi tidak menentu hal ini tidak terjadi.
• Sela (preempt) sumber daya sampai tidak ada deadlock.

C. Penghindaran deadlock (deadlock avoidance)
Pada metode ini keputusan dibuat dinamik untuk mengetahui apakah suatu permintaan sumber daya jika dipenuhi dapat menyebabkan deadlock atau tidak.
Dua pendekatan penghindaran deadlock:

• Jangan memulai proses jika proses tersebut akan menghasilkan deadlock
• Jangan penuhi permintaan penambahan sumber daya jika alokasi ini dapat menyebabkan proses jadi deadlock

Untuk mengetahui kondisi mendatang akan menyebabkan deadlock atau tidak digunakan langkah berikut
Process Initiation Denial
Misal terdapat n proses dan m jenis sumber daya. Didefinisikan dalam bentuk vektor dan matriks

Yang memiliki hubungan

• Sumber daya terdiri dari yang teralokasi dan yang available 
• Untuk semua k,Ck<= Resource Tidak ada proses yang meminta sumber daya melebihi jumlah yang ada 
• Untuk semua k,Ak<=Ck 

Jadi suatu proses akan dimulai hanya jika

Resource Allocation Denial

State : sumber daya yang sedang dialokasikan pada suatu proses

Safe state : state yang setidaknya memiliki satu urutan yang dapat menyebabkan seluruh proses selesai tanpa deadlock (Completion without deadlock)

Contoh safe state dengan total sumber daya R1 = 9, R2 = 3 dan R3 =6

Contoh unsafe state

Tidak ada sumber daya yang dapat dialokasikan agar proses selesai karena sumber daya yang available tidak mencukupi

Pengertian dan Kondisi Deadlock

Deadlock terjadi jika proses menunggu suatu kejadian tertentu yang tidak pernah terjadi. Sekumpulan proses berkondisi deadlock bila setiap proses yang ada di kumpulan menunggu suatu kejadian yang hanya dapat dilakukan proses lain yang juga berada di kumpulan itu.

Prinsip Deadlock:Deadlock dapat didefinisikan sebagai blocking permanen pada beberapa proses yang saling berkompetisi maupun berkomunikasi untuk memperoleh suatu sumber daya

Sumber daya dapat dikatagorikan secara umum menjadi:

1. Reusable resource

Didefinisikan sebagai :Sumber daya yang dapat digunakan dengan aman oleh satu proses pada suatu saat. Terdapat tiga kondisi perlakukan sumber daya oleh proses yaitu : request – hold – release.

Contoh reusable resource :

• Processor
• I/O channel
• Main memory dan secondary memory
• Device
• File
• Database
• Semaphore

Contoh deadlock yang melibatkan reusable resource

Misal terdapat dua proses yang berkompetisi untuk mengakses disk file (D) dan tape drive (T)

Deadlock terjadi jika masing-masing proses memegang (hold) sumber daya dan meminta (request) sumber daya yang lain yang dipegang oleh proses yang lain. Cara mengatasinya dengan memberi batasan pada disain sistem untuk perintah request (Constraint on design system).

2. Consumable resource

Merupakan sumber daya yang dapat dibuat atau dilenyapkan. Kondisi tidak terblock menghasilkan proses-proses yang siap melepaskan sumber daya saat suatu sumber daya diperlukan oleh sebuah proses sumber daya tersebut akan muncul.

Contoh consumable resource :

• interrupt
• sinyal
• message
• informasi dalam I/O buffer

Contoh Deadlock yang melibatkan consumable resource :

Deadlock terjadi jika pesan Recive terblock di salah satu proses.

Beberapa kondisi yang memungkinkan terjadinya deadlock:

• Mutual exclusion :hanya satu proses yang boleh menggunakan sebuah sumber daya pada suatu saat
• Hold and wait :suatu proses dapat mememegang (hold) sumber daya yang sebenarnya ditunggu-tunggu oleh proses lain
• No preemption :Tidak ada sumber daya yang dapat dipaksa lepas dari suatu proses yang memegangnya
• Circular wait :Rantai tertutup yang menyatakan suatu proses memegang sumber daya yang diperlukan oleh proses lain sehingga terjadi saling menunggu

Circular Wait

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

Istilah-Istilah Didalam Sistem Operasi

1. Kernel adalah suatu perangkat lunak yang menjadi bagian utama dari sebuah sistem operasi komputer, tugasnya yaitu melayani bermacam-macam program aplikasi untuk mengakses perangkat keras (hardware) komputer secara aman.
2. Buffer adalah area memori yang menyimpan data ketika mereka sedang dipindahkan antara dua perangkat atau antara perangkat dan aplikasi.
3. device dependent adalah perangkat keras komputer yang tidak dapat berdiri sendiri atau tidak dapat terintegrasi kedalam komputer tanpa adanya software pendukung dalam hal ini disebut driver.
4. Time-sharing adalah metode dimana banyak pengguna dapat melakukan processing dalam satu komputer.
5. Real Time System adalah sistem yang memiliki deadline/jangka waktu penyelesaian tertentu/ditentukan, namun tetap mengutamakan ketepatan dan performa yang tinggi dalam prosesnya.
6. Program Residen adalah program yang secara otomatis akan aktif (start) bersamaan dengan di-load nya OS. Program yang berada dalam memory (RAM) dan selalu stand by untuk digunakan sewaktu-waktu.
7. Floating-point atau bilangan titik mengambang, adalah sebuah format bilangan yang dapat digunakan untuk merepresentasikan sebuah nilai yang sangat besar atau sangat kecil.
8. Fetching merupakan peristiwa pengambilan perintah dan data yang diperlukan. Fetch merupakan proses mengambil atau membawa instruksi dari memori utama ke CPU.