Problema Critical Section serta Penjadwalan Preemptive dan Non Preemptive

Problema Critical Section

Pengertian Critical Section

critical section adalah dengan mendesain sebuah protokol di mana 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.

Struktur umum dari proses Pi yang memiliki segmen critical section adalah :

Struktur umum dari proses Pi adalah:

do {

               entry section

                  critical section

               exit section

                  remainder section

            } while (1);

        

Solusi dari masalah critical section harus memenuhi tiga syarat berikut:

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).

Solusi Untuk Dua Proses

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 variabel tertentu

Selanjutnya akan dibahas sebuah algoritma sebagai solusi masalah dari critical section yang memenuhi tiga syarat seperti yang telah disebutkan di atas. Solusi ini tidak tergantung pada asumsi mengenai instruksi-instruksi perangkat keras atau jumlah prosesor yang dapat didukung oleh perangkat keras. Namun, kita mengasumsikan bahwa insruksi bahasa mesin yang dasar (instruksi-instruksi primitif seperti load, store, dan test) dieksekusi secara atomik. Artinya, jika dua instruksi tersebut dieksekusi secara konkuren, hasilnya ekuivalen dengan eksekusi instruksi tersebut secara sekuensial dalam urutan tertentu. Jadi, jika load dan store dieksekusi secara konkuren, load akan mendapatkan salah satu dari nilai yang lama atau nilai yang baru, tetapi tidak kombinasi dari keduanya.

Alogoritma I

Pada algoritma 1, variabel yang digunakan bersama (shared variabel) adalah sebuah variabel integer turn, yang diinisialisasi awal nilai 0 (atau 1 di proses yang kedua). Jika turn == i, maka proses Pi diizinkan untuk mengeksekusi critical sectionnya.

Algoritma ini menjamin bahwa hanya ada satu proses pada suatu saat yang berada di critical section. Namun, algoritma ini tidak memenuhi syarat terjadinya kemajuan, karena algoritma ini membutuhkan pergiliran proses di dalam menjalankan critical section. Misalnya, jika turn == 0 dan P1 ingin masuk ke critical section, P1 tidak dapat masuk, meskipun P0 sedang berada di remainder section. Hal ini dikarenakan P0 belum masuk ke critical section. dan oleh karenanya P0 belum mengubah nilai turn (menjadi turn == 1.)

            

/**     * Program ini sesuai dengan solusi critical section dengan     * menggunakan algoritma 1.     * Disadur dari  buku Silberschatz dkk,     * Applied Operating Systems Concepts, 2000.     */    public class Algoritma_1 extends MutualExclusion    {       public Algoritma_1() {          turn = TURN_0;       }        public void masukCriticalSection(int t) {          while (turn != t)             Thread.yield();       }       public void keluarCriticalSection(int t) {          turn = 1 - t;       }       private volatile int turn;    }

Algoritma 2

Kelemahan algoritma 1 adalah bahwa algoritma 1 tidak menyediakan informasi yang cukup mengenai keadaan state setiap proses, ia hanya mengingat proses mana yang diperbolehkan untuk memasuki critical section. Untuk memecahkan masalah ini, variabel turn diganti dengan sebuah array, yaitu:

boolean flag[2];

Setiap elemen dari array tersebut diinisialisasi awal ke false. Jika flag[i] bernilai true, maka ini mengindikasikan bahwa Pi siap untuk masuk ke critical section. Setiap proses memantau suatu flag yang mengindikasikan ia ingin memasuki critical section. Dia memeriksa flag proses lain dan tidak akan memasuki critical section bila ada proses lain yang sedang masuk.

/**     * Program ini sesuai dengan solusi critical section dengan     * menggunakan algoritma 2.     * Disadur dari  buku Silberschatz dkk,     * Applied Operating Systems Concepts, 2000.     */    public class Algoritma_2 extends MutualExclusion    {       public Algoritma_2() {          flag[0] = false;          flag[1] = false;       }       public void masukCriticalSection(int t) {          int other;             other = 1 - t;          flag[t] = true;                while (flag[other] == true)             Thread.yield();       }       public void keluarCriticalSection(int t) {          flag[t] = false;       }       private volatile boolean[] flag = new boolean[2];    }

Di algoritma 2 ini, proses Pi pertama-tama mengubah nilai(set) flag[i] menjadi true, menandakan bahwa Pi mau masuk ke critical section. Kemudian Pi mengecek apakah proses Pj juga mau masuk kecritical section. Jika proses Pj mau masuk, maka proses Pi akan menunggu sampai proses Pj mengubah statenya bahwa ia tidak mau lagi masuk ke critical section (flag[j] == false). Pada saat itu, maka Pi akan masuk ke critical section. Ketika keluar dari critical section, Pi akan mengset nilai flag[i] menjadi                 false, memperbolehkan proses lain (jika ada proses lain yang menunggu) untuk masuk ke critical section.

