Kelompok 2 - Organisasi Berkas Relatif [PDF]

Zitiervorschau

MAKALAH SISTEM BERKAS

ORGANISASI BERKAS RELATIF

KELOMPOK 2 : BAYU RIFKI NAISABURI DANANG TRI ANGGARA DEDE YULYANDRI DONI AULIA FAHMI

PROGRAM STUDI TEKNIK INFORMATIKA UNIVERSITAS PAMULANG

KATA PENGANTAR

Assalamu’alaikum warahmatullahi wabarakatuh Segala puji syukur kami panjatkan kepada Allah SWT. Atas rahmat dan karunianya, kami dapat menyelesaikan tugas penulisan makalah mata kuliah Sistem Berkas tepat waktu. Tidak lupa shalawat serta salam tercurah kepada Rasulullah SAW yang syafa’atnya kita nantikan kelak. Penulisan makalah berjudul “Organisasi Berkas Relatif” dapat diselesaikan karena bantuan banyak pihak. Kami berharap makalah tentang Organisasi Berkas Relatif ini dapat menjadi ilmu yang bermanfaat dan menjadi sumber referensi temanteman semua. Kami menyadari makalah ini masi memerlukan penyempurnaan, terutama pada bagian isi. Kami menerima segala bentuk kritik dan saran dari pembaca demi penyempurnaan makalah. Apabila terdapat banyak kesalah pada makalah ini, kami sebagai penulis memohon maaf yang sebesar-besarnya

Pamulang, 3 Oktober 2020

Tim Penyusun

ii

DAFTAR ISI

KATA PENGANTAR.................................................................................

ii

DAFTAR ISI................................................................................................ iii BAB I PENDAHULUAN 1. 2. 3. 4.

Latar Belakang................................................................................. Rumusan Masalah............................................................................ Tujuan.............................................................................................. Metode pengumpulan data...............................................................

4 4 4 4

BAB II PEMBAHASAN 1. 2. 3. 4. 5.

Pengertian Berkas Relatif................................................................. 5 Proses Berkas Relatif....................................................................... 6 Teknik Pemetaan Langsung............................................................. 8 Teknik Pencarian Tabel................................................................... 10 Teknik Kalkulasi Alamat................................................................. 12

BAB III PENUTUP 1. Kesimpulan...................................................................................... 19 DAFTAR PUSTAKA.................................................................................. 20

iii

BAB I PENDAHULUAN

1. Latar Belakang Komputer dapat menyimpan informasi dalam berbagai bentuk fisik tempat penyimpanan seperti pita magnetic, disk optical. Sistem operasi memberikan pandangan logis yang sejenis dari tempat penyimpanan informasi. Bentuk penyimpanan abstraksi dari unit penyimpanan informasi dalam bentuk fisik adalah file. File-file dipetakan oleh sistem operasi ke dalam peralatan fisik. Sistem berkas relatif merupakan mekanisme penyimpana on-line serta untuk mengakses dan mengorganisasi suatu record yang membutuhkan akses cepat.

2. Rumusan Masalah 1. Apakah pengertian organisasi berkas relatif ? 2. Apa implementasi organisasi berkas relatif ? 3. Tujuan 1. Dapat menjelaskan organisasi berkas relatif 2. Dapat memahami implementasi organisasi berkas relatif 4. Metode Pengumpulan Data Dalam menyusun makalah ini, tim penulis melakukan pengumpulan data dengan cara mencari dari sumber-sumber yang berkaitan dengan isi makalah melalui ebook dan media elektronik

4

BAB II PEMBAHASAN

1. Pengertian 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.

8

Input Record

7 5 4 2

Program

DIRECT FILE 2 1

3 2

4 3

5 4

5

5

6 6

7

8 7

8

9

Beginning of file

End of file

Key Value COW ZEBRA APE EEL DOG CAT BAT

Physical Position 1 2

I-1 I I+1

N-1 N

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

2. Proses berkas relatif Pada waktu sebuah record ditulis ke dalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY dari record menjadi ADDRESS dimana record tersebut disimpan. Begitu pula pada waktu akan me-retrieve record dengan nilai key tertentu, fungsi pemetaaan 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.

6

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. Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana R(nilai key) address

7

1. Direct mapping (pemetaan langsung) 2. Directory look up (pencarian tabel) 3. Calculation (kalkulasi)

3. Teknik Pemetaan Langsung

Teknik pemetaan langsung adalah teknik yang paling sederhana, yaitu teknik memetakan blok memori utama hanya ke sebuah saluran cache saja. Ada 2 cara dalam pemetaan langsung, yaitu: 1) Absolute Addressing (Pengalamatan Mutlak) 2) Relative Addressing (Pengalamatan Relatif)

