sinkronisasi

A.   Pengertian

Merupakan suatu proses pengaturan jalannya beberapa proses pada waktu yang bersamaan untuk menyamakan waktu dan data supaya tidak terjadi inconsitensi (ketidak konsistenan) data akibat adanya akses data secara konkuren agar hasilnya bagus dan sesuai dengan apa yang diharapkan.
Disini sinkronisasi diperlukan agar data tersebut tetap konsisten.

Shared memory merupakan solusi ke masalah bounded-butter yang mengijinkan paling banyak n-1 materi dalam buffer pada waktu yang sama. Suatu solusi, jika semua N buffer digunakan tidaklah sederhana. Dimisalkan kita memdifikasi producer-consumer code dengan menambahkan suatu variable counter, dimulai dari 0 dan masing-masing waktu tambahan dari suatu item baru diberikan kepada buffer. 

B.   Masalah-masalah sinkronisasi

1.    Race Condition

Race Condition adalah situasi di mana beberapa proses mengakses dan memanipulasi data bersama pada saat besamaan. Nilai akhir dari data bersama tersebut tergantung pada proses yang terakhir selesai. Untuk mencegah race condition, proses-proses yang berjalan besamaan harus di disinkronisasi.Dalam beberapa sistem operasi, proses-proses yang berjalan bersamaan mungkin untuk membagi beberapa penyimpanan umum, masing-masing dapat melakukan proses baca (read) dan proses tulis (write). Penyimpanan bersama (shared storage) mungkin berada di memori utama atau berupa sebuah berkas bersama, lokasi dari memori bersama tidak merubah kealamian dari komunikasi atau masalah yang muncul. Untuk mengetahui bagaimana komunikasi antar proses bekerja, mari kita simak sebuah contoh sederhana, sebuah print spooler. Ketika sebuah proses ingin mencetak sebuah berkas, proses tersebut memasukkan nama berkas ke dalam sebuah spooler direktori yang khusus. Proses yang lain, printer daemon, secara periodik memeriksa untuk mengetahui jika ada banyak berkas yang akan dicetak, dan jika ada berkas yang sudah dicetak dihilangkan nama berkasnya dari direktori.

Ilustrasi Race Condition:

2.    Critical Section

Kunci untuk mencegah masalah ini dan di situasi yang lain yang melibatkan shared memori, shared berkas, and shared sumber daya yang lain adalah menemukan beberapa jalan untuk mencegah lebih dari satu proses untuk melakukan proses writing dan reading kepada shared data pada saat yang sama. Dengan kata lain kita memutuhkan mutual exclusion, sebuah jalan yang menjamin jika sebuah proses sedang menggunakan shared berkas, proses lain dikeluarkan dari pekerjaan yang sama. Kesulitan yang terjadi karena proses 2 mulai menggunakan variabel bersama sebelum proses 1 menyelesaikan tugasnya.

Masalah menghindari Race Conditions dapat juga diformulasikan secara abstrak. Bagian dari waktu, sebuah proses sedang sibuk melakukan

perhitungan internal dan hal lain yang tidak menggiring ke kondisi race conditions. Bagaimana pun setiap kali sebuah proses mengakses shared memory atau shared berkas atau melakukan sesuatu yang kitis akan menggiring kepada race conditions. Bagian dari program dimana shared memory diakses disebut Critical Section atau Critical Region.

Walau pun dapat mencegah race conditions, tapi tidak cukup untuk melakukan kerjasama antar proses secara pararel dengan baik dan efisien dalam menggunakan shared data. Kita butuh 4 kondisi agar menghasilkan solusi yang baik:

        I.            Tidak ada dua proses secara bersamaan masuk ke dalam critical section

      II.            Tidak ada asumsi mengenai kecepatan atau jumlah cpu

    III.            Tidak ada proses yang berjalan di luar critical secion yang dapat mengeblok proses lain

    IV.            Tidak ada proses yang menunggu selamamya untuk masuk critical section

Critical Section adalah sebuah segmen kode di mana sebuah proses yang mana sumber daya bersama diakses. Terdiri dari:

