Metode Alokasi dan Managemen Ruang Kosong Oleh Catur Adi Nugroho dan M. Faisal Reza 56.6
Kritik dan saran
[email protected]
Silahkan menampilkan slide berikut sebagai halaman web, mengedarkan, memperbanyak, menggunakan untuk keperluan pendidikan tanpa harus mengubah nota hak cipta 2 Desember 2004
Copyright 2004
1
Masalah Bagaimana caranya mengalokasikan ruang untuk sebuah file agar disk dapat digunakan secara optimal dan agar file dapat diakses secara cepat.
2 Desember 2004
Copyright 2004
2
Metode Alokasi n n n
Contiguous Allocation Linked Allocation Indexed Allocation
Managemen Ruang Kosong n n n n 2 Desember 2004
Bit Vector Linked List Grouping Counting Copyright 2004
3
Contiguous Allocation n
n
n
n
File disimpan dalam blok-blok disk yang berurutan (Contiguous). Alamat disk mendefinisikan urutan linear dari blok-blok di dalam disk. Directory entry mengandung alamat blok awal dan panjang blok yang dialokasikan untuk sebuah file. Sangat efisien pada saat pengaksesan blok baik secara sequential maupun random.
2 Desember 2004
Copyright 2004
4
Contiguous Allocation (Cont.)
Operating System Concepts with Java. Silberschatz, Galvin and Gagne © 2003
Blok ke i = Blok awal + i 2 Desember 2004
Copyright 2004
5
Contiguous Allocation (Cont.) Masalah : 1. Mencari ruang yang sesuai untuk sebuah file yang baru. 2. External Fragmentation. 3. Alokasi ruang diawal pembuatan file. 4. Ukuran file tidak dapat membesar.
2 Desember 2004
Copyright 2004
6
Linked Allocation n n n n n
File merupakan linked list dari blok-blok disk. Blok-blok nya boleh blok mana saja yang berada di dalam disk. Directory terdiri dari pointer ke blok pertama dan terakhir dari file. Setiap blok memiliki pointer ke blok berikutnya dalam satu file. Tidak ada external fragmentation dan tidak butuh alokasi ruang awal untuk setiap file.
2 Desember 2004
Copyright 2004
7
Linked Allocation (Cont.)
Operating System Concepts with Java. Silberschatz, Galvin and Gagne © 2003
2 Desember 2004
Copyright 2004
8
Linked Allocation (Cont.) Masalah : 1. Lambat dalam mengakses blok secara random. 2. Ruang yang dibutuhkan untuk menyimpan pointer. 3. Reliability.
2 Desember 2004
Copyright 2004
9
FAT (File Allocation Table)
Operating System Concepts with Java. Silberschatz, Galvin and Gagne © 2003
2 Desember 2004
Copyright 2004
10
Indexed Allocation n n n
n n
n
Setiap file memiliki index blok. Directory terdiri dari pointer ke index blok. Index blok merupakan suatu array yang setiap elemennya merupakan urutan blok dari suatu file. Mendukung akses blok secara langsung. Akses blok ke i , gunakan pointer ke i dari indek blok, cari dan baca blok yang sesuai. Tidak ada external fragmentation.
2 Desember 2004
Copyright 2004
11
Indexed Allocation (Cont.)
0 1 2 … n index table
blok
Operating System Concepts with Java. Silberschatz, Galvin and Gagne © 2003
2 Desember 2004
Copyright 2004
12
Indexed Allocation (Cont.) Masalah : 1. Internal Fragmentation. 2. Ukuran index blok. Mekanisme : 1. Linked scheme. 2. Multilevel Index. 3. Combined Scheme.
2 Desember 2004
Copyright 2004
13
Indexed Allocation (Cont.) Combined Scheme: UNIX (4K bytes per block)
Operating System Concepts with Java. Silberschatz, Galvin and Gagne © 2003
2 Desember 2004
Copyright 2004
14
Managemen Ruang Kosong n
n
Bit Vector F Ruang-ruang kosong diimplementasikan sebagai bit map atau bit vector. F Setiap blok merupakan 1 bit. F blok free = 1 blok Used = 0. F efisien dan simpel dalam mencari n urutan blok kosong yang pertama. Linked List F Membuat link antara blok-blok yang kosong didalam disk.
2 Desember 2004
Copyright 2004
15
Managemen Ruang Kosong n
Linked List (Cont.) F Setiap blok kosong memiliki pointer ke blok kosong berikutnya. F Tidak efisien, karena pengaksesannya harus dilakukan secara sekuensial.
n
Grouping F Menyimpan n buah alamat blok kosong ke blok kosong yang pertama. F n-1 blok berikutnya kosong.
2 Desember 2004
Copyright 2004
16
Managemen Ruang Kosong n
n
Grouping (Cont.) F Blok terakhir dapat digunakan untuk menyimpan alamat blok pertama dari blok kosong lainnya. Counting F Free space list menyimpan alamat pertama blok kosong yang berurutan dan jumlah blok kosong yang mengikutinya.
2 Desember 2004
Copyright 2004
17
Sumber Avi Silberschatz dkk., Operating System Concepts : Sixth Edition 2002
2 Desember 2004
Copyright 2004
18
