sesi 3 - metode blocking

Metode BlockingMetode Blocking

PS ILMU KOMPUTERPS ILMU KOMPUTER

Universitas DiponegoroUniversitas Diponegoro

Sesi – 3Sesi – 3

SISTEM BERKASSISTEM BERKAS Metode BlockingMetode Blocking 22

Manajemen FileManajemen File

• Untuk memetakan struktur logik (record / byte) Untuk memetakan struktur logik (record / byte) menjadi struktur fisik (block).menjadi struktur fisik (block).

• Untuk mengalokasikan block kosong untuk file.Untuk mengalokasikan block kosong untuk file.• Untuk mengatur block yang kosong dari Untuk mengatur block yang kosong dari

penyimpanan sekunder.penyimpanan sekunder.


Elemen Manajemen FileElemen Manajemen File

User & ProgramCommands

DirectoryManagement

Operation,File Name

User AccessControl

FileStructure Access

Method

File Manipulation

Functions

Records

Blocking

DiskScheduling

I / O

FileAllocation

Free StorageManagement

Physical BlocksIn Main Memory

Buffers

Physical BlocksIn SecondaryStorage (disk)

File Management Concerns

Operating System Concerns


Arsitektur Sistem FileArsitektur Sistem File

PilePile SequentialSequential IndexedIndexedSequentialSequential IndexedIndexed HashedHashed

Logical I / OLogical I / O

Basic I / O SupervisorBasic I / O Supervisor

Basic File SystemBasic File System

Disk Device DriverDisk Device Driver Tape Device DriverTape Device Driver

UserUserProgramProgram


Organisasi Fisik FileOrganisasi Fisik File

• Merupakan organisasi data file pada tempat Merupakan organisasi data file pada tempat penyimpanan sekunderpenyimpanan sekunder


BlockingBlocking

• Block adalah unit data yang ditransfer antara device Block adalah unit data yang ditransfer antara device sekunder dengan device primer.sekunder dengan device primer.

• Block Size (ukuran blok) dinyatakan dalam byte, Block Size (ukuran blok) dinyatakan dalam byte, notasi B.notasi B.

• Block Size yang terlalu besar akan mengakibatkan Block Size yang terlalu besar akan mengakibatkan data yang tidak diperlukan ikut berpindah data yang tidak diperlukan ikut berpindah (memerlukan memori besar).(memerlukan memori besar).

• Block Size kecil menyebabkan pembacaan berulang-Block Size kecil menyebabkan pembacaan berulang-ulang.ulang.


BlockingBlocking

• Record-record disimpan dalam block. Metode yang Record-record disimpan dalam block. Metode yang digunakan dalam menempatkan record-record pada digunakan dalam menempatkan record-record pada block adalah Blocking.block adalah Blocking.

• Bfr (Blocking Factor) adalah nilai yang menentukan Bfr (Blocking Factor) adalah nilai yang menentukan berapa banyak record yang dapat ditempatkan berapa banyak record yang dapat ditempatkan dalam satu block.dalam satu block.


Blocking RecordBlocking Record

• Unit logik dari file adalah byte atau record, dan unit Unit logik dari file adalah byte atau record, dan unit fisik file adalah block.fisik file adalah block.

• Tipe Block :Tipe Block :– Fixed Blocking (Fixed-Length Record)Fixed Blocking (Fixed-Length Record)– Variable-Length Spanned BlockingVariable-Length Spanned Blocking– Variable-Length Unspanned BlockingVariable-Length Unspanned Blocking


Fixed BlockingFixed Blocking

R1 R2 R3 R4

R5 R6 R7 R8

Data

Gaps due to hardware design

Waste due to record fit to block size

Waste due to block size constraint from fixed record size

Waste due to block fit to track size



• Jumlah record yang ditempatkan dalam satu block Jumlah record yang ditempatkan dalam satu block sama dengan jumlah record pada block lain, dimana sama dengan jumlah record pada block lain, dimana satu block berisi record yang berukuran sama (fixed satu block berisi record yang berukuran sama (fixed length record).length record).