• Entry Section : kode yang digunakan untuk masuk ke dalam critical section
• Critical Section : Kode di mana hanya ada satu proses yang dapat dieksekusi pada satu waktu.
• Exit Section: akhir dari critical section, mengizinkan proses lain.
• Remainder Section : kode istirahat setelah masuk ke critical section

Critical Section harus melakukan ketiga aturan berikut:

Solusi yang diberikan harus memuaskan permintaaan berikut:

·         Mutual exclution

·         Deadlock free

·         Starvation free

Pendekatan yang mungkin untuk solusi proses sinkronisasi

I.                    Solusi Piranti lunak (Software solution)

-          Tanpa Sinkronisasi.

-          Dengan Sinkronisasi.

o   Low-level primitives: semaphore

o   High-level primitives: monitors

II.                  Solusi Piranti Keras (Hardware solution)

2.1   Mutual Exclusion

Mutual Exclusion: Kondisi-kondisi untuk solusi Tiga kondisi untuk menentukan mutual Exclusion

Ø  Tidak ada dua proses yang pada saat bersamaan berada di critical region.

Ø  Tidak ada proses yang berjalan diluar critical region yang bisa menghambat proses lain

Ø  Tidak ada proses yang tidak bisa masuk ke critical region

2.1.1 Solusi

Cara-cara memecahkan masalah

•  Hanya dua proses, Po dan P1

•  Struktur umum dari proses adalah Pi (proses lain Pj)

do {

critical section remainder section

} while(1);

2.1.1.1  Algoritma 1

Disini kita akan mencoba membuat sebuah rangkaian solusi-solusi dari permasalahan yang makin meningkat kerumitannya.

Pada semua contoh, i adalah proses yang sedang berjalan, j adalah proses yang lain. Pada contoh ini code.

i. Shared variables

·         int turn

initially turn=0

·         turn = i, Pi can enter its critical section

ii. Process Pi

do {

while(turn!=1);

critical section

turn=j;

remainder section

} while(1);

iii. Memenuhi mutual exclusion, tapi bukan progress.

2.1.1.2              Algoritma 2

FLAG untuk setiap proses yang memberi STATE:

Setiap proses memantau suatu flag yang mengindikasikan ia ingin memasuki critical section. Dia memeriksa flag poses lain dan tidak akan memasuki critical section bila ada proses lain yang sedang masuk.

i.  Shared variables                                                                                                                                                            

•  boolean flag[2];

initially flag [0] = flag [1] = false

•   flag [i] = true , Pi ready to enter its critical section

ii. Process Pi

do {

    flag[i]:=true;

    while(turn!=1);

    critical section

    turn=j;

    remainder section

} while(1);

iii. Memenuhi mutual exclusion, tapi tidak memenuhi progess.

2.1.1.3              Algoritma 3

FLAG untuk meminta izin masuk:

•  Setiap proses mengeset sebuah flag untuk meminta izin masuk. Lalu setiap proses mentoggle bit untuk mengizinkan yang lain untuk yang pertama

•  Kode ini dijalankan untuk setiap proses i

Shared variables

F boolean flag[2];

initially flag[0] = flag[1] = false

F flag[i]= true;

Pi ready to enter its critical section

i.                    Gabungan shared variables dari algorima 1 dan 2

ii.                  Process Pi

do {

flag[i]:=true;

           turn = j;

while(flag[j] and turn = j);

critical section             flag[i] = false;

    remainder section

} while(1);

iii.                Memenuhi ketiga persyaratan, memecahkan persoalan critical section untuk kedua proses

3.    Solusi Hardware pada Sinkronisasi

Disabling Interrupts: Hanya untuk uni prosesor saja.

Atomic test and set: Returns parameter and sets parameter to true atomically.

while (test_and_set(lock));

/* critical section */

lock = false;

GET_LOCK: IF_CLEAR_THEN_SET_BIT_AND_SKIP (bit_address) BRANCH GET_LOCK /* set failed   */

        /* set succeeded */

Harus hati-hati jika pendekatan ini untuk menyelesaikan bounded-buffer - harus menggunakan round robin - memerlukan kode yang dibuat di sekitar instruksi lock.