Solusi dengan algoritma 2 ini memenuhi syarat mutual exclusion, tetapi tidak memenuhi syarat terjadinya kemajuan. Untuk mengilustrasikan masalah ini, perhatikan urutan eksekusi berikut:

T0: P0 sets flag[0] true                   T1: P1 sets flag[1] true

Sekarang P0 dan P1 akan loop selama-lamanya di dalam statement while masing-masing. Perhatikan bahwa mengubah urutan instuksi untuk mengset flag[i] dan mengecek nilai flag[j] tidak akan memecahkan masalah ini. Kita malah akan berada di situasi di mana ada kemungkinan untuk kedua proses berada dicritical section pada saat yang bersamaan, yang akan melanggar syarat mutual exclusion.

Algoritma 3

Dengan menggabungkan algoritma 1 dan algoritma 2, kita akan memperoleh solusi yang tepat untuk masalahcritical section, di mana solusi itu akan memenuhi tiga syarat seperti yang telah disebutkan di atas. Setiap proses menggunakan dua variabel:

boolean flag[2];                   int turn;

Awalnya flag[0] = flag[1] = false, dan nilai turn tergantung dari proses yang boleh masuk (0 atau 1). Untuk masuk ke critical section, proses Pi pertama-tama mengset flag[i] menjadi true, dan kemudian mengset nilai turn menjadi j, sehingga memperbolehkan proses lain yang ingin masuk ke critical section untuk dapat masuk ke critical section. Jika kedua proses mencoba untuk masuk ke critical section pada saat yang bersamaan, turn akan diset ke nilai i dan j pada saat yang hampir bersamaan. Yang terakhir mengubah nilai turn akan mempersilakan proses yang lainnya untuk masuk ke critical section.

/**     * Program ini sesuai dengan solusi critical section dengan     * menggunakan algoritma 3.     * Disadur dari  buku Silberschatz dkk,     * Applied Operating Systems Concepts, 2000.     */    public class Algoritma_3 extends MutualExclusion    {       public Algoritma_3() {          flag[0] = false;          flag[1] = false;          turn = TURN_0;       }       public void masukCriticalSection(int t) {          int other;          other = 1 - t;             flag[t] = true;          turn = other;          while ( (flag[other] == true) && (turn == other) )             Thread.yield();       }       public void keluarCriticalSection(int t) {          flag[t] = false;       }       private volatile int turn;       private volatile boolean[] flag = new boolean[2];    }

Solusi Untuk Proses Jamak: Algoritma Tukang Roti

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. 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

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);

1.      NON PREEMPTIVE

Nonpreemptive multitasking adalah gaya komputer multitasking di mana sistem operasi tidak pernah memulai context switch dari proses yang berjalan kepada proses lain. Sistem seperti ini baik statis dijadwalkan, paling sering sistem periodik, atau menunjukkan beberapa bentuk koperasi multitasking, dalam hal ini tugas-tugas komputasi yang dapat menyela diri dan secara sukarela memberikan kontrol kepada tugas-tugas lain. Ketika memesan efek terlebih dahulu tidak digunakan, proses yang menerima sumber daya tersebut tidak dapat terganggu sampai selesai.

Koperasi multitasking adalah jenis multitasking di mana saat ini mengendalikan proses CPU harus menawarkan kontrol untuk proses lainnya. Hal ini disebut "koperasi" karena semua program harus bekerjasama agar ini bekerja. Sebaliknya, preemptive multitasking aplikasi menyela dan memberikan kontrol ke proses lain di luar kontrol aplikasi.

Program yang berjalan dibawah sistem operasi non-preemptive harus khusus ditulis untuk bekerja sama dalam multitasking oleh kontrol menghasilkan prosesor pada interval yang sering. Program yang tidak menghasilkan cukup sering menyebabkan sistem non-preemptive untuk tetap "terkunci" dalam program yangdatang tidak menghasilkan. Contoh gagal non-preemptive multitasking adalah ketidak mampuan untuk melakukan hal lain saat mencetak dokumen di Microsoft Word for Windows 2.0a. Hal ini terjadi karena firman tidak menyerah kontrol prosesor cukup sering saat mencetak dokumen Anda. Kasus terburuk dari program tidak menghasilkan adalah ketika sebuah crash program. Kadang-kadang, program yang crash di Windows 3.1 akan crash keseluruhan sistem hanya karena tidak ada tugas-tugas lain dapat menjalankan sampai jatuh hasil program. 