1) Absolute Addressing (Pengalamatan Mutlak) R(nilai key) Address Nilai key = alamat mutlak Jika nilai ke yang diberikan oleh pemakai porgram 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 Sector Addressing harus ditentukan oleh pemakai. Misalkan, kita memiliki data teman-teman sekelas kita yang akan kita asukkan ke dalam memori (misal hard disk), data tersebut berjumlah 40 orang yang masingmasing terdiri atas atribut-atribut seperti: NIM, NAMA dan ALAMAT_RUMAH. Jika data tersebut kita masukkan dengan organisasi file sequential, maka jika kita mencari data NIM = ‘191011401126’ yang namanya ‘DEDE’ dan beralamat di ‘Jl. Raya Puspiptek No.26’, maka pencarian akan dilakukan mulai dari record pertama (data pertama yang dimasukkan) dan seterusnya menuju ke record terakhir sampai ketemu data yang dicari tersebut. Lain halnya jika data tersebut dimasukkan dengan organisasi file relative, maka data tersebut akan didapat secara langsung dari record yang dituju. Tentu, untuk langsung mendapatkan record yang dituju ada ‘sesuatu’ yang disebut dengan

8

kunci atribut (key field). Kunci atribut itulah yang dikelola sedemikian rupa sehingga ‘kita’ bisa tahu dimana record tersebut disimpan. Untuk teknik pengalamatan mutlak ini, kita tidak terlalu mempermasalahkan kunci atribut karena kita diminta langsung menuliskan dimana alamat record yang akan kita masukkan. Jika kita menggunakan hard disk atau magnetic drum, ada dua cara dalam menentukan alamat memorinya, yaitu dengan cara Cylinder Addressing dan Sector Addressing. Jika kita menggunakan Cylinder Addressing, maka kita harus menetapkan nomornomor dari silinder (Cylinder), permukaan (Surface), dan record, sedangkan bila kita menggunakan Sector Addressing, maka kita harus menetapkan nomor-nomro dari sektor (Sector), lintasan (Track), dan permukaan (Surface). Teknik ini mudah dalam pemetaan (pemberian) alamat memorinya. Sulitnya pada pengambilan (retrieve) data kembali, jika data yang kita masukkan banyak, kita bisa lupa dimana alamat record tertentu. Keuntungan dari pengalamatan mutlak  

Fungsi pemetaan R sangat sederhana Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder

Kelemahan dari pengalamatan mutlak   

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

2) Relative Addressing (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). Recor yang ke I mempunyai alamat relati I atau I-1 (bila dihitung dari 0).

9

Teknik ini menjadikan atribut kunci sebagai alamat memorinya, jadi data dari NIM dijadikan bertipe numeric (integer) dan dijadika alamat dari record yang bersangkutan. Cara ini memang sangat efektif untuk menemukan kembali record yang sudah disimpan, tetapi sangat boros penggunaan memorinya. Tentu alamat memori mulai dari 1 hingga alamat ke sekian juta tidak digunakan karena nilai dari NIM tidak ada yang kecil.

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

Kelemahan dari pengalamatan relatif   

Alamat relatif adalah bukan device dependent Alamat relatif adalah address space dependent Terjadinya pemborosan ruangan

4. 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 menunjukkan alamat dimana record tersebut berada dalam penyimpanan. Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding dengan sequetial search. Alternatif lain, direktori dapat disusun dalam Binary Search Tree, M-way Search Tree atau B-Tree.

:

10

Directory Key

Address

File Relatif

Alamat Relatif

APE

I-1

COW

1

BAT

N

ZEBRA

2

CAT

N-1 APE

I-1

COW

1

EEL

I

DOG

I+1

DOG

I+1

EEL

I CAT

N-1

BAT

N

ZEBRA

2

DIRECTORY

11

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 tidak akan mempengaruhi nilai key, yang berubah adalah alamat dalam direktori

5. Teknik Kalkulasi Alamat

Pada teknik pencarian tabel kita harus menyediakan ruang memori untuk menyimpan tabel indexnya, tapi dalam teknik kalkulasi tidak diperlukan lagi hal itu, yang dilakukan adalah membuat hitungan sedemikian rupa sehingga dengan memasukkan kunci atribut recordnya, alamatnya sudah dapat diketahui, masalahnya bagaimana membuat hitungan dari kunci atribut itu sehingga hasilnya dapat lebih efisien dan tidak berbenturan dengan nilainya. Teknik-teknik yang terdapat pada kalkulasi alamat: 1) 2) 3) 4) 5) 6)