while (test_and_set(lock)); Boolean waiting[N];

int j; /* Takes on values from 0 to N - 1 */ Boolean key;

do {

    waiting[i] = TRUE;

    key = TRUE;

    while ( waiting[i] && key )

       key = test_and_set( lock ); /* Spin lock */

    waiting[i] = FALSE;

     /****** CRITICAL SECTION ********/

     j = ( i + 1 ) mod N;

     while ( ( j != i ) && ( ! waiting[ j ] ) )

     j = ( j + 1 ) % N;

     if ( j == i ) //Using Hardware   

        lock = FALSE; //Test_and_set.

     else

        waiting[ j ] = FALSE;

     /******* REMAINDER SECTION *******/

} while (TRUE);

4.    Semaphore

Jika kita ingin dapat melakukan proses tulis lebih rumit kita membutuhkan sebuah bahasa untuk melakukannya. Kita akhirnya medefinisikan semaphore yang kita asumsikan sebagai sebuah operasi atomik.

Semaphore adalah pendekatan yang diajukan oleh Djikstra, dengan prinsip bahwa dua proses atau lebih dapat bekerja sama dengan menggunakan penanda-penanda sederhana. Seperti proses dapat dipaksa berhenti pada suatu saat, sampai proses mendapatkan penanda tertentu itu. Sembarang kebutuhan koordinasi kompleks dapat dipenuhi dengan struktur penanda yang cocok untuk kebutuhan itu. Variabel khusus untuk penanda ini disebut semaphore.

Semaphore mempunyai dua sifat, yaitu:

i. Semaphore dapat diinisialisasi dengan nilai non-negatif.

ii. Terdapat dua operasi terhadap semaphore, yaitu Down dan Up. Usulan asli yang disampaikan Djikstra adalah operasi P dan V.

3.1 Operasi Down

Operasi ini menurunkan nilai semaphore, jika nilai semaphore menjadi non-positif maka proses yang mengeksekusinya diblocked.

Type Semaphore = Integer, Procedure Down(Var: semaphore);

Begin

s := s-1;

if s <= 0 Then

Begin

Tempatkan antrian pada antrian untuk semaphore s

Proses diblocked

           End;

       End;

Operasi Down adalah atomic, tak dapat diinterupsi sebelaum diselesaikan.menurunkan nilai, memeriksa nilai, menempatkan proses pada antrian dan memblocked sebagai instruksi tunggal. Sejak dimulai, tak ada proses alain yang dapat mengakses semaphore sampai operasi selesai atau diblocked.

           

           

            3.2 Operasi Up

Operasi Up menakkan nilai semaphore. Jika satu proses atau lebih diblocked pada semaphore itu tak dapat menyelesaikan operasi Down, maka salah satu dipilih oleh system dan menyelesaikan operasi Down-nya. Urutan proses yang dipilih tidak ditentukan oleh Djikstra, dapat dipilih secara acak.

Type Semaphore = Integer;

Procedure Down(Var: semaphore);

Begin

s := s + 1;

if s <= 0 Then

Begin

Pindahkan satu proses P dari antrian untuk semaphore s

Tempatkan proses P di senarai ready

End;

End;

Adanya semaphore  mempermudah  persoalan mutual exclusion. Skema penelesaian mutual exclusion mempunyai bagan sebagai berikut:                                     

Cons N = 2;

Var S:semaphore;

Procedure enter_critical_section;

{

mengerjakan kode-kode kritis

}

Procedure enter_noncritical_section;

{

mengerjakan kode-kode tak kritis

}

ProcedureProses(i: integer); Begin

Repeat Down(s); Enter_critical_section;

Up(s); Enter_noncritical_section; Forever

End;

Begin

   S:=1;

        Parbegin

     Proses(0);

     Proses(1);

        ParEnd;

End;

