Sistem Operasi
Pengertian Deadlock
Deadlock adalah keadaan dimana
dua program memegang kontrol terhadap sumber daya yang dibutuhkan oleh
program yang lain. Tidak ada yang dapat melanjutkan proses masing-masing
sampai program yang lain memberikan sumber dayanya, tetapi tidak ada
yang mengalah.
Deadlock yang mungkin dapat terjadi pada suatu proses disebabkan proses
itu menunggu suatu kejadian tertentu yang tidak akan pernah terjadi. Dua
atau lebih proses dikatakan berada dalam kondisi deadlock, bila setiap
proses yang ada menunggu suatu kejadian yang hanya dapat dilakukan oleh
proses lain dalam himpunan tersebut.
Karakteristik Deadlock
Karakteristik-karakteristik ini harus dipenuhi keempatnya untuk terjadi
deadlock. Namun, perlu diperhatikan bahwa hubungan kausatif antara empat
karakteristik ini dengan terjadinya deadlock adalah implikasi. Deadlock
mungkin terjadi apabila keempat karakteristik terpenuhi.
Empat kondisi tersebut adalah:
1.Mutual Exclusion . Kondisi yang pertama adalah mutual exclusion yaitu
proses memiliki hak milik pribadi terhadap sumber daya yang sedang
digunakannya. Jadi, hanya ada satu proses yang menggunakan suatu sumber
daya. Proses lain yang juga ingin menggunakannya harus menunggu hingga
sumber daya tersebut dilepaskan oleh proses yang telah selesai
menggunakannya. Suatu proses hanya dapat menggunakan secara langsung
sumber daya yang tersedia secara bebas.
2.Hold and Wait . Kondisi yang kedua adalah hold and wait yaitu beberapa
proses saling menunggu sambil menahan sumber daya yang dimilikinya.
Suatu proses yang memiliki minimal satu buah sumber daya melakukan
request lagi terhadap sumber daya. Akan tetapi, sumber daya yang
dimintanya sedang dimiliki oleh proses yang lain. Pada saat yang sama,
kemungkinan adanya proses lain yang juga mengalami hal serupa dengan
proses pertama cukup besar terjadi. Akibatnya, proses-proses tersebut
hanya bisa saling menunggu sampai sumber daya yang dimintanya
dilepaskan. Sambil menunggu, sumber daya yang telah dimilikinya pun
tidak akan dilepas. Semua proses itu pada akhirnya saling menunggu dan
menahan sumber daya miliknya.
3.No Preemption . Kondisi yang selanjutnya adalah no preemption yaitu
sebuah sumber daya hanya dapat dilepaskan oleh proses yang memilikinya
secara sukarela setelah ia selesai menggunakannya. Proses yang
menginginkan sumber daya tersebut harus menunggu sampai sumber daya
tersedia, tanpa bisa merebutnya dari proses yang memilikinya.
4.Circular Wait . Kondisi yang terakhir adalah circular wait yaitu
kondisi membentuk siklus yang berisi proses-proses yang saling
membutuhkan. Proses pertama membutuhkan sumber daya yang dimiliki proses
kedua, proses kedua membutuhkan sumber daya milik proses ketiga, dan
seterusnya sampai proses ke n-1 yang membutuhkan sumber daya milik
proses ke n. Terakhir, proses ke n membutuhkan sumber daya milik proses
yang pertama. Yang terjadi adalah proses-proses tersebut akan selamanya
menunggu.
Penanganan Deadlock
4 cara untuk menangani keadaan deadlock, yaitu:
1.Pengabaian. Maksud dari pengabaian di sini adalah sistem mengabaikan
terjadinya deadlock dan pura-pura tidak tahu kalau deadlock terjadi.
Dalam penanganan dengan cara ini dikenal istilah ostrich algorithm.
Pelaksanaan algoritma ini adalah sistem tidak mendeteksi adanya deadlock
dan secara otomatis mematikan proses atau program yang mengalami
deadlock. Kebanyakan sistem operasi yang ada mengadaptasi cara ini untuk
menangani keadaan deadlock. Cara penanganan dengan mengabaikan deadlock
banyak dipilih karena kasus deadlock tersebut jarang terjadi dan
relatif rumit dan kompleks untuk diselesaikan. Sehingga biasanya hanya
diabaikan oleh sistem untuk kemudian diselesaikan masalahnya oleh user
dengan cara melakukan terminasi dengan Ctrl+Alt+Del atau melakukan
restart terhadap komputer.
2.Pencegahan. Penanganan ini dengan cara mencegah terjadinya salah satu
karakteristik deadlock. Penanganan ini dilaksanakan pada saat deadlock
belum terjadi pada sistem. Intinya memastikan agar sistem tidak akan
pernah berada pada kondisi deadlock. Akan dibahas secara lebih mendalam
pada bagian selanjutnya.
3.Penghindaran. Menghindari keadaan deadlock. Bagian yang perlu
diperhatikan oleh pembaca adalah bahwa antara pencegahan dan
penghindaran adalah dua hal yang berbeda. Pencegahan lebih kepada
mencegah salah satu dari empat karakteristik deadlock terjadi, sehingga
deadlock pun tidak terjadi. Sedangkan penghindaran adalah memprediksi
apakah tindakan yang diambil sistem, dalam kaitannya dengan permintaan
proses akan sumber daya, dapat mengakibatkan terjadi deadlock. Akan
dibahas secara lebih mendalam pada bagian selanjutnya.
4.Pendeteksian dan Pemulihan. Pada sistem yang sedang berada pada
kondisi deadlock, tindakan yang harus diambil adalah tindakan yang
bersifat represif. Tindakan tersebut adalah dengan mendeteksi adanya
deadlock, kemudian memulihkan kembali sistem. Proses pendeteksian akan
menghasilkan informasi apakah sistem sedang deadlock atau tidak serta
proses mana yang mengalami deadlock. Akan dibahas secara lebih mendalam
pada bagian selanjutnya.
Pencegahan Deadlock
Pencegahan deadlock dapat dilakukan dengan cara mencegah salah satu dari
empat karakteristik terjadinya deadlock. Berikut ini akan dibahas satu
per satu cara pencegahan terhadap empat karakteristik tersebut.
1.Mutual Exclusion . Kondisi mutual exclusion pada sumber daya adalah
sesuatu yang wajar terjadi, yaitu pada sumber daya yang tidak dapat
dibagi (non-sharable). Sedangkan pada sumber daya yang bisa dibagi tidak
ada istilah mutual exclusive. Jadi, pencegahan kondisi yang pertama ini
sulit karena memang sifat dasar dari sumber daya yang tidak dapat
dibagi.
2.Hold and Wait . Untuk kondisi yang kedua, sistem perlu memastikan
bahwa setiap kali proses meminta sumber daya, ia tidak sedang memiliki
sumber daya lain. Atau bisa dengan proses meminta dan mendapatkan sumber
daya yang dimilikinya sebelum melakukan eksekusi, sehingga tidak perlu
menunggu.
3.No Preemption . Pencegahan kondisi ini dengan cara membolehkan
terjadinya preemption. Maksudnya bila ada proses yang sedang memiliki
sumber daya dan ingin mendapatkan sumber daya tambahan, namun tidak bisa
langsung dialokasikan, maka akan preempted. Sumber daya yang dimiliki
proses tadi akan diberikan pada proses lain yang membutuhkan dan sedang
menunggu. Proses akan mengulang kembali eksekusinya setelah mendapatkan
semua sumber daya yang dibutuhkannya, termasuk sumber daya yang
dimintanya terakhir.
4.Circular Wait . Kondisi 'lingkaran setan' ini dapat 'diputus' dengan
jalan menentukan total kebutuhan terhadap semua tipe sumber daya yang
ada. Selain itu, digunakan pula mekanisme enumerasi terhadap tipe-tipe
sumber daya yang ada. Setiap proses yang akan meminta sumber daya harus
meminta sumber daya dengan urutan yang menaik. Misalkan sumber daya
printer memiliki nomor 1 sedangkan CD-ROM memiliki nomor 3. Proses boleh
melakukan permintaan terhadap printer dan kemudian CD-ROM, namun tidak
boleh sebaliknya.
Penghindaran Deadlock
Penghindaran terhadap deadlock adalah cara penanganan yang selanjutnya.
Inti dari penghindaran adalah jangan sembarangan membolehkan proses
untuk memulai atau meminta lagi. Maksudnya jangan pernah memulai suatu
proses apabila nantinya akan menuju ke keadaan deadlock. Kedua, jangan
memberikan kesempatan pada proses untuk meminta sumber daya tambahan
jika penambahan tersebut akan membawa sistem pada keadaan deadlock.
Tidak mungkin akan terjadi deadlock apabila sebelum terjadi sudah kita
hindari.
Langkah lain untuk menghindari adalah dengan cara tiap proses
memberitahu jumlah kebutuhan maksimum untuk setiap tipe sumber daya yang
ada. Selanjutnya terdapat deadlock-avoidance algorithm yang secara
rutin memeriksa state dari sistem untuk memastikan tidak adanya kondisi
circular wait serta sistem berada pada kondisi safe state. Safe state
adalah suatu kondisi dimana semua proses mendapatkan sumber daya yang
dimintanya dengan sumber daya yang tersedia. Apabila tidak bisa
langsung, ia harus menunggu selama waktu tertentu, kemudian mendapatkan
sumber daya yang diinginkan, melakukan eksekusi, dan terakhir melepas
kembali sumber daya tersebut. Terdapat dua jenis algoritma penghindaran
yaitu resource-allocation graph untuk single instances resources serta
banker's algorithm untuk multiple instances resources.
Dalam banker's algorithm, terdapat beberapa struktur data yang digunakan, yaitu:
Available . Jumlah sumber daya yang tersedia.
Max . Jumlah sumber daya maksimum yang diminta oleh tiap proses.
Allocation . Jumlah sumber daya yang sedang dimiliki oleh tiap proses.
Need . Sisa sumber daya yang masih dibutuhkan oleh proses, didapat dari max- allocation.
Kemudian terdapat safety algorithm untuk menentukan apakah sistem berada pada safe state atau tidak.
Pendeteksian Deadlock
Pada dasarnya kejadian deadlock sangatlah jarang terjadi. Apabila
kondisi tersebut terjadi, masing-masing sistem operasi mempunyai
mekanisme penanganan yang berbeda. Ada sistem operasi yang ketika
terdapat kondisi deadlock dapat langsung mendeteksinya. Namun, ada pula
sistem operasi yang bahkan tidak menyadari kalau dirinya sedang
mengalami deadlock. Untuk sistem operasi yang dapat mendeteksi deadlock,
digunakan algoritma pendeteksi. Secara lebih mendalam, pendeteksian
kondisi deadlock adalah cara penanganan deadlock yang dilaksanakan
apabila sistem telah berada pada kondisi deadlock. Sistem akan
mendeteksi proses mana saja yang terlibat dalam kondisi deadlock.
Setelah diketahui proses mana saja yang mengalami kondisi deadlock, maka
diadakan mekanisme untuk memulihkan sistem dan menjadikan sistem
berjalan kembali dengan normal.
Mekanisme pendeteksian adalah dengan menggunakan detection algorithm
yang akan memberitahu sistem mengenai proses mana saja yang terkena
deadlock. Setelah diketahui proses mana saja yang terlibat dalam
deadlock, selanjutnya adalah dengan menjalankan mekanisme pemulihan
sistem yang akan dibahas pada bagian selanjutnya. Berikut ini adalah
algoritma pendeteksian deadlock.
Pemulihan Deadlock
Pemulihan kondisi sistem terkait dengan pendeteksian terhadap deadlock.
Apabila menurut algoritma pendeteksian deadlock sistem berada pada
keadaan deadlock, maka harus segera dilakukan mekanisme pemulihan
sistem. Berbahaya apabila sistem tidak segera dipulihkan dari deadlock,
karena sistem dapat mengalami penurunan performance dan akhirnya
terhenti.
Cara-cara yang ditempuh untuk memulihkan sistem dari deadlock adalah sebagai berikut:
1.Terminasi proses. Pemulihan sistem dapat dilakukan dengan cara
melalukan terminasi terhadap semua proses yang terlibat dalam deadlock.
Dapat pula dilakukan terminasi terhadap proses yang terlibat dalam
deadlock secara satu per satu sampai 'lingkaran setan' atau circular
wait hilang. Seperti diketahui bahwa circular wait adalah salah satu
karakteristik terjadinya deadlock dan merupakan kesatuan dengan tiga
karakteristik yang lain. Untuk itu, dengan menghilangkan kondisi
circular wait dapat memulihkan sistem dari deadlock.Dalam melakukan
terminasi terhadap proses yang deadlock, terdapat beberapa faktor yang
menentukan proses mana yang akan diterminasi. Faktor pertama adalah
prioritas dari proses-proses yang terlibat deadlock. Faktor kedua adalah
berapa lama waktu yang dibutuhkan untuk eksekusi dan waktu proses
menunggu sumber daya. Faktor ketiga adalah berapa banyak sumber daya
yang telah dihabiskan dan yang masih dibutuhkan. Terakhir, faktor
utilitas dari proses pun menjadi pertimbangan sistem untuk melakukan
terminasi pada suatu proses.
2.Rollback and Restart . Dalam memulihkan keadaan sistem yang deadlock,
dapat dilakukan dengan cara sistem melakukan preempt terhadap sebuah
proses dan kembali ke state yang aman. Pada keadaan safe state tersebut,
proses masih berjalan dengan normal, sehingga sistem dapat memulai
proses dari posisi aman tersebut. Untuk menentukan pada saat apa proses
akan rollback, tentunya ada faktor yang menentukan. Diusahakan untuk
meminimalisasi kerugian yang timbul akibat memilih suatu proses menjadi
korban. Harus pula dihindari keadaan dimana proses yang sama selalu
menjadi korban, sehingga proses tersebut tidak akan pernah sukses
menjalankan eksekusi.
Kemungkinan-Kemungkinan Terjadinya Deadlock
Mengelola deadlock
Mencegah deadlock ! mengeliminasi setiap kemungkinan yang
dapat
menyebabkan deadlock
Menghindari deadlock ! mengatur eksekusi proses sehingga
permintaan
resource selalu dapat dipenuhi sistem
Menangani deadlock !penghentian dan penundaan
Binding Intruksi Data
dan ke Memory
Dilakukan dengan 3 cara
Compile time: lokasi untuk proses diketahui pada saat
kompilasi.
Kompilasi diulang jika alamat awal berubah ! absolute code
Load time: lokasi memori diketahui pada saat load proses
!relocatable
code
Execution time: proses dapat berpindah lokasi pada saat
eksekusi !
generic, umum terdapat dalam sistem operasi
Ruang Alamat Logika
dan Fisik
Ruang alamat logika (logical address space) dibatasi oleh
ruang alamat
fisik (physical address space)
Logical address (virtual address): dihasilkan CPU
Physical address: alamat fisik memori
Pada skema binding:
compile time dan load time: alamat logika dan fisik sama
execution time: alamat logika dan fisik berbeda
Sistem Operasi - Pengelolaan Memory -Konsep
Unit Pengelolaan Memori ( M M U )
Perangkat keras: menterjemahkan alamat logika ke alamat fisik
Pada MMU, sebuah alamat offset (relocation register),
ditambahkan
pada setiap alamat logika setiap akan dikirim ke memori
Program (user) hanya mengenal alamat logika
Dynamic Loading
Latar belakang: program dan data harus berada dalam memori
agar
dapat dieksukusi ! dibatasi memori fisik
Dynamic loading: program dan data tidak di-load sebelum
dipanggil
jika tidak digunakan tidak di-load
meski secara total besar, lokasi memori yang digunakan bisa
lebih kecil
sangat bergunaka ketika sistem lebih banyak dipenuhi program
yang
jarang digunakan
perlu pustaka khusus
Sistem Operasi - Pengelolaan Memory -Konsep
Dynamic Linking
Linking ditunda hingga eksekusi, digunakan pada shared
library.
Pustaka tidak di-linked jika belum digunakan
Stub, sebuah rutin yang bertugas menempatkan pustaka yang
diperlukan
jika ada di memori: gunakan
jika belum: load dan gunakan
Satu pustaka untuk banyak program
Pengertian Swapping:
Suatu metode pengalihan proses yang bersifat sementara dari memori utama kesatu tempat penyimpanan sementara (disk) dan dipanggil kembali ke memori jikaakan melakukan eksekusi. Proses yang dipindahkan yaitu proses yang di-blocked kedisk dan hanya memasukkan proses-proses ready ke memori utama.
Tujuan Swapping:
1. Meningkatkan kinerja saat multiprogramming pada sistem time sharing.
2. Mengatasi masalah-masalah saat multiprogramming: Pemartisian secara dinamis Strategi pengelolaan memori bebas Algoritma penempatan proses ke memori Strategi penempatan ruang swap pada disk.
Swapping
Proses dapat dikeluarkan (swapped out) dari memori untuk
sementara
dan selanjutnya dikembalikan ke memori untuk melanjutkan
eksekusi
Backing store:
lokasi hard disk tempat proses dikeluarkan sementara dari
memori
proses yang dikeluarkan/dimasukkan berdasarkan aturan
tertentu
(prioritas, round robin)
Transfer time: sebanding dengan banyaknya proses/data yang
dipindahkan
Sistem operasi memiliki semacam ready queue untuk
proses-proses
yang berada dalam backing store.
Sistem Operasi - Pengelolaan Memory -Swapping
G A M B A R : Ilustrasi swapping
|
Alokasi Contiguous
(berurutan)
Sebuah proses
dialokasikan dalam ruang yang utuh, sebesar kebutuhan
proses
Skema umum:
Sistem operasi: low end memory
Proses user: high memory
Register relokasi: register yang digunakan dalam translasi
alamat logika
ke alamat fisik
base register: alamat terkecil proses
limit register: jangkauan terbesar memori untuk sebuah
proses, alamat
logika < limit register
MMU: memetakan alamat logika secara dinamis
Multiple-partition
Hole-block: tersebar dalam memori
Ketika proses ter-swapped in, ia akan dialokasikan di lokasi
hole dalam
memori
Sistem operasi mengelola informasi:
partisi teralokasi (block)
partisi bebas (hole)
G A M B A R : Ilustrasi multiple allocation |
Masalah Alokasi Penyimpanan Dinamis
First fit: mengalokasi hole
pertama yang memenuhi permintaan
Best Fit: mengalokasi hole
terkecil yang sesuai permintaan
Worst fit: mengalokasi hole terbesar
sesuai permintaan
Sistem Operasi - Pengelolaan
Memory -Alokasi Contiguous (berurutan)
Fragmentasi
External: total memori tersedia
memenuhi kebutuhan, tetapi tidak
contiguous
Internal: memori yang
dialokasikan sedikit lebih besar daripada
kebutuhan, sisa tidak digunakan
Compaction: memperkecil
kemungkinan fragmentasi eksternal
menyatukan hole agar berada dalam
blok yang sama ! menggeser block
juga
hanya digunakan pada relokasi
dinamik dan dilakukan saat eksekusi
Paging
Ruang alamat logika bisa saja
non-contiguous
Ruang alamat fisik dibagi dalam
blok berukuran tetap (frame),
sedangkan pembagian alamat logika
disebut page
Perlu mekanisme untuk
mengidentifikasi frame kosong, agar page
teralokasi
Proses dengan n page, memerlukan
n frame
Page table, digunakan untuk
mentranslasi alamat logika ke alamat fisik
Sistem Operasi - Pengelolaan
Memory -Paging
Skema Translasi Alamat
Nomor page (p): digunakan sebagai
indeks ke page table, berisi base
address dari setiap page dalam
memori fisik
Offset (d): nilai yang
ditambahkan ke base address untuk
mendefinisikan alamat fisik
G A M B A R : Paging hardware
|
Dukungan Hardware untuk Page Table
Page table disimpan di memori
utama
Page table base register (PTBR):
menunjuk page table
Page table length register (PTLR):
mengindikasikan ukuran page table
Dengan skema ini, setiap akses
instruksi/data memerlukan dua akses
memori, ke page table dan ke
instruksi/data ! menimbulkan masalah
waktu akses
Diatasi dengan associative memory
dan translation look aside buffer
(TLB) ! hardware khusus untuk
mempercepat waktu akses
Beberapa TLBs meyimpan
address-space identifiers (ASIDs) disetiap
entry TLB – Secara unik
mengidentifikasi setiap proses untuk
memberikan proteksi terhadap ruang
alamat
Hanya beberapa dari page table
yang disimpan dalam TLB, kapasitas
terbatas
Sistem Operasi - Pengelolaan
Memory -Paging
Associative Memory
Nomor page Nomor frame
Transalasi alamat p : d
Aturan:
jika diketahui nomor page:
keluarkan nomor frame
jika tidak diketahui nomor page,
cari dari page table, keluarkan nomor
frame
Waktu akses efektif:
Waktu akses TLB + waktu akses
memori
Hit rasio: persentase ditemukannya
page table dalam TLB dalam rentang
waktu tertentu
Proteksi Memory
Setiap referensi ke memori
memiliki pasangan nomor page dan frame
Proteksi memori diterapkan melalui
proteksi bit yang terkait pada setiap
frame, dapat menyebabkan blok
memori bersifat read-write atau read
only
Valid-invalid bit pada page table:
valid: sedang berada pada ruang
alamat logika proses
invalid: tidak sedang pada ruang
alamat logika proses
Struktur Page Table
Target: membuat alokasi page table
dan memori efisien
Mekanisme:
Hierarchical paging: ruang alamat
logika dipecah dalam beberapa tabel
Hashed page table:
inverted page table
Hashed Page Table
Umum digunakan di sisitem > 32
bit
Halaman virtual di-hashed dalam
page table: berisi pointer ke element
hashing di lokasi yang sama
Halaman virtual dibandingkan
dengan pointer, jika ditemukan
dihubungkan dengan alamat fisik
Inverted Page Table
Umum digunakan di sisitem > 32
bit
Setiap entri page table memiliki
pasangan alamat memori fisik dengan
informasi proses yang memilikinya
Butuh lebih sedikit memori untuk
menyimpan, tetapi butuh waktu lebih
banyak untuk me-refer ke lokasi
memori fisik (gunakan hash table)
Segmentation
Skema pengelolaan memori yang
mendukung pemisahan antara lokasi
memori logika dengan lokasi memori
fisik
Sebuah program adalah kumpulan
segment.
Segement adalah unit logika yang
dapat berupa: program utama,
prosedur, fungsi metode, obyek,
variabel lokal dan global, blok bersama,
stack, tabel simbol, array
Arsitektur
Alamat logika terdiri dari dua
bagian: <nomor-segment, offset>
Segment table – memetakan alamat
fisik yang setiap entry terdiri dari:
base – berisi lokasi fisik di mana
segmen dimulai
limit – berisi jumlah lokasi
memory yang diperlukan segmen
Segment-table base register (STBR)
menunjuk ke tabel lokasi segmen
di memori
Segment-table length register
(STLR) menunjukkan banyaknya lokasi
memori yang diperlukan: nomor
segmen s valid jika s < STLR
Arsitektur
Proteksi, setiap entry dalam tabel
segmen menghubungkan:
Bit validasi = 0 ) illegal segment
read/write/execute (privileges)
Bits proteksi terkait dengan
segment: code sharing terjadi pada level
segmen
Karena panjang segemen bervariasi,
alokasi memori merupakan bagian
dari masalah alokasi dinamis
Segmentasi dengan Paging
Memanfaatkan kelebihan segmentasi:
sharing & protection: setiap
segmen memiliki informasi read/write atau
read-only
Memanfaatkan kelebihan paging:
tidak ada fragmentasi external
alokasi cepat
Tidak ada komentar:
Posting Komentar