Pengembangan Tentang Sinkronisasi Yang Terdapat Pada Sistem Operasi

 1.1    Konsep Dasar Sinkronisasi

        Sinkronisasi diperlukan untuk menghindari terjadinya ketidak konsistenan data akibat adanya akses data secara konkuren. Untuk menjaga kekonsistenan data tersebut, diperlukan adanya suatu mekanisme untuk memastikan urutan pengaksesan suatu data yang saling bekerjasama
Sehingga terjadi sinkronisasi.

Masalah - masalah yang dapat timbul bila sinkronisasi tidak diterapkan :

• Masalah Bounded - Buffer
• Race Condition
  

 

1.2    Race Condition
        Race condition yaitu situasi dimana beberapa proses mengakses dan memanipulasi suatu data secara konkuren. Nilai akhir dari data tersebut tergantung dari proses mana yang terakhir selesai dieksekusi.

Untuk menghindari terjadinya situasi tersebut, semua proses yang dapat mengakses suatu data tertentu harus disinkronisasi.

 

1.3    Problem Critical Section

        Suatu system terdiri dari n proses dimana semuanya berkompetisi menggunakan data yang digunakan bersama-sama. Masing - masing proses mempunyai sebuah kode segmen yang disebut dengan critical section, dimana proses memungkinkan untuk mengubah variable umum, mengubah sebuah tabel, menulis file dan lain sebagainya. Gambaran penting dari system adalah, ketika sebuah proses dijalankan di dalam critical section, tidak ada proses lain yang diijinkan untuk menjalankan critical section-nya. Sehingga eksekusi dari critical section oleh proses - proses tersebut berlaku eksklusif (mutually exclusive). Permasalahan critical section digunakan untuk mendesain sebuah Protocol dimana proses-proses dapat bekerjasama. Masing-masing proses harus meminta ijin untuk memasuki critical section-nya. Daerah kode yang Mengimplementasikan perintah ini disebut daerah entry. Critical section biasanya diikuti oleh daerah exit. Kode pengingat terletak di daerah remainder.

Sebuah solusi dari permasalahan critical section harus memenuhi 3 syarat sebagai berikut :

1. Mutual Exclusion. Apabila proses Pi menjalankan critical section-nya, maka tidak ada proses lain yang dapat menjalankan critical section.
2. Progress. Apabila tidak ada proses yang menjalankan critical section-nya dan terdapat beberapa proses yang akan memasuki critical section-nya, maka hanya proses - proses itu yang tidak diproses di dalam daerah pengingat (remainder) dapat ikut berpartisipasi di dalam keputusan proses mana yang akan memasuki critical section selanjutnya, dan pemilihan ini tidak dapat ditunda tiba-tiba.
3. Bounded Waiting. Terdapat batasan jumlah waktu yang diijinkan oleh proses lain untuk memasuki critical section setelah sebuah proses membuat permintaan untuk memasuki critical section-nya dan sebelum permintaan dikabulkan.

        Asumsi bahwa masing - masing proses dijalankan pada kecepatan bukan nol (nonzero). Akan tetapi tidak ada asumsi mengenai kecepatan relative dari proses ke n.

        Pemecahan masalah critical section tidak mengandalkan semua asumsi tentang instruksi hardware atau jumlah prosessor dari hardware yang mendukung. Akan tetapi, di asumsikan bahwa instruksi dasar bahasa mesin ( instruksi primitif, misalnya load, store dan test) dijalankan secara otomatis. Sehingga apabila dua instruksi dijalankan bersama - sama, hasilnya ekuivalen dengan deret eksekusi dalam beberapa pesanan yang tidak diketahui. Sehingga apabila perintah load dan store dijalankan bersama-sama, perintah load akan mempunyai nilai lama atau nilai baru, tetapi tidak kombinasi dari kedua perintah itu.

        Ketika mengimplementasikan suatu algoritma, kita menentukan dahulu hanya variable - variabel yang digunakan untuk keperluan sinkronisasi dan menggambarkan hanya proses Pi seperti struktur seperti Gambar 5-1. Entry section dan exit section didalam kotak untuk menunjukkan segmen kode yang penting. Proses – proses kemungkinan menggunakan variabel-variabel umum untuk sinkronisasi kegiatannya.

Gambar 5-1 : Struktur umum dari proses Pi

 

1.4    Persyaratan
 

        Solusi untuk memecahkan masalah critical section adalah dengan mendesain sebuah protocol dimana proses-proses dapat menggunakannya secara bersama - sama. Setiap proses harus 'meminta izin' untuk memasuki critical section-nya. Bagian dari kode yang mengimplementasikan izin ini disebut entry section. Akhir dari critical section itu disebut exit section. Bagian kode selanjutnya disebut remainder section.

Solusi dari masalah critical section harus memenuhi tiga syarat berikut [Silbeschatz 2004] :
1.    Mutual Exclusion.

        Jika suatu proses sedang menjalankan critical section-nya, maka proses-proses lain tidak dapat menjalankan critical section mereka. Dengan kata lain, tidak ada dua proses yang berada di critical section pada saat yang bersamaan. 