Sebelum masuk critical section, proses melakukan Down. Bila berhasil maka proses masuk ke critical section. Bila tidak berhasil maka proses di-blocked atas semaphore itu. Proses yang diblocked akan dapat melanjutkan kembali bila proses yang ada di critical section keluar dan melakukan opersai up sehingga menjadikan proses yang diblocked ready dan melanjutkan sehingga opersi Down-nya berhasil.

5.    Problem Klasik pada Sinkronisasi

Ada tiga hal yang selalu memjadi masalah pada proses sinkronisasi:

i. Problem Bounded buffer.

ii. Problem Reades and Writer.

iii. Problem Dining Philosophers.

5.1                 Bounded buffer

Kasus Producer – Consumer

Dua proses berbagi sebuah buffer dengan ukuran yang tetap. Salah satunya produser, meletakkan informasi ke buffer yang lainnya. Konsumen mengambil informasi dari buffer. Ini juga dapat digeneralisasi untuk masalah yang memiliki m buah produsen dan n buah konsumen, tetapi kita hanya akan memfokuskan kasus dengan satu produsen dan satu konsumen karena diasumsikan dapat menyederhanakan solusi. Masalah akan timbul ketika produsen ingin menaruh barang yang baru tetapi buffer sudah penuh. Solusi untuk produsen adalah istirahat (sleep) dan akan dibangunkan ketika konsumen telah mengambil satu atau lebih barang dari buffer. Biasanya jika konsumen ingin mengambil barang dari buffer dan melihat bahwa buffer sedang kosong, maka konsumen istirahat (sleep) sampai produsen meletakkan barang pada buffer dan membangunkan (wake up) consumer. Untuk mengetahui jumlah barang di buffer, kita membutuhkan sebuah variabel kita namakan count. Jika jumlah maksimum dairi barang yang dapat ditampung buffer adalah N, kode produser pertama kali akan mencoba untuk mengetahui apakah nilai count sama dengan nilai N. Jika itu terjadi maka produsen akan istirahat (sleep), tetapi jika nilai count tidak sama dengan N, produsen akan terus menambahkan barang dan menaikkan nilai count.

5.2                 Problem Readers-Writers

Problem lain yang terkenal adalah readers-writer problem yang memodelkan proses yang mengakses database. Sebagai contoh sebuah sistem pemesanan sebuah perusahaan penerbangan, dimana banyak proses berkompetisi berharap untuk membaca (read) dan menulis (write). Hal ini dapat diterima bahwa banyak proses membaca database pada saat yang sama, tetapi jika suatu proses sedang menulis database, tidak boleh ada proses lain yang mengakses database tersebut, termasuk membaca database tersebut.

Dalam solusi ini, pertama-tama pembaca mengakses database kemudian melakukan DOWN pada semaphore db.. Langkah selanjutnya readers hanya menaikkkan nilai sebuah counter. Hasil dari pembaca nilai counter diturunkan dan nilai terakhir dilakukan UP pada semaphore, mengizinkan memblok writer.

Misalkan selama sebuah reader menggunakan database, reader lain terus berdatangan. Karena ada dua reader pada saat bersamaan bukanlah sebuah masalah, maka reader yang kedua diterima, reader yang ketiga juga dapat diterima jika terus berdatangan reader-reader baru. Sekarang misalkan writer berdatangan terus menerus. Writer tidak dapat diterima ke database karena writer hanya bisa mengakses data ke database secara ekslusif, jadi writer ditangguhkan. Nanti penambahan reader akan menunjukkan peningkatan. Selama paling tidak ada satu reader yang aktif, reader berikutnya jika datang akan diterima. Sebagai konsekuensi dari strategi ini, selama terdapat suplai reader yang terus-menerus, mereka akan dilayani segera sesuai kedatanga mereka. Writer akan ditunda sampai tidak ada reader lagi. Jika sebuah reader baru tiba, katakan, setiap dua detik, dan masing-masing reader mendapatkan lima detik untuk melakukan tugasnya, writer tudak akan pernah mendapatkan kesempatan.  Untuk mencegah situasi seperti itu, program dapat ditulis agak sedikit berbeda: Ketika reader tiba dan writer menunggu, reader ditunda dibelakang writer yang justru diterima dengan segera. Dengan cara ini, writer tidak harus menunggu reader yang sedang aktif menyelesaikan pekerjaannya, tapi tidak perlu menunggu reader lain yang datang berturut-turut setelah itu.

