Pengantar Sistem Operasi Komputer part II

3.5. Konsep Thread

3.5.1. Apa itu Thread

Thread merupakan unit dasar dari penggunaan CPU, yang terdiri dari Thread_ID, program counter, register set,

dan stack. Sebuah thread berbagi code section, data section, dan sumber daya sistem operasi dengan Thread lain

yang dimiliki oleh proses yang sama. Thread juga sering disebut lightweight process. Sebuah proses tradisional

atau heavyweight process mempunyai thread tunggal yang berfungsi sebagai pengendali. Perbedaan antara

proses dengan thread tunggal dengan proses dengan thread yang banyak adalah proses dengan thread yang

banyak dapat mengerjakan lebih dari satu tugas pada satu satuan waktu.

Gambar 3-18. Thread

Banyak perangkat lunak yang berjalan pada PC modern dirancang secara multi-threading. Sebuah aplikasi

biasanya diimplementasi sebagai proses yang terpisah dengan beberapa thread yang berfungsi sebagai

pengendali. Contohnya sebuah web browser mempunyai thread untuk menampilkan gambar atau tulisan

sedangkan thread yang lain berfungsi sebagai penerima data dari network.

Kadang kala ada situasi dimana sebuah aplikasi diperlukan untuk menjalankan beberapa tugas yang serupa.

Sebagai contohnya sebuah web server dapat mempunyai ratusan klien yang mengaksesnya secara concurrent.

Kalau web server berjalan sebagai proses yang hanya mempunyai thread tunggal maka ia hanya dapat melayani

satu klien pada pada satu satuan waktu. Bila ada klien lain yang ingin mengajukan permintaan maka ia harus

menunggu sampai klien sebelumnya selesai dilayani. Solusinya adalah dengan membuat web server menjadi

multi-threading. Dengan ini maka sebuah web server akan membuat thread yang akan mendengar permintaan

klien, ketika permintaan lain diajukan maka web server akan menciptakan thread lain yang akan melayani

permintaan tersebut.

Java mempunyai pengunaan lain dari thread. Perlu diketahui bahwa Java tidak mempunyai konsep

asynchronous. Sebagai contohnya kalau program java mencoba untuk melakukan koneksi ke server maka ia akan

berada dalam keadaan block state sampai koneksinya jadi (dapat dibayangkan apa yang terjadi apabila servernya

mati). Karena Java tidak memiliki konsep asynchronous maka solusinya adalah dengan membuat thread yang

mencoba untuk melakukan koneksi ke server dan thread lain yang pertamanya tidur selamabeberap waktu

(misalnya 60 detik) kemudian bangun. Ketika waktu tidurnya habis maka ia akan bangun dan memeriksa apakah

thread yang melakukan koneksi ke server masih mencoba untuk melakukan koneksi ke server, kalau thread

tersebut masih dalam keadaan mencoba untuk melakukan koneksi ke server maka ia akan melakukan interrupt

67Bab 3. Proses dan Penjadualan

dan mencegah thread tersebut untuk mencoba melakukan koneksi ke server.

3.5.2. Keuntungan Thread

Keuntungan dari program yang multithreading dapat dipisah menjadi empat kategori:

1. Responsi: Membuat aplikasi yang interaktif menjadi multithreading dapat membuat sebuah program terus

berjalan meskipun sebagian dari program tersebut diblok atau melakukan operasi yang panjang, karena itu

dapat meningkatkan respons kepada pengguna. Sebagai contohnya dalam web browser yang multithreading,

sebuah thread dapat melayani permintaan pengguna sementara thread lain berusaha menampilkan image.

2. Berbagi sumber daya: thread berbagi memori dan sumber daya dengan thread lain yang dimiliki oleh proses

yang sama. Keuntungan dari berbagi kode adalah mengizinkan sebuah aplikasi untuk mempunyai beberapa

thread yang berbeda dalam lokasi memori yang sama.

3. Ekonomi: dalam pembuatan sebuah proses banyak dibutuhkan pengalokasian memori dan sumber daya.

Alternatifnya adalah dengan penggunaan thread, karena thread berbagi memori dan sumber daya proses

yang memilikinya maka akan lebih ekonomis untuk membuat dan context switch thread. Akan susah untuk

mengukur perbedaan waktu antara proses dan thread dalam hal pembuatan dan pengaturan, tetapi secara

umum pembuatan dan pengaturan proses lebih lama dibandingkan thread. Pada Solaris, pembuatan proses

lebih lama 30 kali dibandingkan pembuatan thread, dan context switch proses 5 kali lebih lama

dibandingkan context switch thread.

4. Utilisasi arsitektur multiprocessor: Keuntungan dari multithreading dapat sangat meningkat pada arsitektur

multiprocessor, dimana setiap thread dapat berjalan secara pararel di atas processor yang berbeda. Pada

arsitektur processor tunggal, CPU menjalankan setiap thread secara bergantian tetapi hal ini berlangsung

sangat cepat sehingga menciptakan ilusi pararel, tetapi pada kenyataannya hanya satu thread yang dijalankan

CPU pada satu-satuan waktu (satu-satuan waktu pada CPU biasa disebut time slice atau quantum).

3.5.3. User dan Kernel Threads

User Thread

User thread didukung di atas kernel dan diimplementasi oleh thread library pada user level. Library

menyediakan fasilitas untuk pembuatan thread, penjadualan thread, dan managemen thread tanpa dukungan dari

kernel. Karena kernel tidak menyadari user-level thread maka semua pembuatan dan penjadualan thread

dilakukan di user space tanpa intervensi dari kernel. Oleh karena itu, user-level thread biasanya cepat untuk

dibuat dan diatur. Tetapi user thread mempunyai kelemahan yaitu apabila kernelnya merupakan thread tunggal

maka apabila salah satu user-level thread menjalankan blocking system call maka akan mengakibatkan seluruh

proses diblok walau pun ada thread lain yang dapat jalan dalam aplikasi tersebut. Contoh user-thread libraries

adalah POSIX Pthreads, Mach C-threads, dan Solaris threads.

Kernel Thread

Kernel thread didukung langsung oleh sistem operasi. Pembuatan, penjadualan, dan managemen thread

dilakukan oleh kernel pada kernel space. Karena pengaturan thread dilakukan oleh sistem operasi maka

pembuatan dan pengaturan kernel thread lebih lambat dibandingkan user thread. Keuntungannya adalah thread

diatur oleh kernel, karena itu jika sebuah thread menjalankan blocking system call maka kernel dapat

menjadualkan thread lain di aplikasi untuk melakukan eksekusi. Keuntungan lainnya adalah pada lingkungan

68Bab 3. Proses dan Penjadualan

multiprocessor, kernel dapat menjadual thread-thread pada processor yang berbeda. Contoh sistem operasi yang

mendukung kernel thread adalah Windows NT, Solaris, Digital UNIX.

3.5.4. Multithreading Models

Many-to-One Model

Many-to-One model memetakan banyak user-level thread ke satu kernel thread. Pengaturan thread dilakukan di

user space, oleh karena itu ia efisien tetapi ia mempunyai kelemahan yang sama dengan user thread. Selain itu

karena hanya satu thread yang dapat mengakses thread pada suatu waktu maka multiple thread tidak dapat

berjalan secara pararel pada multiprocessor. User-level thread yang diimplementasi pada sistem operasi yang

tidak mendukung kernel thread menggunakan Many-to-One model.

Gambar 3-19. Many-To-One

One-to-One Model

One-to-One model memetakan setiap user thread ke kernel thread. Ia menyediakan lebih banyak concurrency

dibandingkan Many-to-One model. Keuntungannya sama dengan keuntungan kernel thread. Kelemahannya

model ini adalah setiap pembuatan user thread membutuhkan pembuatan kernel thread. Karena pembuatan

thread dapat menurunkan performa dari sebuah aplikasi maka implmentasi dari model ini membatasi jumlah

thread yang dibatasi oleh sistem. Contoh sistem operasi yang mendukung One-to-One model adalah Windows

NT dan OS/2.

69Bab 3. Proses dan Penjadualan

Gambar 3-20. One-To-One

Many-to-Many Model

Many-to-many model multiplexes banyak user-level thread ke kernel thread yang jumlahnya lebih kecil atau

sama banyaknya dengan user-level thread. Jumlah kernel thread dapat spesifik untuk sebagian aplikasi atau

sebagian mesin. Many-to-One model mengizinkan developer ntuk membuat user thread sebanyak yang ia mau

tetapi concurrency tidak dapat diperoleh karena hanya satu thread yang dapat dijadual oleh kernel pada suatu

waktu. One-to-One menghasilkan concurrency yang lebih tetapi developer harus hati-hati untuk tidak

menciptakan terlalu banyak thread dalam suatu aplikasi (dalam beberapa hal, developer hanya dapat membuat

thread dalam jumlah yang terbatas). Many-to-Many model tidak menderita kelemahan dari 2 model di atas.

Developer dapat membuat user thread sebanyak yang diperlukan, dan kernel thread yang bersangkutan dapat

bejalan secara pararel pada multiprocessor. Dan juga ketika suatu thread menjalankan blocking system call maka

kernel dapat menjadualkan thread lain untuk melakukan eksekusi. Contoh sistem operasi yang mendukung

model ini adalah Solaris, IRIX, dan Digital UNIX.

70Bab 3. Proses dan Penjadualan

Gambar 3-21. Many-To-Many

3.5.5. Fork dan Exec System Call

Ada dua kemungkinan dalam system UNIX jika fork dipanggil oleh salah satu thread dalam proses:

1. Semua thread diduplikasi.

2. Hanya thread yang memanggil fork.

Kalau thread memanggil exec System Call maka program yang dispesifikasi di parameter exec akan mengganti

keseluruhan proses termasuk thread dan LWP.

Penggunaan dua versi dari fork di atas tergantung dari aplikasi. Kalau exec dipanggil seketika sesudah fork,

maka duplikasi seluruh thread tidak dibutuhkan, karena program yang dispesifikasi di parameter exec akan

mengganti seluruh proses. Pada kasus ini cukup hanya mengganti thread yang memanggil fork. Tetapi jika

proses yang terpisah tidak memanggil exec sesudah fork maka proses yang terpisah tersebut hendaknya

menduplikasi seluruh thread.

3.5.6. Cancellation

Thread cancellation adalah tugas untuk memberhentikan thread sebelum ia menyelesaikan tugasnya. Sebagi

contohnya jika dalam program java kita hendak mematikan Java Virtual Machine (JVM) maka sebelum

JVM-nya dimatikan maka seluruh thread yang berjalan dihentikan terlebuh dahulu. Thread yang akan

diberhentikan biasa disebut target thread.

Pemberhentian target thread dapat terjadi melalui dua cara yang berbeda:

1. Asynchronous cancellation: suatu thread seketika itu juga memberhentikan target thread.

2. Defered cancellation: target thread secara perodik memeriksa apakah dia harus berhenti, cara ini

memperbolehkan target thread untuk memberhentikan dirinya sendiri secara terurut.

71Bab 3. Proses dan Penjadualan

Hal yang sulit dari pemberhentian thread ini adalah ketika terjadi situasi dimana sumber daya sudah dialokasikan

untuk thread yang akan diberhentikan. Selain itu kesulitan lain adalah ketika thread yang diberhentikan sedang

meng-update data yang ia bagi dengan thread lain. Hal ini akan menjadi masalah yang sulit apabila digunakan

asynchronous cancellation. Sistem operasi akan mengambil kembali sumber daya dari thread yang diberhentikan

tetapi seringkali sistem operasi tidak mengambil kembali semua sumber daya dari thread yang diberhentikan.

Alternatifnya adalah dengan menggunakan deffered cancellation. Cara kerja dari deffered cancellation adalah

dengan menggunakan satu thread yang berfungsi sebagai pengindikasi bahwa target thread hendak

diberhentikan. Tetapi pemberhentian hanya akan terjadi jika target thread memeriksa apakah ia harus berhenti

atau tidak. Hal ini memperbolehkan thread untuk memeriksa apakah ia harus berhenti pada waktu dimana ia

dapat diberhentikan secara aman yang aman. Pthread merujuk tersebut sebagai cancellation points.

Pada umumnya sistem operasi memperbolehkan proses atau thread untuk diberhentikan secara asynchronous.

Tetapi Pthread API menyediakan deferred cancellation. Hal ini berarti sistem operasi yang

mengimplementasikan Pthread API akan mengizinkan deferred cancellation.

3.5.7. Penanganan Sinyal

Sebuah sinyal digunakan di sistem UNIX untuk notify sebuah proses kalau suatu peristiwa telah terjadi. Sebuah

sinyal dapat diterima secara synchronous atau asynchronous tergantung dari sumber dan alasan kenapa peristiwa

itu memberi sinyal.

Semua sinyal (asynchronous dan synchronous) mengikuti pola yang sama:

1. Sebuah sinyal dimunculkan oleh kejadian dari suatu persitiwa.

2. Sinyal yang dimunculkan tersebut dikirim ke proses.

3. Sesudah dikirim, sinyal tersebut harus ditangani.

Contoh dari sinyal synchronous adalah ketika suatu proses melakukan pengaksesan memori secarai ilegal atau

pembagian dengan nol, sinyal dimunculkan dan dikirim ke proses yang melakukan operasi tersebut. Contoh dari

sinyal asynchronous misalnya kita mengirimkan sinyal untuk mematikan proses dengan keyboard (ALT-F4)

maka sinyal asynchronous dikirim ke proses tersebut. Jadi ketika suatu sinyal dimunculkan oleh peristiwa diluar

proses yang sedang berjalan maka proses tersebut menerima sinyal tersebut secara asynchronous.

Setiap sinyal dapat ditangani oleh salah satu dari dua penerima sinyal:

1. Penerima sinyal yang merupakan set awal dari sistem operasi.

2. Penerima sinyal yang didefinisikan sendiri ole user.

Penanganan sinyal pada program yang hanya memakai thread tunggal cukup mudah yaitu hanya dengan

mengirimkan sinyal ke prosesnya. Tetapi mengirimkan sinyal lebih rumit pada program yang multithreading,

karena sebuah proses dapat memiliki beberapa thread.

Secara umum ada empat pilihan kemana sinyal harus dikirim:

1. Mengirimkan sinyal ke thread yang dituju oleh sinyal tersebut.

2. Mengirimkan sinyal ke setiap thread pada proses tersebut.

3. Mengirimkan sinyal ke thread tertentu dalam proses.

4. Menugaskan thread khusus untuk menerima semua sinyal yang ditujukan pada proses.

Cara untuk mengirimkan sebuah sinyal tergantung dari jenis sinyal yang dimunculkan. Sebagai contoh sinyal

synchronous perlu dikirimkan ke thread yang memunculkan sinyal tersebut bukan thread lain pada proses

tersebut. Tetapi situasi dengan sinyal asynchronous menjadi tidak jelas. Beberapa sinyal asynchronous seperti

72Bab 3. Proses dan Penjadualan

sinyal yang berfungsi untuk mematikan proses (contoh: alt-f4) harus dikirim ke semua thread. Beberapa versi

UNIX yang multithreading mengizinkan thread menerima sinyal yang akan ia terima dan menolak sinyal yang

akan ia tolak. Karena itu sinyal asynchronouns hanya dikirimkan ke thread yang tidak memblok sinyal tersebut.

Solaris 2 mengimplementasikan pilihan ke-4 untuk menangani sinyal. Windows 2000 tidak menyediakan

fasilitas untuk mendukung sinyal, sebagai gantinya Windows 2000 menggunakan asynchronous procedure calls

(APCs). Fasilitas APC memperbolehkan user thread untuk memanggil fungsi tertentu ketika user thread

menerima notifikasi peristiwa tertentu.

3.5.8. Thread Pools

Pada web server yang multithreading ada dua masalah yang timbul:

1. Ukuran waktu yang diperlukan untuk menciptakan thread untuk melayani permintaan yang diajukan

terlebih pada kenyataannya thread dibuang ketika ia seketika sesudah ia menyelesaikan tugasnya.

2. Pembuatan thread yang tidak terbatas jumlahnya dapat menurunkan performa dari sistem.

Solusinya adalah dengan penggunaan Thread Pools, cara kerjanya adalah dengan membuat beberapa thread pada

proses startup dan menempatkan mereka ke pools, dimana mereka duduk diam dan menunggu untuk bekerja.

Jadi ketika server menerima permintaan maka maka ia akan membangunkan thread dari pool dan jika thread

tersedia maka permintaan tersebut akan dilayani. Ketika thread sudah selesai mengerjakan tugasnya maka ia

kembali ke pool dan menunggu pekerjaan lainnya. Bila tidak thread yang tersedia pada saat dibutuhkan maka

server menunggu sampai ada satu thread yang bebas.

Keuntungan thread pool:

1. Biasanya lebih cepat untuk melayani permintaan dengan thread yang ada dibanding dengan menunggu

thread baru dibuat.

2. Thread pool membatasi jumlah thread yang ada pada suatu waktu. Hal ini pentingpada sistem yang tidak

dapat mendukung banyak thread yang berjalan secara concurrent.

Jumlah thread dalam pool dapat tergantung dari jumlah CPU dalam sistem, jumlah memori fisik, dan jumlah

permintaan klien yang concurrent.

3.5.9. Thread Specific Data

Thread yang dimiliki oleh suatu proses memang berbagi data tetapi setiap thread mungkin membutuhkan

duplikat dari data tertentu untuk dirinya sendiri dalam keadaan tertentu. Data ini disebut thread-specific data.

3.5.10. Pthreads

Pthreads merujuk kepada POSIX standard (IEEE 1003.1 c) mendefinisikan sebuah API untuk pembuatan thread

dan sinkronisasi. Pthreads adalah spesifikasi untuk thread dan bukan merupakan suatu implementasi. Desainer

sistem operasi boleh mengimplementasikan spesifikasi tersebut dalam berbagai cara yang mereka inginkan.

Secara umum Libraries yang mengimplementasikan Pthreads dilarang pada sistem berbasis UNIX seperti Solaris

2. Sistem operasi Windows secara umum belum mendukung Pthreads, walau pun versi shareware-nya sudah ada

di domain publik.

73Bab 3. Proses dan Penjadualan

3.6. Ilustrasi Thread dengan Linux dan Java

Dewasa ini, banyak sistem operasi yang telah mendukung proses multithreading. Setiap sistem operasi memiliki

konsep tersendiri dalam mengimplementasikannya ke dalam sistem.

3.6.1. Thread dengan Linux

Kernel Linux mulai menggunakan thread pada versi 2.2. Thread dalam Linux dianggap sebagai task, seperti

halnya proses. Kebanyakan sistem operasi yang mengimplementasikan multithreading menjalankan sebuah

thread terpisah dari proses. Linus Torvalds mendefinisikan bahwa sebuah thread adalah Context of Execution

(COE), yang berarti bahwa hanya ada sebuah Process Control Block (PCB) dan sebuah penjadual yang

diperlukan. Linux tidak mendukung multithreading, struktur data yang terpisah, atau pun rutin kernel.

Linux menyediakan dua macam system call, yaitu fork dan clone. fork memiliki fungsi untuk menduplikasi

proses dimana proses anak yang dihasilkan bersifat independent. clone memiliki sifat yang mirip dengan fork

yaitu sama-sama membuat duplikat dari proses induk. Namun demikian, selain membuat proses baru yang

terpisah dari proses induk, clone juga mengizinkan terjadinya proses berbagi ruang alamat antara proses anak

dengan proses induk, sehingga proses anak yang dihasilkan akan sama persis dengan proses induknya.

Setiap proses memiliki struktur data yang unik. Namun demikian, proses-proses di Linux hanya menyimpan

pointer-pointer ke struktur data lainnya dimana instruksi disimpan, sehingga tidak harus menyimpan instruksi ke

setiap struktur data yang ada. Hal ini menyebabkan context switch antar proses di Linux menjadi lebih cepat.

Ketika fork dieksekusi, sebuah proses baru dibuat bersamaan dengan proses penyalinan struktur data dari proses

induk. Ketika clone dieksekusi, sebuah proses baru juga dibuat, namun proses tersebut tidak menyalin struktur

data dari proses induknya. Proses baru tersebut hanya menyimpan pointer ke struktur data proses induk. Oleh

karena itu, proses anak dapat berbagi ruang alamat dan sumber daya dengan proses induknya. Satu set flag

digunakan untuk mengindikasikan seberapa banyak kedua proses tersebut dapat berbagi. Jika tidak ada flag yang

ditandai, maka tidak ada sharing, sehingga clone berlaku sebagai fork. Jika kelima flag ditandai, maka proses

induk harus berbagi semuanya dengan proses anak.

Tabel 3-1. Tabel Flag dan Fungsinya

Flag Keterangan

CLONE_VM Berbagi data dan Stack

CLONE_FS Berbagi informasi sistem berkas

CLONE_FILES Berbagi berkas

CLONE_SIGHAND Berbagi sinyal

CLONE_PID Berbagi PID dengan proses induk

3.6.2. Thread dengan Java

Sistem operasi mendukung thread pada tingkat kernel atau tingkat pengguna. Java merupakan salah satu dari

sedikit bahasa pemrograman yang mendukung thread di tingkat bahasa untuk pembuatan dan managemen

thread. Karena thread dalam Java diatur oleh Java Virtual Machine (JVM), tidak dengan user level library

ataupun kernel, sulit mengelompokkan thread di Java apakah di tingkat pengguna atau kernel.

Setiap program dalam Java memiliki minimal sebuah thread, yaitu main thread yang merupakan single-thread

tersendiri di JVM. Java juga menyediakan perintah untuk membuat dan memodifikasi thread tambahan sesuai

74Bab 3. Proses dan Penjadualan

kebutuhan di program.

Pembuatan Thread

Ada dua cara untuk membuat thread dalam Java. Pertama, thread dapat dibuat secara eksplisit dengan cara

membuat objek baru dari class yang telah meng-extends class Thread yang menyebabkan class tersebut mewarisi

method-method dan field dari class super. Dalam kasus ini, sebuah class hanya dapat meng-extends sebuah class.

Keterbatasan ini dapat diatasi dengan cara kedua yaitu meng-implements interface Runnable, yang merupakan

cara yang paling sering digunakan untuk membuat thread, sehingga class tersebut dapat meng-extends class lain.

Sebuah objek yang berasal dari subkelas Thread dapat dijalankan sebagai thread pengontrol yang terpisah dalam

JVM. Membuat objek dari class Thread tidak akan membuat thread baru. Hanya dengan method start thread

baru akan terbentuk. Memanggil method start untuk membuat objek baru akan mengakibatkan dua hal, yaitu:

• Pengalokasian memori dan menginisialisasikan sebuah thread baru dalam JVM.

• Memanggil method run, yang sudah di-override, membuat thread dapat dijalankan oleh JVM.

(Catatan: Method run dijalankan jika method start dipanggil. Memanggil method run secara langsung hanya

menghasilkan sebuah single-thread tambahan selain main thread)

Contoh pembuatan thread dengan membuat objek baru dari class yang meng-extends class Thread:

Gambar 3-22. Thread

public class TestThread1 {

public static void main (String[] args) {

BuatThread1 b = new BuatThread1();

for(int i = 0; i < angka; i++) {

b.start();

}

}

}

class BuatThread1 extends Thread {

public void run() {

try {

System.out.println("Thread baru dibuat.");

}

catch (InterruptedException e) {

}

}

}

JVM dan Host Operating System

Implementasi umum dari JVM adalah di atas sebuah host operating system. Hal ini memungkinkan JVM untuk

menyembunyikan implementasi detail dari sistem operasi tempat JVM dijalankan dan menyediakan lingkungan

abstrak dan konsisten yang memungkinkan program-program Java untuk beroperasi di atas platform apa pun

yang mendukung JVM. Spesifikasi untuk JVM tidak mengindikasikan bagaimana thread-thread Java dipetakan

ke sistem operasi tempat JVM dijalankan, melainkan menyerahkan keputusan tersebut kepada implementasi

75Bab 3. Proses dan Penjadualan

tertentu dari JVM. Windows 95/98/NT/2000 menggunakan model One-to-One, sehingga setiap thread Java

untuk JVM pada sistem operasi tersebut dipetakan kepada sebuah kernel thread. Solaris 2 awalnya