2.      PREENTIVE

Dalam komputasi, preemption (kadang pre-emption) adalah tindakan sementara mengganggu tugas yang sedang dilakukan oleh sistem komputer, tanpa memerlukan kerjasama, dan dengan maksud melanjutkan tugas di lain waktu. Perubahan seperti ini dikenal sebagai context switch. Hal ini biasanya dilakukan oleh tugas istimewa atau bagian dari sistem yang dikenal sebagai preemptive scheduler, yang memiliki kekuatan untuk mendahului, atau mengganggu, dan kemudian melanjutkan, tugas-tugas lain dalam sistem. 

Istilah preemptive multitasking digunakan untuk membedakan sistem operasi multitasking, yang memungkinkan preemption tugas, dari sistem multitasking koperasi dimana proses atau tugas harus secara eksplisit diprogram untuk menghasilkan ketika mereka tidak membutuhkan sumber daya sistem.

 Dalam hal sederhana: Preemptive multitasking melibatkan penggunaan mekanisme interupsi yang menunda proses yang sedang dijalankan dan memanggil scheduler untuk menentukan proses harus melaksanakan berikutnya. Oleh karena itu semua proses akan mendapatkan beberapa jumlah waktu CPU pada suatu waktu tertentu. 

Pada preemptive multitasking, kernel sistem operasi juga dapat memulai konteks sebuah saklar untuk memenuhi kendala prioritas kebijakan penjadwalan, dengan demikian preempting tugas aktif.Secara umum, preemption berarti "penyitaan sebelumnya". Ketika tugas prioritas tinggi pada contoh yang merebut tugas yang sedang berjalan, ini dikenal sebagai penjadwalan preemptive.

 Istilah "preemptive multitasking" kadang-kadang keliru digunakan ketika arti yang diinginkan lebih spesifik, mengacu bukan untuk kelas yang dikenal sebagai kebijakan penjadwalan penjadwalan waktu bersama, atau time-sharing. 

Preemptive multitasking memungkinkan sistem komputer untuk lebih andal menjamin setiap proses "slice" biasa waktu operasi.Hal ini juga memungkinkan sistem untuk cepat menangani peristiwa eksternal penting seperti data yang masuk, yang mungkin memerlukan perhatian segera dari satu atau proses lain. 
Pada setiap waktu tertentu, proses dapat dikelompokkan menjadi dua kategori: yang sedang menunggu untuk input atau output (disebut "I / O terikat"), dan mereka yang sepenuhnya menggunakan CPU ("CPU terikat"). Dalam sistem awal, proses sering akan "jajak pendapat", atau "busywait" sambil menunggu input diminta (seperti disk, keyboard atau input jaringan). Selama ini, proses tersebut tidak melakukan pekerjaan yang berguna, namun masih terjaga kontrol dari CPU. Dengan munculnya interrupt dan preemptive multitasking, ini I / O proses terikat bisa "diblokir", atau ditunda, sambil menunggu kedatangan data yang diperlukan, yang memungkinkan proses-proses lain untuk menggunakan CPU. Sebagai kedatangan data yang diminta akan menghasilkan interrupt, diblokir proses dapat jaminan kembali tepat waktu untuk eksekusi. 
Meskipun teknik multitasking pada awalnya dikembangkan untuk mengijinkan beberapa pengguna untuk berbagi satu mesin, segera menjadi jelas bahwa multitasking berguna terlepas dari jumlah pengguna. Banyak sistem operasi, dari mainframe ke single-user komputer pribadi dan sistem kontrol tidak ada pengguna-(seperti di pesawat ruang angkasa robot), telah mengakui manfaat multitasking dukungan untuk berbagai alasan.Multitasking memungkinkan pengguna tunggal untuk menjalankan beberapa aplikasi pada saat yang sama, atau untuk menjalankan "latar belakang" dengan tetap mengontrol proses komputer. 

Periode waktu yang suatu proses diperbolehkan untuk dijalankan dalam sistem preemptive multitasking umumnya disebut potongan waktu, atau kuantum. The scheduler dijalankan sekali setiap irisan waktu untuk memilih proses selanjutnya untuk menjalankan. Jika irisan waktu terlalu pendek maka penjadwal akan memakan waktu proses terlalu banyak. 

Interrupt dijadwalkan untuk memungkinkan kernel sistem operasi untuk beralih di antara proses-proses ketika irisan waktu mereka berakhir, efektif sehingga waktu prosesor untuk dibagi antara sejumlah tugas, memberikan ilusi bahwa berurusan dengan tugas-tugas secara bersamaan, atau secara bersamaan. Sistem operasi yang mengontrol desain seperti ini disebut sistem multi-tasking. 