5.3                 Problem Dining Philosopers

Pada tahun 1965, Djikstra menyelesaikan sebuah masalah sinkronisasi yang beliau sebut dengan dining philisophers problem. Dining philosophers dapat diuraikan sebagai berikut: Lima orang filosuf duduk mengelilingi sebuah meja bundar. Masing-masing filosof mempunyai sepiring spageti. Spageti-spageti tersebut sangat licin dan membutuhkan dua garpu untuk memakannya. Diantara sepiring spageti terdapat satu garpu.

Kehidupan para filosof terdiri dari dua periode, yaitu makan atau berpikir. Ketika seorang filosof lapar, dia berusaha untuk mendapatkan garpu kiri dan garpu kanan sekaligus. Jika sukses dalam mengambil dua garpu, filosof tersebut makan untuk sementara waktu, kemudian meletakkan kedua garpu dan melanjutkan berpikir.

Pertanyaan kuncinya adalah, dapatkah anda menulis program untuk masing-masing filosof yang melakukan apa yang harus mereka lakukan dan tidak pernah mengalami kebuntuan.

Prosedur take-fork menunggu sampai garpu-garpu yang sesuaididapatkan dan kemudian menggunakannya. Sayangnya dari solusi ini ternyata salah. Seharusnya lima orang filosof mengambil garpu kirinya secara bersamaan. Tidak akan mungkin mereka mengambil garpu kanan mereka, dan akan terjadi deadlock.

Kita dapat memodifikasi program sehingga setelah mengambil garpu kiri, program memeriksa apakah garpu kanan meungkinkan untuk diambil. Jika garpu kanan tidak mungkin diambil, filosof tersebut meletakkan kembali garpu kirinya, menunggu untuk beberapa waktu, kemudia mengulangi proses yang sama. Usulan tersebut juga salah, walau pun dengan alasan yang berbeda. Dengan sedikit nasib buruk, semua filosof dapat memulai algoritma secara bersamaan, mengambil garpu kiri mereka, melihat garpu kanan mereka yang tidak mungkin untuk diambil, meletakkan kembali garpu kiri mereka, menunggu, mengambil garpu kiri mereka lagi secara bersamaan, dan begitu seterusnya. Situasi seperti ini dimana semua program terus berjalan secara tidak terbatas tetapi tidak ada perubahan/kemajuan yang dihasilkan disebut starvation.

Sekarang anda dapat berpikir "jika filosof dapat saja menunggu sebuah waktu acak sebagai pengganti waktu yang sama setelah tidak dapat mengambil garpu kiri dan kanan, kesempatan bahwa segala sesuatau akan berlanjut dalam kemandegan untuk beberapa jam adalah sangat kecil." Pemikiran seperti itu adalah benar,tapi beberapa aplikasi mengirimkan sebuah solusi yang selalu bekerja dan tidak ada kesalahan tidak seperti hsk nomor acak yang selalu berubah.

Sebelum mulai mengambil garpu, seorang filosof melakukan DOWN di mutex. Setelah menggantikan garpu dia harus melakukan UP di mutex. Dari segi teori, solusi ini cukup memadai. Dari segi praktek, solusi ini tetap memiliki masalah. Hanya ada satu filosof yang dapat makan spageti dalam berbagai kesempatan. Dengan lima buah garpu, seharusnya kita bisa menyaksikan dua orang filosof makan spageti pada saat bersamaan.

