Saturday, 27 April 2013
1.1 Manajemen
Ruang Kosong
Semenjak
hanya tersedia tempat yang terbatas pada disk maka sangat berguna untuk
menggunakan kembali tempat dari berkas yang dihapus untuk berkas baru, jika
dimungkinkan,karena pada media yang sekali tulis (media optik) hanya dimungkinkan
sekali menulis dan menggunakannyanya kembali secara fisik tidak mungkin. Untuk
mencatat tempat kosong pada disk, sistem mempunyai daftar tempat kosong (free
space list). Daftar ini menyimpan semua blok disk yang kosong yang tidak
dialokasikan pada sebuah berkas atau direktori. Untuk membuat berkas baru,
sistem mencari ke daftar tersebut untuk mencarikan tempat kosong yang di
butuhkan, lalu tempat tersebut dihilangkan dari daftar. Ketika berkas dihapus,
alamat berkas tadi ditambahkan pada daftar.
Menggunakan Bit Vektor
Seringnya
daftar raung kosong diimplementasikan sebagai bit map atau bit vektor. Tiap
blok direpresentasikan sebagai 1 bit. Jika blok tersebut kosong maka isi bitnya
1 dan jika bloknya sedang dialokasikan maka isi bitnya 0. Sebagai contoh sebuah
disk dimana blok 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 dan 27 adalah
kosong, dan sisanya dialokasikan. Bit mapnya akan seperti berikut:
001111001111110001100000011100000...
Keuntungan
utama dari pendekatan ini adalah relatif sederhana dan efisien untuk mencari
blok pertama yang kosong atau berturut-turut n blok yang kosong pada disk.
Banyak komputer yang menyediakan instruksi manipulasi bit yang dapat digunakan
secara efektif untuk tujuan ini. Sebagai contohnya, dari keluarga prosesor
Intel dimulai dari 80386 dan keluarga Motorola dimulai dari 68020 (prosesor
yang ada di PC dan Macintosh) mempunyai instruksi yang mengembalikan jarak
di word dari bit pertama dengan nilai 1. Sistem operasi Apple
Macintosh menggunakan metode bit vektor untuk mengalokasikan tempat pada disk.
Dalam hal ini perangkat keras mendukung perangkat lunak tetapi bit vektor tidak
efisien kecuali seluruh vektor disimpan dalam memori utama (dan ditulis di disk
untuk kebutuhan pemulihan). Menyimpan dalam memori utama dimungkinkan untuk
disk yang kecil pada mikro komputer, tetapi tidak untuk disk yang besar.
Sebuah disk 1,3 GB dengan 512-byte blok akan membutuhkan bit
map sebesar 332K untuk mencatat blok yang kosong.
Linked List
Pendekatan
lain adalah untuk menghubungkan semua blok yang kosong, menyimpan pointer ke
blok pertama yang kosong di tempat yang khusus pada disk dan menyimpannya di
memori. Blok pertama ini menyimpanpointer ke blok kosong berikutnya
dan seterusnya. Pada contoh sebelumnya kita akan menyimpan pointer ke
blok ke 2 sebagai blok kosong pertama, blok 2 akan menyimpan pointer ke
blok 3, yang akan menunjuk ke blok 4 dan seterusnya. Bagaimana pun metode ini
tidak efisien karena untuk traverse daftar tesebut kita perlu
membaca tiap blok yang membutuhkan waktu I/O. Untungnya traverse ini tidak
sering digunakan. Umumnya, sistem operasi membutuhkan blok kosong untuk
mengalokasikan blok tersebut ke berkas, maka blok pertama pada daftar ruang
kosong digunakan.
Grouping
Modifikasi
lainnya adalah dengan menyimpan alamat dari n blok kosong pada blok kosong
pertama. Pada n-1 pertama dari blok-blok ini adalah kosong. Blok terakhir
menyimpan alamat n blok kosong lainnya dan seterusnya. Keuntungannya dari
implementasi seperti ini adalah alamat dari blok kosong yang besar sekali dapat
ditemukan dengan cepat, tidak seperti pendekatan standar linked-list.
Counting
Pendekatan
lain adalah dengan mengambil keuntungan dari fakta bahwa beberapa blok yang
berkesinambungan akan dialokasikan atau dibebaskan secara simultan. Maka dari
itu dari pada menyimpan daftar dari banyak alamat disk, kita dapat menyimpan
alamat dari blok kosong pertama dan jumlah dari blok kosong yang
berkesinambungan yang mengikuti blok kosong pertama. Tiap isi dari daftar
menyimpan alamat disk dan penghitung (counter). Meski pun setiap isi
membutuhkan tempat lebih tetapi secara keseluruhan daftar akan lebih pendek,
selama count lebih dari satu.
1.2
Implementasi
Direktori
Pemilihan
dalam algoritma alokasi direktori dan manajemen direktori mempunyai efek yang
besar dalam efisiensi, performa, dan kehandalan dari sistem berkas.
Linear List
Metode
paling sederhana dalam mengimplementasikan sebuah direktori adalah dengan
menggunakan linear list dari nama berkas dengan penunjuk ke
blok data. Linear list dari direktori memerlukan pencarian
searah untuk mencari suatu direktori didalamnya. Metode sederhana untuk di
program tetapi memakan waktu lama ketika dieksekusi. Untuk membuat berkas baru
kita harus mencari di dalam direktori untuk meyakinkan bahwa tidak ada berkas
yang bernama sama. Lalu kita tambahkan sebuah berkas baru pada akhir direktori.
Untuk menghapus sebuah berkas, kita mencari berkas tersebut dalam direktori,
lalu melepaskan tempat yang dialokasikan untuknya. Untuk menggunakan kembali
suatu berkas dalam direktori kita dapat melakukan beberapa hal. Kita dapat
menandai berkas tersebut sebagai tidak terpakai (dengan menamainya secara
khusus, seperti nama yang kosong, atau bit terpakai atau tidak yang ditambahkan
pada berkas), atau kita dapat menambahkannya pada daftar direktori bebas.
Alternatif lainnya kita dapat menyalin ke tempat yang dikosongkan pada
direktori. Kita juga bisa menggunakan linked list untuk mengurangi waktu untuk
menghapus berkas. Kelemahan dari linear list ini adalah percarian searah untuk
mencari sebuah berkas. Direktori yang berisi informasi sering digunakan,
implementasi yang lambat pada cara aksesnya akan menjadi perhatian pengguna.
Faktanya, banyak sistem operasi mengimplementasikan 'software cache' untuk
menyimpan informasi yang paling sering digunakan. Penggunaan 'cache'
menghindari pembacaan informasi berulang-ulang pada disk. Daftar yang telah
diurutkan memperbolehkan pencarian biner dan mengurangi waktu rata-rata
pencarian. Bagaimana pun juga penjagaan agar daftar tetap terurut dapat
merumitkan operasi pembuatan dan penghapusan berkas, karena kita perlu
memindahkan sejumlah direktori untuk mengurutkannya. Tree yang
lebih lengkap dapat membantu seperti B-tree. Keuntungan dari daftar yang
terurut adalah kita dapatkan daftar direktori yang terurut tanpa pengurutan
yang terpisah.
Hash Table
Struktur
data lainnya yang juga digunakan untuk direktori berkas adalah hash
table. Dalam metode ini linear list menyimpan direktori, tetapi struktur
data hash juga digunakan. Hash table mengambil nilai yang
dihitung dari nama berkas dan mengembalikan sebuah penunjuk ke nama berkas yang
ada di-linear list. Maka dari itu dapat memotong banyak biaya pencarian
direktori. Memasukkan dan menghapus berkas juga lebih mudah dan cepat. Meski
demikian beberapa aturan harus dibuat untuk mncegah tabrakan, situasi dimana
dua nama berkas pada hash mempunyai tempat yang sama.
Kesulitan utama dalam hash table adalah ukuran tetap
dari hash table dan ketergantungan dari fungsi hash dengan
ukuran hash table. Sebagai contoh, misalkan kita membuat
suatu linear-probing hash table yang dapat menampung 64 data.
Fungsi hash mengubah nama berkas menjadi nilai dari 0 sampai
63. Jika kita membuat berkas ke 65 maka ukuran tabel hash harus
diperbesar sampai misalnya 128 dan kita membutuhkan suatu fungsi hash yang
baru yang dapat memetakan nama berkas dari jangkauan 0 sampai 127, dan kita
harus mengatur data direktori yang sudah ada agar memenuhi fungsi hash yang
baru. Sebagai alternatif dapat digunakan chained-overflow hash table,
setiap hash table mempunyai daftar yang terkait (linked
list) dari pada nilai individual dan kita dapat mengatasi tabrakan dengan
menambah tempat pada daftar terkait tersebut. Pencarian dapat menjadi lambat,
karena pencarian nama memerlukan tahap pencarian pada daftar terkait. Tetapi
operasi ini lebih cepat dari pada pencarian linear terhadap seluruh direktori.
Subscribe to:
Post Comments
(Atom)
BLOG ARCHIVE
-
▼
2013
(51)
-
▼
April
(10)
- Budaya, Kreativitas dan Inovasi
- Sistem Operasi - Manajemen Sistem File
- Perubahan dan Pengembangan Organisasi
- Desain dan Struktur Organisasi
- Kepemimpinan
- Pengambilan Keputusan Dalam Organisasi
- Mengembangkan Kemampuan Mahasiswa Dalam Komunikasi
- Rangkuman Seminar : INTERAKSI MANUSIA DAN TEKNOLOG...
- Perilaku Produsen
- Perilaku Konsumen
-
▼
April
(10)
CLOCK
MY PROFILE
Powered by Blogger.
0 comments:
Post a Comment