• Record length <= Block sizeRecord length <= Block size• Blocking factor (Bfr) = Blocking factor (Bfr) =

R

B



• Jika Block Size B = 100 byte, R = 30 byte, maka Jika Block Size B = 100 byte, R = 30 byte, maka dengan fixed blocking akan ada 3 buah record per dengan fixed blocking akan ada 3 buah record per block.block.

• Pada fixed blocking mungkin ada block space yang Pada fixed blocking mungkin ada block space yang terbuang.terbuang.


Variable-LengthVariable-LengthSpanned BlockingSpanned Blocking

R1 R2 R3 R4

R7

Data




R4 R5 R6

R6 R8 R9 R9 R10 R11 R12 R13


Variable-LengthVariable-LengthSpanned BlockingSpanned Blocking• Ukuran record tidak sama (variable)Ukuran record tidak sama (variable)• Record dapat dipecah bila menemukan gap antar Record dapat dipecah bila menemukan gap antar

blok.blok.• Panjang record dapat lebih besar dari block size.Panjang record dapat lebih besar dari block size.• Tidak ada ruang yang terbuang karena blocking, tapi Tidak ada ruang yang terbuang karena blocking, tapi

sulit untuk diimplementasikan.sulit untuk diimplementasikan.• Record yang berada pada 2 block memerlukan waktu Record yang berada pada 2 block memerlukan waktu

yang lebih lama dalam pembacaannya.yang lebih lama dalam pembacaannya.


Variable-LengthVariable-LengthUnspanned BlockingUnspanned Blocking

R1 R2 R3 R4

R7

Data




R5

R6 R9 R10R8


Variable-LengthVariable-LengthUnspanned BlockingUnspanned Blocking• Ukuran record bervariasiUkuran record bervariasi• Hanya record yang utuh yang dapat menempati Hanya record yang utuh yang dapat menempati

block.block.• Ada kemungkinan terjadi ruang kosong akibat Ada kemungkinan terjadi ruang kosong akibat

blocking.blocking.• Record length <= block sizeRecord length <= block size


Blocking FactorBlocking FactorVariable SpannedVariable Spanned• Sebuah block pointer (P) harus disertakan pada tiap Sebuah block pointer (P) harus disertakan pada tiap

block.block.• Ukuran efektif block = B – PUkuran efektif block = B – P• Ukuran record + marker = R + MUkuran record + marker = R + M• Bfr = (B – P) / (R + M)Bfr = (B – P) / (R + M)• Jika diasumsikan M = P, didapatJika diasumsikan M = P, didapat

Bfr = (B – P) / (R + P)Bfr = (B – P) / (R + P)


Blocking FactorBlocking FactorVariable UnspannedVariable Unspanned• Rata-rata ruang block terbuang = ½ RRata-rata ruang block terbuang = ½ R• Tidak ada block pointerTidak ada block pointer• Ukuran block efektif = B – ½ RUkuran block efektif = B – ½ R• Bfr = (B – ½ R) / (R + M)Bfr = (B – ½ R) / (R + M)


Pemborosan Ruang (waste/W)Pemborosan Ruang (waste/W)

• Ruang yang terbuang tidak dapat digunakan untuk Ruang yang terbuang tidak dapat digunakan untuk menyimpan data.menyimpan data.

• W dipengaruhi oleh :W dipengaruhi oleh :– WWgg : Waste yang muncul karena gap antar block : Waste yang muncul karena gap antar block

– WWrr : Waste yang muncul karena blocking : Waste yang muncul karena blocking

• W = WW = Wgg + W + Wr r , nilai W dihitung per record, nilai W dihitung per record


W pada Fixed BlockingW pada Fixed Blocking

• Pada fixed blocking, ruang terbuang akibat blocking Pada fixed blocking, ruang terbuang akibat blocking adalah < Radalah < R

• Dihitung per record : 0 Dihitung per record : 0 ≤ W≤ Wrr < R / Bfr < R / Bfr