Solusi yang diberikan diatas benar dan juga mengizinkan jumlah maksimum kegiatan paralel untuk sebuah jumlah filosf yang berubah-ubah ini menggunakan sebuah array, state, untuk merekam status seorang filosof apakah sedang makan (eating), berpikir (think), atau sedang lapar (hungry) karena sedang berusaha mengambil garpu. Seorang filosof hanya dapat berstatus makan (eating) jika tidak ada tetangganya yang sedang makan juga. Tetangga seorang filosof didefinisikan ole LEFT dan RIGHT. Dengan kata lain, jika i = 2, maka tetangga kirinya (LEFT) = 1 dan tetangga kanannya (RIGHT) = 3. Program ini menggunakan sebuah array dari semaphore yang lapar (hungry) dapat ditahan jika garpu kiri atau kanannya sedang dipakai tetangganya. Catatan bahwa masing-masing proses menjalankan prosedur filosof sebagai kode utama, tetapi prosedur yang lain seperti take-forks, dan test adalah prosedur biasa dan bukan proses-proses yang terpisah. berusaha mengambil garpu. Seorang filosof hanya dapat berstatus makan (eating) jika tidak ada tetangganya yang sedang makan juga. Tetangga seorang filosof didefinisikan ole LEFT dan RIGHT. Dengan kata lain, jika i = 2, maka tetangga kirinya (LEFT) = 1 dan tetangga kanannya (RIGHT) = 3. Program ini menggunakan sebuah array dari semaphore yang lapar (hungry) dapat ditahan jika garpu kiri atau kanannya sedang dipakai tetangganya. Catatan bahwa masing-masing proses menjalankan prosedur filosof sebagai kode utama, tetapi prosedur yang lain seperti take-forks, dan test adalah prosedur biasa dan bukan proses-proses yang terpisah.

6.    Monitors

Solusi sinkronisasi ini dikemukakan oleh Hoare pada tahun 1974. Monitor adalah kumpulan prosedur, variabel dan struktur data di satu modul atau paket khusus. Proses dapat memanggil prosedur-prosedur kapan pun diinginkan. Tapi proses tak dapat mengakses struktur data internal dalam monitor secara langsung. Hanya lewat prosedur-prosedur yang dideklarasikan minitor untuk mengakses struktur internal.

Properti-properti monitor adalah sebagai berikut:

i. Variabel-variabel data lokal, hanya dapat diakses oleh prosedur-prosedur dala monitor dan tidak oleh prosedur di luar monitor.

ii. Hanya satu proses yang dapat aktif di monitor pada satu saat. Kompilator harus mengimplementasi ini(mutual exclusion).

iii. Terdapat cara agar proses yang tidak dapat berlangsung di-blocked. Menambahkan variabel-variabel kondisi, dengan dua operasi, yaitu Wait dan Signal.

iv. Wait: Ketika prosedur monitor tidak dapat berkanjut (misal producer menemui buffer penuh) menyebabkan proses pemanggil diblocked dan mengizinkan proses lain masuk monitor.

v. Signal: Proses membangunkan partner-nya yang sedang diblocked dengan signal pada variabel kondisi yang sedang ditunggu partnernya.

vi. Versi Hoare: Setelah signal, membangunkan proses baru agar berjalan dan menunda proses lain.

vii. Versi Brinch Hansen: Setelah melakukan signal, proses segera keluar dari monitor. Dengan memaksakan disiplin hanya satu proses pada satu saat yang berjalan pada monitor, monitor menyediakan fasilitas mutual exclusion. Variabel-variabel data dalam monitor hanya dapat diakses oleh satu proses pada satu saat. Struktur data bersama dapat dilindungi dengan menempatkannya dalam monitor. Jika data pada monitor merepresentasikan sumber daya, maka monitor menyediakan fasilitas mutual exclusion dalam mengakses sumber daya itu

C.     Kesimpulan

Untuk mengatasi problem critical section dapat digunakan berbagai solusi software. Namun masalah yang akan timbul dengan solusi software adalah solusi software tidak mampu menangani masalah yang lebih berat dari critical section. Tetapi Semaphores mampu menanganinya, terlebih jika hardware yang digunakan mendukung maka akan memudahkan dalam menghadapi problem sinkronisasi.

Berbagai contoh klasik problem sinkronisasi berguna untuk mengecek setiap skema baru sinkronisasi. Monitor termasuk ke dalam level tertinggi mekanisme sinkronisasi yang berguna untuk mengkoordinir aktivitas dari banyak thread ketika mengakses data melalui pernyataan yang telah disinkronisasi.