mengimplementasikan JVM menggunakan model Many-to-One (disebut Green Threads). Akan tetapi, sejak

JVM versi 1.1 dengan Solaris 2.6, mulai diimplementasikan menggunakan model Many-to-Many.

3.7. Penjadual CPU

Penjadualan CPU adalah basis dari multi programming sistem operasi. Dengan men-switch CPU diantara proses.

Akibatnya sistem operasi dapat membuat komputer produktif. Dalam bab ini kami akan mengenalkan tentang

dasar dari konsep penjadualan dan beberapa algoritma penjadualan. Dan kita juga memaparkan masalah dalam

memilih algoritma dalam suatu sistem.

3.7.1. Konsep Dasar

Tujuan dari multi programming adalah untuk mempunyai proses berjalan secara bersamaan, unutk

memaksimalkan kinerja dari CPU. Pada sistem prosesor tunggal, tidak pernah ada proses yang berjalan lebih

dari satu. Bila ada proses yang lebih dari satu maka proses yang lain harus mengantri sampai CPU bebas proses.

Ide dari multi porgamming sangat sederhana. Ketika sebuah proses dieksekusi maka proses yang lain harus

menunggu sampai proses pertama selesai. Pada sistem komputer yang sederhana CPU akan banyak dalam posisi

idle. Sehingga waktu CPU ini sangat terbuang,. Akan tetapi dengan multiprogamming, kita mencoba

menggunakan waktu secara produktif. Beberapa proses di simpan di memori dalam satu waktu. Ketika suatu

proses harus menuggu, Sistem operasi dapat saja akan menghentikan CPU dari suatu proses yang sedang

diekseskusi dan memberikan sumberdaya kepada proses yang lainnya. Begitu seterusnya.

Penjadualan adalah fungsi dasar dari suatu sistem opersai. Hampir semua sumber komputer dijadualkan sebelum

digunakan. CPU salah satu sumber dari komputer yang penting yang menjadi sentral dari sentral penjadualan di

sistem operasi.

3.7.2. Siklus Burst CPU-I/O

Keberhasilan dari penjadualan CPU tergantung dari beberapa properti prosesor. Pengeksekusian dari proses

tersebut terdiri atas siklus CPU ekskusi dan I/O Wait. Proses hanya akan bolak-balik dari dua state ini.

Pengeksekusian proses dimulai dengan CPU Burst, setelah itu diikuti oleh I/O burst, kemudian CPU Burst lagi

lalu I/O Burst lagi begitu seterusnya dan dilakukan secara bergiliran. Dan, CPU Burst terakhir, akan berakhir

dengan permintaan sistem untuk mengakhiri pengeksekusian daripada melalui I/O Burst lagi. Kejadian siklus

Burst akan dijelaskan pada Gambar 3-23

76Bab 3. Proses dan Penjadualan

Gambar 3-23. Siklus Burst

Durasi dari CPU bust ini telah diukur secara ekstensif, walau pun mereka sangat berbeda dari proses ke prose.

Mereka mempunyai frekeunsi kurva yang sama seperti yang diperlihatkan pada Gambar 3-24

77Bab 3. Proses dan Penjadualan

Gambar 3-24. Burst

3.7.3. Penjadualan CPU

Kapanpun CPU menjadi idle, sistem operasi harus memilih salah satu proses untuk masuk kedalam antrian ready

(siap) untuk dieksekusi. Pemilihan tersebut dilakukan oleh penjadual short term. Penjadualan memilih dari

sekian proses yang ada di memori yang sudah siap dieksekusi, den mengalokasikan CPU untuk

mengeksekusinya.

3.7.4. Penjadualan Preemptive

Penjadualan CPU mungkin akan dijalankan ketika proses:

1. Berubah dari running ke waiting state

2. Berubah dari running ke ready state

3. Berubah dari waiting ke ready

4. Terminates

Penjadualan dari no 1 sampai 4 non premptive sedangkan yang lain premptive. Dalam penjadualan

nonpreemptive sekali CPU telah dialokasikan untuk sebuah proses, maka tidak dapat di ganggu, penjadualan

model seperti ini digunakan oleh windows 3.X; windows 95 telah menggunakan penjadualan preemptive.

78Bab 3. Proses dan Penjadualan

3.7.5. Dispatcher

Komponen yang lain yang terlibat dalam penjadualan CPU adalan dispatcher. Dispatcher adalah modul yang

memberikan kontrol CPU kepada proses yang fungsinya adalah:

1. Switching context

2. Switching to user mode

3. Lompat dari suatu bagian di progam user untuk mengulang progam.

Dispatcher seharusnya secepat mungkin.

3.7.6. Kriteria Penjadualan

Algoritma penjadualan CPU yang berbeda mempunyai property yang berbeda. Dalam memilih algoritma yang

digunakan untuk situasi tertentu, kita harus memikirkan properti yang berbeda untuk algoritma yang berbeda.

Banyak kriteria yang dianjurkan untuk membandingkan penjadualan CPU algoritma.

3.7.7. Penjadualan Preemptive

Kritria yang biasanya digunakan dalam memilh adalah:

1. CPU utilization: kita ingin menjaga CPU sesibuk mungkin. CPU utilization akan mempunyai range dari 0

ke 100 persen. Di sistem yang sebenarnya seharusnya ia mempunyai range dari 40 persen samapi 90 persen

2. Throughput: jika CPU sibuk mengeksekusi proses, jika begitu kerja telah dilaksanakan. Salah satu ukuran

kerja adalah banyak proses yang diselesaikan per unit waktu, disebut througput. Untuk proses yang lama

mungkin satu proses per jam ; untuk proses yang sebentar mungkin 10 proses perdetik.

3. Turnaround time: dari sudur pandang proses tertentu, kriteria yang penting adalah berapa lama untuk

mengeksekusi proses tersebut. Interval dari waktu yang dijinkan dengan waktu yang dibutuhkan untuk

menyelesaikan sebuah prose disebut turn around time. Turn around time adalah jumlah periode untuk

menunggu untuk dapat ke memori, menunggu di ready queue, eksekusi di CPU, dan melakukan I/O

4. Waiting time: algoritma penjadualan CPU tidak mempengaruhi waktu untuk melaksanakan proses tersebut

atau I/O; itu hanya mempengaruhi jumlah waktu yang dibutuhkan proses di antrian ready. Waiting time

adalah jumlah periode menghabiskan di antrian ready.

5. Response time: di sistem yang interaktif, turnaround time mungkin bukan waktu yang terbaik untuk kriteria.

Sering sebuah proses dapat memproduksi output diawal, dan dapat meneruskan hasil yang baru sementara

hasil yang sebelumnya telah diberikan ke user. Ukuran yang lain adalah waktu dari pengiriamn permintaan

sampai respon yang pertama di berikan. Ini disebut response time, yaitu waktu untuk memulai memberikan

respon, tetapi bukan waktu yang dipakai output untu respon tersebut.

Biasanya yang dilakukan adalah memaksimalkan CPU utilization dan throughput, dan minimalkan turnaround

time, waiting time, dan response time dalam kasus tertentu kita mengambil rata-rata.

79Bab 3. Proses dan Penjadualan

3.8. Algoritma Penjadualan

Proses yang belum mendapat jatah alokasi dari CPU akan mengantri di ready queue. Di sini algoritma

diperlukan untuk mengatur giliran proses-proses tersebut. Berikut ini adalah algoritmanya

3.8.1. First-Come, First-Served

Algoritma ini merupakan algoritma yang paling sederhana. Dari namanya, kita dapat menebak kalau algoritma

ini akan mendahulukan proses yang lebih dulu datang. Jadi proses akan mengantri sesuai waktu kedatangannya.

Kelemahan algoritma ini adalah waiting time rata-rata yang cukup lama. Sebagai contoh ; ada tiga algoritma

yang datang berturut-turut. Algoritma pertama mempunyai burst time 7 milidetik, sedangkan yang kedua dan

ketiga masing-masing 5 milidetik dan 1 milidetik. Waiting time proses pertama ialah 0 milidetik (proses pertama

tak perlu menunggu). Waiting time proses kedua ialah 7 milidetik (menunggu proses pertama), dan yang ketiga

12 milidetik (menunggu proses pertama dan kedua). Jadi waiting time rata-rata sebesar (0+7+12)/3 = 6,33

milidetik. Bandingkan jika proses datang dengan urutan terbalik (yang terakhir datang pertama dan

kebalikannya). Waiting time rata-ratanya hanya sebesar (0+1+6)/3 = 2,33 milidetik (jauh lebih kecil). Bayangkan

selisih yang mungkin terjadi jika beda burst time tiap proses sangat besar.

Munculah istilah convoy effect, dimana proses lain menunggu satu proses besar mengembalikan sumber daya

CPU. Tentu kemungkinan utilisasi CPU akan lebih baik jika proses yang lebih singkat didahulukan.

Algoritma ini nonpreemptive. Setelah CPU dialokasikan ke suatu proses, hanya proses tersebut yang dapat

mengembalikannya.

3.8.2. Shortest-Job First

Algoritma ini mempunyai cara yang berbeda untuk mengatur ntrian di ready queue. Proses diatur menurut

panjang CPU burst berikutnya (lebih tepatnya shortest next CPU burst).

Waiting time rata-rata dari algoritma ini sangat kecil, sehingga layak disebut optimal. Perbandingan algoritma ini

dengan algoritma pertama telah kita lihat di bagian sebelumnya (shortest job first), di mana proses yang memiliki

CPU burst terkecil jika didahulukan akan mengurangi waiting time rata-ratanya. Kelemahan algoritma ini yaitu

kita tak pernah tahu secara pasti panjang CPU burst proses berikutnya. Kita hanya dapat mengira-ngira nilainya.

Algoritma ini dapat merupakan preemptive atau nonpreemptive. Jika preemptive, jika ada proses datang dengan

sisa CPU burst yang lebih kecil daripada yang sedang dieksekusi, maka proses tersebut akan menggantikan

proses yang sedang dieksekusi. Contoh: 2 proses datang bersamaan dengan CPU burst masing-masing sebesar 4

dan 5 milidetik. Algoritma ini akan mengalokasikan CPU untuk proses yang memiliki CPU burst 4 milidetik,

sementara satu lagi akan menunggu di ready queue. Baru 1 milidetik proses pertama dieksekusi, ada proses lain

datang dengan besar CPU burst 2 milidetik. Alokasi CPU segera diberikan pada proses baru tersebut karena

mempunyai sisa waktu terkecil yaitu 2 milidetik(proses yang dieksekusi mempunyai sisa waktu 3 milidetik

karena telah mendapat alokasi CPU selama 1 milidetik), dan kedua proses yang datang pertama kembali

menunggau di ready queue. Bandingkan waiting time rata-ratanya, yang nonpreemptive sebesar (0+4+9)/3 =

4,33 milidetik, dan yang preemptive sebesar ((3-1)+6+(1-1))/3 = 2,66 milidetik.

3.8.3. Priority

Algoritma ini memberikan skala prioritas kepada tiap proses. Proses yang mendapat prioritas terbesar akan

didahulukan. Skala diberikan dalam bentuk integer. Beberapa sistem menggunakan integer kecil untuk prioritas

tertinggi, beberapa sistem menggunakan integer besar.

80Bab 3. Proses dan Penjadualan

Algoritma ini dapat preemptive maupun nonpreeemptive. Jika preemptive maka proses dapat diinterupsi oleh

proses yang prioritasnya lebih tinggi.

Kelemahan dari algoritma ini adalah proses dengan prioritas kecil tidak akan mendapat jatah CPU. Hal ini dapat

diatasi dengan aging, yaitu semakin lama menunggu, prioritas semakin tinggi.

3.8.4. Round-Robin

Algoritma ini menggilir proses yang ada di antrian. Proses akan mendapat jatah sebesar time quantum. Jika time

quantum-nya habis atau proses sudah selesai CPU akan dialokasikan ke proses berikutnya. Tentu proses ini

cukup adil karena tak ada proses yang diprioritaskan, semua proses mendapat jatah waktu yang sama dari CPU

(1/n), dan tak akan menunggu lebih lama dari (n-1)/q.

Algoritma ini sepenuhnya bergantung besarnya time quantum. Jika terlalu besar, algoritma ini akan sama saja

dengan algoritma first-come first-served. Jika terlalu kecil, akan semakin banyak peralihan proses sehingga

banyak waktu terbuang.

3.8.5. Multilevel Queue

Algoritma ini mengelompokkan antrian dalam beberapa buah antrian. Antrian-antrian tersebut diberi

prioritas.Antrian yang lebih rendah tak boleh mendapat alokasi selama ada antrian tinggi yang belum kebagian.

Tiap antrian boleh memiliki algoritma yang berbeda. Kita juga dapat menjatah waktu CPU untuk tiap antrian.

Semakin tinggi tingkatannya, semakin besar jatah waktu CPU-nya.

3.8.6. Multilevel Feedback Queue

Algoritma ini mirip sekali dengan algoritma Multilevel Queue. Perbedaannya ialah algoritma ini mengizinkan

proses untuk pindah antrian. Jika suatu proses menyita CPU terlalu lama, maka proses itu akan dipindahkan ke

antrian yang lebih rendah. Ini menguntungkan proses interaksi, karena proses ini hanya memakai waktu CPU

yang sedikit. Demikian pula dengan proses yang menunggu terlalu lama. Proses ini akan dinaikkan tingkatannya.

Biasanya prioritas tertinggi diberikan kepada proses dengan CPU burst terkecil, dengan begitu CPU akan

terutilisasi penuh dan I/O dapat terus sibuk. Semakin rendah tingkatannya, panjang CPU burst proses juga

semakin besar.

Algoritma ini didefinisikan melalui beberapa parameter, antara lain:

• Jumlah antrian

• Algoritma penjadualan tiap antrian

• Kapan menaikkan proses ke antrian yang lebih tinggi

• Kapan menurunkan proses ke antrian yang lebih rendah

• Antrian mana yang akan dimasuki proses yang membutuhkan

Dengan pendefinisian seperti tadi membuat algoritma ini sering dipakai. Karena algoritma ini mudah

dikonfigurasi ulang supaya cocok dengan sistem. Tapi untuk mengatahui mana penjadual terbaik, kita harus

mengetahui nilai parameter tersebut.

81Bab 3. Proses dan Penjadualan

3.9. Prioritas dan Multiprosesor

Penjadualan pada multiprosesor jelas lebih kompleks, karena kemungkinan masalah yang timbul jauh lebih

banyak daripada prosesor tunggal.

3.9.1. Prioritas

Prioritas adalah suatu istilah yang digunakan untuk menentukan tingkat urutan atau hirarki suatu proses yang

sedang masuk dalam ready queue.

3.9.2. Multiprosesor

Mengacu Silberschatz dkk., sistem dengan prosesor jamak yang dimaksud adalah suatu sistem dimana

prosesor-prosesornya identik. Dalam hal ini berarti tiap proses dapat masuk antrian manapun dari

prosesor-prosesor yang ada. Yang patut diperhatikan, tiap prosesor dapat memilih proses apa saja yang ingin

dijalankan dari ready queue. Dengan kata lain, prioritas proses ditentukan secara independen oleh

masing-masing prosesor. Jadi salah satu prosesor dapat saja idle ketika ada proses yang sedang ditunda. Oleh

karena itu, tiap prosesor harus di synchronize lebih dulu agar tidak ada dua prosesor atau lebih yang berebut

mengeksekusi proses yang sama dan mengubah shared data. Sistem seperti ini dikenal juga dengan sebutan

synchronous. Selain synchronous, ada juga sistem lain yang disebut asynchronous, yang juga dikenal dengan

struktur "master-slave" dimana salah satu prosesor dialokasikan khusus untuk mengatur penjadualan. Sedangkan

prosesor yang lain ditujukan untuk mengkomputasikan proses yang telah dijadualkan sebelumnya oleh master

prosesor. Peningkatan dari sistem ini adalah mengalokasikan penjadualan, pemrosesan I/O, dan kegiatan sistem

lainnya kepada satu prosesor tertentu kepada master. Sedangkan prosesor yang lain hanya bertugas

mengeksekusi user code.

3.10. Sistem Waktu Nyata

Pada sub bab ini, kami akan mencoba sedikit menggambarkan fasilitas penjadualan yang dibutuhkan untuk

mendukung komputasi real-time dengan bantuan sistem komputer.

Suatu sistem komputasi dinamakan real-time jika sistem tersebut dapat mendukung eksekusi program/aplikasi

dengan waktu yang memiliki batasan. Dengan kata lain, sistem real-time harus memenuhi kondisi berikut:

• Batasan waktu: memenuhi deadline, artinya bahwa aplikasi harus menyelesaikan tugasnya dalam waktu yang

telah dibatasi.

• Dapat diprediksi: artinya bahwa sistem harus bereaksi terhadap semua kemungkinan kejadian selama kejadian

tersebut dapat diprediksi.

• Proses bersamaan: artinya jika ada beberapa proses yang terjadi bersamaan, maka semua deadline nya harus

terpenuhi.

Komputasi real-time ada dua jenis, yaitu sistem Hard Real-time dan sistem Soft Real-time.

82Bab 3. Proses dan Penjadualan

3.10.1. Sistem Hard Real-Time

Sistem hard real-time dibutuhkan untuk menyelesaikan critical task dengan jaminan waktu tertentu. Jika

kebutuhan waktu tidak terpenuhi, maka aplikasi akan gagal. Dalam definisi lain disebutkan bahwa kontrol sistem

hard real-time dapat mentoleransi keterlambatan tidak lebih dari 100 mikro detik. Secara umum, sebuah proses

di kirim dengan sebuah pernyataan jumlah waktu dimana dibutuhkan untuk menyelesaikan atau menjalankan

I/O. Kemudian penjadual dapat menjamin proses untuk selesai atau menolak permintaan karena tidak mungkin

dilakukan. Mekanisme ini dikenal dengan resource reservation. Oleh karena itu setiap operasi harus dijamin

dengan waktu maksimum. Pemberian jaminan seperti ini tidak dapat dilakukan dalam sistem dengan secondary

storage atau virtual memory, karena sistem seperti ini tidak dapat meramalkan waktu yang dibutuhkan untuk

mengeksekusi suatu proses.

Contoh dalam kehidupan sehari-hari adalah pada sistem pengontrol pesawat terbang. Dalam hal ini,

keterlambatan sama sekali tidak boleh terjadi, karena dapat berakibat tidak terkontrolnya pesawat terbang.

Nyawa penumpang yang ada dalam pesawat tergantung dari sistem ini, karena jika sistem pengontrol tidak dapat

merespon tepat waktu, maka dapat menyebabkan kecelakaan yang merenggut korban jiwa.

3.10.2. Sistem Soft Real-Time

Komputasi soft real-time memiliki sedikit kelonggaran. Dalam sistem ini, proses yang kritis menerima prioritas

lebih daripada yang lain. Walaupun menambah fungsi soft real-time ke sistem time sharing mungkin akan

mengakibatkan ketidakadilan pembagian sumber daya dan mengakibatkan delay yang lebih lama, atau mungkin

menyebabkan starvation, hasilnya adalah tujuan secara umum sistem yang dapat mendukung multimedia, grafik

berkecepatan tinggi, dan variasi tugas yang tidak dapat diterima di lingkungan yang tidak mendukunng

komputasi soft real-time.

Contoh penerapan sistem ini dalam kehidupan sehari-hari adalah pada alat penjual/pelayan otomatis. Jika mesin

yang menggunakan sistem ini telah lama digunakan, maka mesin tersebut dapat mengalami penurunan kualitas,

misalnya waktu pelayanannya menjadi lebih lambat dibandingkan ketika masih baru. Keterlambatan pada sistem

ini tidak menyebabkan kecelakaan atau akibat fatal lainnya, melainkan hanya menyebabkan kerugian keuangan

saja. Jika pelayanan mesin menjadi lambat, maka para pengguna dapat saja merasa tidak puas dan akhirnya

dapat menurunkan pendapatan pemilik mesin.

Untuk lebih memahami tentang perbedaan kedua sistem ini dapat diperhatikan dari diagram dibawah ini.

83Bab 3. Proses dan Penjadualan

Gambar 3-25. Grafik Hard Real-Time

Sumber: http://www.ncst.ernet.in/education/pgdst/coosfac/slides/rtos.pdf per Desember 2003.

Gambar 3-26. Grafik Soft Real-Time

Sumber: http://www.ncst.ernet.in/education/pgdst/coosfac/slides/rtos.pdf; per Desember 2003.

Setelah batas waktu yang diberikan telah habis, pada sistem hard real-time, aplikasi yang dijalankan langsung

dihentikan. Akan tetapi, pada sistem soft real-time, aplikasi yang telah habis masa waktu pengerjaan tugasnya,

dihentikan secara bertahap atau dengan kata lain masih diberikan toleransi waktu.

84Bab 3. Proses dan Penjadualan

Mengimplementasikan fungsi soft real time membutuhkan design yang hati-hati dan aspek yang berkaitan

dengan sistem operasi. Pertama, sistem harus punya prioritas penjadualan, dan proses real-time harus memiliki

prioritas tertinggi, tidak melampaui waktu, walaupun prioritas non real time dapat terjadi. Kedua, dispatch

latency harus lebih kecil. Semakin kecil latency, semakin cepat real time proses mengeksekusi.

Untuk menjaga dispatch tetap rendah, kita butuh agar system call untuk preemptible. Ada beberapa cara untuk

mencapai tujuan ini. Pertama adalah dengan memasukkan preemption points di durasi system call yang lama,

yang memeriksa apakah prioritas utama butuh untuk dieksekusi. Jika sudah, maka contex switch mengambil alih,

ketika high priority proses selesai, proses yang diinterupsi meneruskan dengan system call. Points premption

dapat diganti hanya di lokasi yang aman di kernel dimana kernel struktur tidak dapat dimodifikasi.

Metoda yang lain adalah dengan membuat semua kernel preemptible. Karena operasi yang benar dapat dijamin,

semua struktur data kernel harus diproteksi dengan mekanisme sinkronisasi. Dengan metode ini, kernel dapat

selalu di preemptible, karena setiap data kernel yang sedang di update diproteksi dengan pemberian prioritas

yang tinggi. Jika ada proses dengan prioritas tinggi ingin membaca atau memodifikasi data kernel yang sedang

dijalankan, prioritas yang tinggi harus menunggu sampai proses dengan prioritas rendah tersebut selesai. Situasi

seperti ini dikenal dengan priority inversion. Kenyataanya, serangkaian proses dapat saja mengakses sumber

daya yang sedang dibutuhkan oleh proses yang lebih tinggi prioritasnya. Masalah ini dapat diatasi dengan

priority-inheritance protocol, yaitu semua proses yang sedang mengakses sumber daya mendapat prioritas

tinggi sampai selesai menggunakan sumber daya. Setelah selesai, prioritas proses ini dikembalikan menjadi

seperti semula.

3.11. Rangkuman

3.11.1. Proses

Sebuah proses adalah suatu program yang sedang dieksekusi. Proses lebih dari sebuah kode program tetapi juga

mencakup program counter, stack, dan sebuah data section. Dalam pengeksekusiannya sebuah proses juga

memiliki status yang mencerminkan keadaan dari proses tersebut. Status dari proses dapat berubah-ubah setiap

saat sesuai dengan kondisinya. Status tersebut mungkin menjadi satu dari lima status berikut: new, ready,

running, waiting, atau terminated. Setiap proses juga direpresentasikan oleh Proces Control Block (PCB) yang

menyimpan segala informasi yang berkaitan dengan proses tersebut.

Sebuah proses, ketika sedang tidak dieksekusi, ditempatkan pada antrian yang sama. Disini ada dua kelas besar

dari antrian dalam sebuah sistem operasi: permintaan antrian I/O dan ready queue. Ready queue memuat semua

proses yang siap untuk dieksekusi dan yang sedang menunggu untuk dijalankan pada CPU. PCB dapat

digunakan untuk mencatat sebuah ready queue. Penjadualan Long-term adalah pilihan dari proses-proses untuk

diberi ijin menjalankan CPU. Normalnya, penjadualan long-term memiliki pengaruh yang sangat besar bagi

penempatan sumber daya, terutama managemen memori. Penjadualan short-term adalah pilihan dari satu proses

