Tugas Sistem Berkas Hanik Rosyidah PDF

Preview

Summary

BAB I PENDAHULUAN 1.1. LATAR BELAKANG Komputer dapat menyimpan informasi dalam berbagai bentuk fisik tempat penyimpanan seperti pita magnetik, disk magnetic, disk optical.Sistem operasi memberikan pandangan logis yang sejenis dari tempat penyimpanan informasi. Bentuk penyimpanan abstraksi dari unit ...

Description

BAB I PENDAHULUAN 1.1. LATAR BELAKANG Komputer dapat menyimpan informasi dalam berbagai bentuk fisik tempat penyimpanan seperti pita magnetik, disk magnetic, disk optical.Sistem operasi memberikan pandangan logis yang sejenis dari tempat penyimpanan informasi. Bentuk penyimpanan abstraksi dari unit penyimpan informasi dalam bentuk fisik adalah file. File–file dipetakan oleh sistem operasi ke dalam peralatan fisik. Sistem berkas merupakan mekanisme penyimpanan on-line serta untuk akses, baikdata maupun program yang berada dalam system operasi. Salah satu kegiatan dalam materi system berkas adalah bagaimana mengorganisir sebuah record yang ada dalam berkas. Organisasi berkas indeks sequential adalah Berkas/file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung) atau kombinasi keduanya, direct dan sequential . Organisasi berkas ini mempunyai semua keunggulan dari sequential file. Tetapi kemampuan aksesnya jauh lebih baik. 1.2. RUMUSAN MASALAH Adapun rurmusan masalah dalam penyusunan paper ini adalah: 1. Apakah yang dimaksud dengan organsasi berkas sequential? 2. Apakah yang dimaksud dengan organisasi berkas relatif? 3. Apakah yang dimaksud dengan organisasi berkas indeks sequential? 1.3.TUJUAN 1. Mengetahui apa yang dimaksud dengan organisasi berkas sequential dan penerapannya. 2. Mengetahui apa yang dimaksud dengan organisasi berkas relatif dan penerapannya. 3. Mengetahui apa yang dimaksud dengan organisasi berkas indeks sequential dan penerapannya.

1

BAB II PEMBAHASAN A. ORGANISASI BERKAS SEQUENTIAL Organisasi berkas sequential adalah merupakan cara yang paling dasar untuk mengorganisasikan kumpulan record-record dalam sebuah berkas. Dalam organisasi berkas sequential, pada waktu record ini dibuat, record-record direkam secara berurutan. Record pertama ditempatkan pada posisi pertama dalam berkas, record kedua ditempatkan pada posisi kedua dalam berkas dan seterusnya. Begitu pula pada waktu pengaksesan dan pada waktu berkas ini digunakan sebagai input, record-record harus diakses secara berurutan.

Gambar struktur sequential file.

Jadi dalam organisasi berkas sequential, bukan berarti bahwa recordrecord tersebut disimpan dalam urutan numerik. Jika kita ingin menambahkan suatu record pada berkas sequential, maka record tersebut akan terletak pada akhir berkas. Organisasi berkas sequential dapat terdiri dari record-record yang berbeda jenis. 1. PROSES Karena record-record dalam organisasi berkas sequential harus diakses secara berurutan, maka berkas sekuensial lebih sering menggunakan batch processing dari pada interactive processing.

2

2.

KEUNTUNGAN DAN KETERBATASAN Adapun keuntungan utama dari teknik organisasi berkas sequential adalah kemampuan untuk mengakses record berikutnya secara tepat. Sedangkan keterbatasan dari organisasi berkas sequential adalah kita tidak dapat mengakses langsung pada record yang diinginkan.

3.

POLA AKSES

Pola Akses adalah penentuan akses berdasarkan field tertentu. Selama pola akses, berkas sequential dapat dipasangkan dengan record-record yang sudah diurut pada berkas, maka waktu aksesnya sangat baik. Jadi kita harus menentukan pola akses terlebih dahulu, kemudian baru menentukan organisasi berkas sequential berdasarkan urutan yang sesuai dengan pola aksesnya, jangan sebaliknya. 4.

