File-System Implementation

File System (Implementation) – Ch. 11 SISTIM OPERASI (Operating System) IKI-20230 Johny Moningka ([email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001

File-System Implementation n n n

File-System Structure Allocation Methods Free-Space Management

File System JM -2000/v1.1/2

1

Review n

Storage management (server): n

Performance management (secara global): • File sharing (server), potensi user akses yang sangat banyak. • Bottleneck pada I/O dari server => dedicated komputer untuk disk storage => management mudah (centralized). • Teknologi: SAN (storage area network).

n

Capacity management: • Strategi untuk mendukung memori hirarkis: kapan data harus di migrasi dari storage cost/byte mahal ke storage cost/byte lebih murah => Backup dan pengarsipan. • Quota dan alokasi disk high speed untuk aplikasi penting.

n

Availability: • Termasuk solusi RAID, network restore etc. • Bad blocks (disk)? Hardware or software recovery. File System JM -2000/v1.1/3

File-System Structure n

File structure n

n

n

Isi file: kumpulan byte yang berhubungan dengan informasi. Logical storage unit: urutan byte, dengan akses address secara logical (offset:1 s/d sizeof file).

Bagaimana layout file => disk (sektor) n

Data file disimpan dalam blok (kelipatan besarnya sector). • Logical address disk: urutan blok data.

n

Implementasi: • Mengurangi overhead mendapatkan data (seek, rotation). • Manajemen blok yang bebas (free list). File System JM -2000/v1.1/4

2

Disk Management n

Alokasi struktur blok disk: n n n

n n

Contiguous allocation Linked allocation. Indexed allocation.

Manajemen free list dari blok storage. Manajemen volume, partisi disk.


Workloads n

Bagaimana cara user menggunakan file? n n

n

Sequential access: data besar dan berurut. Random access: data kecil dan lokasi blok tidak berurut.

Hal yang menjadi dasar design file structure: n n

n

Umumnya file ukurannya kecil (pengamatan). Sebagian dari blok disk digunakan oleh file yang besar (porsi terbesar). Jadi perlu dukungan untuk kedua model akses : akses random (file kecil yang banyak) dan sequential (file yang besar dan aktifitas tinggi) => trade off yang sulit dipenuhi. File System JM -2000/v1.1/6

3

Contiguous Allocation n n n

Setiap file menempati “sekumpulan” blok yang contiguous (sinambung) pada disk. Umumnya max. besar file telah tetap (user menentukan). Pro’s: n n

n

Manajemen blok yang dialokasikan sederhana. Informasi awal lokasi nomor blok dan panjang blok yang dialokasikan.

Con’s: n n

Space terbuang percuma, belum tentu sebesar data/isi file (dynamic storage-allocation problem). Sulit memperbesar (demand, grow) dari file.


Simple mechanism n

Example: IBM OS/360

n

When creating a file, make the user specify pre-specify its length and allocate all space at once File descriptor contents: location and size

n

Pro: simple, fast access, both sequential and random.

n

Masalah: fragementasi => perlu penggabungan blok yang kecil menjadi contiguous blok besar

n

what happens if file c needs 2 blok??? file a (base=1,len=3)

file b (base=5,len=2) File System JM -2000/v1.1/8

4

Simple mechanism n

“Extent-based”: allocate files like segmented memory

file a (base=1,len=3)

what happens if file c needs 2 sectors??? file b (base=5,len=2)


Linked files n

Basically a linked list on disk. n

Keep a linked list of all free blocks Variably Variablysized, sized,flexibly flexiblylaid laidout outfiles files

how do you find the last block in a? file a (base=1) file b (base=5) n pro: easy dynamic growth & sequential access, no fragmentation n con? n Examples (sort-of): Alto, TOPS-10, DOS FAT


5

Linked Allocation n

Setiap file terdiri dari “linked list” dari blok disk: n n

Mekanisme pengurutan blok yang dialokasikan untuk suatu file. Blok yang dialokasikan dapat tersebar (scattered): • Tidak perlu “fixed allocation” => menjawab dynamic allocation problem.

n n

File descriptor: a pointer to file’s first block Setiap blok menyimpan pointer yang menunjuk ke blok yang berikut. pointer ke alokasi blok berikutnya block

=

Data


Linked List Allocate as needed, link together; e.g., file starts at block 9 Bagaimana melakukan random access? “Follow the link”, overhead besar (read blok disk; linked list) => banyak seek)


6

Example: DOS FS (simplified) Performance: Link dikumpulkan pada fixed-sized “file allocation table” (FAT) => tidak disebarkan pada setiap blok. FAT (16-bit entries) file a free Directory (5) 0 6 4 3 eof 1 a: 6 1 2 file b b: 2 eof 3 2 1 3 4 eof 5 4 6 ... n

n

FAT cukup kecil dapat disimpan “cache” disk => akses tanpa melakukan seek. File System JM -2000/v1.1/13

FAT discussion n

Entry size = 16 bits nomor blok n n

n

n

Berapa maksimum ukuran FAT? Jika 512 byte per blok, what’s the maximum size of FS yang dapat dikenal? Solusi sederhana: memperbesar ukuran blok.

Reliability: how to protect against errors? n

n

n

64k* 64k*22==128K 128K 64K*.5k 64K*.5k==32M 32MFS FS

FAT menempati satu area tertentu (contiguous sector) => what happen if corrupt? Buat duplikat FAT on disk.

Bootstrapping: where is root directory? n

Fixed location on disk:

FAT (opt) FAT

root dir

…


7

Indexed files n

Kumpulkan pointer blok ke dalam satu “indexed block”. n

n

Implementasi: array pointer => max. ukuran file yang dapat ditampung oleh array tersebut. Create file: alokasikan blok pertama untuk menyimpan array pointer, blok akan diberikan “on demand” oleh user (dynamic).

file a n

file b

Pro: mendukung sequential access dan random (read the first block, and scan the array pointer). File System JM -2000/v1.1/15

Example of Indexed Allocation


8

Indexed files n

Issues (sama seperti masalah page table besar) 2^20 entries! 4K 4Kblock blocksize, size,4GB 4GBfile file ==1M 1Mentries entries(4MB!) (4MB!)

idle 2^32 file size n n

4K blocks

Ukuran file kecil = lots of unused entries Mendukung file besar? table array menempati banyak blok yang contiguous.


Multi-leve indexed Pembagian struktur index hirarkis: region dengan index array (1 st level), menunjuk ke index array (2 nd level) dst. Masalah: akses ke index array => overhead

idle


9

Indexed Allocation – Mapping

M

outer- index

index table

file


Example UNIX: inode Untuk file kecil: 1 blok data Size: 4 Kbytes/blok Ukuran inode: 100 bytes Overhead: 2,5%


10

Multi-level indexed files n

File descriptor (inode) = 14 block pointers

stuff

data blocks

Indirect block Ptr 1 ptr 2 … ptr 128

Ptr 1 ptr 2 ptr 3 ptr 4 ...

Indirect blks Ptr 1 ptr 2 … ptr 128 Double indirect block File System JM -2000/v1.1/21

ptr 13 ptr 14

UNIX: inodes n

Inodes disimpan pada array (fixed) n

n

Besarnya array inode ditentuk saat disk di format (initialized) dan menempati lokasi tertentu (awal atau tersebar). Array inode tidak dapat diubah (kecuali melakuk reformat).

Inode array file blocks ...

n

n

File system menyimpan (direktori) index yang menunjuk ke i-node (OS Unix menyebut i-number). Saat file dibuka, maka I-number diambil dari direktori dan i-node disimpan ke memori (bagian dari referensi PCB proses tsb). File System JM -2000/v1.1/22

11

Example: Unix file system n

Want to modify byte 4 in /a/b.c: . : 10 : dir a: 12: dir

. :12 dir .. :10:dir b.c :13:inode

Root directory n n n

“read” root directory (blk 10) refcnt=1 14 0 … 0 lookup a (blk 12); “read” lookup inode for b.c (13); “read” int main() { …

n

Gunakan inode mencari byte 4 (blksize = 4KB, so File System JM -2000/v1.1/23 offset = 0 gives blk 14); “read”

Block: OS view n

Berapa besar blok data suatu file system? n n

Sistim lama (disk kecil): 512 Bytes => saat ini 4 KB. Contoh: Unix (V7) => Unix 4.2 BSD (Berkeley) • Analisa performance response time FS, meningkat 4 x lebih cepat (sequential access). • Why? Makin kecil ukuran block => makin banyak blok yang yang harus ditransfer atau makin banyak I/O operation yang harus dilakukan. • Setiap I/O operation: faktor waktu latency sampai data dapat ditransfer.

n

Mengapa tidak membuat blok menjadi sangat besar? • Internal fragmentation (ingat: umumnya ukuran file kecil): waste of space.

Notes: Windows mengenal istilah “cluster” untuk blok. File System JM -2000/v1.1/24

12

Free-Space Management Bit vector (n blocks)

n

0

1

2

n-1

bit[ i] =

n

678

…

0 1

⇒ ⇒

block[ i] free block[ i] occupied

Free list: model pembagian daftar blok yang bebas dalam linked list. n Pointer (next) disimpan pada blok yang bebas. n Umumnya tidak satu linked list tunggal, tapi di pilah dalam sekumpulan linked list. File System JM -2000/v1.1/25

Free-Space Management (Cont.) n

Bit map requires extra space. Example: block size = 2^12 bytes (4 K) disk size = 2^30 bytes (1 gigabyte) n = 2^30/2^12 = 2^18 bits (or 32K bytes)

n

Need to protect: n n

Pointer to free list Bit map • Must be kept on disk • Copy in memory and disk may differ.

n

Solution (konsistensi check) • Set bit[i] = 1 in disk. • Allocate block[i] • Set bit[i] = 1 in memory File System JM -2000/v1.1/26

13

File-System Implementation

Recommend Documents