dari ready queue.

Proses-proses pada sistem dapat dieksekusi secara berkelanjutan. Disini ada beberapa alasan mengapa proses

tersebut dapat dieksekusi secara berkelanjutan: pembagian informasi, penambahan kecepatan komputasi,

modularitas, dan kenyamanan atau kemudahan. Eksekusi secara berkelanjutan menyediakan sebuah mekanisme

bagi proses pembuatan dan penghapusan.

Pengeksekusian proses-proses pada sistem operasi mungkin dapat digolongkan menjadi proses yang mandiri dan

kooperasi. Proses kooperasi harus memiliki beberapa alat untuk mendukung komunikasi antara satu dengan yang

lainnya. Prinsipnya adalah ada dua rencana komplementer komunikasi: pembagian memori dan sistem pesan.

Metode pembagian memori menyediakan proses komunikasi untuk berbagi beberapa variabel. Proses-proses

tersebut diharapkan dapat saling melakukan tukar-menukar informasi seputar pengguna variabel yang terbagi ini.

85Bab 3. Proses dan Penjadualan

Pada sistem pembagian memori, tanggung jawab bagi penyedia komunikasi terjadi dengan programmer aplikasi;

sistem operasi harus menyediakan hanya pembagian memori saja. Metode sistem pesan mengijinkan

proses-proses untuk tukar-menukar pesan. Tanggung jawab bagi penyedia komunikasi ini terjadi dengan sistem

operasi tersebut.

3.11.2. Thread

Threadadalah sebuah alur kontrol dari sebuah proses. Suatu proses yang multithreaded mengandung beberapa

perbedaan alur kontrol dengan ruang alamat yang sama. Keuntungan dari multithreaded meliputi peningkatan

respon dari pengguna, pembagian sumber daya proses, ekonomis, dan kemampuan untuk mengambil

keuntungan dari arsitektur multiprosesor. Thread tingkat pengguna adalah thread yang tampak oleh programmer

dan tidak diketahui oleh kernel. Thread tingkat pengguna secara tipikal dikelola oleh sebuah library thread di

ruang pengguna. Thread tingkat kernel didukung dan dikelola oleh kernel sistem operasi. Secara umum, thread

tingkat pengguna lebih cepat dalam pembuatan dan pengelolaan dari pada kernel thread. Ada 3 perbedaan tipe

dari model yang berhubungan dengan pengguna dan kernel thread yaitu one-to one model, many-to-one model,

many-to-many model.

• Model many to one: memetakan beberapa pengguna level thread hanya ke satu buah kernel thread.

• Model one to one: memetakan setiap thread pengguna ke dalam satu kernel thread berakhir.

• Model many to many: mengijinkan pengembang untuk membuat thread pengguna sebanyak mungkin,

konkurensi tidak dapat tercapai karena hanya satu thread yang dapat dijadualkan oleh kernel dalam satu

waktu.

Thread cancellation adalah tugas untuk memberhentikan thread sebelum ia menyelesaikan tugasnya. Thread

yang akan diberhentikan disebut target thread

Pemberhentian target thread dapat terjadi melalui 2 cara yang berbeda

• Asynchronous cancellation: suatu thread seketika itu juga memberhentikan target thread.

• Deffered cancellation: target thread secara periodik memeriksa apakah dia harus berhenti, cara ini

memperbolehkan target thread untuk memberhentikan dirinya sendiri secara terurut.

Thread Pools adalah cara kerja dengan membuat beberapa thread pada proses startup dan menempatkan mereka

ke pools.

Keuntungan Thread Pools

• Biasanya lebih cepat untuk melayani permintaan dengan thread yang ada dibanding dengan menunggu thread

baru dibuat.

• Thread pool membatasi jumlah thread yang ada pada suatu waktu. Hal ini penting pada sistem yang tidak

dapat mendukung banyak thread yang berjalan secara concurrent

Thread di Linux dianggap sebagai task. System call yang dipakai antara lain fork dan clone. Perbedaan antara

keduanya adalah clone selain dapat membuat duplikat dari proses induknya seperti fork, juga dapat berbagi

ruang alamat yang sama antara proses induk dengan proses anak. Seberapa besar kedua proses tersebut dapat

berbagi tergantung banyaknya flag yang ditandai.

86Bab 3. Proses dan Penjadualan

Java adalah unik karena telah mendukung thread didalam tingkatan bahasanya. Semua program Java sedikitnya

terdiri dari kontrol sebuah thread tunggal dan mempermudah membuat kontrol untuk multiple thread dengan

program yang sama. JAVA juga menyediakan library berupa API untuk membuat thread, termasuk method untuk

suspend dan resume suatu thread, agar thread tidur untuk jangka waktu tertentu dan menghentikan thread yang

berjalan. Sebuah java thread juga mempunyai 4 kemungkinan keadaan, diantaranya: New, Runnable, Blocked

dan Dead. Perbedaan API untuk mengelola thread seringkali mengganti keadaan thread itu sendiri.

3.11.3. Penjadualan CPU

Penjadualan CPU adalah pemilihan proses dari antrian ready untuk dapat dieksekusi. Algoritma yang digunakan

dalam penjadulan CPU ada bermacam-macam. Diantaranya adalah First Come Firsrt Serve (FCFS), merupakan

algoritma sederhana dimana proses yang datang duluan maka dia yang dieksekusi pertama kalinya. Algoritma

lainnya adalah Shorthest Job First (SJF), yaitu penjadulan CPU dimana proses yang paling pendek dieksekusi

terlebih dahulu.

Kelemahan algoritma SJF adalah tidak dapat menghindari starvation. Untuk itu diciptakan algoritma Round

Robin (RR). Penjadulan CPU dengan Round Robin adalah membagi proses berdasarkan waktu tertentu yaitu

waktu quantum q. Setelah proses menjalankan eksekusi selama q satuan waktu maka akan digantikan oleh

proses yang lain. Permasalahannya adalah bila waktu quantumnya besar sedang proses hanya membutuhkan

waktu sedikit maka akan membuang waktu. Sedang bila waktu quantum kecil maka akan memakan waktu saat

context-switch.

Penjadualan FCFS adalah nonpreemptive yaitu tidak dapat diinterupsi sebelum proses dieksekusi seluruhnya.

Penjadualan RR adalah preemtive yaitu dapat dieksekusi saat prosesnya masih dieksekusi. Sedangkan

penjadualan SJF dapat berupa nonpreemtive dan preemtive.

3.12. Latihan

3.12.1. Proses

1. sebutkan 5 aktivitas sistem operasi yang merupakan contoh dari suatu managemen proses.

2. Definisikan perbedaan antara penjadualan short term, medium term dan long term.

3. Jelaskan tindakan yang diambil oleh sebuah kernel ketika context switch antar proses.

4. Informasi apa saja yang disimpan pada tabel proses saat context switch dari satu proses ke proses lain.

5. Di sistem UNIX terdapat banyak status proses yang dapat timbul (transisi) akibat event (eksternal) OS dan

proses tersebut itu sendiri. Transisi state apa sajakah yang dapat ditimbulkan oleh proses itu sendiri.

Sebutkan!

6. Apa keuntungan dan kekurangan dari:

• komunikasi Simetrik dan asimetrik

• Automatic dan explicit buffering

• Send by copy dan send by reference

• Fixed-size dan variable sized messages

7. Jelaskan perbedaan short-term, medium-term dan long-term ?

8. Jelaskan apa yang akan dilakukan oleh kernel kepada context switch ketika proses sedang berlangsung ?

9. Beberapa single-user mikrokomputer sistem operasi seperti MS-DOS menyediakan sedikit atau tidak sama

sekali arti dari pemrosesan yang konkuren. Diskusikan dampak yang paling mungkin ketika pemrosesan

yang konkuren dimasukkan ke dalam suatu sistem operasi ?

10. Perlihatkan semua kemungkinan keadaan dimana suatu proses dapat sedang berjalan, dan gambarkan

diagram transisi keadaan yang menjelaskan bagaimana proses bergerak diantara state.

11. Apakah suatu proses memberikan ’issue’ ke suatu disk I/O ketika, proses tersebut dalam ’ready’ state,

jelaskan ?

12. Kernel menjaga suatu rekaman untuk setiap proses, disebut Proses Control Blocks (PCB). Ketika suatu

proses sedang tidak berjalan, PCB berisi informasi tentang perlunya melakukan restart suatu proses dalam

CPU. Jelaskan 2 informasi yang harus dipunyai PCB.

3.12.2. Thread

1. Tunjukkan dua contoh pemrograman dari multithreading yang dapat meningkatkan sebuah solusi thread

tunggal.

2. Tunjukkan dua contoh pemrograman dari multithreading yang tidak dapat meningkatkan sebuah solusi

thread tunggal.

3. Sebutkan dua perbedaan antara user level thread dan kernel thread. Saat kondisi bagaimana salah satu dari

thread tersebut lebih baik

4. Jelaskan tindakan yang diambil oleh sebuah kernel saat context switch antara kernel level thread.

5. Sumber daya apa sajakah yang digunakan ketika sebuah thread dibuat? Apa yang membedakannya dengan

pembentukan sebuah proses.

6. Tunjukkan tindakan yang diambil oleh sebuah thread library saat context switch antara user level thread.

3.12.3. Penjadualan CPU

1. Definisikan perbedaan antara penjadualan secara preemptive dan nonpreemptive!

2. Jelaskan mengapa penjadualan strict nonpreemptive tidak seperti yang digunakan di sebuah komputer pusat.

3. Apakah keuntungan menggunakan time quantum size di level yang berbeda dari sebuah antrian sistem

multilevel?

Pertanyaan nomor 4 sampai dengan 5 dibawah menggunakan soal berikut:

Misal diberikan beberapa proses dibawah ini dengan panjang CPU burst ( dalam milidetik)

Semua proses diasumsikan datang pada saat t=0

88Bab 3. Proses dan Penjadualan

Tabel 3-2. Tabel untuk soal 4 - 5

Proses Burst Time Prioritas

P1 10 3

P2 1 1

P3 2 3

P4 1 4

P5 5 2

4. Gambarkan 4 diagram Chart yang mengilustrasikan eksekusi dari proses-proses tersebut menggunakan

FCFS, SJF, prioritas nonpreemptive dan round robin.

5. Hitung waktu tunggu dari setiap proses untuk setiap algoritma penjadualan.

6. Jelaskan perbedaan algoritma penjadualan berikut:

• FCFS

• Round Robin

• Antrian Multilevel feedback

7. Penjadualan CPU mendefinisikan suatu urutan eksekusi dari proses terjadual. Diberikan n buah proses yang

akan dijadualkan dalam satu prosesor, berapa banyak kemungkinan penjadualan yang berbeda? berikan

formula dari n.

8. Tentukan perbedaan antara penjadualan preemptive dan nonpreemptive (cooperative). Nyatakan kenapa

nonpreemptive scheduling tidak dapat digunakan pada suatu komputer center. Di sistem komputer

nonpreemptive, penjadualan yang lebih baik digunakan.

3.12.4. Client/Server System

1. Jelaskan bagaimana Java RMI dapat bekerja

2. Apa yang dimaksud dengan marshaling, jelaskan kegunaanya!

3.13. Rujukan

Avi Silberschatz, Peter Galvin, Greg Gagne. Applied Operationg System Concepts 1st Ed. 2000. John Wiley &

Sons, Inc.

William Stallings: Operating Systems -- Fourth Edition, Prentice Hall, 2001.

Soal Mid-Test 2002 Fasilkom UI - RMS Ibrahim

http://people.cs.uchicago.edu/~mark/51081/LabFAQ/lab5/IPC.html

89Bab 3. Proses dan Penjadualan

Website Kuliah Sistem Terdistribusi Fasilkom UI, http://telaga.cs.ui.ac.id/WebKuliah/sisdis2003/

http://linas.org/linux/threads-faq.html

http://www.javaworld.com/javaworld/jw-04-1996/jw-04-threads.html

90Bab 4. Sinkronisasi dan Deadlock

4.1. Latar Belakang Sinkronisasi

Apakah sinkronisasi itu sebenarnya? Dan mengapa kita memerlukan sinkronisasi tersebut? Marilah kita pelajari

lebih lanjut mengenai sinkronisasi. 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. Untuk lebih

jelasnya marilah kita lihat contoh program java berikut yang memperlihatkan timbulnya Race Condition.

Gambar 4-1. Produser/Konsumer

01. int counter = 0;

02.

03. //Proses yang dilakukan oleh produsen

04. item nextProduced;

05.

06. while (1)

07. {

08. while (counter == BUFFER_SIZE) { ... do nothing ... }

09.

10. buffer[in] = nextProduced;

11. in = (in + 1) % BUFFER_SIZE;

12. counter++;

13. }

14.

15. //Proses yang dilakukan oleh konsumen

16. item nextConsumed;

17.

18. while (1)

19. {

20. while (counter == 0) { ... do nothing ... }

21. nextConsumed = buffer[out] ;

22. out = (out + 1) % BUFFER_SIZE;

23. counter--;

24. }

Pada program produser/konsumer tersebut dapat kita lihat pada baris 12 dan baris 23 terdapat perintah

counter++ dan counter-- yang dapat diimplementasikan dengan bahasa mesin sebagai berikut:

Gambar 4-2. Counter (1)

01. //counter++(nilai counter bertambah 1 setiap dieksekusi)

02. register1 = counter

03. register1 = register1 + 1

04. counter = register1

05. //counter--(nilai counter berkurang 1 setiap dieksekusi)

06. register2 = counter

91Bab 4. Sinkronisasi dan Deadlock

07. register2 = register2 - 1

08. counter = register2

Dapat dilihat jika perintah dari counter++ dan counter-- dieksekusi secara bersama maka akan sulit untuk

mengetahui nilai dari counter sebenarnya sehingga nilai dari counter itu akan menjadi tidak konsisten. Marilah

kita lihat contoh berikut ini:

Gambar 4-3. Counter (2)

01. //misalkan nilai awal counter adalah 2

02. produsen: register1 = counter (register1 = 2)

03. produsen: register1 = register1 + 1 (register1 = 3)

04. konsumen: register2 = counter (register2 = 2)

05. konsumen: register2 = register2 - 1 (register2 = 1)

06. konsumen: counter = register2 (counter = 1)

07. produsen: counter = register1 (counter = 3)

Pada contoh tersebut dapat kita lihat bahwa counter memiliki dua buah nilai yaitu bernilai 3 (pada saat

counter++ dieksekusi) dan bernilai 1 (pada saat counter-- dieksekusi). Hal ini menyebabkan nilai dari

counter tersebut menjadi tidak konsisten. Perhatikan bahwa nilai dari counter akan bergantung dari perintah

terakhir yang dieksekusi. Oleh karena itu maka kita membutuhkan sinkronisasi yang merupakan suatu upaya

yang dilakukan agar proses-proses yang saling bekerja bersama-sama dieksekusi secara beraturan demi

mencegah timbulnya suatu keadaan yang disebut dengan Race Condition.

4.2. Critical Section

4.2.1. Pengertian

Pada sub pokok bahasan sebelumnya, kita telah mengenal race condition sebagai masalah yang dapat terjadi

pada beberapa proses yang memanipulasi suatu data secara konkruen, sehingga data tersebut tidak sinkron lagi.

Nilai akhirnya akan tergantung pada proses mana yang terakhir dieksekusi.

Maka bagaimana cara menghindari race condition ini serta situasi-situasi lain yang melibatkan memori bersama,

berkas bersama atau sumber daya yang digunakan bersama-sama? Kuncinya adalah menemukan jalan untuk

mencegah lebih dari satu proses melakukan proses tulis atau baca kepada data atau berkas pada saat yang

bersamaan. Dengan kata lain, kita membutuhkan Mutual Exclusion. Mutual Exclusion adalah suatu cara yang

menjamin jika ada sebuah proses yang menggunakan variabel atau berkas yang sama (digunakan juga oleh

proses lain), maka proses lain akan dikeluarkan dari pekerjaan yang sama.

Sekarang kita akan membahas masalah race condition ini dari sisi teknis programming. Biasanya sebuah proses

akan sibuk melakukan perhitungan internal dan hal-hal lainnya tanpa ada bahaya yang menuju ke race condition

pada sebagian besar waktu. Akan tetapi, beberapa proses memiliki suatu segmen kode dimana jika segmen itu

dieksekusi, maka proses-proses itu dapat saling mengubah variabel, mengupdate suatu tabel, menulis ke suatu

file, dan lain sebagainya, dan hal ini dapat membawa proses tersebut ke dalam bahaya race condition. Segmen

kode yang seperti inilah yang disebut Critical Section.

Solusi untuk memecahkan masalah 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.

92Bab 4. Sinkronisasi dan Deadlock

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

Gambar 4-4. Critical Section (1)

do {

entry section

critical section

exit section

remainder section

} while (1);

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

4.2.2. 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 (Lihat: Bagian 4.3).

93Bab 4. Sinkronisasi dan Deadlock

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.

Untuk mengilustrasikan proses-proses yang akan masuk ke critical section, kita mengimplementasikan thread

dengan menggunakan class Pengguna. Class Algoritma123 akan digunakan untuk menjalankan ketiga

algoritma tersebut.

Gambar 4-5. Critical Section (2)

/**

* Program implementasi CriticalSectionAlgoritma

* dengan menggunakan elemen flag dan elemen kunci

* Author: V A Pragantha( vap20@mhs.cs.ui.ac.id)

*

**/

public class CriticalSectionAlgoritma

{

public static void main(String args[])

{

int kunci=0;

Pengguna user1;

Pengguna user2 ;

user1 = new Pengguna(kunci,0);

user2 = new Pengguna(kunci,1);

user1.setUser(user2);

user2.setUser(user1);

user1.start();

user2.start();

}

}

class Pengguna extends Thread