MEDIA PENYIMPANAN BERKAS SEQUETIAL Berkas sequential dapat disimpan dalam SASD, seperti magnetic tape atau pada DASD, seperti magnetic disk. Beberapa alasan untuk menyimpan berkas sequential pada DASD : a. Pada umumnya komputer dihubungkan dengan sedikit tape drive, sehingga tidak cukup untuk menunjang program aplikasi yang banyak membutuhkan berkas sekuensial. Contoh : Jika 3 berkas sequential, seperti master file, transaction file dan update master akan oleh sebuah program. Karena hanya ada 2 tape drive, maka salah satu dari ketiga berkas tersebut disimpan dalam disk. b. Sistem yang dikonfigurasikan untuk fungsi berkas tertentu, selalu disimpan dalam disk. Contoh : Printer hanya dapat menerima semua berkas yang akan dicetak, bila terlebih dahulu berkas tersebut disimpan dalam disk. Jadi bila kita ingin membuat sebuah berkas laporan, maka harus ditentukan dari disk ke printer. c. Karakteristik lalu lintas saluran dan kapasitas saluran pada sistem dapat dibuat menguntungkan dengan cara memisahkan berkas-berkas dalam media penyimpanan. Contoh : Sebuah sistem akan dikonfigurasikan dengan 2 tape drive pada satu saluran dan 2 disk drive pada saluran lain. Jika volume data besar, yang dihasilkan oleh sebuah program dari 2 berkas sekuensial, maka akan menguntungkan bila berkas-berkas tersebut diletakkan pada saluran terpisah, daripada diletakan pada perlatan yang salurannya digunakan bersama-sama.

3

5.

PEMBUATAN BERKAS SEQUENTIAL

Pembuatan berkas sequential meliputi penulisan record-record dalam serangkaian yang diinginkan pada media penyimpanan. Pembuatan berkas transaksi sequential meliputi tugas-tugas: Pengumpulan data Perubahan data dalam bentuk bahasa yang dapat dibaca oleh mesin Pengeditan data Pemeriksaan transaksi yang ditolak Penyortiran edit data 6. PEMBUATAN BERKAS LAPORAN Dalam pembuatan berkas laporan sequential dikenal 3 jenis record : 1) Header Record; Mencakup report header, page header dan group header. Dikenal sebagai informasi pengenal (Identifying Information). 2) Detail Record; Mencakup isi laporan yang umumnya disusun dalam kolom. 3) Footer Record; Mencakup report footer, page footer dan group footer. Dikenal sebagai informasi ringkasan (Summary Information). 7.

RETRIEVAL TERHADAP BERKAS SEQUENTIAL

Record pada berkas sequential di retrieve secara berurutan. Urutan dimana record tersebut ditulis pada berkas menentukan urutan dimana record tersebut di dapat kembali. Retrieve dari sebuah berkas dapat dibagi 2, yaitu : Report Generation dan Inquiry, yang bergantung pada jumlah data yang dihasilkan. Pada umumnya berkas sequential diakses dalam model report generation. Karena record-record harus diakses secara berurutan, tentunya lebih efisien mengakses setiap record dari berkas tersebut. Inquiry dari berkas sequential mengalami hambatan, karena organisasi berkas ini memerlukan pengaksesan record secara satu persatu. Namun ada inquiry yang memerlukan pengaksesan semua record dari berkas. Contoh : Berapa jumlah mahasiswa yang berumur di atas 20 tahun ? Berapa jumlah pegawai yang mempunyai gaji di bawah Rp. 1.000.000; ? 8.

HIT RATIO

1. Banyaknya record yang harus diakses untuk mendapatkan informasi yang diinginkan dibagi dengan banyaknya record dalam berkas tersebut .

4

2. Semakin rendah hit ratio, semakin tidak baik bila menggunakan organisasi sequential. 3. Semakin tinggi hit ratio, semakin baik bila menggunakan organisasi sequential. 9. FILE ACTIVITY RATIO Banyaknya record pada master file yang di-update dibagi dengan banyaknya record pada master file. File Activity Ratio = (1 + 1) / 4 = 0.5 a. Semakin tinggi file activity ratio, semakin lama proses peng-update-an master file. b. Semakin tinggi kebutuhan akan data yang baru pada master file, maka semakin sering file tersebut diakses. c. Semakin sering master file di-update, semakin tinggi biaya pemrosesannya. 10. GENERATION FILE Selama next cycle pada proses update, new master file yang sekarang akan menjadi old master file. Menjadi banyaknya master file inilah yang disebut sebagai Generation File. File yang mempunyai nama yang sama, tetapi berbeda nomor generasinya. Jika old master sekarang merupakan generasi 1, maka new master berikutnya merupakan generasi 2, new master pada next cycle menjadi generasi 3, dan seterusnya. 11. JENIS UPDATE Ada 3 jenis update yang akan dapat dilaksanakan pada master file : 1) Insert a new record 2) Delete an existing record 3) Modify an existing record Menangani Kesalahan Dalam pelaksanaan update, dapat ditemukan beberapa kesalahan seperti : (a) Insert a record that already exists (b) Delete a record that does not exist (c) Modify a record that does not exist B. ORGANISASI BERKAS RELATIF 1. PENGERTIAN ORGANISASI BERKAS RELATIF Suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat adalah organisasi berkas relatif. Dalam berkas relatif ada hubungan antara key yang dipakai untuk mengidentifikasi record dengan lokasi record dalam penyimpanan sekunder. Urutan record secara logik tidak ada hubungannya dengan urutan secara fisik. Record tidak perlu tersortir secara fisik menurut nilai key. 5