• Fixed blocking umumnya digunakan jika ukuran Fixed blocking umumnya digunakan jika ukuran record jauh lebih kecil dibandingkan kapasitas block record jauh lebih kecil dibandingkan kapasitas block (W(Wgg jauh lebih besar dibandingkan W jauh lebih besar dibandingkan Wrr).).

• W = WW = Wgg + W + Wrr W = W W = Wg g = G / Bfr= G / Bfr


W pada Variable SpannedW pada Variable Spanned

• Tidak ada ruang terbuang karena blockingTidak ada ruang terbuang karena blocking• Muncul penanda record (M) dan pointer block (P)Muncul penanda record (M) dan pointer block (P)

• WWrr = M + P / Bfr = M + P / Bfr

• W = WW = Wgg + W + Wrr G / Bfr + M + (P / Bfr) G / Bfr + M + (P / Bfr)

W = M + (P + G) / BfrW = M + (P + G) / Bfr• Jika M = P, maka W = P + (P + G) / BfrJika M = P, maka W = P + (P + G) / Bfr


W pada Variable UnspannedW pada Variable Unspanned

• Ada ruang terbuangAda ruang terbuang• Ada penanda recordAda penanda record

• WWrr = M + ((½ R) / Bfr) = M + ((½ R) / Bfr)