{

public Pengguna(int elemenKunci,int noStatus)

{

noPengguna = noStatus;

kunci = elemenKunci;

}

public void setBagianKritis(int t)

{

int others = 1-t;

kunci = others;

if(t==noPengguna)

94Bab 4. Sinkronisasi dan Deadlock

{

butuh = true;

System.out.println("\nuser "+noPengguna +

" mempersilahkan user lain memakai"+

" dan memberikan kunci");

while( (lain.getFlag() == true)

&amp;&amp; (lain.getKunci()== others) )

{

System.out.println("\nuser lain"+

" mengambil alih kendali");

Thread.yield();

}

System.out.println("\ntampaknya user lain"+

" tidak membutuhkan\n");

}

else

{

lain.setFlag(true);

while( (butuh == true) && (kunci == others)

lain.yield();

}

}

public void keluarBagianKritis(int t)

{

if( t == noPengguna )

{

butuh = false;

}

else

{

lain.setFlag(false);

}

}

public void run()

{

while(true)

{

try

{

setBagianKritis(noPengguna);

System.out.println(" user "+

noPengguna+" sedang menggunakan"+

", kunci dipegang oleh user "+

kunci);

keluarBagianKritis(noPengguna);

System.out.println("user "+ noPengguna+

" selesai memakai");

Thread.sleep(10);

}

catch(Exception e)

{

95Bab 4. Sinkronisasi dan Deadlock

System.out.println(e);

System.exit(0);

}

}

}

public boolean getFlag()

{

return butuh;

}

public int getKunci()

{

return kunci;

}

public void setFlag( boolean flag)

{

butuh = flag;

}

public void setUser( Pengguna p1)

{

lain = p1;

}

private boolean butuh;

private int kunci;

private int noPengguna;

private Pengguna lain;

}

Pada algoritma di atas, thread-thread digambarkan sebagai pengguna atau user dan kami membatasi sebanyak 2

pengguna saja. Kedua pengguna ini pada awalnya belum memiliki kunci tetapi hanya nomor pengguna yang

berbeda. Ketika salah satu user ingin memasuki critical section , maka ia akan memberikan kuncinya kepada

pengguna lain terlebih dahulu sedangkan pengguna lain akan medapatkan giliran dari nomor statusnya beserta

kuncinya. Oleh karena itu ia akan diizinkan untuk memasuki critical section-nya. Pada program di atas, yang

akan mengatur masuknya suatu thread ke dalam critical section- nya adalah method setBagianKritis. Jika

salah satu pengguna selesai menjalankan critical section-nya, ia tidak akan lagi membutuhkan kuncinya,

sehingga butuh akan diset menjadi false. Pada program di atas, bagian yang mengatur keluarnya suatu thread

dari critical sectionnya adalah keluarBagianKritis.

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

96Bab 4. Sinkronisasi dan Deadlock

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

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

4.3. Perangkat Keras dan Semafor

4.3.1. Peran Perangkat Keras Dalam Proses Sinkronisasi

Sebelum adanya berbagai macam teknik sinkronisasi seperti saat ini, para programmer cenderung menggunakan

fasilitas yang disediakan oleh perangkat keras dari komputer untuk melakukan sinkronisasi. Oleh karena itu

maka perangkat keras memiliki peranan penting dengan masalah sinkronisasi. Para programmer tidak

menggunakan pendekatan perangkat lunak, karena pendekatan tersebut cenderung sulit dan kompleks

diimplementasikan. Selain itu dapat menyebabkan turunnya kinerja dari suatu produk yang dibuat.

4.3.2. Metode dalam sinkronisasi perangkat keras

Seperti yang telah kita ketahui bahwa untuk tercapainya sinkronisasi, salah satu syaratnya adalah harus tercipta

suatu kondisi yang mutual exclusive, yaitu suatu kondisi dimana hanya ada sebuah proses yang sedang

dieksekusi. Pada pendekatan perangkat keras ini ditekankan bagaimana caranya agar kondisi mutual exclusive itu

tercapai.

Pendekatan dari sisi perangkat keras dapat dibagi menjadi dua:

97Bab 4. Sinkronisasi dan Deadlock

1. Processor Synchronous

2. Memory Synchronous

Processor Synchronous

Central Processing Unit (CPU) mempunyai suatu mekanisme yang dinamakan interrupt. Di dalam sistem

operasi, mekanisme ini digunakan secara intensif, atau dengan kata lain, banyak Konsep sistem operasi yang

menggunakan mekanisme ini. Sebagai contoh: system call, process scheduling, dsb.

Berbicara mengenai sinkronisasi berarti kita mengasumsikan bahwa akan ada dua atau lebih proses yang sedang

berjalan di komputer secara concurrent, atau dengan kata lain konsep time-shared sudah diimplementasikan di

sistem operasi.

Sistem time-shared yang sering diimplementasikan dengan algoritma RR (Round Robin), memanfaatkan

mekanisme interrupt di CPU. Jadi di dalam RR ada suatu satuan waktu yg dinamakan quantum yang mana setiap

quantum dibatasi oleh satu software interrupt.

Teknisnya, akan ada suatu interrupt -- yang biasanya adalah timer interrupt -- yang secara berkala akan

menginterrupt sistem. Pada saat interrupt dilakukan sistem operasi akan segera melakukan proses pergantian dari

proses yang satu ke proses yang lainnya sesuai dengan algoritma.

Seperti yang telah diketahui bahwa untuk menghentikan instruksi tersebut kita memerlukan suatu mekanisme

yang terdapat pada sistem operasi (baca mengenai process scheduling). Dan mekanisme tersebut sangat

bergantung kepada mekanisme interrupt dari perangkat keras. Sehingga, jika kita dapat menon-aktifkan interrupt

pada saat sebuah proses berada di dalam critical section maka permasalahan dari sinkronisasi dapat diselesaikan.

Ternyata para designer komputer melihat celah ini, sehingga saat ini hampir semua komputer yang ada telah

mengimplementasikan instruksi mesin yang akan menon-aktifkan serfis interrupt, dan terdapat instruksi mesin

lain yang kemudian akan mengaktifkan interrupt tersebut.

Sebagai contoh sederhana, kita akan melihat contoh program dari prosesor Atmel ARM tm

(contoh ini diambil

karena prosesor ini mudah didapatkan dan harganya tidak terlalu mahal, serta memiliki dev-kit, silahkan merujuk

ke http://www.atmel.com (http://www.atmel.com)).

Gambar 4-7. Critical Section

mainModul:

00 CLI ’ masuk ke Critical Section dengan cara

’ men-disable interrupt

01 ADD r1,r2 ’ Critical Section

02 .... ’ Critical Section

03 SBI ’ pergi dari Critical Section dengan cara

’ meng-enable interrupt

04 .. ’ Remainder Section

Pada baris ke 0, prosesor akan menon-aktifkan interrupt, yang menyebabkan instruksi-instruksi berikutnya tidak

akan terganggu oleh interrupt. Kemudian setelah setelah baris 03 dieksekusi maka proses akan keluar dari

critical section, yang menyebabkan prosesor mengaktifkan kembali interrupt dan mekanisme scheduling di

sistem operasi dapat berjalan kembali.

Terlihat bahwa dengan mekanisme ini kita sudah cukup mengatasi isu yang ada. Tetapi ternyata mekanisme ini

tidak dapat diterapkan dengan baik di lingkungan multiprocessor. Hal ini disebabkan jika kita menon-aktifkan

98Bab 4. Sinkronisasi dan Deadlock

interrupt, maka yang akan dinon-aktifkan hanyalah satu prosesor saja, sehingga dapat mengakibatkan terjadinya

hal-hal yang tidak diinginkan.

Memory Synchronous

Dilihat dari nama mekanismenya, maka kita sudah dapat memprediksi bahwa mekanisme ini menggunakan jasa

dari memori. Hal tersebut benar adanya, mekanisme memory synchronous memakai suatu nilai yang disimpan di

dalam memori, dan jika suatu proses berhasil mengubah nilai ini, maka proses tersebut akan meneruskan ke

instruksi selanjutnya. Tetapi jika tidak, maka proses ini akan berusaha terus untuk mengubah nilai tersebut.

Jika dilihat dari paragraf di atas, mekanisme ini lebih cocok dikategorikan sebagai pendekatan dari perangkat

lunak. Tetapi, jika kita perhatikan lebih lanjut, ternyata mekanisme ini memerlukan jasa dari perangkat keras.

Mekanisme ini memiliki suatu syarat yang harus dipenuhi agar dapat berjalan sesuai dengan yang diinginkan

yaitu perlunya perangkat keras mempunyai kemampuan untuk membuat suatu instruksi dijalankan secara

atomik. Pengertian dari instruksi atomik adalah satu atau sekelompok instruksi yang tidak dapat diberhentikan

sampai instruksi tsb selesai. Detil mengenai hal ini akan dibicarakan di bagian-bagian selanjutnya.

Sebagai contoh, kita dapat memperhatikan contoh program Java

tm

yang ada di bawah ini:

Gambar 4-8. testANDset

00 boolean testAndSet( boolean variable[] )

01 {

02 boolean t = variable[0];

03 variable[0] = true;

04 return t;

05 }

.....

56 while (testAndSet(lock)) { /* do nothing */ }

57 // Critical Section

58 Lock[0] = false;

59

// Remainder Section

Metoda testAndSet haruslah bersifat atomik, sehingga method ini dianggap sebagai satu instruksi mesin.

Perhatikan pada baris 56 dimana method ini dipakai. Pada baris ini proses berusaha untuk mengubah nilai dari

variable reference lock. Jikalau ia tidak berhasil maka akan terus mencoba, tapi jika berhasil maka proses akan

masuk ke bagian kritis dan setelah ini proses akan mengubah nilai dari lock sehingga memberikan kemungkinan

proses lain untuk masuk.

Janganlah bingung dengan lock, boolean[], yang terkesan aneh. Hal ini bukanlah bagian dari sinkronisasi tetapi

hanyalah suatu bagian dari konsep pass-by-reference dan pass-by-value dari Java

tm

, untuk lebih lanjut mengenai

konsep ini dapat dibaca buku-buku programming Java

tm

. Satu catatan di sini adalah, contoh ini hanyalah sebuah

ilustrasi dan tidak dapat dicompile dan dijalankan, karena Java

tm

konsep instruksi atomik di Java

tm

bersifat

transparan dari sisi programmer (akan dijelaskan pada bagian-bagian selanjutnya).

Keunggulan dari memory synchronous adalah pada lingkungan multiprocessor, semua processor akan terkena

dampak ini. Jadi semua proses yang berada di processor, yang ingin mengakses critical section, meskipun berada

di processor yang berbeda-beda, akan berusaha untuk mengubah nilai yang dimaksud. Sehingga semua

processor akan tersinkronisasi.

99Bab 4. Sinkronisasi dan Deadlock

4.3.3. Instruksi Atomik

Seperti yang telah dijelaskan pada bagian sebelumnya, instruksi atomik adalah satu atau sekelompok instruksi

yang tidak dapat diberhentikan sampai instruksi tersebut selesai. Kita telah memakai instruksi ini pada method

testAndSet.

Instruksi yang dimaksud di sini adalah instruksi-instruksi pada high-level programming, bukanlah pada tingkat

instruksi mesin yang memang sudah bersifat atomik. Sebagai contoh: i++ pada suatu bahasa pemrograman akan

diinterpertasikan beberapa instruksi mesin yang bersifat atomik sebagai berikut:

00 Load R1,i ’ load nilai i ke register 1

01 Inc R1 ’ tambahkan nilai register 1 dengan angka 1

02 Store i,R1 ’ simpan nilai register 1 ke i

Instruksi baris 00-02 bersifat atomik, tetapi i++ tidak bersifat atomik, mengapa? Sebagai contoh kasus,

katakanlah sekarang processor baru menyelesaikan baris 01, dan ternyata pada saat tersebut interrupt datang, dan

menyebabkan processor melayani interrupt terlebih dahulu. Hal ini menyebabkan terhentinya instruksi i++

sebelum instruksi ini selesai. Jikalau instruksi ini (i++) bersifat atomik, maka ketiga instruksi mesin tsb tidak

akan diganggu dengan interrupt.

Perlu diketahui bahwa instruksi ini bukanlah seperti pada processor synchronous yang mana akan mematikan

interrupt terlebih dahulu, tetapi instruksi ini sudah build-in di processor.

Designer processor dapat mengimplementasi konsep ini dengan dua cara yaitu:

1. mengimplementasi instruksi yang build-in

2. mengimplementasi processor mampu membuat suatu instruksi menjadi atomik.

Intel Pentium ternyata memakai cara yang kedua, yaitu dengan adanya suatu perintah LOCK-Assert. Dengan

perintah ini maka semua instruksi dapat dijadikan atomik. Sedangkan SPARC dan IBM mengimplementasikan

suatu rutin yang bersifat atomik seperti swap dan compareAndSwap.

4.3.4. Semafor

Telah dikatakan di atas bahwa pada awalnya orang-orang memakai konsep-konsep sinkronisasi yang sederhana

yang didukung oleh perangkat keras, seperti pemakaian interrupt atau pemakaian rutin-rutin yang mungkin telah

diimplementasi oleh perangkat keras.

Pada tahun 1967, Djikstra mengajukan suatu konsep dimana kita memakai suatu variable integer untuk

menghitung banyaknya proses yang sedang aktif atau yang sedang tidur. Jenis variabel ini disebut semafor.

Tahun-tahun berikutnya, semafor banyak dipakai sebagai primitif dari mekanisme sinkronisasi yang lebih tinggi

dan kompleks lagi. Sebagai contoh: monitor dari Java

tm

. Selain untuk hal tersebut, kebanyakkan semafor juga

digunakan untuk sinkronisasi dalam komunikasi antar device perangkat keras.

Konsep semafor yang diajukan oleh Djikstra terdiri dari dua subrutin yang bernama P dan V. Nama P dan V

berasal dari bahasa Belanda yang berarti Naik dan Turun atau Wait dan Signal. Untuk pembahasan kali ini, kita

akan memakai Wait dan Signal.

Sub-rutin wait akan memeriksa apakah nilai dari semafor tersebut di atas 0. Jika ya, maka nilainya akan

dikurangi dan akan melanjutkan operasi berikutnya. Jika tidak maka proses yang menjalankan wait akan

menunggu sampai ada proses lain yang menjalankan subrutin signal.

100Bab 4. Sinkronisasi dan Deadlock

Satu hal yang perlu diingat adalah subrutin wait dan signal haruslah bersifat atomik. Di sini kita lihat betapa

besarnya dukungan perangkat keras dalam proses sinkronisasi.

Nilai awal dari semaphore tersebut menunjukkan berapa banyak proses yang boleh memasuki critical section

dari suatu program. Biasanya untuk mendukung sifat mutual exclusive, nilai ini diberi 1.

Perlu ditekankan di sini, bahwa semafor bukan digunakan untuk menyelesaikan masalah critical section saja,

melainkan untuk menyelesaikan permasalahan sinkronisasi secara umum.

4.3.5. Wait dan Signal

Seperti yang telah dikatakan di atas, bahwa di dalam subrutin ini, proses akan memeriksa harga dari semafor,

apabila harganya 0 atau kurang maka proses akan menunggu, sebaliknya jika lebih dari 0, maka proses akan

mengurangi nilai dari semaphore tersebut dan menjalankan operasi yang lain.

Arti dari harga semafor dalam kasus ini adalah hanya boleh satu proses yang dapat melewati subrutin wait pada

suatu waktu tertentu, sampai ada salah satu atau proses itu sendiri yang akan memanggil signal.

Bila kita perhatikan lebih kritis lagi, pernyataan "menunggu" sebenarnya masih abstrak. Bagaimanakah cara

proses tersebut menunggu, adalah hal yang menarik. Cara proses menunggu dapat dibagi menjadi dua:

1. spinlock waiting

2. non-spinlock waiting

Spinlock waiting berarti proses tersebut menunggu dengan cara menjalankan perintah-perintah yang tidak ada

artinya. Dengan kata lain proses masih running state di dalam spinlock waiting. Keuntungan spinlock pada

lingkungan multiprocessor adalah, tidak diperlukan context switch. Tetapi spinlock yang biasanya disebut busy

waiting ini menghabiskan cpu cycle karena, daripada proses tersebut melakukan perintah-perintah yang tidak ada

gunanya, sebaiknya dialihkan ke proses lain yang mungkin lebih membutuhkan untuk mengeksekusi

perintah-perintah yang berguna.

Berbeda dengan spinlock waiting, non-spinlock waiting, memanfaatkan fasilitas sistem operasi. Proses yang

melakukan non-spinlock waiting akan memblock dirinya sendiri dan secara otomatis akan membawa proses

tersebut ke dalam waiting queue. Di dalam waiting queue ini proses tidak aktif dan menunggu sampai ada proses

lain yang membangunkan dia sehingga membawanya ke ready queue.

Maka marilah kita lihat listing subrutin dari kedua versi wait.

Gambar 4-9. waitSpinLock

00 void waitSpinLock(int semaphore[] )

01 {

02 while(semaphore[0] <= 0)

{ .. Do nothing .. } // spinlock

03 semaphore[0]--;

04 }

10 void synchronized

waitNonSpinLock( int semaphore [])

11 {

12 while(semaphore[0] <= 0)

13 {

14 wait(); // blocks thread

15 }

16 semaphore[0]--;

101Bab 4. Sinkronisasi dan Deadlock

17 }

Perbedaan dari kedua subrutin ini adalah terletak pada aksi dari kondisi nilai semafor kurang atau sama dengan

dari 0 (nol). Untuk spinlock, disini kita dapat melihat bahwa proses akan berputar-putar di while baris 02 (maka

itu disebut spinlock atau menunggu dengan berputar). Sedangkan pada non-spinlock, proses dengan mudah

memanggil perintah wait, setelah itu sistem operasi akan mengurus mekanisme selanjutnya.

Jangan bingung dengan kata synchronized pada baris 10. Kata ini ada karena memang konsep dari Java

tm

, apabila

sebuah proses ingin menunggu, maka proses tersebut harus menunggu di suatu objek. Pembahasan mengenai hal

ini sudah diluar dari konteks buku ini, jadi untuk lebih lanjut silahkan merujuk kepada buku Java

tm

pegangan

anda.

Karena subrutin wait memiliki dua versi maka hal ini juga berpengaruh terhadap subrutin signal. Subrutin signal

akan terdiri dari dua versi sesuai dengan yang ada pada subrutin wait.

Marilah kita lihat listing programnya

Gambar 4-10. signalSpinLock

00 void signalSpinLock( int semaphore [])

01 {

02 semaphore[0]++;

03 }

10 void synchronized

11 signalNonSpinLock( int semaphore [])

12 {

13 semaphore[0]++;

14 notifyAll(); // membawa waiting thread

15 // ke ready queue

16 }

Letak perbedaan dari kedua subrutin di atas adalah pada notifyAll. NotifyAll berarti membangunkan semua

proses yang sedang berada di waiting queue dan menunggu semaphore yang disignal.

Perlu diketahui di sini bahwa setelah semaphore disignal, proses-proses yang sedang menunggu, apakah itu

spinlock waiting ataukah non-spinlock waiting, akan berkompetisi mendapatkan akses semafor tersebut. Jadi

memanggil signal bukan berarti membangunkan salah satu proses tetapi memberikan kesempatan proses-proses

untuk berkompetisi.

4.3.6. Macam-macam Semafor

Ada 2 macam semafor yang cukup umum, yaitu:

1. Binary semaphore

2. Counting semaphore

Binary semaphore adalah semafor yang bernilai hanya 1 dan 0. Sedangkan Counting semaphore adalah semafor

yang dapat bernilai 1 dan 0 dan nilai integer yang lainnya.

Banyak sistem operasi yang hanya mengimplementasi binary semaphore sebagai primitif, sedangkan counting

semaphore dibuat dengan memakai primitif ini. Untuk lebih rinci mengenai cara pembuatan counting semaphore

dapat dilihat pada bagian berikutnya.

102Bab 4. Sinkronisasi dan Deadlock

Ada beberapa jenis counting semaphore, yaitu semafor yang dapat mencapai nilai negatif dan semafor yang

tidak dapat mencapai nilai negatif (seperti yang telah dicontohkan pada bagian sebelumnya).

4.3.7. Semafor Menyelesaikan Masalah Critical Section

Seperti yang telah dikatakan di atas bahwa semafor tidak hanya digunakan untuk menyelesaikan masalah critical

section saja, tetapi menyelesaikan masalah sinkronisasi yang lainnya. Bahkan tidak jarang semafor dijadikan

primitif untuk membuat solusi dari masalah sinkronisasi yang lebih kompleks.

Kita telah lihat bagaimana penggunaan semafor untuk menyelesaikan masalah sinkronisasi dengan memakai

contoh pada masalah critical section. Pada bagian ini, kita akan melihat lebih dekat lagi apa dan seberapa besar

sebenarnya peran dari semafor itu sendiri sebagai solusi dalam memecahkan masalah critical section.

Lihatlah pada kode-kode di bagian demo. Telitilah, bagian manakah yang harus dieksekusi secara mutual

exclusive, dan bagian manakah yang tidak. Jika diperhatikan lebih lanjut anda akan menyadari bahwa akan selalu

ada satu pasang instruksi wait dan signal dari suatu semafor.

Perintah wait digunakan sebagai pintu masuk critical section dan perintah signal sebagai pintu keluarnya.

Mengapa semafor dapat dijadikan seperti ini? Hal ini disebabkan dengan semafor ketiga syarat utama

sinkronisasi dapat dipenuhi.

Seperti yang telah dijelaskan pada bagian sebelumnya, agar critical section dapat terselesaikan ada tiga syarat

yaitu:

1. Mutual exclusive

2. Make progress

3. Bounded waiting

Sekarang marilah melihat lagi listing program yg ada di bagian sebelumnya mengenai wait dan signal. Jika nilai

awal dari semafor diberikan 1, maka artinya adalah hanya ada satu proses yang akan dapat melewati pasangan

wait-signal. Proses-proses yang lainnya akan menunggu. Dengan kata lain, mekanisme semaphore dengan policy

nilai diberikan 1, dapat menjamin syarat yang pertama, yaitu mutual exclusive.

Bagaimana dengan syarat yang kedua, make progress? Sebenarnya pada waktu proses yang sedang berada di

dalam critical section keluar dari bagian tersebut dengan memanggil signal, proses tersebut tidak memberikan

akses ke critical section kepada proses tertentu yang sedang menunggu tetapi, membuka kesempatan bagi

proses lain untuk berkompetisi untuk mendapatkannya. Lalu bagaimana jika ada 2 proses yang sedang

menunggu dan saling mengalah? mekanisme semafor memungkinkan salah satu pasti ada yang masuk, yaitu

yang pertama kali yang berhasil mengurangi nilai semaphore menjadi 0. Jadi di sini semafor juga berperan

dalam memenuhi syarat kedua.

Untuk syarat yang ketiga, jelas tampak bahwa semafor didefinisikan sebagai pasangan wait-signal. Dengan kata

lain, setelah wait, pasti ada signal. Jadi proses yang sedang menunggu pasti akan mendapat giliran, yaitu pada

saat proses sedang berada di critical section memanggil signal.

Contoh suatu potongan program critical section yang memakai semaphore dapat dilihat di bawah ini. Catatan

bahwa program di bawah ini hanyalah pseudo code.

00 wait(semaphoreVar)

01 // critical section

02 signal(semaphoreVar)

103Bab 4. Sinkronisasi dan Deadlock

Baris 00 dan 02 menjamin adanya mutual exclusive. Sedangkan mekanisme semaphore menjamin kedua syarat

yang lainnya.

4.3.8. Semafor Menyelesaikan Masalah Sinkronisasi antar Proses

Kadangkala kita ingin membuat suatu proses untuk menunggu proses yang lain untuk menjalankan suatu

perintah. Isu yang ada di sini adalah bagaimana caranya suatu proses mengetahui bahwa proses yang lain telah

menyelesaikan instruksi tertentu. Oleh karena itu digunakanlah semafor karena semafor adalah solusi yang

cukup baik dan mudah untuk mengatasi hal tersebut.

Nilai semaphore diset menjadi 0

Proses 1 Proses 2

56 print "satu" 17 wait(semaphoreVar)

57 signal(semaphoreVar) 18 print "dua"

siapapun yang berjalan lebih cepat, maka keluarannya pasti "satu" kemudian diikuti oleh "dua". Hal ini

disebabkan karena jika proses 2 berjalan terlebih dahulu, maka proses tersebut akan menunggu (nilai semafor =

0) sampai proses 1 memanggil signal. Sebaliknya jika proses 1 berjalan terlebih dahulu, maka proses tersebut

akan memanggil signal untuk memberikan jalan terlebih dahulu kepada proses 2.

4.3.9. Solusi Pembuatan Counting Semaphore dari Binary Semaphore.

Pembuatan counting semaphore banyak dilakukan para programmer untuk memenuhi alat sinkronisasi yang

sesuai dengannya. Seperti yang telah dibahas di atas, bahwa counting semaphore ada beberapa macam. Pada

bagian ini, akan dibahas counting semaphore yang memperbolehkan harga negatif.

Listing program di bawah ini diambil dari buku Silberschatz.

00 binary-semaphore S1,S2;

01 int C;

Subrutin waitC dapat dilihat di bawah ini:

02 wait (S1);

03 C--;

04 if ( C < 0 ) {

05 signal (S1);

06 wait (S2);

07 }

08 signal (S1);

subrutin signalC dapat dilihat di bawah ini:

09 wait (S1);

10 C++;

11 if (C <= 0)

104Bab 4. Sinkronisasi dan Deadlock

12 signal (S2);

13 else

14 signal (S1);

Kita memerlukan dua binary semaphore pada kasus ini, maka pada baris 00 didefinisikan dua binary semaphore.

Baris 01 mendefinisikan nilai dari semafor tersebut. Perlu diketahui di sini bahwa waitC adalah wait untuk

counting semaphore, sedangkan wait adalah untuk binary semaphore.

Jika diperhatikan pada subrutin waitC dan signalC di awal dan akhir diberikan pasangan wait dan signal dari

binary semaphore. Fungsi dari binary semaphore ini adalah untuk menjamin critical section (instruksi wait dan

signal dari semafor bersifat atomik, maka begitu pula untuk waitC dan signalC, jadi kegunaan lain semafor

adalah untuk membuat suatu subrutin bersifat atomik).

Binary semaphore S2 sendiri digunakan sebagai tempat menunggu giliran proses-proses. Proses-proses tersebut

menunggu dengan cara spinlock atau non-spinlock tergantung dari implementasi binary semaphore yang ada.

Perhatikan baris 03 dan 04. Baris ini berbeda dengan apa yang sudah dijabarkan pada bagian sebelumnya.

Karena baris ini maka memungkinkan nilai semafor untuk menjadi negatif. Lalu apa artinya bagi kita? Ternyata

nilai negatif mengandung informasi tambahan yang cukup berarti bagi kita yaitu bila nilai semafor negatif, maka

absolut dari nilai tersebut menunjukkan banyaknya proses yang sedang menunggu atau wait. Jadi arti baris 11

menyatakan bahwa bila ada proses yang menunggu maka semua proses dibangunkan untuk berkompetisi.

Mengapa pada baris 05 dilakukan signal untuk S1? Alasannya karena seperti yang telah kita ketahui bahwa

semaphore menjamin ketiga sifat dari critical section. Tetapi adalah tidak relevan bila pada saat waktu

menunggu, waitC masih mempertahankan mutual exclusivenya. Bila hal ini terjadi, proses lain tidak akan dapat

masuk, sedangkan proses yang berada di dalam menunggu proses yang lain untuk signal. Dengan kata lain

deadlock terjadi. Jadi, baris 05 perlu dilakukan untuk menghilangkan sifat mutual exclusive pada saat suatu

proses menunggu.

Pada baris 12 hanya menyatakan signal untuk S2 saja. Hal ini bukanlah merupakan suatu masalah, karena jika

signal S2 dipanggil, maka pasti ada proses yang menunggu akan masuk dan meneruskan ke instruksi 07

kemudian ke instruksi 08 di mana proses ini akan memanggil signal S1 yang akan mewakili kebutuhan di baris

12.

4.3.10. Pemrograman Windows

Win32API (Windows 32 bit Application Programming Interface), menyediakan fungsi-fungsi yang berkaitan

dengan semafor. Fungsi-fungsi yang ada antara lain adalah membuat semaphore dan menambahkan semafor.

Hal yg menarik dari semaphore yang terdapat di Windows

tm

adalah tersedianya dua jenis semafor yaitu, Binary

semaphore dan counting semaphore. Pada Windows

tm

selain kita dapat menentukan nilai awal dari semafor, kita

juga dapat menentukan nilai maksimal dari semafor. Setiap thread yang menunggu di semafor pada Windows

tm

menggunakan metode antrian FIFO (First In First Out.)

4.3.11. Pemrograman Java

tm

Seperti yang telah kita ketahui bahwa satu-satunya alat sinkronisasi yang disediakan oleh Java

tm

untuk

programmer adalah kata kunci synchronized. Sebenarnya kata kunci ini diilhami dari konsep monitor.

Sedikit mengulang, monitor, konsep sinkronisasi yang sudah sangat kompleks, adalah konsep di mana potongan

program ikut di dalamnya. Dalam konsep ini biasanya menggunakan semafor sebagai primitif.

105Bab 4. Sinkronisasi dan Deadlock

Jadi dengan kata lain, secara implisit Java

tm

telah menyediakan semafor bagi kita, namun seperti layaknya

Thread Event Dispatcher di Java

tm

yang bersifat transparan bagi programmer maupun end-user, semaphore juga

tidak dapat diraba dan diketahui oleh kita di Java

tm

ini. Hanya pengetahuan mengenai semafor dan monitorlah

yang dapat menyimpulkan bahwa Java

tm

sebenarnya memakai semafor untuk alat sinkronisasinya.

4.3.12. Masalah Umum yang Berkaitan dengan Sinkronisasi

Secara garis besar ada 3 masalah umum yang berkaitan dengan sinkronisasi yang dapat diselesaikan dengan

menggunakan semafor, ketiga masalah itu adalah:

1. Masalah Bounded Buffer (Producer/Consumer)

2. Masalah Readers/Writers

3. Masalah Dining Philosophers

Latar belakang dan solusi dari ketiga permasalahan di atas akan kita pahami lebih lanjut di bab-bab berikutnya.

4.4. Bounded Buffer

Bounded buffer merupakan suatu struktur data yang mampu untuk menyimpan beberapa nilai dan

mengeluarkannya kembali ketika diperlukan. Jika dianalogikan bounded buffer ini akan mirip dengan sebuah

tumpukan piring. Kita menaruh piring dan menaruh lagi sebuah piring, ketika ingin mengambil piring maka

tumpukan yang paling atas yang akan terambil. Jadi piring terakhir yang dimasukan akan pertama kali diambil.

Pada bagian ini akan dicontohkan suatu produser konsumer. produser akan menghasilkan suatu barang dan

konsumer akan mengkonsumsi barang yang dihasilkan oleh produser. produser dan konsumer ini akan

mengakses bounded buffer yang sama. produser setelah menghasilkan suatu barang dia akan menaruh barang itu

di bounded buffer sebaliknya konsumer ketika membutuhkan suatu barang, dia akan mengambilkannya dari

bounded buffer.

Hal yang harus diperhatikan dalam contoh program ini bahwa:

• Bounded buffer memiliki batas banyaknya data yang dimasukan.

• Barang yang dikonsumsi oleh konsumer terbatas.

• Jika bounded buffer telah penuh produser tidak mampu menaruh lagi dan akan menunggu sampai ada tempat

yang kosong.

• Jika bounded buffer kosong maka konsumer harus menunggu sampai ada barang yang ditauh oleh produser.

Gambar 4-11. Bounded buffer dengan sinkronisasi

/**

contoh penggunaan bounded buffer

author vap20@mhs.cs.ui.ac.id

**/

public class ContohBoundedBuffer

{

public static void main(String args[])

{

106Bab 4. Sinkronisasi dan Deadlock

BoundedBuffer buffer = new BoundedBuffer();

Produser prod = new Produser(buffer);

Consumer con = new Consumer(buffer);

prod.start();

con.start();

}

}

/**

*struktur data yang akan digunakan untuk menyimpan data

*/

class BoundedBuffer

{

//deklarasi variabel

int data[];

int penunjuk;

boolean bisa;

public BoundedBuffer()

{

data= new int[4];

penunjuk =0;

bisa = true;

}

public int getData()

{

try

{

while( penunjuk < 0 )

wait();

int dataKe = penunjuk;

penunjuk-=1;

bisa = true;

System.out.println("pointer buffer menunjuk ke:"+penunjuk);

return data[dataKe];

}

catch(Exception e)

{

return -1;

}

}

public void inputData(int sesuatu)

{

try

{

penunjuk+=1;

if(penunjuk > 3)

bisa = false;

while(!bisa)

wait();

107Bab 4. Sinkronisasi dan Deadlock

data[penunjuk]=sesuatu;

System.out.println("memasukan nilai:"+ sesuatu);

System.out.println("pointer buffer menunjuk ke:"+penunjuk);

}

catch(Exception e)

{

}

}

}

class Produser extends Thread

{

//deklarasi variabel

BoundedBuffer buffer;

public Produser(BoundedBuffer aBuffer)

{

buffer = aBuffer;

}

public void run()

{

int i=0;

for(int ij=0;ij<10;ij++)

{

i++;

try

{

buffer.inputData(i);

System.out.println("memasukan nilai sebesar:"+i);

sleep(30);

}

catch(Exception e)

{

System.exit(0);

}

}

}

}

class Consumer extends Thread

{

//deklarasi variabel

BoundedBuffer buffer;

public Consumer(BoundedBuffer aBuffer)

{

buffer = aBuffer;

}

public void run()

{

int i=0;

108Bab 4. Sinkronisasi dan Deadlock

for(int ik=0;ik<10;ik++)

{

try

{

i=buffer.getData();

System.out.println("mengambil nilai:"+i);

sleep(30);

}

catch(Exception e)

{

System.exit(0);

}

}

}

}

Seperti yang terlihat pada contoh program diatas. Jika bounded buffer kosong maka produser akan berhenti

sejenak dan menunggu sampai ada konsumer yang mengkonsumsi. Sebaliknya jika bounded buffer kosong maka

konsumer akan menunggu sampai bounded buffer disi oleh produser.

Pada contoh program ini yang harus diperhatikan adanya kemungkinan terjadinya deadlock. Yaitu keadaan

dimana produser dan konsumer saling menunggu. Produser menunggu konsumer mengkonsumsi barang dan

konsumer menunggu produser menaruh barang. Hal ini terjadi karena adanya komunikasi yang macet antara

produser dan konsumer. Produser setelah menaruh barang tidak menginformasikan ke konsumer bahwa ada

barang yang sudah dimasukan. konsumer terus menunggu tanpa tahu bahwa barang sudah dimasukan.

Hal yang sebaliknya bisa terjadi; produser menunggu sampai bounded buffer ada yang kosong ,padahal

konsumer telah mengkonsumsi yang otomatis ada ruang kosong dalam bounded buffer hanya saja produser tidak

diberitahu. Sehingga pada saat bounded buffer kosong produser tetap saja menunggu.

Deadlock yang sederhana pada contoh diatas bisa diatasi jika komunikasi bisa dilakukan oleh produser dan

konsumer. Pada contoh program ada kode program notifyAll() pada bagian produser dan konsumer. Kode ini

berfungsi untuk memberitahu kepada semua proses yang menunggu bahwa suatu proses telah melakukan

sesuatu. sehingga proses yang lain akan melihat apakah mereka masih harus menunggu atau melakuan aksi

mereka lagi. Jika produser setelah menaruh ke bounded buffer dia akan memberitahukan ke konsumer

sebaliknya konsumer akan memberitahukan ke produser bahwa dia melakukan konsumsi.

4.5. Masalah Readers/Writers dan Dining Philosophers

4.5.1. Gambaran Umum Masalah Readers/Writers

Masalah Readers/Writersmerupakan salah satu masalah sinkronisasi klasik yang sering digunakan untuk

mendiskusikan dan membandingkan berbagai cara untuk menyelesaikan masalah sinkronisasi. Secara singkat,

masalah ini terjadi ketika ada beberapa pembaca dan penulis ingin mengakses suatu berkas pada saat

bersamaan.Kembali kepada masalah Readers/Writers, bahwa inti dari permasalahan ini adalah adanya beberapa

pembaca dan penulis yang ingin mengakses suatu berkas secara simultan. Sebagai syarat bahwa data yang

terkandung dalam berkas tersebut tetap konsisten, maka setiap kali berkas tersebut ditulis, maka hanya ada boleh

maksimal satu penulis yang menulisnya. Untuk pembaca, hal ini tidak perlu dikhawatirkan sebab membaca suatu

berkas tidak mengubah isi berkas. Dengan kata lain, pada suatu saat diperbolehkan untuk beberapa pembaca

untuk membaca berkas tersebut. Akan tetapi, ketika ada yang sedang menulis, tidak boleh ada satupun yang

membaca. Ini berarti bahwa thread penulis menjalankan tugasnya secara mutual eksklusif .

109Bab 4. Sinkronisasi dan Deadlock

Untuk mengatasi masalah ini, ada tiga macam solusi yang akan dibahas. Dasar pembagian solusi ini adalah

prioritas. Pertama, solusi dengan pembaca diprioritaskan akan dibahas. Kemudian dilanjutkan dengan solusi

dengan penulis yang diprioritaskan. Terakhir, solusi dengan pembaca dan penulis saling bergantian akan dibahas.

Pada setiap solusi akan dilihat mengenai tingkat kesuksesan solusi tersebut bila kita lihat dari sudut pandang

syarat penyelesaian critical section. Implementasi dari setiap solusi yang diberikan di bawah ini adalah dengan

menggunakan semafor.

4.5.2. Solusi Dengan Pembaca Diprioritaskan

Pada solusi ini, setiap kali ada thread pembaca yang berusaha \untuk memulai membaca ketika ada

setidak-tidaknya satu thread pembaca yang sedang membaca, maka thread pembaca yang baru ingin untuk

membaca akan diberikan akses untuk membaca. Tujuan dari pemberian prioritas ini adalah untuk

memaksimalkan throughput. Sebagai ganti dari pemaksimalan throughput ini, thread penulis dapat berada pada

antrian untuk waktu yang tak terbatas atau dapat disebut sebagaistarvation, terutama ketika terjadi permintaan

untuk membaca berkas secara berkelanjutan. Padahal, agar sebuah thread penulis dapat masuk ke critical

sectionnya, tidak boleh ada satupun thread pembaca yang sedang mengakses berkas.

Dengan demikian, solusi ini gagal memenuhi persyaratan bahwa setiap thread seharusnya tidak dibiarkan

menunggu dalam waktu yang tidak terbatas karena akan mengakibatkan starvation . Akan tetapi, jika yang ingin

dituju adalah throughput yang sebesar-besarnya, maka solusi ini adalah yang paling tepat.

Berikut adalah contoh implementasi dari solusi ini:

Gambar 4-12. Ilustrasi Penulis/Pembaca

/**

* Tempat segala sesuatunya dimulai.

* Pada kelas ini, semua thread penulis dan pembaca

* dibuat dan dijalankan. Agar kemungkinannya lebih

* tinggi untuk semua thread penulis dan pembaca

* memiliki kesempatan bersaing secara adil mendapatkan

* waktu CPU, maka prioritas thread Pembuat dibuat

* maksimum, sementara semua thread penulis dan pembaca

* dibuat normal. Catatan: hal ini tidak berguna dalam

* lingkungan Linux.

*/

public class PembuatBacaTulis1

{

public static void main(String args[])

{

Thread.currentThread().setPriority(Thread.MAX_PRIORITY);

Penulis penulis[] = new Penulis[N_PENULIS];

Pembaca pembaca[] = new Pembaca[N_PEMBACA];

Berkas berkas = new Berkas();

for (int i = 0; i < N_PENULIS; i++)

{

penulis[i] = new Penulis(i, berkas);

penulis[i].setPriority(Thread.NORM_PRIORITY);

penulis[i].start();

}

for (int i = 0; i < N_PEMBACA; i++)

{

pembaca[i] = new Pembaca(i, berkas);

pembaca[i].setPriority(Thread.NORM_PRIORITY);

pembaca[i].start();

110Bab 4. Sinkronisasi dan Deadlock

}

}

final static int N_PEMBACA = 3;

final static int N_PENULIS = 3;

final static int BATAS = 1;

}

/**

* kelas Penulis dengan siklus hidup sebesar

batas yang diberikan oleh konstanta BATAS pada

kelas PembacaBuatTulis1. Siklus hidup dari

sebuah penulis adalah tidur, mulai menulis,

sedang menulis dan selesai menulis.

*/

class Penulis extends Thread

{

public Penulis(int id, Berkas berkas)

{

this.id = id;

this.berkas = berkas;

hitungan = 0;

setName("Penulis " + id);

}

public void run()

{

while (hitungan < PembuatBacaTulis1.BATAS)

{

berkas.tidur();

System.out.println("Penulis " + id + " tidur.");

berkas.mulaiMenulis();

System.out.println("Penulis " + id + " mulai menulis.");

berkas.tidur();

System.out.println("Penulis " + id + " sedang menulis.");

berkas.selesaiMenulis();

System.out.println("Penulis " + id + " selesai menulis.");

hitungan++;

}

}

private Berkas berkas;

private int id;

private int hitungan;

}

/**

* kelas Pembaca dengan siklus hidup sebesar

batas yang diberikan oleh konstanta BATAS pada

kelas PembacaBuatTulis1. Siklus hidup dari

sebuah pembaca adalah tidur, mulai membaca,

sedang membaca dan selesai membaca.

*/

class Pembaca extends Thread

{

{

this.id = id;

111Bab 4. Sinkronisasi dan Deadlock

this.berkas = berkas;

hitungan = 0;

setName("Pembaca " + id);

}

public void run()

{

while (hitungan < PembuatBacaTulis1.BATAS)

{

berkas.tidur();

System.out.println("Pembaca " + id + " tidur.");

berkas.mulaiMembaca();

System.out.println("Pembaca " + id + " mulai membaca.");

berkas.tidur();

System.out.println("Pembaca " + id + " sedang membaca.");

berkas.selesaiMembaca();

System.out.println("Pembaca " + id + " selesai membaca.");

hitungan++;

}

}

private Berkas berkas;

private int id;

private int hitungan;

}

/**

* Kelas ini menggambarkan apa saja yang dapat

* dilakukan oleh setiap thread pembaca dan penulis

* ke suatu berkas.

*/

class Berkas

{

public Berkas()

{

nPembaca = 0;

brks = new Semafor(1);

mutex = new Semafor(1);

}

public void mulaiMembaca()

{

mutex.tunggu();

nPembaca++;

if (nPembaca == 1) brks.tunggu();

mutex.sinyal();

}

public void selesaiMembaca()

{

mutex.tunggu();

--nPembaca;

if (nPembaca == 0) brks.sinyal();

mutex.sinyal();

}

public void mulaiMenulis()

112Bab 4. Sinkronisasi dan Deadlock

{

brks.tunggu();

}

public void selesaiMenulis()

{

brks.sinyal();

}

public void tidur()

{

try

{

long t = (long) (Math.random() * 1000);

Thread.sleep(t);

}

catch (InterruptedException e) {}

}

private Semafor brks, mutex;

private int nPembaca;

}

/**

* kelas ini merupakan implementasi semafor.

* Implementasi ini merupakan modifikasi dari

* implementasi semafor oleh Silberschatz, Galvin,

* dan Gagne.

*/

final class Semafor

{

public Semafor()

{

nilai = 0;

}

public Semafor(int n)

{

nilai = n;

}

public synchronized void tunggu()

{

nilai--;

if (nilai < 0)

{

try { wait(); }

catch(InterruptedException e) {}

}

}

public synchronized void sinyal()

{

nilai++;

if (nilai <= 0) notify();

}

113Bab 4. Sinkronisasi dan Deadlock

private int nilai;

}

Bila contoh diatas dijalankan, maka hasil yang cukup mungkin didapatkan adalah seperti berikut:

Gambar 4-13. Tampilan Layar

Pembaca 0 tidur.

Pembaca 0 mulai membaca.

Pembaca 2 tidur.

Pembaca 2 mulai membaca.

Penulis 1 tidur.

Pembaca 1 tidur.

Pembaca 1 mulai membaca.

Penulis 0 tidur.

Penulis 2 tidur.

Pembaca 1 sedang membaca.

Pembaca 1 selesai membaca.

Pembaca 0 sedang membaca.

Pembaca 0 selesai membaca.

Pembaca 2 sedang membaca.

Pembaca 2 selesai membaca.

Penulis 1 mulai menulis.

Penulis 1 sedang menulis.

Penulis 1 selesai menulis.

Penulis 0 mulai menulis.

Penulis 0 sedang menulis.

Penulis 0 selesai menulis.

Penulis 2 mulai menulis.

Penulis 2 sedang menulis.

Penulis 2 selesai menulis.

Seperti terlihat di atas, thread-thread pembaca (BC0, BC1, BC2) mendominasi thread-thread penulis (TL0,

TL1, TL2) dalam hal akses berkas, sehingga semua thread penulis harus menunggu hingga semua thread

pembaca selesai.

4.5.3. Solusi Dengan Penulis Diprioritaskan

Pada bagian ini, begitu tidak ada yang mengakses berkas dan ada thread penulis yang sedang menunggu untuk

mendapatkan akses berkas tersebut, maka thread penulis ini akan langsung mendapatkan akses ke berkas.

Sebaliknya, bila ada thread pembaca yang juga sama-sama menunggu, maka thread pembaca ini harus

menunggu hingga semua threadpenulis yang sedang menunggu diantrian mendapatkan akses ke berkas dan

menyelesaikan proses penulisannya. Walaupun pada saat tersebut ada sebuah thread pembaca yang sedang

mengakses berkasnya, jika sudah ada thread penulis yang menunggu di antrian, maka semua thread pembaca

yang menginginkan akses ke berkas tidak mendapatkannya hingga thread penulis yang berada diantrian

mendapatkan akses yang dibutuhkannya.

Akibat dari cara prioritas seperti ini adalah adanya jaminan bahwa setiap thread pembaca akan mendapatkan

informasi terbaru. Akan tetapi, hal ini berakibat bahwa jika ada sekelompok besar thread penulis yang datang

pada suatu waktu, maka thread pembaca tidak akan mendapatkan giliran sampai waktu yang tidak terbatas dan

terjadilah starvation pada threadpembaca. Oleh karena itu, solusi ini pun gagal memenuhi persyaratan bahwa

seharusnya setiap thread tidak boleh dibiarkan menunggu dalam waktu yang tidak terbatas.

114Bab 4. Sinkronisasi dan Deadlock

Implementasi dari solusi ini tidak jauh berbeda dengan solusi sebelumnya. Bahkan, kita hanya perlu sedikit

memodifikasi kelas Berkas dengan menambahkan sebuah flag untuk menyatakan apakah ada thread penulis yang

sedang menunggu di antrian. Berikut ini adalah implementasi kelas Berkas untuk solusi ini:

Gambar 4-14. Ilustrasi Penulis/Pembaca

/**

* Kelas ini menggambarkan apa saja yang dapat

* dilakukan oleh setiap thread pembaca dan penulis

* ke suatu berkas. Kelas ini diadaptasi dari Stallings98.

*/

class Berkas

{

public Berkas()

{

nPembaca = nPenulis = 0;

baca = new Semafor(1);

mutex1 = new Semafor(1);

mutex2 = new Semafor(1);

mutex3 = new Semafor(1);

tulis = new Semafor(1);

}

public void mulaiMembaca()

{

mutex1.tunggu();

baca.tunggu();

mutex2.tunggu();

nPembaca++;

if (nPembaca == 1) tulis.tunggu();

mutex2.sinyal();

baca.sinyal();

mutex1.sinyal();

}

public void selesaiMembaca()

{

mutex2.tunggu();

nPembaca--;

if (nPembaca == 0) tulis.sinyal();

mutex2.sinyal();

}

public void mulaiMenulis()

{

mutex3.tunggu();

nPenulis++;

if (nPenulis == 1) baca.tunggu();

mutex3.sinyal();

tulis.tunggu();

}

public void selesaiMenulis()

{

tulis.sinyal();

mutex3.tunggu();

nPenulis--;

if (nPenulis == 0) baca.sinyal();

mutex3.sinyal();

}

public void tidur()

{

try { Thread.sleep((long) (Math.random() * 1000)); }

catch (InterruptedException e) {}

}

private Semafor baca, tulis, mutex1, mutex2, mutex3;

private int nPembaca, nPenulis;

}

Perlu diperhatikan bahwa jumlah critical section bertambah banyak seiring dengan keperluan untuk menghitung

jumlah penulis yang adadi antrian. Karena jumlah criticalsection bertambah, banyak semafor yang diperlukan

juga meningkat. Yang perlu diperhatikan adalah bahwa pada method mulaiMembaca(), kita memerlukan sebuah

semafor tambahan untuk menjaga agar semafor baca tidak langsung begitu saja diakses. Bila semafor baca dapat

langsung diakses,maka dapat terjadi deadlock.

Dengan kelas yang lain tidak berubah, maka hasil yang cukup mungkin didapatkan adalah seperti berikut:

Gambar 4-15. Tampilan Layar

Penulis 0 tidur.

Penulis 0 mulai menulis.

Pembaca 2 tidur.

Pembaca 0 tidur.

Penulis 2 tidur.

Penulis 1 tidur.

Penulis 0 sedang menulis.

Penulis 0 selesai menulis.

Penulis 2 mulai menulis.

Penulis 2 sedang menulis.

Penulis 2 selesai menulis.

Penulis 1 mulai menulis.

Penulis 1 sedang menulis.

Penulis 1 selesai menulis.

Pembaca 2 mulai membaca.

Pembaca 0 mulai membaca.

Pembaca 1 tidur.

Pembaca 1 mulai membaca.

Pembaca 1 sedang membaca.

Pembaca 1 selesai membaca.

Pembaca 2 sedang membaca.

Pembaca 2 selesai membaca.

Pembaca 0 sedang membaca.

Pembaca 0 selesai membaca.

Berikut adalah ilustrasi dari hasil contoh di atas:

Ilustrasi di atas menegaskan bahwa ketika thread penulis menunggu di antrian, maka tidak ada satupun thread

pembaca yang dapat mengakses berkas yang diinginkan hingga setiap thread penulis yang ada di antrian telah

menyelesaikan tugasnya. Bila thread penulis terus berdatangan, maka thread pembaca tidak akan mendapatkan

giliran sedikitpun dan dengan demikian terjadilah kelaparan.

116Bab 4. Sinkronisasi dan Deadlock

4.5.4. Solusi Dengan Pembaca Dan Penulis Mendapat Prioritas Secara

Bergantian

Karena kedua solusi sebelumnya menghasilkan kedua ekstrem dalam akses berkas (thread pembaca atau thread

penulis menunggu terus di antrian tanpa ada kepastian akan dijalankan) atau dapat juga dibilang pada kedua

solusi diatas tersebut selalu harus ada pihak yang starvation maka pada solusi ini diusahakan sebuah metode

yang mengakomodasi kedua belah pihak. Cara untuk melakukan ini cukup mudah yaitu dengan menerapkan

metode gilir-menggilir. Sebuah penulis dapat mengakses berkas jika tidak ada thread pembaca yang sedang

mengakses. Setelah selesai,thread ini memberikan giliran ke thread pembaca.Sebuah pembaca dapat mengakses

berkas yang ada jika tidak ada penulis yang menunggu atau bila pada saat itu adalah giliran pembaca. Pembaca

pertama yang pertama selesai mengakses berkas kemudian mengganti giliran sekarang menjadi giliran penulis.

Dengan metode giliran ini, tidak ada thread yang tertunda tanpa batas. Karena setiap syarat dari penyelesaian

criticalsection yang baik dipenuhi, maka cara seperti ini merupakan cara yang baik untuk menyelesaikan

masalah konkurensi.

4.5.5. Masalah Dining Philosophers

Masalah ini pertama ini pertama kali ditulis dan diselesaikan oleh Djikstra pada tahun 1965.Masalah ini

memodelkan masalah enkapsulasi dari ketergantungan mesin dan masalah portabilitas. Dalam masalah Dining

Philosophers, diketahui sejumlah (N) filusuf yang hanya memiliki tiga status, berpikir, lapar, dan makan. Semua

filusuf berada di sebuah meja makan bundar yang ditata sehingga di depan setiap filusuf ada sebuah piring berisi

mie dan di antara dua piring yang bersebelahan terdapat sebuah sumpit.

Pada awalnya, semua filusuf akan berpikir selama waktu yang tidak tentu. Setelah berpikir lama, filusuf akan

merasa lapar. Pada saat lapar, ia berusaha untuk mengambil 2 buah sumpit yang ada di kanan dan di kirinya

untuk makan. Dia mengambil sumpitnya satu per satu. Begitu ia mendapat sebuah sumpit, ia tidak akan

melepaskannya. Jika ia hanya berhasil mengambil kurang dari 2 sumpit, maka ia akan menunggu sampai 2

sumpit diambil. Begitu dia mendapatkan 2 sumpit, maka dia akan makan mienya untuk sementara waktu dan

kemudian meletakkan kedua sumpitnya. Kedua sumpit ini kemudian dapat digunakan oleh filusuf-filusuf yang

lain.Posisi meja Filsuf dengan menggunakan semafor.Setiap sumpit mewakili sebuah semafor. Kemudian,ketika

seorang filsuf lapar,maka dia akan mencoba mengambil sumpit di kiri dan dikananya atau dengan kata lain dia

akan menunggu sampai kedua sumpit itu dapat digunakan. Setelah selesai makan,sumpit diletakan kembali dan

sinyal diberikan ke semafor sehingga filusuf lain yang membutuhkan dapat menggunakan sumpitnya.Dan dia

sendiri kemudian kembali berpikir. Tujuan dari masalah ini adalah untuk mencari cara sehingga para filusuf tidak

akan pernah mati kelaparan. Hal ini juga merupakan salah satu representasi dari pengalokasian source komputer

yang terbatas dengan beberapa proses sehingga dapat mengakibatkan deadlock dan starvation.

Salah satu solusi yang mungkin langsung terlihat adalah dengan menggunakan semafor. Setiap sumpit mewakili

sebuah semafor. Kemudian, ketika seorang filusuf lapar, maka dia akan mencoba mengambil sumpit di kiri dan

di kanannya, atau dengan kata lain dia akan menunggu sampai kedua sumpit tersebut dapat ia gunakan. Setelah

selesai makan, sumpit diletakkan kembali dan sinyal diberikan ke semafor sehingga filusuf lain yang

membutuhkan dapat menggunakan sumpitnya. Berikut contoh programnya:

Gambar 4-16. Program Dining Philosopher

/**

* @author Sylvia Susanto

* @author V.A.Pragantha

*

* Program ini berlisensi GPL

*

* Kelas ini membuat sebuah simulasi untuk masalah

117Bab 4. Sinkronisasi dan Deadlock

* Dining Philosophers.

*/

public class Dining

{

public static void main (String args[])

{

Semafor sumpit[] =

{

new Semafor(1), new Semafor(1),

new Semafor(1), new Semafor(1)

};

Filsuf filsuf[] =

{

new Filsuf("Filsuf A", sumpit[0], sumpit[1]),

new Filsuf("Filsuf B", sumpit[1], sumpit[2]),

new Filsuf("Filsuf C", sumpit[2], sumpit[3]),

new Filsuf("Filsuf D", sumpit[3], sumpit[0])

};

int i=0;

while(i< 4)

{

filsuf[i].start();

i++;

}

}

}

/**

* Kelas ini menggambarkan kegiatan dari setiap filsuf.

*/

class Filsuf extends Thread

{

public Filsuf(String name, Semafor sumpit1, Semafor sumpit2)

{

nama = name;

setName("Filsuf " + i);

kiri = sumpit1; kanan = sumpit2;

}

/*

* Method ini dipanggil pada saat Filsuf di start

*/

public void run()

{

int i=0;

try

{

while (true)

{

System.out.println(this + " sedang berpikir");

berpikir();

System.out.println(this + " lapar");

makan();

System.out.println(this + " sudah kenyang");

}

118Bab 4. Sinkronisasi dan Deadlock

}

catch(Exception e)

{

System.out.println(e);

System.exit(0);

}

public void berpikir()

{

try

{

Thread.sleep((long) (Math.random() * 1000));

}

catch (InterruptedException e){}

}

public void makan()

{

kanan.tunggu();

System.out.println(" "+nama+" melihat sumpit kanan..ternyata ada..");

kiri.tunggu();

System.out.println(" "+nama+" melihat sumpit kiri..ternyata ada..");

System.out.println(" "+nama+ "sedang makan");

kanan.sinyal();

System.out.println(" "+nama+" melepas sumpit kanan");

kiri.sinyal();

System.out.println(" "+nama+" melepas sumpit kiri");

}

private String nama;

private Semafor kiri, kanan;

}

/**

* kelas ini merupakan implementasi semafor.

* Implementasi ini merupakan modifikasi dari

* implementasi semafor oleh Silberschatz, Galvin,

* dan Gagne.

*/

final class Semafor

{

public Semafor()

{

nilai = 0;

}

public Semafor(int n)

{

nilai = n;

}

public synchronized void tunggu()

{

nilai--;

if (nilai < 0)

{

try

119Bab 4. Sinkronisasi dan Deadlock

{

wait();

}

catch(InterruptedException e)

{

System.exit(0);

}

}

}

public synchronized void sinyal()

{

nilai++;

if (nilai <= 0) notifyAll();

}

private int nilai;

}

Akan tetapi, solusi ini tidak dapat diterima. Alasannya sangat sederhana, yaitu deadlock dapat terjadi. Contoh

kasusnya adalah ketika semua filusuf telah mengambil sumpit di sebelah kirinya, maka tidak ada lagi sumpit

yang tersisa di meja. Karena tidak ada sumpit yang tersisa di meja, maka setiap filusuf kekurangan sebuah

sumpit. Berhubung setelah berhasil mengambil sebuah sumpit, sumpit tersebut tidak akan diletakkan kembali

sampai filusuf yang bersangkutan makan, maka tidak akan ada satu filusuf pun yang akan makan.

Ada beberapa alternatif yang merupakan pemecahan dari permasalahan ini diantaranya yang disajikan oleh

Stallings,antara lain dengan menyuruh setiap filusuf untuk mengambil sumpitnya secara berselang-seling. Filsuf

dengan urutan bilangan ganjil pertama kali mengambil sumpit di sebelah kanannya,sementara filusuf dengan

urutan bilangan genap pertama kali mengambil sumpit di sebelah kirinya sedangkan alternatif yang lain adalah

dengan menyediakan sebanyak N sumpit lagi,sehingga lebih higienis di samping dijamin tidak menghasilkan

deadlock; mengurangi banyak filusuf yang boleh duduk di meja makan sebanyak satu.

4.6. Critical Region Dan Monitor

4.6.1. Latar Belakang

Sejauh ini, kita telah mengenal semafor sebagai perangkat keras sinkronisasi yang ampuh, lalu mengapa kita

membutuhkan bahasa pemrograman untuk melakukan sinkronisasi? Alasan yang sederhana adalah karena

ternyata implementasi semafor memiliki beberapa kelemahan. Kelemahan yang pertama adalah kenyataan

bahwa semafor memerlukan implementasi di tingkat rendah, sesuatu hal yang kompleks untuk dilakukan

kebanyakan orang. Bahasa pemrograman lebih mudah untuk dipelajari dan diimplementasikan. Kode semafor

terdistribusi dalam seluruh program sehingga menyulitkan pemeliharaan. Hal ini merupakan kelemahan lain dari

semafor. Sehingga jelas tampaknya, bahwa kita memerlukan konstruksi tingkat tinggi yang dapat mengatasi atau

paling tidak mengurangi kelemahan-kelemahan yang terdapat dalam semafor.

4.6.2. Critical Region

Critical region adalah bagian dari program dan diamanatkan untuk selalu berada dalam keadaan mutual

exclusion. perbedaan critical region ini dengan mutual exclusion biasa yang dibahas sebelumnya adalah critcal

120Bab 4. Sinkronisasi dan Deadlock

region diimplementasikan oleh compiler. keuntungan menggunakan ini adalah programmer tidak perlu lagi

mengimplementasikan algoritma yang rumit untuk mendapatkan mutual exclusion.

4.6.2.1. Cara Kerja Critical Region

Pada critical region memiliki sebuah komponen boolean yang mentest apakah bagian dari program boleh masuk

kedalam state critical region atau tidak. jika nilai boolean ini true maka proses boleh masuk ke critical region.

jika boolean ini bernilai false bagian yang ini akan dimasukan kedalam sebuah antrian sampai nilai boolean ini

bernilai true.

Dalam critical region dikenal ada 2 antrian: main queue dan event queue. main queue berfungsi untuk

menampung proses yang akan memasuki critical region hanya saja critical region masih digunakan oleh proses

lain. event queue berguna untuk menampung proses yang tidak dapat memasuki critical region karena nilai

boolennya bernilai false.

4.6.3. Monitor

Konsep monitor diperkenalkan pertama kali oleh Hoare (1974) dan Brinch Hansen (1975) untuk mengatasi

beberapa masalah yang timbul ketika memakai semafor.

Monitor merupakan kumpulan dari prosedur, variabel, dan struktur data dalam satu modul. monitor hanya dapat

diakses dengan menjalankan fungsinya. kita tidak dapat mengambil variabel dari monitor tanpa melalui

prosedurnya. hal ini dilakukan untuk melindungivariabel dari akses yang tidak sah dan juga mengurangi

terjadinya error.

Monitor mungkin bisa dianalogikan dengan sebuah sekretariat didalam sebuah fakultas. dengan sekretariat

sebagai suatu monitor dan mahasiswa,dosen sebagai proses. dan informasi akademik( jadwal, nilai, jadwal dosen

etc) sebagai variabel. kila seorang mahasiswa ingin mengambil transkip nilainya dia akan meminta kepada

petugas sekretariat daripada mengambilnya sendiri dan mencarinya sendiri, berapa besar kemungkinan

kerusakan yang bisa ditimbulkan dengan mengambilnya secara langsung?.jika meminta kepada petugas

sekretariat maka petugas akan melakukan berbagi kegiatan untuk memberikan transkip. dan kerusakan terhadap

terhadap dokumen lain bisa dihindari.

4.6.3.1. Keterbatasan Monitor

Karena monitor berkaitan dengan konsep bahasa pemrograman sehingga kompiler bertanggung-jawab untuk

mengkondisikan monitor sebagai mutual eksklusif. Namun, pada kenyataannya tidak semua kompiler dapat

menerapkan peraturan mutual eksklusif seperti yang dibutuhkan oleh Monitor tersebut. Mungkin bahasa

pemrograman yang sama juga tidak memiliki semafor, tetapi menambahkan semafor jauh lebih mudah.

jika dianalogikan lagi dengan sekretariat akademik fakultas. ambil contoh kasus penjadwalan ulang ujian untuk

seorang mahasiswa. dalam proses ini sekretariat tidak mampu langsung memberikan jadwal ulang tetapi perlu

bantuan mahasiswa tersebut untuk menghubungi dosen yang bersangkutan, dosen perlu untuk membuat soal

yang baru,mahasiswa mungkin perlu mengurus ijin ke pembantu dekan 1,etc.

121Bab 4. Sinkronisasi dan Deadlock

4.7. Deadlock

4.7.1. Prinsip dari Deadlock

Deadlock dalam arti sebenarnya adalah kebuntuan. Kebuntuan yang dimaksud dalam sistem operasi adalah

kebuntuan proses. Jadi Deadlock ialah suatu kondisi dimana proses tidak berjalan lagi ataupun tidak ada

komunikasi lagi antar proses. Deadlock disebabkan karena proses yang satu menunggu sumber daya yang

sedang dipegang oleh proses lain yang sedang menunggu sumber daya yang dipegang oleh proses tersebut.

Dengan kata lain setiap proses dalam set menunggu untuk sumber yang hanya dapat dikerjakan oleh proses lain

dalam set yang sedang menunggu. Contoh sederhananya ialah pada gambar berikut ini

Proses P1 Proses P2

..... .....

..... .....

Receive (P2); Receive (P1);

..... .....

..... .....

Send (P2, M1); Send (P1, M2);

Proses tersebut dapat direpresentasikan dengan gambar sebagai berikut

Gambar 4-17. Contoh deadlock pada rel kereta

Disadur dari www.tvcc.cc.or.us/staff/fuller/ cs160/chap3/chap3.html

Dari gambar tersebut bisa dilihat bahwa kedua kereta tersebut tidak dapat berjalan. Karena kedua kereta tersebut

saling menunggu kereta yang lain untuk lewat dulu agar keretanya dapat berjalan. Sehingga terjadilah deadlock.

Contoh lain yang dapat merepresentasikan deadlock ialah jembatan gantung sebagai berikut:

Gambar 4-18. Contoh Deadlock di Jembatan Gantung

disadur dari Modern Operating Systems, Tanenbaum, 1992

122Bab 4. Sinkronisasi dan Deadlock

sehingga orang yang ada di sebelah kiri jembatan tidak dapat melaju sebab terjadi deadlock di tengah jembatan

(bagian yang dilingkari). Contoh lain ialah di persimpangan jalan berikut ini:

Gambar 4-19. Contoh Deadlock di Persimpangan Jalan

disadur dari buku Stallings, William, "Operating Systems -- Fourth Edition", Prentice Hall, 2001

Dalam kasus ini setiap mobil bergerak sesuai nomor yang ditentukan, tetapi tanpa pengaturan yang benar, maka

setiap mobil akan bertemu pada satu titik yang permanen (yang dilingkari)atau dapat dikatakan bahwa setiap

mobil tidak dapat meanjutkan perjalanan lagi atau dengan kata lain terjadi deadlock. Contoh lain pada proses

yang secara umum terdiri dari tiga tahap, yaitu untuk meminta, memakai, dan melepaskan sumber daya yang di

mintanya. Contoh kode-nya:

Gambar 4-20. Lalulintas

public class Proses {

public synchronized void getA() {

//proses untuk mendapat sumber daya a

}

public synchronized void getB(){

//proses untuk mendapat sumber daya b

}

public void releaseA(){

//proses untuk melepaskan sumber daya a

}

public void releaseB(){

//proses untuk melepaskan sumber daya b

}

}

public class Coba {

public static void main(String [] args) {

Proses P = new Proses();

Proses Q = new Proses();

P.getA();

Q.getB();

123Bab 4. Sinkronisasi dan Deadlock

P.getB();

Q.getA();

}

}

Tanpa adanya perintah untuk mereleased artinya saat P mendapatkan A dan Q mendapatkan B, tetapi tidak

dilepaskan, maka saat P minta B dan Q minta A, maka keduanya akan saling menunggu hingga salah satu

melepaskan sumber dayanya, sedangkan kebutuhan P ada pada Q dan Q ada pada P, sehingga terjadi deadlock.

Secara umum kejadian ini dapat mudah terjadi dalam pemrograman multi-thread. Sebab ada kemungkinan lebih

besar untuk menggunakan sumber daya bersama.

4.7.2. Sumber Daya yang Bisa Dipakai Berulang-Ulang

Kejadian deadlock selalu tidak lepas dari sumber daya, seperti kita lihat dari contoh contoh diatas, bahwa hampir

seluruhnya merupakan masalah sumber daya yang digunakan bersama-sama. Oleh karena itu, kita juga perlu

tahu tentang jenis sumber daya, yaitu: sumber daya dapat digunakan lagi berulang-ulang dan sumber daya yang

dapat digunakan dan habis dipakai atau dapat dikatakan sumber daya sekali pakai.

Sumber daya ini tidak habis dipakai oleh proses manapun.Tetapi setelah proses berakhir, sumber daya ini

dikembalikan untuk dipakai oleh proses lain yang sebelumnya tidak kebagian sumber daya ini. Contohnya

prosesor, kanal I/O, disk, semaphores. Contoh peran sumber daya jenis ini pada terjadinya deadlock ialah

misalnya sebuah proses memakai disk A dan B, maka akan terjadi deadlock jika setiap proses sudah memiliki

salah satu disk dan meminta disk yang lain. Masalah ini tidak hanya dirasakan oleh pemrogram tetapi oleh

seorang yang merancang sebuah sistem operasi. Cara yang digunakan pada umumnya dengan cara

memperhitungkan dahulu sumber daya yang digunakan oleh proses-proses yang akan menggunakan sumber

daya tersebut. Contoh lain yang menyebabkan deadlock dari sumber yang dapat dipakai berulang-ulang ialah

berkaitan dengan jumlah proses yang memakai memori utama. Contohnya dapat dilihat dari kode berikut ini:

Gambar 4-21. P-Q

//dari kelas proses kita tambahkan method yaitu meminta

public void meminta (int banyakA) {

//meminta dari sumber daya a

if ( banyakA &lt; banyak )

banyak = banyak - banyakA;

else

wait();

}

//mengubah kode pada mainnya sebagai berikut

public static void main ( String [] args ) {

Proses P = new Proses();

Proses Q = new Proses();

P.meminta(80);

Q.meminta(70);

P.meminta(60);

Q.meminta(80);

}

private int banyak = 200;

private int banyakA;

124Bab 4. Sinkronisasi dan Deadlock

Setelah proses P dan Q telah melakukan fungsi meminta untuk pertama kali, maka sumber daya yang tersedia

dalam banyak ialah 50 ( 200-70- 80). Maka saat P menjalankan fungsi meminta lagi sebanyak 60, maka P tidak

akan menemukan sumber daya dari banyak sebanyak 60, maka P akan menunggu hingga sumber daya yang

diminta dipenuhi. Demikian juga dengan Q, akan menunggu hingga permintaannya dipenuhi, akhirnya terjadi

deadlock. Cara mengatasinya dengan menggunakan memori maya.

4.7.3. Sumber Daya Sekali Pakai

Dalam kondisi biasa tidak ada batasan untuk memakai sumber daya apapun, selain itu dengan tidak terbatasnya

produksi akan membuat banyak sumber daya yang tersedia.Tetapi dalam kondisi ini juga dapat terjadi deadlock.

Contohnya:

Gambar 4-22. Deadlock

//menambahkan method receive dan send

public void receive( Proses p ){

//method untuk menerima sumber daya

}

public void send ( Proses p ){

//method untuk memberi sumber daya

}

dari kedua fungsi tersebut ada yang bertindak untuk menerima dan memberi sumber daya, tetapi ada kalanya

proses tidak mendapat sumber daya yang dibuat sehingga terjadi blok, karena itu terjadi deadlock. Tentu saja hal

ini sangat jarang terjadi mengingat tidak ada batasan untuk memproduksi dan mengkonsumsi, tetapi ada suatu

keadaan seperti ini yang mengakibatkan deadlock. Hal ini mengakibatkan deadlock jenis ini sulit untuk

dideteksi. Selain itu deadlock ini dihasilkan oleh beberapa kombinasi yang sangat jarang terjadi.

4.7.4. Kondisi untuk Terjadinya deadlock

Menurut Coffman (1971) ada empat kondisi yang dapat mengakibatkan terjadinya deadlock, yaitu:

1. Mutual Eksklusif: hanya ada satu proses yang boleh memakai sumber daya, dan proses lain yang ingin

memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses

yang memakai sumber daya tersebut.

2. Memegang dan menunggu: proses yang sedang memakai sumber daya boleh meminta sumber daya lagi

maksudnya menunggu hingga benar-benar sumber daya yang diminta tidak dipakai oleh proses lain, hal ini

dapat menyebabkan kelaparan sumber daya sebab dapat saja sebuah proses tidak mendapat sumber daya

dalam waktu yang lama

3. Tidak ada Preemption: sumber daya yang ada pada sebuah proses tidak boleh diambil begitu saja oleh

proses lainnya. Untuk mendapatkan sumber daya tersebut, maka harus dilepaskan terlebih dahulu oleh

proses yang memegangnya, selain itu seluruh proses menunggu dan mempersilahkan hanya proses yang

memiliki sumber daya yang boleh berjalan

4. Circular Wait: kondisi seperti rantai, yaitu sebuah proses membutuhkan sumber daya yang dipegang proses

berikutnya

125Bab 4. Sinkronisasi dan Deadlock

Banyak cara untuk menanggulangi deadlock:

1. Mengabaikan masalah deadlock.

2. Mendeteksi dan memperbaiki

3. Penghindaran yang terus menerus dan pengalokasian yang baik dengan menggunakan protokol untuk

memastikan sistem tidak pernah memasuki keadaan deadlock. Yaitu dengan deadlock avoidance sistem

untuk mendata informasi tambahan tentang proses mana yang akan meminta dan menggunakan sumber

daya.

4. Pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock dengan deadlock

prevention sistem untuk memasti- kan bahwa salah satu kondisi yang penting tidak dapat menunggu.

4.7.5. Mengabaikan Masalah deadlock

Metode ini lebih dikenal dengan Algoritma Ostrich. Dalam algoritma ini dikatakan bahwa untuk menghadapi

deadlock ialah dengan berpura-pura bahwa tidak ada masalah apapun. Hal ini seakan-akan melakukan suatu hal

yang fatal, tetapi sistem operasi Unix menanggulangi deadlock dengan cara ini dengan tidak mendeteksi

deadlock dan membiarkannya secara otomatis mematikan program sehingga seakan-akan tidak terjadi apapun.

Jadi jika terjadi deadlock, maka tabel akan penuh, sehingga proses yang menjalankan proses melalui operator

harus menunggu pada waktu tertantu dan mencoba lagi.

4.7.6. Mendeteksi dan Memperbaiki

Caranya ialah dengan cara mendeteksi jika terjadi deadlock pada suatu proses maka dideteksi sistem mana yang

terlibat di dalamnya. Setelah diketahui sistem mana saja yang terlibat maka diadakan proses untuk memperbaiki

dan menjadikan sistem berjalan kembali.

Hal-hal yang terjadi dalam mendeteksi adanya deadlock adalah:

1. Permintaan sumber daya dikabulkan selama memungkinkan.

2. Sistem operasi memeriksa adakah kondisi circular wait secara periodik.

3. Pemeriksaan adanya deadlock dapat dilakukan setiap ada sumber daya yang hendak digunakan oleh sebuah

proses.

4. Memeriksa dengan algoritma tertentu.

Ada beberapa jalan untuk kembali dari deadlock:

Lewat Preemption

Dengan cara untuk sementara waktu menjauhkan sumber daya dari pemakainya, dan memberikannya pada

proses yang lain. Ide untuk memberi pada proses lain tanpa diketahui oleh pemilik dari sumber daya tersebut

tergantung dari sifat sumber daya itu sendiri. Perbaikan dengan cara ini sangat sulit atau dapat dikatakan tidak

mungkin. Cara ini dapat dilakukan dengan memilih korban yang akan dikorbankan atau diambil sumber dayanya

utuk sementara, tentu saja harus dengan perhitungan yang cukup agar waktu yang dikorbankan seminimal

126Bab 4. Sinkronisasi dan Deadlock

mungkin. Setelah kita melakukan preemption dilakukan pengkondisian proses tersebut dalam kondisi aman.

Setelah itu proses dilakukan lagi dalam kondisi aman tersebut.

Lewat Melacak Kembali

Setelah melakukan beberapa langkah preemption, maka proses utama yang diambil sumber dayanya akan

berhenti dan tidak dapat melanjutkan kegiatannya, oleh karena itu dibutuhkan langkah untuk kembali pada

keadaan aman dimana proses masih berjalan dan memulai proses lagi dari situ. Tetapi untuk beberapa keadaan

sangat sulit menentukan kondisi aman tersebut, oleh karena itu umumnya dilakukan cara mematikan program

tersebut lalu memulai kembali proses. Meskipun sebenarnya lebih efektif jika hanya mundur beberapa langkah

saja sampai deadlock tidak terjadi lagi. Untuk beberapa sistem mencoba dengan cara mengadakan pengecekan

beberapa kali secara periodik dan menandai tempat terakhir kali menulis ke disk, sehingga saat terjadi deadlock

dapat mulai dari tempat terakhir penandaannya berada.

Lewat membunuh proses yang menyebabkan

deadlock

Cara yang paling umum ialah membunuh semua proses yang mengalami deadlock. Cara ini paling umum

dilakukan dan dilakukan oleh hampir semua sistem operasi. Namun, untuk beberapa sistem, kita juga dapat

membunuh beberapa proses saja dalam siklus deadlock untuk menghindari deadlock dan mempersilahkan proses

lainnya kembali berjalan. Atau dipilih salah satu korban untuk melepaskan sumber dayanya, dengan cara ini

maka masalah pemilihan korban menjadi lebih selektif, sebab telah diperhitungkan beberapa kemungkinan jika

si proses harus melepaskan sumber dayanya.

Kriteria seleksi korban ialah:

1. Yang paling jarang memakai prosesor

2. Yang paling sedikit hasil programnya

3. Yang paling banyak memakai sumber daya sampai saat ini

4. Yang alokasi sumber daya totalnya tersedkit

5. Yang memiliki prioritas terkecil

4.7.7. Menghindari deadlock

Pada sistem kebanyakan permintaan terhadap sumber daya dilakukan sebanyak sekali saja. Sistem sudah harus

dapat mengenali bahwa sumber daya itu aman atau tidak( dalam arti tidak terkena deadlock), setelah itu baru

dialokasikan. Ada dua cara yaitu:

1. Jangan memulai proses apapun jika proses tersebut akan membawa kita pada kondisi deadlock, sehingga

tidak mungkin terjadi deadlock karena ketika akan menuju deadlock sudah dicegah.

2. Jangan memberi kesempatan pada suatu proses untuk meminta sumber daya lagi jika penambahan ini akan

membawa kita pada suatu keadaan deadlock

127Bab 4. Sinkronisasi dan Deadlock

Jadi diadakan dua kali penjagaan, yaitu saat pengalokasian awal, dijaga agar tidak deadlock dan ditambah

dengan penjagaan kedua saat suatu proses meminta sumber daya, dijaga agar jangan sampai terjadi deadlock.

Pada deadlock avoidance sistem dilakukan dengan cara memastikan bahwa program memiliki maksimum

permintaan. Dengan kata lain cara sistem ini memastikan terlebih dahulu bahwa sistem akan selalu dalam

kondisi aman. Baik mengadakan permintaan awal ataupun saat meminta permintaan sumber daya tambahan,

sistem harus selalu berada dalam kondisi aman.

Kondisi Aman

Saat kondisi aman, maka suatu sistem dapat mengalokasikan sumber daya pada setiap proses (sampai pada batas

maksimumnya)dengan urutan tertentu. Dengan gambar sebagai berikut:

Gambar 4-23. Kondisi Deadlock Dilihat dari Safe State

disadur dari buku Silberschatz, dkk, Applied Operating System Concepts, 2000.

Dengan mengenal arti dari kondisi aman ini, kita dapat membuat algoritma untuk menghindari deadlock. Idenya

ialah dengan memastikan bahwa sistem selalu berada dalam kondisi aman. Dengan asumsi bahwa dalam kondisi

tidak aman terkandung deadlock. Contoh penerapan algoritmanya ialah algoritma bankir.

Algoritma Bankir

Menurut Dijstra (1965) algoritma penjadualan dapat menghindari deadlock dan algoritma penjadualan itu lebih

dikenal dengan sebutan algoritma bankir. Algoritma ini dapat digambarkan sebagai seorang bankir dikota kecil

yang berurusan dengan kelompok orang yang meminta pinjaman. Jadi kepada siapa dia dapat memberikan

pinjamannya. Dan setiap pelanggan memberikan batas pinjaman maksimum kepada setiap peminjam dana.

Tentu saja si bankir tahu bahwa si peminjam tidak akan meminjam dana maksimum yang mereka butuhkan

dalam waktu yang singkat melainkan bertahap. Jadi dana yang ia punya lebih sedikit dari batas maksimum yang

dipinjamkan. Lalu ia memprioritaskan yang meminta dana lebih banyak, sedangkan yang lain disuruh menunggu

hingga peminta dana yang lebih besar itu mengembalikan pinjaman berikut bunganya, baru setelah itu ia

meminjamkan pada peminjam yang menunggu.

Jadi algoritma bankir ini mempertimbangkan apakah permintaan mereka itu sesuai dengan jumlah dana yang ia

miliki, sekaligus memperkirakan jumlah dana yang mungkin diminta lagi. Jangan sampai ia sampai pada kondisi

dimana dananya habis dantidak dapat meminjamkan uang lagi. Jika demikian maka akan terjadi kondisi

deadlock. Agar kondisi aman, maka asumsi setiap pinjaman harus dikembalikan waktu yang tepat.

Secara umum algoritma bankir dapat dibagi menjadi 4 struktur data:

1. Tersedia: jumlah sumber daya/dana yang tersedia

2. Maksimum: jumlah sumber daya maksimum yang diminta oleh setiap proses

128Bab 4. Sinkronisasi dan Deadlock

3. Alokasi: jumlah sumber daya yang dibutuhkan oleh setiap proses

4. Kebutuhan: sumber daya yang sedang dibutuhkan oleh setiap proses

4.7.8. Pencegahan Deadlock

Jika pada awal bab ini kita membahas tentang ke-empat hal yang menyebabkan terjadinya deadlock. Maka pada

bagian ini, kita akan membahas cara menanggulangi keempat penyebab deadlock itu, sehingga dengan kata lain

kita mengadakan pencegahan terhadap deadlock.

Penanggulangannya ialah sebagai berikut:

1. Masalah Mutual Eksklusif Kondisi ini tidak dapat dilarang, jika aksesnya perlu bersifat spesial untuk satu

proses, maka hal ini harus di dukung oleh kemampuan sistem operasi. Jadi diusahakan agar tidak

mempergunakan kondisi spesial tersebut sehingga sedapat mungkin deadlock dapat dihindari.

2. Masalah Kondisi Menunggu dan Memegang Penanggulangan deadlock dari kondisi ini lebih baik dan

menjanjikan, asalkan kita dapat menahan proses yang memegang sumber daya untuk tidak menunggu

sumber daya laun, kita dapat mencegah deadlock. Caranya ialah dengan meminta semua sumber daya yang

ia butuhkan sebelum proses berjalan. Tetapi masalahnya sebagian proses tidak mengetahui keperluannya

sebelum ia berjalan. Jadi untuk mengatasi hal ini, kita dapat menggunakan algoritma bankir. Yang mengatur

hal ini dapat sistem operasi ataupun sebuah protokol. Hasil yang dapat terjadi ialah sumber daya lebih

di-spesifikasi dan kelaparan sumber daya, atau proses yang membutuhkan sumber daya yang banyak harus

menunggu sekian lama untuk mendapat sumber daya yang dibutuhkan.

3. Masalah tidak ada Preemption Hal ketiga ialah jangan sampai ada preemption pada sumber daya yang telah

dialokasikan. Untuk memastikan hal ini, kita dapat menggunakan protokol. Jadi jika sebuah proses meminta

sumber daya yang tidak dapat dipenuhi saat itu juga, maka proses mengalami preempted. Atau dengan kata

lain ada sumber daya dilepaskan dan diberikan ke proses yang menunggu, dan proses itu akan menunggu

sampai kebutuhan sumber dayanya dipenuhi.

Atau kita harus mencek sumber daya yang dimaui oleh proses di cek dahulu apakah tersedia. Jika ya maka

kita langsung alokasikan, sedangkan jika tidak tersedia maka kita melihat apakah ada proses lain yang

menunggu sumber daya juga. Jika ya, maka kita ambil sumber daya dari proses yang menunggu tersebut dan

memberikan pada proses yang meminta tersebut. Jika tidak tersedia juga, maka proses itu harus menunggu.

Dalam menunggu, beberapa dari sumber dayanya dapat saja di preempted, tetapi jika ada proses yang

memintanya. Cara ini efektif untuk proses yang menyimpan dalam memory atau register.

4. Masalah Circular Wait Masalah ini dapat ditangani oleh sebuah protokol yang menjaga agar sebuah proses

tidak membuat lingkaran siklus yang dapat mengakibatkan deadlock

4.8. Diagram Graf

System komputer terdiri dari berbagai macam resources(sumber daya, diantaranya:

1. Phisical (Device, Memory)

2. Logical (Lock, Database record)

129Bab 4. Sinkronisasi dan Deadlock

3. OS internal (PCB Slots)

4. Aplication level (File/Berkas)

Diantara resource tersebut ada yang preemptable dan ada juga yang tidak. Resource-resource ini akan digunakan

oleh proses - proses yang membutuhkannya. Mekanisme hubungan dari proses - proses dan resource yang

dibutuhkan/digunakan dapat di diwa kilkan dengan dengan graf.

Graf adalah suatu struktur diskret yang terdiri dari vertex dan sisi, dimana sisi menghubungkan vertex-vertex

yang ada. Berdasarkan tingkat kompleksitasnya, graf dibagi menjadi dua bagian, yaitu simple graf dan multigraf.

Simpel graf tidak mengandung sisi paralel (lebih dari satu sisi yang menghubungkan dua vertex yang sama).

Berdasarkan arahnya graf dapat dibagi menjadi dua bagian yaitu graf berarah dan graf tidak berarah. Graf

berarah memperhatikan arah sisi yang menghubungkan dua vertex, sedangkan graf tidak berarah tidak

memperhatikan arah sisi yang menghubungkan dua vertex.

Dalam hal ini akan dibahas mengenai implementasi graf dalam sistem operasi. Salah satunya dalah graf alokasi

sumber daya. Graf alokasi sumber daya merupakan graf sederhana dan graf berarah. Graf alokasi sumber daya

adalah bentuk visualisasi dalam mendeteksi maupun menyelesaikan masalah. deadlock.

4.8.1. Komponen Graf Alokasi Sumber Daya

Pada dasarnya graf G= (V, E) terdiri dari 2 komponen yaitu vertex dan sisi.

Untuk graf alokasi sumber daya, vertex maupun sisinya dibedakan menjadi beberapa bagian.

Gambar 4-24. Proses Pi

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Vertex terdiri dari dua jenis, yaitu:

1. Proses P= {P0, P1, P2, P3, , Pi, , Pm}. Terdiri dari semua proses yang ada di sistem. Untuk proses,

vertexnya digambarkan sebagai lingkaran dengan nama prosesnya.

2. Sumber daya R= {R0, R1, R2, R3, , Rj, , Rn}. Terdiri dari semua sumber daya yang ada di sistem. Untuk

sumber daya, vertexnya digambarkan sebagai segi empat dengan instans yang dapat dialokasikan serta nama

sumber dayanya.

Dalam hal ini jumlah proses dan sumber daya tidak selalu sama.

Gambar 4-25. Sumber daya Rj dengan 2 instans

130Bab 4. Sinkronisasi dan Deadlock

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Sisi, E={Pi-> Rj, , Rj-> Pi, } terdiri dari dua jenis, yaitu:

Gambar 4-26. Proses Pi meminta sumber daya Rj

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

1. Sisi permintaan: Pi -> Rj Sisi permintaan menggambarkan adanya suatu proses Pi yang meminta sumber

daya Rj.

2. Sisi alokasi: Rj -> Pi. Sisi alokasi menggambarkan adanya suatu sumber daya Rj yang mengalokasikan salah

satu instansnya pada proses Pi.

Gambar 4-27. Sumber daya Rj yang mengalokasikan salah satu instansnya pada proses Pi

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Pada graf di atas terdiri dari 7 vertex, V={P0, P1, P2, P3, R0, R1, R3} dan 5 sisi, E= {P0->R0, R0->P1, R1->P1,

R2->P0, R2->P2}. Gambar 4-28 menunjukkan beberapa hal:

1. P0 meminta sumber daya dari R0.

2. R0 memberikan sumber dayanya kepada P1.

3. R1 memberikan salah satu instans sumber dayanya kepada P1.

4. R2 memberikan salah satu instans sumber dayanya kepada P0.

5. R2 memberikan salah satu instans sumber dayanya kepada P2.

Gambar 4-28. Graf Alokasi Sumber Daya

Setelah suatu proses telah mendapatkan semua sumber daya yang diperlukan maka sumber daya tersebut dilepas

dan dapat digunakan oleh proses lain.

4.8.2. Deteksi Deadlock Berdasarkan Graf Alokasi Sumber Daya

Penghindaran dan pencegahan deadlock dalam dilihat pada subbab sebelumnnya. yang telah menjelaskan secara

cukup lengkap langkah-langkah untuk menghindari terjadinya deadlock .

Untuk mengetahui ada atau tidaknya deadlock dalam suatu graf dapat dilihat dari perputaran dan resource yang

dimilikinya.

1. Jika tidak ada perputaran berarti tidak deadlock.

2. Jika ada perputaran, ada potensi terjadi deadlock.

3. Resource dengan instan tunggal DAN perputaran mengakibatkan deadlock.

Pada bagian berikut ini akan ditunjukkan bahwa perputaran tidak selalu mengakibatkan deadlock. Pada Gambar

4-29 graf memiliki perputaran dan deadlock terjadi sedangkan pada Gambar 4-30 graf memiliki perputaran

tetapi tidak terjadi deadlock.

132Bab 4. Sinkronisasi dan Deadlock

Gambar 4-29. Graf dengan deadlock

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Gambar 4-29 Terlihat bahwa ada perputaran yang memungkinkan tejadinya deadlock dan semua sumber daya

memiliki satu instans kecuali sumber daya R2.

Graf di atas memiliki minimal dua perputaran:

1. R2 -> P0 -> R0 -> P1 -> R1 -> P2 -> R2

2. R2 -> P1 -> R1 -> P2 -> R2

Gambar di atas menunjukkan beberapa hal sebagai berikut:

1. P0 meminta sumber daya R0.

2. R0 mengalokasikan sumber dayanya pada P1.

3. P1 meminta sumber daya R1.

4. R1 mengalokasikan sumber dayanya pada P2.

5. P2 meminta sumber daya R2.

133Bab 4. Sinkronisasi dan Deadlock

6. R2 mengalokasikan sumber dayanya pada P0 dan P1.

7. R3 mengalokasikan sumber dayanya pada P2.

Hal-hal tersebut dapat mengakibatkan deadlock sebab P0 memerlukan sumber daya R0 untuk menyelesaikan

prosesnya, sedangkan R0 dialokasikan untuk P1. Di lain pihak P1 memerlukan sumber daya R1 sedangkan R1

dialokasikan untuk P2. P2 memerlukan sumber daya R2 akan tetapi R2 mengalokasikan sumber dayanya pada

R3.

Dengan kata lain, tidak ada satu pun dari proses-proses tersebut yang dapat menyelesaikan tugasnya sebab

sumber daya yang diperlukan sedang digunakan oleh proses lain. Sedangkan proses lain juga memerlukan

sumber daya lain. Semua sumber daya yang diperlukan oleh suatu proses tidak dapat dpenuhi sehingga proses

tersebut tidak dapat melepaskan sumber daya yang telah dialokasikan kepadanya. Dan terjadi proses

tunggu-menunggu antarproses yang tidak dapat berakhir. Inilah yang dinamakan deadlock.

Gambar 4-30. Tanpa deadlock

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Gambar 4-30 memiliki perputaran tetapi deadlock tidak terjadi. Pada gambar di atas, graf memiliki 1 perputaran

yaitu: P0 -> R1 -> P2 -> R0 -> P3 - > R2 -> P0

Graf di atas menunjukkan beberapa hal:

1. P0 meminta sumber daya R1.

2. R1 mengalokasikan sumber dayanya pada P2.

3. P2 meminta sumber daya R0.

4. R0 mengalokasikan sumber dayanya pada P3.

5. P3 meminta sumber daya R2.

134Bab 4. Sinkronisasi dan Deadlock

6. R0 mengalokasikan sumber dayanya pada P3.

7. R1 mengalokasikan sumber dayanya pada P1.

Hal ini tidak menyebabkan deadlock walaupun ada perputaran sebab semua sumber daya yand diperlukan P1

dapat terpenuhi sehingga P1 dapat melepaskan semua sumber dayanya dan sumber daya tersebut dapat

digunakan oleh proses lain.

4.8.3. Algoritma Graf Alokasi Sumber Daya untuk Mencegah Deadlock

Algoritma ini dapat dipakai untuk mencegah deadlock jika sumber daya hanya memiliki satu instans. Pada

algoritma ini ada komponen tambahan pada sisi yaitu claimed edge. Sama halnya dengan sisi yang lain, claimed

edge menghubungkan antara sumber daya dan vertex.

Claimed edge Pi -> Rj berarti bahwa proses Pi akan meminta sumber daya Rj pada suatu waktu. Claimed edge

sebenarnya merupakan sisi permintaan yang digamabarkan sebagai garis putus-putus. Ketika proses Pi

memerlukan sumber daya Rj, claimed edge diubah menjadi sisi permintaan. Dan setelah proses Pi selesai

menggunakan Rj, sisi alokasi diubah kembali menjadi claimed edge.

Dengan algoritma ini bentuk perputaran pada graf tidak dapat terjadi. Sebab untuk setiap perubahan yang terjadi

akan diperiksa dengan algoritma deteksi perputaran. Algoritma ini memerlukan waktu n

2

dalam mendeteksi

perputaran dimana n adalah jumlah proses dalam sistem.

Jika tidak ada perputaran dalam graf, maka sistem berada dalam status aman. Tetapi jika perputaran ditemukan

maka sistem berada dalam status tidak aman. Pada saat status tidak aman ini, proses Pi harus menunggu sampai

permintaan sumber dayanya dipenuhi.

Gambar 4-31. Graf alokasi sumber daya dalam status aman

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Pada saat ini R1 sedang tidak mengalokasikan sumber dayanya, sehingga P1 dapat memperoleh sumber daya R1.

Namun, jika claimed edge diubah menjadi sisi permintaan dan kemudian diubah menjadi sisi alokasi, hal ini

dapat menyebabkan terjadinya perputaran (Gambar 4-32).

135Bab 4. Sinkronisasi dan Deadlock

Gambar 4-32. Graf alokasi sumber daya dalam status tidak aman

Sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

4.8.4. Deteksi Deadlock dengan Menggunakan Graf Tunggu

Jika semua sumber daya hanya memiliki satu instans, deadlock dapat dideteksi dengan mengubah graf alokasi

sumber daya menjadi graf tunggu. Adapun caranya sebagai berikut:

1. Cari sumber daya Rm yang memberikan instansnya pada Pi dan Pj yang meminta sumber daya pada Rm.

2. Hilangkan sumber daya Rm dan hubungkan sisi Pi dan Pj dengan arah yang bersesuaian yaitu Pj->Pi.

3. Lihat apakah terdapat perputaran pada graf tunggu? Deadlock terjadi jika dan hanya jika pada graf

tunggu terdapat perputaran.

136Bab 4. Sinkronisasi dan Deadlock

Gambar 4-33. Graf alokasi sumber daya

sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Gambar 4-34. Graf tunggu

sumber: Silberschatz, "Operating System Concepts -- Fourth Edition", John Wiley & Sons, 2003

Untuk mendeteksi deadlock, sistem perlu membuat graf tunggu dan secara berkala memeriksa apakah ada

perputaran atau tidak. Untuk mendeteksi adanya perputaran diperlukan operasi sebanyak n

2

, dimana n adalah

jumlah vertex dalam graf alokasi sumber daya.

4.9. Rangkuman

Critical section adalah suatu segmen kode yang mengakses data yang digunakan secara bersama-sama.

137Bab 4. Sinkronisasi dan Deadlock

Problema critical section yaitu bagaimana menjamin bahwa jika suatu proses sedang menjalankan critical

section, maka proses lain tidak boleh masuk ke dalam critical section tersebut.

Solusi dari critical section harus memenuhi tiga syarat, yaitu:

1. mutual exclusion

2. terjadi kemajuan (progress)

3. ada batas waktu tunggu (bounded waiting)

Solusi dari critical section dibagi menjadi dua jenis, yaitu solusi perangkat lunak dan solusi perangkat keras.

Solusi dengan perangkat lunak yaitu dengan menggunakan algoritma 1, algoritma 2 dan algoritma 3 seperti yang

telah dijelaskan. Dari ketiga algoritma itu, hanya algoritma 3 yang memenuhi ketiga syarat solusi critical

section. Untuk menyelesaikan masalah critical section untuk lebih dari dua proses, maka dapat digunakan

algoritma tukang roti.

Hardware merupakan faktor pendukung yang sangat berperan dalam proses sinkronisasi. Banyak dari para

designer prosesor yang membuat fasilitas atomic instruction dalam produknya. Ada 2 metode dalam sinkronisasi

hardware, yaitu: Processor Synchronous dan Memory Synchronous. semafor merupakan konsep yang dibuat oleh

Djikstra dengan mengandalkan sebuah variable integer dan fasilitas atomic instruction dari prosesor. Semafor

merupakan primitif dalam pembuatan alat sinkronisasi yang lebih tinggi lagi. Semafor dapat menyelesaikan

permasalahan seperti: Critical section, sinkronisasi baris, counting semaphore, Dining philosopher,

readers-writers, dan producer-consumer. Semafor banyak dipakai oleh para programmer, sebagai contoh dapat

dilihat di pemrograman Win32API. Tetapi ternyata Java

tm

tidak menggunakan semaphore secara explisit namun

memakai konsep monitor yang dibangun dari semafor ini.

Critical Region merupakan bagian kode yang selalu dilaksanakan dalam kondisi mutual eksklusif. Perbedaannya

adalah bahwa yang mengkondisikan mutual eksklusif adalah kompiler dan bukan programmer sehingga

mengurangi resiko kesalahan programmer. Monitor merupakan kumpulan dari prosedur, variabel, dan struktur

data dalam satu modul. Dengan mempergunakan monitor, sebuah proses dapat memanggil prosedur di dalam

monitor, tetapi tidak dapat mengakses struktur data (termasuk variabel- variabel) internal dalam monitor. Dengan

karakteristik demikian, monitor dapat mengatasi manipulasi yang tidak sah terhadap variabel yang diakses

bersama-sama karena variabel lokal hanya dapat diakses oleh prosedur lokal.

Deadlock ialah suatu kondisi permanen dimana proses tidak berjalan lagi ataupun tidak berkomunikasi lagi antar

proses. Perebutan sumber daya itu dapat dibagi 2: sumber daya yang dapat dipakai berulang-ulang dan sumber

daya yang sekali dibuat dan langsung dipakai.

Sebenarnya deadlock dapat disebabkan oleh empat hal yaitu:

1. Proses Mutual Exclusion

2. Proses memegang dan menunggu

3. Proses Preemption

4. Proses Menunggu dengan siklus deadlock tertentu

Penanganan deadlock Banyak cara untuk menanggulangi deadlock:

1. mengabaikan masalah deadlock.

2. mendeteksi dan memperbaiki

3. penghindaran yang terus menerus dan pengalokasian yang baik.

4. pencegahan yang secara struktur bertentangan dengan empat kondisi terjadinya deadlock.

138Bab 4. Sinkronisasi dan Deadlock

Untuk mendeteksi deadlock dan menyelesaikannya dapat digunakan graf sebagai visualisasinya. Jika tidak ada

cycle, berarti tidak ada deadlock. Jika ada cycle, ada potensi terjadi deadlock. Resource dengan 1 instans DAN

cycle mengakibatkan deadlock.

4.10. Latihan

1. Sebutkan keterbatasan penggunaan Monitor!

Jawab: Tidak semua kompiler dapat menerapkan aturan mutual eksklusif dan tidak dapat diterapkan pada

sistem terdistribusi.

2. Proses dapat meminta berbagai kombinasi dari sumber daya dibawah ini: CDROM, soundcard, dan floppy.

Jelaskan tiga macam pencegahan deadlock skema yang meniadakan:

• Hold and Wait

• Circular Wait

• No Preemption

3. Sebutkan dan jelaskan tiga syarat untuk mengatasi problema critical section!

Jawab:

a. Mutual Exclusion. Jika proses Pi sedang menjalankan critical section (dari proses Pi), maka tidak ada

proses-proses lain yang dapat menjalankan critical section dari proses-proses tersebut. Dengan kata lain,

tidak ada dua proses yang berada di critical section pada saat yang bersamaan.

b. Terjadi kemajuan (progress). Jika tidak ada proses yang sedang menjalankan critical sectionnya dan jika

terdapat lebih dari satu proses lain yang ingin masuk ke critical section, maka hanya proses-proses yang

tidak sedang menjalankan remainder sectionnya yang dapat berpartisipasi dalam memutuskan siapa yang

berikutnya yang akan masuk ke critical section, dan pemilihan siapa yang berhak masuk ke critical section

ini tidak dapat ditunda secara tak terbatas (sehingga tidak terjadi deadlock).

c. Ada batas waktu tunggu (bounded waiting). Jika seandainya ada proses yang sedang menjalankan critical

section, maka terdapat batasan waktu berapa lama suatu proses lain harus menunggu giliran untuk

mengakses critical section. Dengan adanya batas waktu tunggu akan menjamin proses dapat mengakses ke

critical section (tidak mengalami starvation: proses seolah-olah berhenti, menunggu request akses ke

critical section diperbolehkan).

4. Telah dibahas mengenai program dari counting semafor. lihatlah potongan program di bawah ini.

Subrutin Wait

02 wait (S1);

03 C--;

04 if ( C < 0 ) {

05 signal (S1);

06 wait (S2);

07 }

08 signal (S1);

Subrutin Signal

09 wait (S1);

139Bab 4. Sinkronisasi dan Deadlock

10 C++;

11 if (C <= 0)

12 signal (S2);

13 else

14 signal (S1);

a. Apakah yang terjadi bila pada baris nomor 11 diubah menjadi lebih besar dan sama dengan ? b. Apakah

yang terjadi apabila pada baris 4 ditambahkan sama dengan sehingga menjadi <= ?

Jawab:

a. Program tidak akan berjalan karena tanda lebih kecil mempunyai arti bahwa ada proses yang sedang wait.

Jadi arti dari baris 11 adalah jika ada proses yang sedang wait maka proses yg sekarang akan memanggil

signal S2.

b. Program tidak akan berjalan dengan benar. Sebagai contoh jika nilai awal semafor adalah 1, maka jika

ada proses yang memanggil wait, seharusnya proses tsb mengunci semafor tersebut, tetapi kenyataannya

semafor tsb akan terhenti seakan - akan ada proses lain yang sudah mengunci (padahal tidak ada).

5. Pada implementasi solusi dari masalah Readers/Writers dengan penulis diutamakan (solusi kedua), terlihat

ada lima buah semafor yang digunakan. Mengapa perlu memakai lima semafor? Mengapa semafor mutex1

diperlukan, terutama mengingat bahwa pada method tersebut telah terdapat semafor baca?

Jawaban:

Semafor mutex1 pada solusi di atas diperlukan agar setiap thread pembaca tidak menunggu di semafor

baca. Bila banyak pembaca yang menunggu di semafor baca, maka para penulis terkadang tidak

mendapatkan prioritas yang diinginkan, karena tidak dapat melompati antrian di semafor baca. Untuk lebih

jelasnya baca rujukan [Stallings2001].

6. Dalam sebuah sistem terdapat 4 proses yang akan siap di ready queue. Proses(Waktu Datang, Permintaan

R1, Permintaan R2) P1(0, 3, 2) P2(0, 2, 1) P3(1, 2, 2) P4(1, 2, 1) Jumlah sumber daya R1 = 4, R2 = 3

Pemberian sumber daya berdasarkan aturan berikut:

1. Jika ada dua proses yang sedang meminta sumber daya dan sumber daya yang tersedia hanya

mencukupi salah satu proses, maka proses dengan ID terkecil didahulukan. Jika sumber daya dapat

memenuhi semua proses yang meminta, maka sumber daya yang tersedia diberikan kepada semua

proses yang membutuhkan.

2. Jika sumber daya yang dibutuhkan proses telah terpenuhi semuanya pada Tn, maka pada Tn+1 sumber

daya dilepas dan dapat dipakai oleh proses lain pada Tn+1

Jawab:

140Bab 4. Sinkronisasi dan Deadlock

Graf alokasi sumber daya saat T0

Graf alokasi sumber daya saat T1

141Bab 4. Sinkronisasi dan Deadlock

Graf alokasi sumber daya saat T2

Graf alokasi sumber daya saat T3

142Bab 4. Sinkronisasi dan Deadlock

Graf alokasi sumber daya saat T4

7. Jelaskan tentang keempat hal yang menyebabkan deadlock?

8. Bagaimana cara mengatasi keempat masalah tersebut?

9. Jelaskan tentang algoritma bankir!

10. Diasumsikan proses P0 memegang sumber daya R2 dan R3, meminta sumber daya R4; P1 menggunakan R4

dan meminta R1; P2 menggunakan R1 dan meminta R3. Gambarkan Wait-for Graph. Apakah sistem

terjebak dalam deadlock? Jika ya, tunjukkan proses mana yang menyebabkan deadlock. Jika tidak,

tunjukkan urutan proses untuk selesai.

11. Buatlah implementasi dengan menggunakan monitor dari pemecahan Readers/Writers dengan solusi thread

pembaca dan penulis mendapatkan prioritas saling bergantian.

12. User x telah menggunakan 7 printer dan harus menggunakan 10 printer. User y telah menggunakan 1 printer

dan akan memerlukan paling banyak 4 printer. User z telah menggunakan 2 printer dan akan menggunakan

paling banyak 4 printer. Setiap user pada saat ini meminta 1 printer. Kepada siapakah OS akan memberikan

grant printer tersebut dan tunjukkan "safe sequence" yang ada sehingga tidak terjadi deadlock.

13. Pernyataan manakah yang benar mengenai deadlock:

i. Pencegahan deadlock lebih sulit dilakukan (implementasi) daripada menghindari deadlock.

ii. Deteksi deadlock dipilih karena utilisasi dari resources dapat lebih optimal.

iii. Salah satu prasyarat untuk melakukan deteksi deadlock adalah: hold and wait.

iv. Algoritma Banker’s (Djikstra) tidak dapat menghindari terjadinya deadlock.

v. Suatu sistem jika berada dalam keadaan tidak aman: "unsafe", berarti telah terjadi deadlock.

14. Diketahui:

1.set P yang terdiri dari dua (2) proses; P = { P1, P2 }.

2.set R yang terdiri dari dua (2) sumber-daya (resources); denga n berturut-turut lima (5) dan dua (2)

instances; R = { R1, R2 } = { {r11, r12, r13, r14, r15 }, {r21, r22 } }.

3. Plafon (jatah maksimum) sumber-daya untuk masing-masing proses ialah:

143Bab 4. Sinkronisasi dan Deadlock

R1 r2

p1 5 1

p2 3 1

4.Pencegahan deadlock dilakukan dengan Banker’s Algorithm.

5.Alokasi sumber-daya yang memenuhi kriteria Banker’s Algorithm di atas, akan diprioritaskan pada proses

dengan indeks yang lebih kecil.

6.Setelah mendapatkan semua sumber-daya yang diminta, proses aka n mengembalikan SELURUH

sumber-daya tersebut.

7.Pada saat T0, ”Teralokasi” serta ”Permintaan” sumber-daya proses ditentukan sebagai berikut:

teralokasi permintaan

R1|R2| R1|R2

p1 2| 0| 2 | 1

p2 2| 0| 1| 1

Gambarkan graph pada urutan T0, T1,... dan seterusnya, hingga se mua permintaan sumber-daya terpenuhi

dan dikembalikan. Sebutkan, jika terjadi kondisi ”unsafe”!

15. Problem Reader/Writer I

Perhatikan berkas ”ReaderWriterServer.java” berikut ini (source-code terlampir):

a) Ada berapa object class ”Reader” yang terbentuk? Sebutkan nama-namanya!

b) Ada berapa object class ”Writer” yang terbentuk? Sebutkan nama-namanya!

c) Modifikasi kode program tersebut (cukup baris terkait), sehingga akan terdapat 6 (enam) ”Reader” dan 4

(empat) ”Writer”.

d) Modifikasi kode program tersebut, dengan menambahkan sebuah (satu!) object thread baru yaitu