Gambar 1 : organisasi file relative

Bagaimana record yang ke-N dapat ditemukan ?? . Dalam hal ini, perlu kita buat hubungan yang akan menerjemahkan antara NILAI KEY dan ADDRESS. Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan. R(NILAI KEY) ADDRESS Dari nilai key ke address dalam penyimpanan sekunder. 2. PROSES Pada waktu sebuah record ditulis ke dalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY dari record menjadadi ADDRESS, dimana record tersebut disimpan.

6

Begitu pula pada waktu akan me-retrieve record dengan nilai key tertentu, fungsi pemetaan R digunakan terhadap nilai key tersebut, untuk menerjemahkan nilai key itu menjadi sebuah address dalam penyimpanan sekunder, dimana record tersebut ditemukan. Organisasi berkas relatif ini tidak menguntungkan bila penyimpanan sekundernya berupa media SASD seperti magnetic tape. Berkas relatif harus disimpan dalam media DASD seperti magnetic disk atau drum. Juga dimungkinkan untuk mengakses record-record dalam berkas relatif secara consecutive, tetapi perlu diketahui bahwa nilai key tidak terurut secara logik.

Contoh Record dalam gambar 1, diretrieve secara consecutive; COW, ZEBRA, … , APE, EEL, DOG, … , CAT, BAT Karena kemampuan mengakses record tertentu secara cepat, maka organisasi berkas relatif paling sering digunakan dalam proses interactive. Contoh Sebuah on-line sistem perbankan yang mempunyai sebuah master file dan sebuah transaksi file. Field account number dipakai sebagai nilai key untuk kedua berkas tersebut. Pada saat nilai key account number dimasukan kedalam transaksi, nilai key tersebut akan meretrieve secara langsung record yang ada pada master file. Jika trans-type = ‘I’, maka balance account akan ditampilkan dilayar.

Jika trans-type = ‘C’ atau ‘D’, maka record-record dari master file customer account akan dimodifikasi dengan amount dan date yang ada ditransaction file, dimana account number yang menentukan lokasi record dalam berkas tersebut. Catatan : Kita tidak perlu mengakses semua record master file, cukup mengakses langsung record yang dikehendaki. Record dari berkas relatif dapat diupdate langsung tanpa perlu merekam kembali semua record. Keuntungan dari berkas relatif ini adalah kemampuan mengakses record secara langsung, sebuah record dapat diretrieve, insert, modifikasi atau didelete, tanpa mempengaruhi record lain dalam berkas yang sama. 3. TEKNIK PEMETAAN LANGSUNG

7

Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address. Ada 2 cara dalam pemetaan langsung : 1. Absolute Addressing (Pengalamatan Mutlak) 2. Relative Addressing (Pengalamatan Relatif)

Pengalamatan Mutlak R(nilai key)

Address

Nilai key = alamat mutlak Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder. Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai cylinder addressing atau (nomor sektor, nomor record) bila dipakai sector addressing harus ditentukan oleh pamakai. Keuntungan dari pengalamatan mutlak • Fungsi pemetaan R sangat sederhana • Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder Kelemahannya : • Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik • Alamat mutlak adalah device dependent, perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key • Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan menyebabkan nilai key berubah. Pengalamatan Relatif R(nilai key)

Address

Nilai key = alamat relatif Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas. Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1). Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0). Keuntungan dari pengalamatan relatif • Fungsi pemetaan R sangat sederhana • Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti. 8

Kelemahannya • Alamat relatif adalah bukan device dependent • Alamat relatif adalah address space dependent • Terjadinya pemborosan ruangan. Teknik Pencarian Tabel. Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address. Untuk menemukan sebuah record dalam berkas relatif, pertama dicari dalam direktori nilai key dari record tersebut, yang akan menunjukan alamat dimana record tersebut berada dalam penyimpanan. Gambar struktur tabel file relatif Directory Key

Address

APE

I–1

BAT

N

CAT

N–1 .

File Relatif

Alamat Relatif

COW

1

ZEBRA

2

. APE

I–1

COW

1

EEL

I

DOG

I+1

DOG

I+1

EEL

I .

ZEBRA

2

. CAT

N–1

BAT

N

9

4. DIRECTORY APE, I - 1

BAT, N CAT, N - 1 COW, 1 DOG, I + 1 EEL, I ZEBRA, 2

Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequential search. Alternatif lain, direktori dapat disusun dalam binary search tree, m-way search tree atau B-tree. Keuntungan dari Pencarian Tabel : • •

