Sistem Operasi

B. CRITICAL SECTION

Critical Section adalah bagian dari suatu proses yang akan melakukan akses dan manipulasi data.    Ketika sebuah proses sedang dijalankan dalam critical section nya, tidak ada proses lain yang boleh dijalankan dalam critical section tersebut, karena akan menyebabkan keadaan mutually exclusive.

Mutually exclusive yakni keadaan terjadinya akses resources yang sama di saat yang bersamaan. Mutually exclusive memerlukan kondisi tertentu agar dapat terpenuhi.

Critical section biasanya digunakan saat program multithreading, dimana program tersebut terdiri dari banyak thread, akan mengubah nilai dari variabel. Dalam hal ini critical section diperlukan untuk melindungi variabel dari concurrent access (pengaksesan program di saat yang bersamaan) yang dapat membuat nilai dari variabel tersebut menjadi tidak konsisten.

Seperti yang telah kita ketahui bahwa proses dapat bekerja sendiri (independent process) dan juga dapat bekerja bersama proses-proses yang lain (cooperating process). Pada umumnya ketika proses saling bekerjasama (cooperating process) maka proses-proses tersebut akan saling berbagi data. Pada saat proses-proses berbagi data, ada kemungkinan bahwa data yang dibagi secara bersama itu akan menjadi tidak konsisten dikarenakan

adanya kemungkinan proses-proses tersebut melakukan akses secara bersamaan yang menyebabkan data tersebut berubah, hal ini dikenal dengan istilah Race Condition.

Oleh karena itu, dibutuhkan solusi yang tepat untuk menghindari munculnya Race Condition. Solusi tersebut harus memenuhi ketiga syarat berikut:

Ada dua jenis solusi untuk memecahkan masalah critical section, yaitu.

Berikut ini algoritma-algoritma yang digunakan untuk mengatasi masalah critical section:

Algoritma I memberikan giliran kepada setiap proses untuk memproses critical section-nya secara bergantian.

Asumsi yang digunakan disini setiap proses secara bergantian memasuki critical section-nya.

Statement while(turn != 4) akan memeriksa apakah pada saat itu proses 4 mendapatkan turn, jika tidak maka proses 4 akan busy waiting(lihat kembali bahwa printah while diakhiri dengan “;”). Jika ternyata pada saat itu merupakan giliran proses 4 maka proses 4 akan mengerjakan critical section-nya. Sampai sini jelas terlihat bahwa mutex terpenuhi! Proses yang tidak mendapatkan turn tidak akan dapat mengerjakan critical section-nya dan turn hanya akan diberikan pada satu proses saja.

Setelah proses 4 selesai mengerjakan critical section maka turn diberikan pada proses lainnya (turn= j, j merupakan proses selanjutnya yang dapat mengerjakan critical section). Setelah turn-nya diberikan kepada proses lain, proses 4 akan mengerjakan remainder section.   Disini jelas terlihat bahwa syarat bounded waiting jelas terpenuhi. Ingat asumsi yang digunakan dalam algoritma ini adalah setiap proses secar bergantian memasuki critical section-nya, jika pada saat itu proses 4 ternyata belum mau mengerjakan critical section-nya maka proses ke-j tidak akan mendapatkan kesempatan untuk mengerjakan critical section walau saat itu sebenarnya proses ke-j akan memasuki critical section. Artinya syarat progress tidak terpenuhi pada algoritma ini.

Masalah yang terjadi pada algoritma 1 ialah ketika di entry section terdapat sebuah proses yang ingin masuk ke critical section, sementara di critical section sendiri tidak ada proses yang sedang berjalan, tetapi proses yang ada di entry section tadi tidak bisa masuk ke critical section. Hal ini terjadi karena giliran untuk memasuki critical section adalah giliran proses yg lain sementara proses tersebut masih berada di remainder section. Untuk mengatasi masalah ini maka dapat diatasi dengan merubah variabel trun pada algoritma pertama dengan array

Boolean flag [2];

Elemen array diinisialisasi false. Jika flag[i] true, nilai tersebut menandakan bahwa Pi ready untuk memasuki critical section. Pada algoritma ini. hal pertama yang dilakukan ialah mengeset proses Pi dengan nilai True, ini menandakan bahwa Pi ready untuk masuk ke critical section. kemudian, Pi memeriksa apakah Pj