”janitor”. Sang ”janitor” berfungsi untuk membersihkan (cleaning). Setelah membersihkan, ”janitor” akan

tidur (sleeping). Pada saat bangun, ”janitor” kembali akan membersihkan. Dan seterusnya... Pada saat

”janitor” akan membersihkan, tidak boleh ada ”reader” atau ”writer” yang aktif. Jika ada, ”janitor” harus

menunggu. Demikian pula, ”reader” atau ”writer” harus menunggu ”janitor” hingga selesai membersihkan.

16. Problem Reader/Writer II

Perhatikan berkas .ReaderWriterServer.java. berikut ini, yang merupakan gabungan

.ReaderWriterServer.java., .Reader.java., .Writer.java., .Semaphore.java., .Database.java., oleh Gagne,

Galvin, dan Silberschatz. Terangkan berdasarkan berkas tersebut:

1. akan terbentuk berapa thread, jika menjalankan program class .ReaderWriterServer. ini? Apa yang

membedakan antara sebuah thread dengan thread lainnya?

2. mengapa: jika ada .Reader. yang sedang membaca, tidak ada .Writer. yang dapat menulis; dan

mengapa: jika ada .Writer. yang sedang menulis, tidak ada .Reader. yang dapat membaca?

3. mengapa: jika ada .Reader. yang sedang membaca, boleh ada .Reader. lainnya yang turut membaca?