Scatter Storage Technique Randomizing Technique Key-to-address Transformation Methods Direct Addressig Technique Hash Table Technique Hashing

1) Scatter Storage Technique Sebuah metode baru untuk memasukkan dan mengambil informasi yang digambarkan dalam tabel hash. Metode ini akan menjadi efisien jika lebih banyak bagian yang sering dilihat. Jumlah yang diharapkan dari kemungkinan untuk mencari entri, diperkirakan secara teoritis dan diverifikasi oleh percobaan Monte Carlo adalah kurang dari untuk metode sebanding lain jika tabel hampir penuh

12

2) Randomizing Technique Sebuah metode yang digunakan untuk pengambilan data dan informasi secara random (acak) 3) Key-to-addres Transformation Methods Teknik yang digunakan dalam teori mengkoreksi kesalahan kode, hal ini diterapkan untuk dapat menyelesaikan masalah dalam menangani file besar. Dalam pendekatan baru, file menangani masalah yang digambarkan dengan desain khusus untuk menampilkan kelayakan. Contoh: Asumsi nilai dari digit orde rendah didistribusikan dengan rata dan karenanya memungkinkan untuk memperoleh 3 digit nomor unik untuk setiap karyawan. Jika salah satu menginginkan ruang yag mungkin untuk 500 karyawan, nillai kunci bisa dibagi dengan 500, menghasilkan sisa dengan nilai antara 0 s.d 499. Alamat yang bisa terjadi: Ali

atau

322-45-6178 memberikan Address 178

Joe

123-45-6284

284

Mary

036-23-0373

373

Pete

901-23-4784

284

Disini Joe dan Pete keduanya ditandai untuk satu record dengan nomor sama =284. Record untuk Joe dan Pete akan bertubruka jika keduanya ditempatkan secara langsung dalam satu file

4) Direct Addressing Technique Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung yang berarti, bahwa data yang telah direferensikan sebenarnya dan disimpan dalam struktur lain, baik sebuah register atau lokasi memori

13

5) Hash Table Technique Merupakan struktur yang menggunakan fungsi hash untuk efisien peta pengidentifikasi tertentu atau kunci/key (misalkan nama-nama orang) untuk dihubungkan nilai (misalkan nomor telepon mereka). Fungsi dari hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot/ember) dimana nilai yang sesuai akan dicari. Dalam banyak situasi, hash table technique atau yang sering disebut teknik tabel hash ternyata lebih efisien daripada pohon pencarian atau struktur lookup. Biasanya banyak digunakan di berbagai jenis komputer perangkat lunak terutama untuk array asosiatif, pengideksan database, cache dan set. Keuntungan menggunakan teknik tabel hash: 



Keuntungan utamanya adalah kecepatannya, keuntungan ini lebih jelas ketika jumlah entri yang besar (ribuan atau lebih), tabel hash dapat sangat efisien ketika jumlah maksimum entri dapat diprediksi dari sebelumnya, sehingga ember array dapat dialokasikan sekali dengan ukuran optimal dan tidak pernah diubah ukurannya. Jika himpunan pasangan kunci-nilai adalah tetap dan dikenal lebih dulu sehingga insersi serta penghapusan tidak diijinkan, yang dapat mengurangi biaya rata-rata lookup pilihan hati-hati dari fungsi hash, ember ukura meja dan struktur data internal. Secara khusus ada kemungkinan dapat menyusun fungsi hash yang tabrakan atau bahkan sempurna.

Kelemahan menggunakan teknik tabel hash: 







Untuk aplikasi pengolahan string tertentu, seperti spell-checking, tabel hash mungkin kurang efisien. Jika setiap tombol diwakili oleh sejumlah kecil bit yang cukup, maka bukan sebuah tabel hash yang dapat menggunakan tombol langsung sebagai indeks ke array nilai Meskipun rata-rata biaya per operasi adalah konstan dan cukup kecil dengan biaya operasi tunggal dapat cukup tinggi. Secara khusus, jika tabel hash menggunakan ukuran dinamis, penyisipan atau penghapusan operasi yang memerlukan waktu sebanding dengan jumlah entri. Hal ini dapat dikatakan kelemahan yang serius secara realtime atau interaktif Tabel hash biasanya dalam pameran umumnya miskin pemukiman referensi artinya data yang akan deakses didistribusikan tampaknya secara acak di memori. Hal ini dikarenakan tabel hash menyebabkan pola akses berupa lompatan, ini dapat memicu cache mikroprosesor yang menyebabkan penundaan yang lama Tabel hash menjadi sangat tidak efisien bila ada banyak tabrakan