tidak ready untuk memasukui critical section. Jika Pj ready, maka Pi menunggu sampai Pj keluar dari critical section (flag[j] bernilai false). Ketika keluar dari critcal section, Pi harus merubah nilai flag[i] menjadi false agar prores lain dapat memasuki critical section.

Contoh:

Pada algoritma ini, kriteria Mutual-exclusion terpenuhi, tetapi  tidak memenuhi kriteria

progress. Ilustrasinya seperti di bawah ini.

T0 : Po set flag [0] = true

T1 : Po set flag [1] = true

Dari ilustrasi diatas terlihat bahwa algoritma ini memungkinkan terjadinya nilai true untuk kedua proses, akibatnya tidak ada proses yang akan berhasil memasuki critical section.

Jadi untuk algoritma 2 masih terdapat kelemahan, seperti yang terjadi di atas.

Idenya berasal dari algoritma 1 dan 2. Algoritma 3 mengatasi kelemahan pada algoritma 1 dan 2 sehingga progres yang diperlukan untuk mengatasi critical section terpenuhi.

Algoritma III ditemukan oleh G.L. Petterson pada tahun 1981 dan dikenal juga sebagai Algoritma Petterson. Petterson menemukan cara yang sederhana untuk mengatur proses agar memenuhi mutual exclusion. Algoritma ini adalah solusi untuk memecahkan masalah critical section pada dua proses. Ide dari algoritma ini adalah menggabungkan variabel yang di- sharing pada Algoritma I dan Algoritma II, yaitu variabel turn dan variabel flag. Sama seperti pada Algoritma I dan II, variabel turn menunjukkan giliran proses mana yang diperbolehkan memasuki critical section dan variabel flag menunjukkan apakah suatu proses membutuhkan akses ke critical section atau tidak.

Awalnya flag untuk kedua proses diinisialisai bernilai false, yang artinya kedua proses tersebut tidak membutuhkan akses ke critical section. Kemudian jika suatu proses ingin memasuki critical section, ia akan mengubah flag-nya menjadi true (memberikan tanda bahwa ia butuh critical section) lalu proses tersebut memberikan turn kepada lawannya. Jika lawannya tidak menginginkan critical section (flag-nya false), maka proses tersebut dapat menggunakan critical section, dan setelah selesai menggunakan critical section ia akan mengubah flag-nya menjadi false. Tetapi apabila proses lawannya juga menginginkan critical section maka proses lawan-lah yang dapat memasuki critical section, dan proses tersebut harus menunggu sampai proses lawan menyelesaikan critical section dan mengubah flag-nya menjadi false.

Misalkan ketika P0 membutuhkan critical section, maka P0 akan mengubah flag[0] = true, lalu P0 mengubah turn= 1. Jika P1 mempunyai flag[1] = false, (berapapun nilai turn) maka P0 yang dapat mengakses critical section. Namun apabila P1 juga membutuhkan critical section, karena flag[1] = true dan turn= 1, maka P1 yang dapat memasuki critical section dan P0 harus menunggu sampai P1 menyelesaikan critical section dan mengubah flag[1] = false, setelah itu barulah P0 dapat mengakses critical section.

Bagaimana bila kedua proses membutuhkan critical section secara bersamaan? Proses mana yang dapat mengakses critical section terlebih dahulu? Apabila kedua proses (P0 dan P1) datang bersamaan, kedua proses akan menset masing-masing flag menjadi true (flag[0] = true dan flag[1] = true), dalam kondisi ini P0 dapat mengubah turn = 1 dan P1 juga dapat mengubah turn = 0. Proses yang dapat mengakses critical section terlebih dahulu adalah proses yang terlebih dahulu mengubah turn menjadi turn lawannya. Misalkan P0 terlebih dahulu mengubah turn= 1, lalu P1 akan mengubah turn= 0, karena turn yang terakhir adalah 0 maka P0-lah yang dapat mengakses critical section terlebih dahulu dan P1 harus menunggu.