• W = WW = Wgg + W + Wrr G / Bfr + M + ((½ R) / Bfr G / Bfr + M + ((½ R) / Bfr

W = M + (½ R + G) / BfrW = M + (½ R + G) / Bfr• Jika M = P, maka W = P + (½ R + G) / BfrJika M = P, maka W = P + (½ R + G) / Bfr


Transfer RateTransfer Rate

• Transfer Rate (t) adalah kecepatan data yang dapat Transfer Rate (t) adalah kecepatan data yang dapat ditransfer / kecepatan transfer data sesaat.ditransfer / kecepatan transfer data sesaat.

• Satuan byte / s, besarnya t diinformasikan oleh Satuan byte / s, besarnya t diinformasikan oleh pembuat perangkat.pembuat perangkat.

• Terdapat 2 pengukuran yang tergantung pada Terdapat 2 pengukuran yang tergantung pada transfer rate :transfer rate :– Record Transfer Time (TRecord Transfer Time (TRR))

– Block Transfer Time (Btt)Block Transfer Time (Btt)


Transfer RateTransfer Rate

• TTRR adalah waktu transfer record dengan panjang R, adalah waktu transfer record dengan panjang R,

dimana Tdimana TRR = R / t = R / t

• Btt adalah waktu transfer block dengan besar B, Btt adalah waktu transfer block dengan besar B, dimana Btt = B / tdimana Btt = B / t

• Satuan TSatuan TRR dan Btt adalah milisecond dan Btt adalah milisecond


Bulk Transfer DataBulk Transfer Data

• Untuk pembacaan data dalam jumlah besar, Untuk pembacaan data dalam jumlah besar, diperhitungkan nilai bulk transfer rate (t’).diperhitungkan nilai bulk transfer rate (t’).

• Bulk transfer rate dihitung dengan Bulk transfer rate dihitung dengan mempertimbangkan besar dan banyaknya gap area mempertimbangkan besar dan banyaknya gap area non data yang harus dilalui.non data yang harus dilalui.

• t’ = (t / 2) (R / (R + W))t’ = (t / 2) (R / (R + W))


Contoh KasusContoh Kasus

• Diketahui sebuah harddisk memiliki karakteristik :Diketahui sebuah harddisk memiliki karakteristik :– Seek time (s) = 10 msSeek time (s) = 10 ms– Kecepatan putar disk 6000 rpmKecepatan putar disk 6000 rpm– Transfer rate (t) = 2048 byte / sTransfer rate (t) = 2048 byte / s– Kapasitas block (B) = 2048 byteKapasitas block (B) = 2048 byte– Ukuran record (R) = 250 byteUkuran record (R) = 250 byte– Ukuran gap (G) = 256 byteUkuran gap (G) = 256 byte– Ukuran M = P = 8 byteUkuran M = P = 8 byte



• Ditanya :Ditanya :– Blocking FactorBlocking Factor– Record Transfer TimeRecord Transfer Time– Block Transfer TimeBlock Transfer Time– Pemborosan Ruang (Waste)Pemborosan Ruang (Waste)– Bulk Transfer RateBulk Transfer Rate

• Jika metode blockingnya :Jika metode blockingnya :– Fixed blockingFixed blocking– Variable spannedVariable spanned– Variable unspannedVariable unspanned



• Pembahasan dengan Fixed Blocking :Pembahasan dengan Fixed Blocking :– Bfr = B / R = 2048 / 250 = 8 recordBfr = B / R = 2048 / 250 = 8 record

– Record Transfer Time (TRecord Transfer Time (TRR) = R / t = 250 / 2048 = 0,122 s) = R / t = 250 / 2048 = 0,122 s

– Block Transfer Time (Btt) = B / t = 2048 / 2048 = 1 sBlock Transfer Time (Btt) = B / t = 2048 / 2048 = 1 s

– W = WW = WGG = G / Bfr = 256 / 8 = 32 byte = G / Bfr = 256 / 8 = 32 byte

– Bulk Transfer Rate :Bulk Transfer Rate :

t’ = (t / 2) (R / (R + W))t’ = (t / 2) (R / (R + W))

= (2048 / 2) (250 / (250 + 32))= (2048 / 2) (250 / (250 + 32))

= 1024 (250 / 282)= 1024 (250 / 282)

= 1024 (0,886)= 1024 (0,886)

= 907,8 s= 907,8 s



• Pembahasan dengan Spanned Blocking :Pembahasan dengan Spanned Blocking :– Bfr = (B – P) / (R + M) = (2048 – 8) / (250 + 8) = 7 recordBfr = (B – P) / (R + M) = (2048 – 8) / (250 + 8) = 7 record


– Block Transfer Time (Btt) = B / t = 2048 / 2048 = 1 sBlock Transfer Time (Btt) = B / t = 2048 / 2048 = 1 s– W = M + (P + G) / Bfr = 8 + (8 + 256) / 7 = 45 byteW = M + (P + G) / Bfr = 8 + (8 + 256) / 7 = 45 byte


t’ = (t / 2) (R / (R + W))t’ = (t / 2) (R / (R + W))

= (2048 / 2) (250 / (250 + = (2048 / 2) (250 / (250 + 4545))))

= 1024 (250 / 2= 1024 (250 / 29595))

= 1024 (0,886)= 1024 (0,886)

= 907,8 byte/s= 907,8 byte/s



• Pembahasan dengan Unspanned Blocking :Pembahasan dengan Unspanned Blocking :– Bfr = (B – ½ R) / (R + M) = (2048 – ½ (250)) / (250 + 8) = 7 recBfr = (B – ½ R) / (R + M) = (2048 – ½ (250)) / (250 + 8) = 7 rec


– Block Transfer Time (Btt) = B / t = 2048 / 2048 = 1 sBlock Transfer Time (Btt) = B / t = 2048 / 2048 = 1 s– W = M + (½ R + G) / Bfr = 8 + (½ (250) + 256) / 7 = 62 byteW = M + (½ R + G) / Bfr = 8 + (½ (250) + 256) / 7 = 62 byte


t’ = (t / 2) (R / (R + W))t’ = (t / 2) (R / (R + W))

= (2048 / 2) (250 / (250 + 32))= (2048 / 2) (250 / (250 + 32))

= 1024 (250 / 282)= 1024 (250 / 282)

= 1024 (0,886)= 1024 (0,886)

= 907,8 s= 907,8 s


Manajemen Tempat Manajemen Tempat Penyimpanan SekunderPenyimpanan Sekunder• Space / tempat kosong harus dialokasikan untuk file Space / tempat kosong harus dialokasikan untuk file

yang akan disimpan.yang akan disimpan.• Harus menyimpan track dari space yang masih ada Harus menyimpan track dari space yang masih ada

untuk alokasi data.untuk alokasi data.


Porsi UkuranPorsi Ukuran

• Variable-size atau fixed-sizeVariable-size atau fixed-size

variabel : kompleksitas tapi efisiensivariabel : kompleksitas tapi efisiensi• Large-size atau small sizeLarge-size atau small size

besar : efisiensi untuk transferbesar : efisiensi untuk transfer


Pre – AlokasiPre – Alokasi

• Membutuhkan ukuran maksimum untuk file pada Membutuhkan ukuran maksimum untuk file pada saat pembuatan file.saat pembuatan file.

• Sulit untuk memperkirakan ukuran potensial Sulit untuk memperkirakan ukuran potensial maksimum file.maksimum file.

• Berusaha untuk memperkirakan ukuran file sehingga Berusaha untuk memperkirakan ukuran file sehingga tidak melebihi kapasitas.tidak melebihi kapasitas.


Metode Alokasi FileMetode Alokasi File

• Alokasi KontinuAlokasi Kontinu– Sebuah kumpulan block dialokasikan untuk sebuah file Sebuah kumpulan block dialokasikan untuk sebuah file

pada saat pembuatan file.pada saat pembuatan file.– Hanya sebuah single entry pada tabel alokasi file (Starting Hanya sebuah single entry pada tabel alokasi file (Starting

block dan panjang block).block dan panjang block).

• Fragmentasi external akan munculFragmentasi external akan muncul



• Contiguous File AllocationContiguous File Allocation

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File A

File B

File C

File D

File E

File Allocation TableFile Allocation Table

File NameFile Name Start BlockStart Block LengthLength

File AFile A 22 33

File BFile B 99 55

File CFile C 1818 88

File DFile D 3030 22

File EFile E 2626 33



• Contiguous File Allocation (after Compaction)Contiguous File Allocation (after Compaction)



File AFile A 00 33

File BFile B 33 55

File CFile C 88 88

File DFile D 1919 22

File EFile E 1616 33

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File A

File B

File C

File DFile E



• Alokasi ChainedAlokasi Chained– Alokasi berbasis block individual.Alokasi berbasis block individual.– Tiap block mengandung sebuah pointer ke block berikutnya Tiap block mengandung sebuah pointer ke block berikutnya

pada chain.pada chain.– Hanya single entry pada tabel alokasi file (Starting block Hanya single entry pada tabel alokasi file (Starting block

dan panjang file).dan panjang file).

• Tidak ada fregmentasi externalTidak ada fregmentasi external• Baik untuk file sequentialBaik untuk file sequential



• Chained AllocationChained Allocation



…… …… ……

File BFile B 11 55

…… …… ……

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File B



• Chained Allocation (after Consolidation)Chained Allocation (after Consolidation)



…… …… ……

File BFile B 00 55

…… …… ……

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File B



• Alokasi BerindeksAlokasi Berindeks– Tabel alokasi file mengandung sebuah 1 indeks 1 level pada Tabel alokasi file mengandung sebuah 1 indeks 1 level pada

tiap file.tiap file.– Indeks mempunyai 1 entry untuk tiap porsi alokasi ke file.Indeks mempunyai 1 entry untuk tiap porsi alokasi ke file.– Tabel alokasi file mengandung nomor block untuk indeks.Tabel alokasi file mengandung nomor block untuk indeks.



• Indexed Allocation with Block PortionIndexed Allocation with Block Portion


File NameFile Name Index BlockIndex Block

…… ……

File BFile B 2424

…… ……

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File B

183

1428



• Indexed Allocation with Variable-Length PortionIndexed Allocation with Variable-Length Portion


File NameFile Name Index BlockIndex Block

…… ……

File BFile B 2424

…… ……

0 1 2 3 4

5 6 7 8 9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

25 26 27 28 29

30 31 32 33 34

File B

111414

442828

3311

LengthLengthStart BlockStart Block

111414

442828

3311

LengthLengthStart BlockStart Block

sesi 3 - metode blocking

Documents