2.    Terjadi kemajuan (progress).

        Jika tidak ada proses yang sedang menjalankan critical section-nya dan ada proses-proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang yang sedang berada dalam entry section saja yang dapat berkompetisi untuk mengerjakan critical section. 

3.    Ada batas waktu tunggu (bounded waiting).

Jika seandainya ada proses yang sedang menjalankan critical section, maka proses lain memiliki waktu tunggu yang ada batasnya untuk menjalankan critical section-nya, sehingga dapat dipastikan bahwa proses tersebut dapat mengakses critical section-nya ( tidak mengalami starvation: proses seolah – olah berhenti, menunggu request akses ke critical section diperbolehkan ) .

1.5    Pemecahan masalah Critical Section 

        Berikut akan di perlihatkan algoritma untuk pemecahan masalah critical section. Setiap algoritma menggunakan dua proses dan dianggap berjalan secara concurrent / bersamaan. Ada dua jenis solusi masalah critical section, yaitu:

1. Solusi Perangkat Lunak. Dengan menggunakan algoritma - alogoritma yang nilai kebenarannya tidak tergantung pada asumsi – asumsi lain, selain bahwa setiap proses berjalan pada kecepatan yang bukan nol.
2. Solusi Perangkat Keras. Tergantung pada beberapa instruksi mesin tertentu, misalnya dengan me-non-aktifkan interupsi atau dengan mengunci suatu variable tertentu.

            Untuk jelasnya, ketika menyatakan Pi, kita gunakan Pj untuk menyatakan proses yang lain, dimana j = 1 – i.

1.    Algoritma 1

Pendekatan pertama adalah memperbolehkan semua proses menggunakan variable integer turn diinisialisasi ke 0 (atau 1). int turn;

Apabila turn = i, maka proses Pi diijinkan untuk menjalankan critical section – nya.
Struktur dari proses Pi  adalah sebagai berikut :

    do {
            while (turn != i) ;
                critical section
            turn = j;
                reminder section
    } while (1);

Pemecahan ini menjamin hanya satu proses pada satu waktu yang dapat berada di critical section. Tetapi hal ini tidak memuaskan kebutuhan progress, karena hal ini membutuhkan proses lain yang tepat pada eksekusi dari critical section. Sebagai contoh, apabila turn=0 dan P1 siap untuk memasuki critical section, P1  tidak dapat melakukannya, meskipun P0 mungkin di dalam remainder section – nya.

2.    Algoritma 2

Kelemahan dengan algoritma 1 adalah tidak adanya informasi yang cukup tentang state dari masing-masing proses. Untuk mengatasi masalah ini dilakukan penggantian variabel turn dengan array boolean flag[2];

Inisialisasi awal flag [0] = flag [1] = false. Apabila flag[i] bernilai true, nilai ini menandakan bahwa Pi siap untuk memasuki critical section.
Struktur dari proses Pi adalah sebagai berikut :
 

    do {
            flag[i] := true;
                    while (flag[j]) ;
            critical section
                    flag [i] = false;
            remainder section
     } while (1);

Pemecahan ini menjamin mutual exclusion, tetapi masih belum memenuhi progress .


3.    Algoritma 3

        Algoritma ini merupakan kombinasi algoritma 1 dan algoritma 2. Harapannya akan didapatkan solusi yang benar untuk masalah critical-section, dimana proses ini menggunakan dua variabel : int turn; boolean flag[2];
Inisialisasi flagI[0] = flag[1] = false dan nilai dari turn bernilai 0 atau 1. Struktur dari proses Pi adalah :

    do {
            flag [i]:= true;
                    turn = j;
            while (flag [j] and turn = j) ;
                    critical section
            flag [i] = false;
                    remainder section
    } while (1);

Algoritma ketiga ini memenuhi ketiga kebutuhan diatas yaitu mutual exclusion, progress dan bounded waiting dan memecahkan permasalahan critical section untuk dua proses.

Algoritma Tukang Roti

Diperkenalkan pertama kali oleh Leslie Lamport.

          Algoritma ini didasarkan pada algoritma penjadualan yang biasanya digunakan oleh tukang roti, di mana 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. 

        Sebelum memasuki critical section, setiap proses menerima sebuah nomor. Proses yang memegang nomor terkecil dapat masuk ke dalam critical section.
Jika proses Pi dan Pj menerima nomor yang sama, jika i < j, maka Pi dilayani dahulu, dan sebaliknya jika i > j, maka Pj dilayani dahulu. Dengan kata lain, yang memegang ID terkecil yang dilayani dahulu.

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

contoh 20.6. Algoritma Tukang Roti  

do {
choosing[i] = true;
number[i] = max(number[0], number [1], ..., number [n+1])+1;
choosing[i] = false;
for (j=0; j < n; j++) {
          while (choosing[j]);
          while ((number[j]!=0) && ((number[j],j) < number[i],i)));
     }
<foreignphrase>critical section</foreignphrase>
number[i] = 0;
<foreignphrase>remainder section</foreignphrase>
}while (1);