•

Sebuah record dapat diakses dengan cepat, setelah nilai key dalam direktori ditentukan. Nilai key dapat berupa field yang mudah dimengerti seperti PART NUMBER, NPM, karena nilai key tersebut akan diterjemahkan menjadi alamat. Nilai key adalah address space independent, dimana reorganisasi berkas tak akan memepengaruhi nilai key, yang berubah adalah alamat dalam direktori.

Teknik Kalkulasi Alamat

R (NILAI KEY)

ADDRESS

Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relatif. Salah satu kelemahan dari teknik pengalamatan relatif adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key.

10

Salah satu masalah dari teknik ini adalah ditemukannya alamat relatif yang sama untuk nilai key yang berbeda. Keadaan dimana :

R(K1) = R(K2) K1 ≠ K2

disebut benturan atau collision

Sedangkan nilai key K1 dan K2 disebut synomin. Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama. Teknik-teknik yang terdapat pada kalkulasi alamat : • Scatter storage techniques • Randomizing techniques • Key-to-address transformation methods • Direct addressing techniques • Hash table methods • Hashing Disini akan dibahas mengenai teknik hashing. Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash. Keuntungan pemakaian Hashing: • •

Nilai key yang sebenarnya dapat dipakai karena diterjemahkan kedalam sebuah alamat. Nilai key adalah address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.

Kelemahannya : • Membutuhkan waktu proses dalam mengimplementasikan fungsi hash. • Membutuhkan waktu proses dan akses I/O dalam mengatasi benturan. Hashing dapat digunakan bersama-sama dengan pencarian tabel. Penampilan fungsi hash bergantung pada: • • •

Distribusi nilai key yang dipakai Banyaknya nilai key yang dipakai relatif terhadap ukuran dari ruang alamat. Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan. 11

•

Teknik yang dipakai untuk mengatasi benturan

Beberapa fungsi hash yang umum digunakan: •

Division Remainder Pada division remainder, alamat relatif dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut sebagai bilangan pembagi.

•

Mid Square Untuk mendapatkan alamat relatif, nilai key dikuadratkan, kemudian beberapa digit diambil dari tengah .

•

Folding Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

Perbandingan fungsi Hash * Teknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan. * Teknik Mid Square dapat dipakai untuk file dengan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat menghasilkan penampilan yang buruk dengan beberapa collision. * Teknik folding adalah teknik yang paling mudah dalam perhitungan tetapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address. 5. PENDEKATAN TERHADAP MASALAH COLLISION Ada 2 pendekatan dasar untuk menetapkan dimana K2 harus disimpan, yaitu : *

*

Open Addressing Menemukan address yang bukan home address untuk K2 relatif.

dalam berkas

Separate Overflow Menemukan address untuk K2 diluar dari primary area dalam berkas relatif, yaitu di overflow area yang dipakai hanya untuk menyimpan record-record yang tak dapat disimpan di home addressnya.

Ada 2 teknik untuk mengatasi collision : *

Linier Probing, yang merupakan teknik open addresing. Salah satu cara menemukan lokasi record yang tak dapat disimpan di home addressnya adalah dengan menggunakan Linear Probing, yang merupakan 12

sebuah proses pencarian secara sequential/linear dari home address sampai lokasi yang kosong. *

Double Hashing, yang dapat dipakai selain open addressing atau separate overflow. Pendekatan lain dalam menemukan lokasi sebuah record pada waktu record tersebut tidak dapat disimpan dalam home addressnya adalah dengan menggunakan Double Hashing, yang akan memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama. Address dari record yang dihash kembali dapat terletak pada primary area atau di separate overflow area. Keuntungan dari metode separate overflow adalah menghindari keadaan dimana dapat terjadi metode open addressing untuk sebuah record yang tak disimpan dalam home addressnya menggantikan record lain yang terakhir di hash ke home addressnya. Masalah ini dapat dihindari dengan open addressing sederhana dengan memindahkan record yang sebelumnya ke lokasi lain (dengan probing atau hashing kembali) dan menyimpan record yang baru ketempat yang kosong. Metode ini membutuhkan pengeluaran tambahan untuk pemeliharaan berkas.

Berkas relatif dibagi menjadi 2 berkas , yaitu :

Primary area dan Overflow area

Synonim Chaining Pendekatan pemecahan collision yang mengakses synonim dengan fasilitas link list untuk record-recordnya dalam kelas ekivalen. Adapun link list record-record dengan home address yang sama tak akan mengurangi jumlah collision, tetapi akan mengurangi waktu akses untuk me-retrieve record-record yang tak ada di home addressnya. C. ORGANISASI BERKAS INDEX SEQUENTIAL 1. P...