4. modifikasi kode program tersebut (cukup mengubah baris terkait), sehingga akan terdapat 5 (lima)

.Reader .dan 4 (empat) .Writer.!

144Bab 4. Sinkronisasi dan Deadlock

Modifikasi kode program tersebut (cukup mengubah method terkait), sehingga pada saat RAJA (Reader 0)

ingin membaca, tidak boleh ada RAKYAT (Reader lainnya) yang sedang/ akan membaca. JANGAN

MEMPERSULIT DIRI SENDIRI: jika RAJA sedang membaca, RAKYAT boleh turut membaca.

001 // Gabungan ReaderWriterServer.java Reader.java Writer.java

002 // Semaphore.java Database.java

003 // (c) 2000 Gagne, Galvin, Silberschatz

004

005 public class ReaderWriterServer {

006 public static void main(String args[]) {

007 Database server = new Database();

008 Reader[] readerArray = new Reader[NUM_OF_READERS];

009 Writer[] writerArray = new Writer[NUM_OF_WRITERS];

010 for (int i = 0; i < NUM_OF_READERS; i++) {

011 readerArray[i] = new Reader(i, server);

012 readerArray[i].start();

013 }

014 for (int i = 0; i < NUM_OF_WRITERS; i++) {

015 writerArray[i] = new Writer(i, server);

016 writerArray[i].start();

017 }

018 }

019 private static final int NUM_OF_READERS = 3;

020 private static final int NUM_OF_WRITERS = 2;

021 }

