PENDETEKSIAN DAN PENCEGAHAN DEADLOCK PADA SISTEM OPERASI MENGGUNAKAN PENDEKATAN GRAPH ALOKASI SUMBER DAYA
SKRIPSI
Oleh :
NENNA IRSA SYAHPUTRI
050803029
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009
Universitas Sumatera Utara
ii
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PENDETEKSIAN DAN PENCEGAHAN DEADLOCK PADA SISTEM OPERASI MENGGUNAKAN PENDEKATAN GRAPH ALOKASI SUMBER DAYA. : SKRIPSI : NENNA IRSA SYAHPUTRI : 050803029 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Medan, Oktober 2009
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Drs. Ujian Sinulingga, M.Si NIP 19560303 1984031 004
Prof. Dr. Herman Mawengkang NIP 19461128 1974031 001
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua.
Dr. Saib Suwilo, M.Sc NIP 19640109 198803 1004
Universitas Sumatera Utara
iii
PERNYATAAN
PENDETEKSIAN DAN PENCEGAHAN DEADLOCK PADA SISTEM OPERASI MENGGUNAKAN PENDEKATAN GRAPH ALOKASI SUMBER DAYA
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Oktober 2009-
NENNA IRSA SYAHPUTRI 050803029
Universitas Sumatera Utara
iv
PENGHARGAAN
Puji dan syukur penulis ucapkan kehadirat Allah SWT yang telah melimpahkan karunia-Nya, sehingga penulis berhasil menyelesaikan skripsi ini dalam waktu yang telah ditetapkan.
Dalam kesempatan ini, penulis mengucapkan terima kasih yang sebesarbesarnya kepada semua pihak yang telah membantu dan membimbing penulis dalam penyusunan skripsi ini, ucapan terima kasih penulis sampaikan kepada: 1. Bapak Prof. Dr. Herman Mawengkang. selaku pembimbing I dan Bapak Drs. Ujian Sinulingga, M.Si. selaku pembimbing II yang telah memberikan bimbingan dan pengarahan kepada penulis sehingga skripsi ini dapat diselesaikan. 2. Bapak Syahril Efendi, S.Si, M.IT. dan Bapak James Piter Marbun, M.Kom. selaku dosen penguji penulis. 3. Ibu Dra. Esther Sorta MN, M.Sc. selaku dosen wali penulis selama mengikuti perkuliahan. 4. Bapak Dr. Saib Suwilo, M.Sc. dan Bapak Drs. Henry Rani Sitepu, M.Sc. selaku Ketua dan Sekretaris, Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. 5. Dekan dan Pembantu Dekan FMIPA USU. 6. Semua Dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU. 7. Teman-teman di Departemen Matematika khususnya stambuk 2005, serta sahabat-sahabat penulis: Cinta, feby, dika, Lia, Rima, Radhi, Santri, Sundari dan Yuni yang selama ini telah memberikan semangat, dorongan dan saran dalam pengerjaan skripsi ini. 8. Kedua orang tua penulis yang tercinta Bapak Sarwo dan Ibunda Iriani, kakak Nenny Asri Syahputri dan adik Mimmy Sari Syahputri yang selalu berdoa dan memberikan dorongan, pengorbanan moril maupun materil kepada penulis selama masa perkuliahan hingga selesainya skripsi ini.
Universitas Sumatera Utara
v
Penulis menyadari sepenuhnya bahwa isi maupun sistematika penyajian tulisan ini belum layak dikatakan sempurna. Untuk itu dengan segala kerendahan hati, penulis mengharapkan kritik dan saran yang membangun. Akhirnya, semoga tulisan ini dapat bermanfaat bagi para pembaca dan yang memerlukannya. Semoga segala bentuk bantuan yang telah diberikan kepada penulis mendapatkan balasan yang lebih baik dari Allah SWT.
Universitas Sumatera Utara
vi
ABSTRAK
Setiap sumber daya pada sistem operasi akan digunakan oleh proses-proses yang membutuhkannya. Mekanisme hubungan dari proses-proses dan sumber daya yang dibutuhkan atau digunakan dapat divisualisasikan kedalam graph alokasi sumber daya dan graph tunggu, sehingga permasalahan deadlock pada sistem operasi dapat dideteksi, dicegah, dan diselesaikan.
Universitas Sumatera Utara
vii
DEADLOCK DETECTION AND PREVENTION IN OPERATING SYSTEM USING RESOURCE ALLOCATION GRAPH
ABSTRACT
Every resource on the operating system will be used by the processes that need it. The mechanism of relationship processes and resource needed or used can be visualized into the resource allocation graph and waiting graph. Deadlock on the issue in the operating system can be detected, prevented, and resolved.
Universitas Sumatera Utara
viii
DAFTAR ISI
PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR
Halaman ii iii iv vi vii viii ix x
Bab 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Identifikasi Masalah 1.3 Tujuan Penelitian 1.4 Kontribusi Penelitian 1.5 Batasan Masalah 1.6 Metode Penelitian 1.7 Tinjauan Pustaka
1 1 2 2 2 2 3 3
Bab 2 LANDASAN TEORI 2.1 Konsep Dasar Graph 2.1.1 Sejarah Graph 2.1.2 Definisi Graph 2.1.3 Jenis-Jeins Graph 2.2 Graph Alokasi Sumber daya 2.2.1 Definisi Graph Alokasi Sumber Daya 2.2.2 Komponen Graph Alokasi Sumber Daya 2.3 Definisi Sistem Operasi 2.4 Definisi Deadlock 2.4.1 Model Sistem 2.4.2 Sumber Daya 2.4.3 Penyebab dan Penanggulangan Deadlock
5 5 6 7 11 11 11 13 15 16 17 18
Bab 3 PEMBAHASAN 3.1 Pendeteksian Deadlock 3.1.1 Algoritma Deteksi Deadlock 3.1.2 Pendeteksian dengan Graph Tunggu
19 19 19 20
Universitas Sumatera Utara
ix
3.2 Pencegahan Deadlock 3.3 Pemulihan Deadlock 3.3.1 Terminasi Proses 3.3.2 Penyelaan Penggunaan Sumber Daya 3.4 Penghindaran Deadlock 3.5 Contoh Pendeteksian Deadlock
22 25 25 25 27 30
Bab 4 KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
33 33 34
DAFTAR PUSTAKA
35
Universitas Sumatera Utara
x
DAFTAR TABEL
Tabel 3.1 Tabel contoh safe state Tabel 3.2 Tabel contoh unsafe state
Halaman 28 29
Universitas Sumatera Utara
xi
DAFTAR GAMBAR
Gambar 2.1 Jembatan Koningsberg Gambar 2.2 Graph pemodelan jembatan Koningsberg Gambar 2.3 Graph empat simpul lima sisi Gambar 2.4 Graph sederhana Gambar 2.5 Graph ganda Gambar 2.6 Graph semu Gambar 2.7 Graph berhingga Gambar 2.8 Graph tak berhingga Gambar 2.9 Graph tak berarah Gambar 2.10 Graph berarah Gambar 2.11 Proses Gambar 2.12 Sumber daya Gambar 2.13 Sisi permintaan Gambar 2.14 Sisi alokasi Gambar 2.15 Graph alokasi sumber daya tiga proses empat sumber daya Gambar 2.16 Deadlock pada jembatan Gambar 2.17 Proses C dan D deadlock terhadap sumber daya T dan U Gambar 2.18 Deadlock pada rel kereta api Gambar 3.1 Graph alokasi sumber daya empat proses tiga sumber daya Gambar 3.2 Graph tunggu Gambar 3.3 Graph alokasi sumber daya status aman Gambar 3.4 Graph alokasi sumber daya status tidak aman Gambar 3.5 Graph alokasi sumber daya dengan deadlock Gambar 3.6 Graph alokasi sumber daya tanpa deadlock
Halaman 5 6 7 7 8 8 9 9 10 10 11 11 12 12 13 15 15 16 21 21 24
24 30 31
Universitas Sumatera Utara