14

Contoh tabel hash:

6) Hashing Keuntungan menggunakan teknik hashing:  

Nilai key yang sebenarnya dapat dipakai karena diterjemahkan ke dalam sebuah alamat Nilai key adalah addres space independent bila berkas direorganisasi, fungsi hash dapat berubah tapi nilai key akan tetap

Kelemahan menggunakan teknik hashing:  

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 Teknik yang dipakai untuk mengatasi benturan

15

Beberapa fungsi hash yang umum digunakan:   

Division Remainder Mid Square Folding a. 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. Contoh: Bila DIV adalah pembagi, KEY adalah nilai key dan ADDR adalah alamat relatif, maka dalam bahasa pascal, fungsi R(NILAIKEY) ADDRESS dapat diimplementasikan: ADDR := KEY MOD DIV Dalam bahasa COBOL: DIVIDE KEY BY DIV GIVING TEMP REMAINDER ADDR Sisa pembagian (sebagai hasil dari fungsi MOD pada Pascal), dapat dijabarkan sebagai berikut: ADDR := KEY-DIV*TEMP ADDR harus merupakan bilangan integer Banyak faktor yang harus dipertimbangkan dalam pemilihan pembagi: 



 

Jangkauan dari nilai key yang dihasilkan dari operasi KEY MOD DIV adalah 0 sampai DIV-1. Nilai dari DIV menentukan ukuran “relatif address space”. Jika diketahui berkas relatif terdiri dari N record dan dianggap hanya satu record dapat disimpan dalam sebuah alamat relatif, maka akan didapat DIV>N Pembagi harus diseleksi untuk mengurangi benturan. Penyelidikan menunjukkan bahwa pembagi yang berupa bilangan genap akan cenderung jelek, terutama dengan nilai key-nya yang dominan ganjik Menurut riset dari W. Buchholz, sebaikanya pembagi itu merupakan bilangan prima Menurut pendapatnya, bukan bilangan prima yang mempunyai faktor prima kurang dari 20 akan dapat memberikan jaminan penampilan yang lebih baik

16



Walaupun kita telah menentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relatif mendekati penuh, maka peluang terjadinya benturan akan meningkat

Untuk mengukur kepenuhan berkas relatif digunakan Load Factor (Faktor Muat) Load Factor=

banyak record dalam berkas max .banyak record dalam berkas

Biasanya load factor yang sering digunakan adalah 0,7 atau 0,8. Jika load factor lebih besar dari 0,7 atau 0,8 maka berkas tersebut harus diperbesar dan direorganisasi. Jadi jika kita ingin menyimpan sebanyak n record pada suatu berkas dan load factor adalah 0,8, maka max banyak recor pada berkas adalah 1.25 n. Contoh: Kita ingin membuat berkas yang terdiri dari 4000 record. Load Factor (Faktor Muat) = 0.8 Maka max. Banyak record pada berkas:

( 1.25 ) n= (1.25 ) × 4000 = 5000

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

c. Hashing by 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).

17

Perbandingan Fungsi Hash  



Teknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan Teknik Mid Square dipakai untuk file dengan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat menghasilkan hasil yang buruk dengan beberapa collision. Teknik folding adalah teknik yang paling mudah dalam perhitungan tatapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address

18

BAB III PENUTUP

1. Kesimpulan Dari pembahasan diatas, maka dapat kita tarik kesimpulan bahwa organisasi berkas relati merupakan suatu cara yang efektif dalam mengorganisasi sekumpulan record dengan cepat melalu beberapa teknik seperti: 1. Teknik pemetaan langsung, yaitu teknik yang sederhana untuk menerjemahkan nilai record key menjadi address 2. Teknik pencarian tabel, yaitu teknik pencarian dengan memanfaatkan sebuah tabel atau direktori dari nilai key dan address 3. Teknik kalkulasi alamat, yaitu teknik pencarian dengan mengubah jangkauan nilai key yang mungkin menjadi sejumlah kecil alamat relatif

19

DAFTAR PUSTAKA

1. https://amnazz.wordpress.com/2010/04/14/organisasi-berkas-relatif/ 2. http://syns-adityaminggar.blogspot.com/2014/12/organisasi-berkas-

relatif.html 3. http://uchieghokil.blogspot.com/2011/04/teknik-pemetaan-langsung.html? m=1 4. https://rizkinawawi.wordpress.com/2020/06/24/pertemuan-8-organisasiberkas-relatif/ 5. http://pantheratigris45.blogspot.com/2010/04/organisasi-berkasrelatif.html

20