[TUGAS] 3 Teknik Dasar Yang Digunakan Untuk Menyatakan Fungsi Pemetaan R

1. Directory Look Up (Pencarian Tabel)

Dasar pemikiran pendekatan pencarian table adalah sebuah table atau direktori dari nilai key dan address. Untuk menemukan sebuah record dalam berkas relative, 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 dibandingkan 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 nilaimkey tersebut akan diterjemahkan menjadi alamat.
• Nilai key adalah address space independent, dimana reorganisasi berkas tak akan mempengaruhi nilai key, yang berubah adalah alamat dalam direktori.

2. Direct Mapping (Pemetaan Langsung)

Pemetaan langsung adalah teknik yang paling sederhana, yaitu teknik ini memetakan blokmemori utama hanya ke sebuah saluran cache saja. i = j modulus m dan m = 2r dimana :

i = nomer saluran cache

j = nomer blok memori utama

m = jumlah saluran yang terdapat dalam cache

Fungsi pemetaan diimplementasikan dengan menggunakan alamat, yang terdiri dari tigafield (tag, line, word), 

w = word, adalah bit paling kurang berarti yang mengidentifikasikan word atau byte unik dalam blok memori utama.

s = byte sisa word yang menspesifikasi salah satu dari 2S blok memori utama. Cache logik menginterpretasikan bit – bit S sebagai suatu tag s – r bit (bagian paling berarti dalam alamat) dan field saluran r bit.43

Efek pemetaan tersebut adalah blok – blok memori utama diberikan ke saluran cache seperti berikut ini:

Jadi dalam metode ini pemetaan adalah bagian alamat blok memori utama sebagai nomersaluran cache. Ketika suatu blok data sedang diakses atau dibaca terhadap saluran yang diberikan,maka perlu memberikan tag bagi data untuk membedakannya dengan blok – blok lain yang dapat sesuai dengan saluran tersebut.

Teknik pemetaan ini sederhana dan mudah diimplementasikan, namun kelemahannya adalah terdapat lokasi cache yang tetap bagi sembarang blok – blok yang diketahui. Dengan demikian, apabila suatu program berulang – ulang melakukan word referensi dari dua blok yang berbeda memetakan saluran yang sama maka blok – blok itu secara terus – menerus akan di-swap ke dalam cache sehingga hit rasionya akan rendah.

 Ada 2 cara dalam pemetaan langsung, yaitu:
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.

Kelemahannya

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

3. Calculation (Kalkulasi)

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 relative. Salah satu kelemahan dari teknik pengalamatan relative adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key. Salah satu masalah dari teknik ini adalah ditemukannya alamat relative yang sama untuk nilai key yang berbeda. Seperti di bawah ini adalah maksud dari keadaan itu;

Keadaan dimana :

R(K1) = R(K2) Disebut benturan atau

K1 ¹ K2 collision

Sedangkan nilai K1 dan K2 disebut synonym.

Ket : Synonim merupakan dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.

Teknik-teknik yang terdapat pada kalkulasi alamat :

Dalam teknik kalkulasi terdapat macam – macamnya dan sebagai berikut;

• Scatter storage techniques
• Randomizing technique
• Key-to-address transformation methods
• Direct addressing techniques
• Hash table methods
• Hashing

Share on Google Plus

About Unknown

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.