022

023 class Reader extends Thread {

024 public Reader(int r, Database db) {

025 readerNum = r;

026 server = db;

027 }

028 public void run() {

029 int c;

030 while (true) {

031 Database.napping();

032 System.out.println("reader " + readerNum + " wants to read.");

033 c = server.startRead();

034 System.out.println("reader " + readerNum +

035 " is reading. Reader Count = " + c);

036 Database.napping();

037 System.out.print("reader " + readerNum + " is done reading. ");

038 c = server.endRead();

039 }

040 }

041 private Database server;

042 private int readerNum;

043 }

045 class Writer extends Thread {

046 public Writer(int w, Database db) {

047 writerNum = w;

048 server = db;

049 }

050 public void run() {

051 while (true) {

052 System.out.println("writer " + writerNum + " is sleeping.");

053 Database.napping();

054 System.out.println("writer " + writerNum + " wants to write.");

145Bab 4. Sinkronisasi dan Deadlock

055 server.startWrite();

056 System.out.println("writer " + writerNum + " is writing.");

057 Database.napping();

058 System.out.println("writer " + writerNum + " is done writing.");

059 server.endWrite();

060 }

061 }

062 private Database server;

063 private int writerNum;

064 }

065

066 final class Semaphore {

067 public Semaphore() {

068 value = 0;

069 }

070 public Semaphore(int v) {

071 value = v;

072 }

073 public synchronized void P() {

074 while (value <= 0) {

075 try { wait(); }

076 catch (InterruptedException e) { }

077 }

078 value--;

079 }

080 public synchronized void V() {

081 ++value;

082 notify();

083 }

084 private int value;

085 }

