Kemudahan
dalam mengakses langsung suatu disk memberikan fleksibilitas dalam
mengimplementasikan sebuah berkas. Masalah utama dalam implementasi adalah
bagaimana mengalokasikan berkas-berkas ke dalam disk, sehingga disk dapat terutilisasi
dengan efektif dan berkas dapat diakses dengan cepat. Ada tiga metode utama,
menurut buku "Applied Operating System Concepts: First Edition"
oleh Avi Silberschatz, Peter Galvin dan Greg Gagne untuk mengalokasi ruang disk
yang digunakan secara luas yaitu, contiguous, linked, dan indexed.
Metode
ini menempatkan setiap berkas pada satu himpunan blok yang berurut di dalam
disk. Alamat disk menyatakan sebuah urutan linier. Dengan urutan linier ini
maka head disk hanya bergerak jika mengakses dari sektor terakhir suatu
silinder ke sektor pertama silinder berikutnya. Waktu pencarian (seek time)
dan banyak disk seek yang dibutuhkan untuk mengakses berkas yang di
alokasi secara berdampingan ini sangat minimal. Contoh dari sistem operasi yang
menggunakan contiguous allocation adalah IBM VM/ CMS karena pendekatan
ini menghasilkan performa yang baik.
Contiguous allocation dari suatu berkas diketahui melalui
alamat dan panjang disk (dalam unit blok) dari blok pertama. Jadi, misalkan ada
berkas dengan panjang n blok dan mulai dari lokasi b maka berkas tersebut
menempati blok b, b+1, b+2, ..., b+n-1. Direktori untuk setiap berkas
mengindikasikan alamat blok awal dan panjang area yang dialokasikan untuk berkas
tersebut. Terdapat dua macam cara untuk mengakses berkas yang dialokasi dengan
metode ini, yaitu:
- Sequential
access, sistem berkas mengetahui alamat blok terakhir dari
disk dan membaca blok berikutnya jika diperlukan.
- Direct
access, untuk akses langsung ke blok i dari suatu berkas yang
dimulai pada blok b, dapat langsung mengakses blok b+i.
Kesulitan
dari metode alokasi secara berdampingan ini adalah menemukan ruang untuk berkas
baru. Masalah pengalokasian ruang disk dengan metode ini merupakan aplikasi
masalah dari dynamic storage-allocation (alokasi tempat penyimpanan
secara dinamik), yaitu bagaimana memenuhi permintaan ukuran n dari daftar ruang
kosong. Strategi-strategi yang umum adalah first fit dan best fit.
Kedua strategi tersebut mengalami masalah fragmentasi eksternal, dimana jika
berkas dialokasi dan dihapus maka ruang kosong disk terpecah menjadi
kepingan-kepingan kecil. Hal ini akan menjadi masalah ketika banyak kepingan
kecil tidak dapat memenuhi permintaan karena kepingan-kepingan kecil tidak
cukup besar untuk menyimpan berkas, sehingga terdapat banyak ruang yang
terbuang.
Masalah
yang lain adalah menentukan berapa banyak ruang yang diperlukan untuk suatu
berkas. Ketika berkas dibuat, jumlah dari ruang berkas harus ditentukan dan
dialokasikan. Jika ruang yang dialokasikan terlalu kecil maka berkas tidak
dapat diperbesar dari yang telah dialokasikan. Untuk mengatasi hal ini ada dua
kemungkinan. Pertama, program pengguna dapat diakhiri dengan pesan error yang
sesuai. Lalu, pengguna harus mengalokasikan tambahan ruang dan menjalankan
programnya lagi, tetapi hal ini cost yang dihasilkan lebih mahal. Untuk
mengatasinya, pengguna dapat melakukan estimasi yang lebih terhadap ruang yang
harus dialokasikan pada suatu berkas tetapi hal ini akan membuang ruang disk.
Kemungkinan yang kedua adalah mencari ruang kosong yang lebih besar, lalu
menyalin isi dari berkas ke ruang yang baru dan mengkosongkan ruang yang
sebelumnya. Hal ini menghabiskan waktu yang cukup banyak. Walau pun jumlah
ruang yang diperlukan untuk suatu berkas dapat diketahui, pengalokasian awal
akan tidak efisien. Ukuran berkas yang bertambah dalam periode yang lama harus
dapat dialokasi ke ruang yang cukup untuk ukuran akhirnya, walau pun ruang
tersebut tidak akan digunakan dalam waktu yang lama. Hal ini akan menyebabkan
berkas dengan jumlah fragmentasi internal yang besar.
Untuk
menghindari hal-hal tersebut, beberapa sistem operasi memodifikasi skema metode
alokasi secara berdampingan, dimana kepingan kecil yang berurut dalam ruang
disk diinisialisasi terlebih dahulu, kemudian ketika jumlah ruang disk kurang
besar, kepingan kecil yang berurut lainnya, ditambahkan pada alokasi awal.
Kejadian seperti ini disebut perpanjangan. Fragmentasi internal masih dapat
terjadi jika perpanjangan-perpanjangan ini terlalu besar dan fragmentasi
eksternal masih menjadi masalah begitu perpanjangan-perpanjangan dengan ukuran
yang bervariasi dialokasikan dan didealokasi.
Metode
ini menyelesaikan semua masalah yang terdapat pada contiguous allocation.
Dengan metode ini, setiap berkas merupakan linked list dari blok-blok
disk, dimana blok-blok disk dapat tersebar di dalam disk. Setiap direktori
berisi sebuah penunjuk (pointer) ke awal dan akhir blok sebuah berkas.
Setiap blok mempunyai penunjuk ke blok berikutnya. Untuk membuat berkas baru,
kita dengan mudah membuat masukan baru dalam direktori. Dengan metode ini,
setiap direktori masukan mempunyai penunjuk ke awal blok disk dari berkas.
Penunjuk ini diinisialisasi menjadi nil (nilai penunjuk untuk akhir dari
list) untuk menandakan berkas kosong. Ukurannya juga diset menjadi 0. Penulisan
suatu berkas menyebabkan ditemukannya blok yang kosong melalui sistem manajemen
ruang kosong (free-space management system), dan blok baru ini ditulis
dan disambungkan ke akhir berkas. Untuk membaca suatu berkas, cukup dengan
membaca blok-blok dengan mengikuti pergerakan penunjuk.
Metode
ini tidak mengalami fragmentasi eksternal dan kita dapat menggunakan blok
kosong yang terdapat dalam daftar ruang kosong untuk memenuhi permintaan
pengguna. Ukuran dari berkas tidak perlu ditentukan ketika berkas pertama kali
dibuat, sehingga ukuran berkas dapat bertambah selama masih ada blok-blok
kosong.
Metode
ini tentunya mempunyai kerugian, yaitu metode ini hanya dapat digunakan secara
efektif untuk pengaksesan berkas secara sequential (sequential-access file).
Untuk mencari blok ke-i dari suatu berkas, harus dimulai dari awal
berkas dan mengikuti penunjuk sampai berada di blok ke-i. Setiap akses
ke penunjuk akan membaca disk dan kadang melakukan pencarian disk (disk seek).
Hal ini sangat tidak efisien untuk mendukung kemampuan akses langsung (direct-access)
terhadap berkas yang menggunakan metode alokasi link. Kerugian yang lain dari
metode ini adalah ruang yang harus disediakan untuk penunjuk. Solusi yang umum
untuk masalah ini adalah mengumpulkan blok-blok persekutuan terkecil dinamakan clusters
dan mengalokasikan cluster-cluster daripada blok. Dengan solusi ini
maka, penunjuk menggunakan ruang disk berkas dengan persentase yang sangat
kecil. Metode ini membuat mapping logikal ke fisikal blok tetap
sederhana, tetapi meningkatkan disk throughput dan memperkecil ruang
yang diperlukan untuk alokasi blok dan management daftar kosong (free-list
management). Akibat dari pendekatan ini adalah meningkatnya fragmentasi
internal, karena lebih banyak ruang yang terbuang jika sebuah cluster
sebagian penuh daripada ketika sebuah blok sebagian penuh. Alasan cluster
digunakan oleh kebanyakan sistem operasi adalah kemampuannya yang dapat
meningkatkan waktu akses disk untuk berbagai macam algoritma.
Masalah
yang lain adalah masalah daya tahan metode ini. Karena semua berkas saling
berhubungan dengan penunjuk yang tersebar di semua bagian disk, apa yang
terjadi jika sebuah penunjuk rusak atau hilang. Hal ini menyebabkan berkas
menyambung ke daftar ruang kosong atau ke berkas yang lain. Salah satu
solusinya adalah menggunakan linked list ganda atau menyimpan nama
berkas dan nomor relatif blok dalam setiap blok, tetapi solusi ini membutuhkan
perhatian lebih untuk setiap berkas.
Variasi
penting dari metode ini adalah penggunaan file allocation table (FAT),
yang digunakan oleh sistem operasi MS-DOS dan OS/2. Bagian awal
disk pada setiap partisi disingkirkan untuk menempatkan tabelnya. Tabel ini
mempunyai satu masukkan untuk setiap blok disk, dan diberi indeks oleh nomor
blok. Masukkan direktori mengandung nomor blok dari blok awal berkas. Masukkan
tabel diberi indeks oleh nomor blok itu lalu mengandung nomor blok untuk blok
berikutnya dari berkas. Rantai ini berlanjut sampai blok terakhir, yang
mempunyai nilai akhir berkas yang khusus sebagai masukkan tabel. Blok yang
tidak digunakan diberi nilai 0. Untuk mengalokasi blok baru untuk suatu berkas
hanya dengan mencari nilai 0 pertama dalam tabel, dan mengganti nilai akhir
berkas sebelumnya dengan alamat blok yang baru. Metode pengalokasian FAT ini
dapat menghasilkan jumlah pencarian head disk yang signifikan, jika
berkas tidak di cache. Head disk harus bergerak dari awal partisi untuk
membaca FAT dan menemukan lokasi blok yang ditanyakan, lalu menemukan lokasi
blok itu sendiri. Kasus buruknya, kedua pergerakan terjadi untuk setiap blok.
Keuntungannya waktu random akses meningkat, akibat dari head disk dapat
mencari lokasi blok apa saja dengan membaca informasi dalam FAT.
Metode
alokasi dengan berangkai dapat menyelesaikan masalah fragmentasi eksternal dan
pendeklarasian ukuran dari metode alokasi berdampingan. Bagaimana pun tanpa
FAT, metode alokasi berangkai tidak mendukung keefisiensian akses langsung,
karena penunjuk ke bloknya berserakan dengan bloknya didalam disk dan perlu
didapatkan secara berurutan. Metode alokasi dengan indeks menyelesaikan masalah
ini dengan mengumpulkan semua penunjuk menjadi dalam satu lokasi yang dinamakan
blok indeks (index block). Setiap berkas mempunyai blok indeks, yang
merupakan sebuah larik array dari alamat-alamat disk-blok. Direktori
mempunyai alamat dari blok indeks. Ketika berkas dibuat, semua penunjuk dalam
blok indeks di set menjadi nil. Ketika blok ke-i pertama kali
ditulis, sebuah blok didapat dari pengatur ruang kosong free-space manager
dan alamatnya diletakkan ke dalam blok indeks ke-i.
Metode
ini mendukung akses secara langsung, tanpa mengalami fragmentasi eksternal
karena blok kosong mana pun dalam disk dapat memenuhi permintaan ruang
tambahan. Tetapi metode ini dapat menyebabkan ada ruang yang terbuang. Penunjuk
yang berlebihan dari blok indeks secara umum lebih besar dari yang terjadi pada
metode alokasi berangkai.
Mekanisme
untuk menghadapi masalah berapa besar blok indeks yang diperlukan sebagai
berikut:
- Linked
scheme: untuk berkas-berkas yang besar, dilakukan dengan
menyambung beberapa blok indeks menjadi satu.
- Multilevel
index: sebuah varian dari representasi yang berantai adalah
dengan menggunakan blok indeks level pertama menunjuk ke himpunan blok
indeks level kedua, yang akhirnya menunjuk ke blok-blok berkas.
- Combined
scheme: digunakan oleh sistem BSD UNIX yaitu dengan
menetapkan 15 penunjuk dari blok indeks dalam blok indeksnya berkas. 12
penunjuk pertama menunjuk ke direct blocks yang menyimpan
alamat-alamat blok yang berisi data dari berkas. 3 penunjuk berikutnya
menunjuk ke indirect blocks. Penunjuk indirect blok yang
pertama adalah alamat dari single indirect block, yang merupakan
blok indeks yang berisi alamat-alamat blok yang berisi data. Lalu ada
penunjuk double indirect block yang berisi alamat dari sebuah blok
yang berisi alamat-alamat blok yang berisi penunjuk ke blok data yang
sebenarnya.
Salah
satu kesulitan dalam membandingkan performa sistem adalah menentukan bagaimana
sistem tersebut akan digunakan. Sistem yang lebih banyak menggunakan akses
sekuensial (berurutan) akan memakai metode yang berbeda dengan sistem yang
lebih sering menggunakan akses random (acak). Untuk jenis akses apa pun,
alokasi yang berdampingan hanya memerlukan satu akses untuk mendapatkan sebuah
blok disk. Karena kita dapat menyimpan initial address dari berkas di
dalam memori, maka alamat disk pada blok ke-i dapat segera dikalkulasi
dan dibaca secara langsung.
Untuk
alokasi berangkai (linked list), kita juga dapat menyimpan alamat dari
blok selanjutnya ke dalam memori, lalu membacanya secara langsung. Metode ini
sangat baik untuk akses sekuensial, namun untuk akses langsung, akses menuju
blok ke-ikemungkinan membutuhkan pembacaan disk sebanyak i kali.
Masalah ini mengindikasikan bahwa alokasi berangkai sebaiknya tidak digunakan
untuk aplikasi yang membutuhkan akses langsung.
Oleh
sebab itu, beberapa sistem mendukung akses langsung dengan menggunakan alokasi
berdampingan (contiguous allocation), serta akses berurutan dengan
alokasi berangkai. Untuk sistem-sistem tersebut, jenis akses harus
dideklarasikan pada saat berkas dibuat. Berkas yang dibuat untuk akses
sekuensial (berurutan) akan dirangkaikan dan tidak dapat digunakan untuk akses
langsung. Berkas yang dibuat untuk akses langsung akan berdampingan dan dapat
mendukung baik akses langsung mau pun akses berurutan, dengan mendeklarasikan
jarak maksimum. Perhatikan bahwa sistem operasi harus mendukung struktur data
dan algoritma yang sesuai untuk mendukung kedua metode alokasi di atas.
Alokasi
dengan menggunakan indeks lebih rumit lagi. Jika blok indeks telah terdapat
dalam memori, akses dapat dilakukan secara langsung. Namun, menyimpan blok
indeks dalam memori memerlukan ruang (space) yang besar. Jika ruang memori
tidak tersedia, maka kita mungkin harus membaca blok indeks terlebih dahulu,
baru kemudian blok data yang diinginkan. Untuk indeks dua tingkat, pembacaan
dua blok indeks mungkin diperlukan. Untuk berkas yang berukuran sangat besar,
mengakses blok di dekat akhir suatu berkas akan membutuhkan pembacaan seluruh
blok indeks agar dapat mengikuti rantai penunjuk sebelum blok data dapat
dibaca. Dengan demikian, performa alokasi dengan menggunakan indeks ditentukan
oleh: struktur indeks, ukuran berkas, dan posisi dari blok yang diinginkan.
Beberapa
sistem mengkombinasikan alokasi berdampingan dengan alokasi indeks. Caranya
adalah dengan menggunakan alokasi berdampingan untuk berkas berukuran kecil
(3-4 blok), dan beralih secara otomatis ke alokasi indeks jika berkas semakin
membesar.
Tidak ada komentar:
Posting Komentar