Algoritma III memenuhi ketiga syarat yang dibutuhkan. Syarat progress dan bounded waiting yang tidak dipenuhi pada Algoritma I dan II dapat dipenuhi oleh algoritma ini karena ketika ada proses yang ingin mengakses critical section dan tidak ada yang menggunakan critical section maka dapat dipastikan ada proses yang bisa menggunakan critical section, dan proses tidak perlu menunggu selamanya untuk dapat masuk ke critical section.

Algoritma ini didasarkan pada algoritma penjadwalan yang biasanya digunakan oleh tukang roti, dimana urutan pelayanan ditentukan dalam situasi yang sangat sibuk. Algoritma ini dapat digunakan untuk memecahkan masalah critical section untuk n buah proses, yang diilustrasikan dengan n buah pelanggan. Ketika memasuki toko, setiap pelanggan menerima

sebuah nomor. Sayangnya, algoritma tukang roti ini tidak dapat menjamin bahwa dua proses (dua pelanggan) tidak akan menerima nomor yang sama. Dalam kasus di mana dua proses menerima nomor yang sama, maka proses dengan nomor ID terkecil yang akan dilayani dahulu. Jadi, jika Pi dan Pj menerima nomor yang sama dan i < j, maka Pi dilayani dahulu. Karena setiap nama proses adalah unik dan berurut, maka algoritma ini dapat digunakan untuk memecahkan masalah critical section untuk n buah proses.

Struktur data umum algoritma ini adalah

boolean choosing[n];

int number [n];

Awalnya, struktur data ini diinisialisasi masing-masing ke false dan 0, dan menggunakan notasi berikut:

– (a, b) < (c, d) jika a < c atau jika a= c dan b < d

– max(a0, …, an-1) adalah sebuah bilangan k, sedemikian sehingga k >= ai untuk
   setiap i= 0, …, n – 1

Dengan demikian, diketahui bahwa  Algoritma I dan II terbukti tidak dapat memecahkan masalah critical section untuk dua proses karena tidak memenuhi syarat progress dan bounded waiting. Algoritma yang dapat menyelesaikan masalah critical section pada dua proses adalah Algoritma III. Sedangkan untuk masalah critical section pada n-buah proses dapat diselesaikan dengan menggunakan Algoritma Tukang Roti.

• Keadaan proses: Keadaan mungkin, new ,ready ,running, waiting, halted, dan juga banyak lagi.
• Program counter: Counter mengindikasikan address dari perintah selanjutnya untuk dijalankan untuk ditambah code information pada kondisi apapun. Besertaan dengan program counter, keadaan/ status informasi harus disimpan ketika gangguan terjadi, untuk memungkinkan proses tersebut berjalan/bekerja dengan benar setelahnya.
• Informasi manajemen memori: Informasi ini dapat termasuk suatu informasi sebagai nilai dari dasardan batas register. tabel page/ halaman, atau tabel segmen tergantung pada sistem memori yangdigunakan oleh sistem operasi (ch 9).
• Informasi pencatatan: Informasi ini termasuk jumlah dari CPU dan waktu riil yang digunakan bataswaktu, jumlah akun, jumlah job atau proses, dan banyak lagi.
• Informasi status I/O: Informasi termasuk daftar dari perangkat I/O yang di gunakan pada proses ini,suatu daftar open file dan banyak lagi.
• PCB hanya berfungsi sebagai tempat menyimpan/gudang untuk informasi apapun yang dapatbervariasi dari prose ke proses.proses ini.
• CPU register: Register bervariasi dalam jumlah dan jenis, tergantung pada rancangan komputer.Register tersebut termasuk accumulator, index register, stack pointer, general-puposes register.

1. Identifier proses
2. Identifier proses yang menciptakan
3. Identifier pemakai

• Register-register yang terlihat pemakai yaitu Register-register yang dapat ditunjuk instruksi bahasa assembly untuk diproses pemroses
• Register-register kendali dan status yaitu Register-register yang digunakan untuk mengendalikan operasi pemroses, a.l.:

1. Program counter
2. PSW, dsb.

• Pointer stack yaitu Tiap proses mempunyai satu stack atau lebih. Stack digunakan untuk parameter atau alamat prosedur pemanggil dan system call. Pointer stack menunjuk posisi paling atas dari stack

• Informasi penjadwalan dan status yaitu Informasi-informasi yang dipakai untuk menjalankan fungsi penjadwalan a.l :