Sistem pendukung preemptive multitasking 

Hampir semua sistem operasi mendukung preemptive multitasking, termasuk versi terbaru Windows, Mac OS, Linux, IOS dan Android. Contoh awal sistem operasi preemptive termasuk AmigaOS, yang 95/98/ME Windows (32-bit hanya aplikasi) [2] dan Windows keluarga NT (termasuk 2000, XP, Vista, dan 7), Linux, * BSD, OS / 2 2.x - OS / 2 Warp 3-4,5, Mac OS X. Unix dan sistem berbasis Unix, dan VMS, serta sistem lainnya yang digunakan di pasar bisnis akademik dan menengah sampai besar, selalu mendukung preemptive multitasking, tapi untuk waktu yang lama berada di luar jangkauan kebanyakan pengguna baik karena biaya lisensi atau perangkat keras yang mahal diperlukan untuk mendukung mereka. 

Contoh yang lebih tua, non-preemptive (koperasi) sistem operasi termasuk Windows 1.x, 2.x, 3.x, Windows for Workgroups, Windows 95/98/ME (ketika menjalankan aplikasi 16-bit), NetWare, dan Classic Mac versi OS (sistem 5.0 dan ke atas). Non-multitasking sistem operasi termasuk versi Mac OS, MS DOS, dan Commodore 64 OS yang hanya bisa menjalankan satu program pada satu waktu.  Beberapa sistem operasi yang paling awal yang tersedia untuk pengguna rumahan menampilkan preemptive multitasking adalah Sinclair QDOS (1984 [3]) dan Amiga OS (1985). Kedua berlari pada mikroprosesor Motorola 68000-keluarga tanpa manajemen memori. Meskipun ada sistem Unix-like lainnya seperti Xenix dan koheren, mereka sering bisa mahal untuk digunakan di rumah.Amiga OS digunakan pembebanan dinamis dari blok kode yang dapat direlokasikan ("bakhil" dalam jargon Amiga) untuk multitask Terlebih Dahulu semua proses dalam ruang alamat yang sama datar.  Awal sistem operasi PC, seperti MS-DOS dan DR-DOS, tidak mendukung multitasking sama sekali. Novell NetWare, Microsoft Windows dan OS / 2 sistem diperkenalkan koperasi multitasking ke PC, tetapi tidak mendukung preemptive multitasking. Dalam hal PC, lambat awal sebagian karena kebutuhan untuk mendukung kode warisan besar perangkat lunak DOS tertulis untuk menjalankan dalam modus single-user, sedangkan sistem Amiga dirancang untuk multitask dari awal. Versi awal Windows untuk mendukung bentuk terbatas preemptive multitasking adalah Windows 2.1x, yang menggunakan Intel 80386 Virtual 8086 mode untuk menjalankan aplikasi DOS di mesin virtual 8086 - dikenal sebagai "kotak DOS" - yang dapat mendahului. Pada Windows 95, 98 dan ME, aplikasi 32-bit dibuat memesan efek terlebih dahulu dengan menjalankan masing-masing dalam ruang alamat yang terpisah, tapi aplikasi 16 bit tetap kooperatif. [2] Windows NT selalu mendukung preemptive multitasking.

 Meskipun ada rencana untuk meng-upgrade koperasi multitasking Mac OS untuk model preemptive (dan API preemptive memang ada di Mac OS 9, walaupun dalam arti yang sangat terbatas [4] dan jarang dieksploitasi), ini adalah ditinggalkan mendukung Mac OS X , hibrida dari MacOS dan sistem operasi nextstep, yang didasarkan pada kernel Mach dan menyediakan Unix-like preemptive multitasking. OS / 2 Warp, IBM menulis ulang dari sebuah kolaborasi / IBM sebelumnya Microsoft, OS / 2, ditargetkan pada 386 sistem, didukung preemptive multitasking aplikasi asli, dan juga beberapa diijinkan berbeda Windows sesi yang akan multitasked Terlebih Dahulu.

Sebuah sistem operasi preemptive mengambil kendali dari prosesor dari tugas dalam dua cara: 

Ketika waktu kuantum tugas (atau time slice) berjalan keluar.Setiap tugas yang diberikan hanya diberikan kontrol untuk menetapkan jumlah waktu sebelum sistem operasi interrupts dan jadwal yang lain untuk menjalankan tugas. 

Ketika sebuah tugas yang memiliki prioritas lebih tinggi menjadi siap dijalankan. Tugas yang sedang berjalan kehilangan kontrol prosesor ketika tugas dengan prioritas yang lebih tinggi siap dijalankan terlepas dari apakah itu memiliki waktu tersisa di kuantum atau tidak.