086

087 class Database {

088 public Database() {

089 readerCount = 0;

090 mutex = new Semaphore(1);

091 db = new Semaphore(1);

092 }

093 public static void napping() {

094 int sleepTime = (int) (NAP_TIME * Math.random() );

095 try { Thread.sleep(sleepTime*1000); }

096 catch(InterruptedException e) {}

097 }

098 public int startRead() {

099 mutex.P();

100 ++readerCount;

101 if (readerCount == 1) {

102 db.P();

103 }

104 mutex.V();

105 return readerCount;

106 }

107 public int endRead() {

108 mutex.P();

109 --readerCount;

146Bab 4. Sinkronisasi dan Deadlock

110 if (readerCount == 0) {

111 db.V();;

112 }

113 mutex.V();

114 System.out.println("Reader count = " + readerCount);

115 return readerCount;

116 }

117 public void startWrite() {

118 db.P();

119 }

120 public void endWrite() {

121 db.V();

122 }

123 private int readerCount;

124 Semaphore mutex;

125 Semaphore db;

126 private static final int NAP_TIME = 15;

127 }

128

129 // The Class java.lang.Thread

130 // When a thread is created, it is not yet active; it begins to run when method

131 // .start. is called. Invoking the .start. method causes this thread to begin

132 // execution; by calling the .run. method.

133 // public class Thread implements Runnable {

134 // ...

135 // public void run();

136 // public void start()

137 // throws IllegalThreadStateException;

138 // ...

139 // }

Bounded Buffer

Perhatikan berkas ”BoundedBufferServer.java” pada halaman berikut:

a) Berapakah ukuran penyangga (buffer) ?

b) Modifikasi program (sebutkan nomor barisnya) agar ukuran penyangga (buffer) menjadi 6.

c) Tuliskan/ perkirakan keluaran (output) 10 baris pertama, jika menjalankan program ini.

d) Jelaskan fungsi dari ketiga semaphore (mutex, full, empty) pada program tersebut.

e) Tambahkan (sebutkan nomor barisnya) sebuah thread dari class Supervisor yang berfungsi:

i. pada awal dijalankan, melaporkan ukuran penyangga (buffer).

ii. secara berkala (acak), melaporkan jumlah pesan (message) yang berada dalam penyangga (buffer).

f) Semaphore mana yang paling relevan untuk modifikas butir .e. di atas?

001 // Authors: Greg Gagne, Peter Galvin, Avi Silberschatz

002 // Slightly Modified by: Rahmat M. Samik-Ibrahim

003 // Copyright (c) 2000 by Greg Gagne, Peter Galvin, Avi Silberschatz

004 // Applied Operating Systems Concepts - John Wiley and Sons, Inc.

005 //

006 // Class "Date":

007 // Allocates a Date object and initializes it so that it represents

008 // the time at which it was allocated,

009 // (E.g.): "Wed Apr 09 11:12:34 JAVT 2003"

010 // Class "Object"/ method "notify":

147Bab 4. Sinkronisasi dan Deadlock

011 // Wakes up a single thread that is waiting on this object’s monitor.

012 // Class "Thread"/ method "start":

013 // Begins the thread execution and calls the run method of the thread.

014 // Class "Thread"/ method "run":

015 // The Runnable object’s run method is called.

016

017 import java.util.*;

018 // main ***********************************************************

019 public class BoundedBufferServer

020 {

021 public static void main(String args[])

022 {

023 BoundedBuffer server = new BoundedBuffer();

024 Producer producerThread = new Producer(server);

025 Consumer consumerThread = new Consumer(server);

026 producerThread.start();

027 consumerThread.start();

028 }

029 }

030

031 // Producer *******************************************************

032 class Producer extends Thread

033 {

034 public Producer(BoundedBuffer b)

035 {

036 buffer = b;

037 }

038

039 public void run()

040 {

041 Date message;

042 while (true)

043 {

044 BoundedBuffer.napping();

045

046 message = new Date();

047 System.out.println("P: PRODUCE " + message);

048 buffer.enter(message);

049 }

050 }

051 private BoundedBuffer buffer;

052 }

053

054 // Consumer *******************************************************

055 class Consumer extends Thread

056 {

057 public Consumer(BoundedBuffer b)

058 {

059 buffer = b;

060 }

061 public void run()

062 {

063 Date message;

064 while (true)

065 {

066 BoundedBuffer.napping();

067 System.out.println("C: CONSUME START");

148Bab 4. Sinkronisasi dan Deadlock

068 message = (Date)buffer.remove();

069 }

070 }

071 private BoundedBuffer buffer;

072 }

073

074 // BoundedBuffer.java *********************************************

075 class BoundedBuffer

076 {

077 public BoundedBuffer()

078 {

079 count = 0;

080 in = 0;

081 out = 0;

082 buffer = new Object[BUFFER_SIZE];

083 mutex = new Semaphore(1);

084 empty = new Semaphore(BUFFER_SIZE);

085 full = new Semaphore(0);

086 }

087 public static void napping()

088 {

089 int sleepTime = (int) (NAP_TIME * Math.random() );

090 try { Thread.sleep(sleepTime*1000); }

091 catch(InterruptedException e) { }

092 }

093 public void enter(Object item)

094 {

095 empty.P();

096 mutex.P();

097 ++count;

098 buffer[in] = item;

099 in = (in + 1) % BUFFER_SIZE;

100 System.out.println("P: ENTER " + item);

101 mutex.V();

102 full.V();

103 }

104 public Object remove()

105 {

106 Object item;

107 full.P();

108 mutex.P();

109 --count;

110 item = buffer[out];

111 out = (out + 1) % BUFFER_SIZE;

112 System.out.println("C: CONSUMED " + item);

113 mutex.V();

114 empty.V();

115 return item;

116 }

117 public static final int NAP_TIME = 5;

118 private static final int BUFFER_SIZE = 3;

119 private Semaphore mutex;

120 private Semaphore empty;

121 private Semaphore full;

122 private int count, in, out;

123 private Object[] buffer;

124 }

149Bab 4. Sinkronisasi dan Deadlock

125

126 // Semaphore.java *************************************************

128 final class Semaphore

129 {

130 public Semaphore()

131 {

132 value = 0;

133 }

134 public Semaphore(int v)

135 {

136 value = v;

137 }

138 public synchronized void P()

139 {

140 while (value <= 0)

141 {

142 try { wait(); }

143 catch (InterruptedException e) { }

144 }

145 value --;

146 }

147 public synchronized void V()

148 {

149 ++value;

150 notify();

151 }

152 private int value;

153 }

17. perhatikan berkas program java berikut ini:

001 /* Gabungan Berkas:

002 * FirstSemaphore.java, Runner,java, Semaphore.java, Worker.java.

003 * Copyright (c) 2000 oleh Greg Gagne, Peter Galvin, Avi Silberschatz.

004 * Applied Operating Systems Concepts - John Wiley and Sons, Inc.

005 * Slightly modified by Rahmat M. Samik-Ibrahim.

006 *

007 * Informasi Singkat (RMS46):

008 * Threat.start() --> memulai thread yang akan memanggil Threat.run().

009 * Threat.sleep(xxx) --> thread akan tidur selama xxx milidetik.

010 * try {...} catch (InterruptedException e) {} --> sarana terminasi program.

011 */

012

013 public class FirstSemaphore

014 {

015 public static void main(String args[]) {

016 Semaphore sem = new Semaphore(1);

017 Worker[] bees = new Worker[NN];

018 for (int ii = 0; ii < NN; ii++)

019 bees[ii] = new Worker(sem, ii);

020 for (int ii = 0; ii < NN; ii++)

021 bees[ii].start();

022 }

023 private final static int NN=4;

150Bab 4. Sinkronisasi dan Deadlock

024 }

025

026 // Worker ===============================================================

027 class Worker extends Thread

028 {

029 public Worker(Semaphore sss, int nnn) {

030 sem = sss;

031 wnumber = nnn;

032 wstring = WORKER + (new Integer(nnn)).toString();

033 }

034

035 public void run() {

036 while (true) {

037 System.out.println(wstring + PESAN1);

038 sem.P();

039 System.out.println(wstring + PESAN2);

040 Runner.criticalSection();

041 System.out.println(wstring + PESAN3);

042 sem.V();

043 Runner.nonCriticalSection();

044 }

045 }

046 private Semaphore sem;

047 private String wstring;

048 private int wnumber;

049 private final static String PESAN1=" akan masuk ke Critical Section.";

050 private final static String PESAN2=" berada di dalam Critical Section.";

051 private final static String PESAN3=" telah keluar dari Critical Section.";

052 private final static String WORKER="PEKERJA ";

053 }

054

055 // Runner ===============================================================

056 class Runner

057 {

058 public static void criticalSection() {

059 try {

060 Thread.sleep( (int) (Math.random() * CS_TIME * 1000) );

061 }

062 catch (InterruptedException e) { }

063 }

064

065 public static void nonCriticalSection() {

066 try {

067 Thread.sleep( (int) (Math.random() * NON_CS_TIME * 1000) );

068 }

069 catch (InterruptedException e) { }

070 }

071 private final static int CS_TIME = 2;

072 private final static int NON_CS_TIME = 2;

073 }

074

075 // Semaphore ===============================================================

076 final class Semaphore

077 {

078 public Semaphore() {

079 value = 0;

080 }

151Bab 4. Sinkronisasi dan Deadlock

081

082 public Semaphore(int v) {

083 value = v;

084 }

085

086 public synchronized void P() {

087 while (value <= 0) {

088 try {

089 wait();

090 }

091 catch (InterruptedException e) { }

092 }

093 value --;

094 }

095

096 public synchronized void V() {

097 ++value;

098 notify();

099 }

100

101 private int value;

102 }

103

104 // END ===============================================================

1. Berapakah jumlah object dari ”Worker Class” yang akan terbentuk?

2. b)Sebutkan nama-nama object dari ”Worker Class” tersebut!

3. c)Tuliskan/ perkirakan keluaran (output) 10 baris pertama, jika menjalankan program ini!

4. d)Apakah keluaran pada butir ”c” di atas akan berubah, jika parameter CS_TIME diubah menjadi dua

kali NON_CS_TIME? Terangkan!

5. e)Apakah keluaran pada butir ”c” di atas akan berubah, jika selain parameter CS_TIME diubah menjadi

dua kali NON_CS_TIME, dilakukan modifikasi NN menjadi 10? Terangkan!

4.11. Rujukan

Berikut merupakan rangkuman dari semua rujukan yang digunakan di bab ini.

http://bebas.vlsm.org/v06/Kuliah/SistemOperasi/BUKU/ SistemOperasi

http://www-ist.massey.ac.nz/csnotes/355/lectures/monitors.pdf

http://vip.cs.utsa.edu/nsf/pubs/starving/starving.pdf

Bibliografi

[Silberschatz2000] Avi Silberschatz, Peter Galvin, dan Grag Gagne, 2000, Applied Operating Systems: First

Edition, Edisi Pertama, John Wiley & Sons.

[KennethRosen1999] Kenneth H. Rosen, 1999, Discrete Mathematics and Its Application, McGraw Hill.

152Bab 4. Sinkronisasi dan Deadlock

[Stallings2001] William Stallings, 2001, Operating Systems, Prentice Hall.

[Tanenbaum1992] Andrew S. Tanenbaum, 1992, Modern Operating Systems, Prentice-Hall Inc..

153Bab 5. Managemen Memori

5.1. Managemen Memori

5.1.1. Latar Belakang

Memori adalah pusat kegiatan pada sebuah komputer, karena setiap proses yang akan dijalankan, harus melalui

memori terlebih dahulu. CPU mengambil instruksi dari memori sesuai yang ada pada Program Counter.

Instruksi dapat berupa menempatkan/menyimpan dari/ke alamat di memori, penambahan, dan sebagainya. Tugas

sistem operasi adalah mengatur peletakan banyak proses pada suatu memori. Memori harus dapat digunakan

dengan baik, sehingga dapat memuat banyak proses dalam suatu waktu. Dalam managemen memori ini, kita

akan membahas bagaimana urutan alamat memori yang dibuat oleh program yang berjalan.

5.1.2. Pemberian Alamat

Sebelum masuk ke memori, suatu proses harus menunggu. Hal ini disebut antrian masukan. Proses-proses ini

akan berada dalam beberapa tahapan sebelum dieksekusi. Alamat-alamat yang dibutuhkan mungkin saja

direpresentasikan dalam cara yang berbeda dalam tahapan-tahapan ini. Alamat dalam kode program masih

berupa simbolik. Alamat ini akan diikat oleh kompilator ke alamat memori yang dapat diakses. Kemudian

linkage editor dan loader, akan mengikat alamat fisiknya. Setiap pengikatan akan memetakan suatu ruang

alamat ke lainnya.

Penjilidan alamat dapat terjadi pada 3 saat, yaitu:

• Waktu Kompilasi: Jika diketahui pada waktu kompilasi, dimana proses ditempatkan di memori. Untuk

kemudian kode absolutnya dapat dibuat. Jika kemudian alamat awalnya berubah, maka harus dikompilasi

ulang.

• Waktu pemanggilan: Jika tidak diketahui dimana poses ditempatkan di memori, maka kompilator harus

membuat kode yang dapat dialokasikan. Dalam kasus pengikatan akan ditunda sampai waktu pemanggilan.

Jika alamat awalnya berubah, kita hanya perlu menempatkan ulang kode, untuk menyesuaikan dengan

perubahan.

• Waktu eksekusi: Jika proses dapat dipindahkan dari suatu segmen memori ke lainnya selama dieksekusi.

Pengikatan akan ditunda sampai run-time.

5.1.3. Ruang Alamat Logika dan Fisik

Alamat Logika adalah alamat yang dibentuk di CPU, disebut juga alamat virtual. Alamat fisik adalah alamat

yang telihat oleh memori. Waktu kompilasi dan waktu pemanggilan menghasilkan daerah dimana alamat logika

dan alamat fisik sama. Sedangkan pada waktu eksekusi menghasilkan alamat fisik dan logika yang berbeda.

Kumpulan alamat logika yang dibuat oleh program adalah ruang alamat logika. Kumpulan alamat fisik yang

berkorespondensi dengan alamat logika disebut ruang alamat fisik. Untuk mengubah dari alamat logika ke

alamat fisik diperlukan suatu perangkat keras yang bernama Memory Management Unit (MMU).