1. Status proses. Mendefinisikan status proses (running,ready,block, dsb)
2. Prioritas. Menjelaskan prioritas proses
3. Informasi berkaitan penjadwalan. Informasi ini seperti lama menunggu, lama proses terakhir dieksekusi dsb.
4. Kejadian (Event). Identitas kejadian yang ditunggu proses

• Penstrukturan data yaitu Suatu proses dapat dikaitkan dengan proses lain dalam satu antrian atau ring, atau struktur lainnya. PCB harus memiliki pointer untuk mendukung struktur ini.
• Komunikasi antar proses yaitu Beragam flag, sinyal dan pesan dapat diasosiasikan dengan komunikasi antara dua proses yang terpisah. Informasi ini disimpan dalam PCB
• Kewenangan proses yaitu Proses dapat mempunyai kewenangan berkaitan dengan memori dan tipe instruksi yang dapat dijalankan
• Manajemen memori Bagian ini berisi pointer ke tabel segmen atau page yang menyatakan memori virtual proses
• Kepemilikan dan utilisasi sumber daya yaitu Sumber daya yang dikendalikan proses harus diberi tanda, misalnya :

1. Berkas yang dibuka
2. Pemakaian pemroses
3. Pemakaian sumberdaya lainnya

    Thread adalah unit dasar dari utilitas CPU. Di dalamnya terdapat ID thread, program counter, register, dan stack. Dan saling berbagi dengan thread lain dalam proses yang sama.

Keuntungan memakai Thread:
* Tanggap: Multi-threading mengizinkan program untuk terus berjalan walaupun pada bagian program tersebut diblock atau sedang dalam keadaan menjalankan operasi yang lama/panjang. Contohnya multithread web browser dapat mengizinkan pengguna berinteraksi dengan suatu thread ketika suatu gambar sedang diload oleh thread yang lain.

* Pembagian sumber daya: Secara default, thread membagi memori dan sumber daya dari proses. Keuntungan dari pembagian kode adalah aplikasi mempunyai perbedaan aktifitas thread dengan alokasi.

* Ekonomis: Mengalokasikan memori dan sumber daya untuk membuat proses itu sangat mahal. Alternatifnya thread membagi sumber daya dari proses, Jadi lebih ekonomis.

* Pemberdayaan arsitektur multiprosesor: Keuntungann dari multithreading dapat ditingkatkan dengan arsitektur multiprosesor, dimana setiap thread dapat berjalan secara parallel pada prosesor yang berbeda. Pada arsitektur prosesor tunggal, CPU biasanya berpindah-pindah antara setiap thread dengan cepat, sehingga terdapat ilusi paralelisme, tetapi pada kenyataannya hanya satu thread yang berjalan di setiap waktu.

Selain itu :

1. User thread adalah pengelolaan thread yang dilakukan oleh user level (pengguna)

2. Kernel thread adalah pengelolaan thread yang dilakukan oleh kernel komputer sehingga user tidak dapat menginterupsi.

Macam-macam Thread

Single threading : proses hanya mengeksekusi satu thread dalam satu waktu.

Multi-threading : proses dapat mengeksekusi sejumlah thread dalam satu waktu.

Contoh program yang menggunakan thread:
berikut ini adalah contoh program yang menggunakan thread. program berikut ini adalah program simulai balapan dari 5 peserta sebanyak 2 putaran, lalu pada akhir program akan mencetak siapa juara 1, 2, dan 3. pada program berikut ini menggunakan thread sebanyak 6, yaitu 5 thread untuk peserta, yang berisi pertambahan jarak yang dicapai peserta dan status juara jika sudah mencapai finish. dan satu lagi thread untuk mencetak posisi peserta. pada fungsi print menggunakan metode clear lalu print lagi, dan seterusnya sampai kelimanya mencapai finish, agar terlihat seperti balapan sungguhan.

Referensi

http://budysatria2.blogspot.com/2015/03/pengantar-sistem-operasi.html

https://mediekaputra.wordpress.com/2011/03/26/critical-section/

https://uniquesciences.wordpress.com/2012/10/04/process-control-block-pcb/

https://id.wikipedia.org/wiki/Handheld_computer

http://javaniy.blogspot.com/2014/11/thread-dan-contoh-pengaplikasiannya.html