Disk & Memory Semester Ganjil 2014 Fak. Teknik Jurusan Teknik Informatika Universitas U i i Pasundan P d Caca E Supriana S Si MT Caca E. Supriana, S.Si.,MT.
[email protected]
Pengelolaan Record dalam Disk & Pengelolaan Record dalam Disk & Memory y Data dalam sebuah DBMS disimpan dalam tempat
penyimpanan seperti disk. Dalam sebuah disk terdapat Disk Space Manager yang berfungsi untuk mengatur tempat yang tersedia di dalam disk. y File manager, yang menyediakan abstraksi dari File manager yang menyediakan abstraksi dari record‐record yang tersedia dalam sebuah file dalam kode tingkat tinggi sebuah DBMS, meminta Disk Space Manager mendapatkan atau melepas ruang (space) dalam disk.
2
y Lapisan manajemen file akan meminta dan
melepaskan unit ruang disk dalam halaman (page), dimana ukuran halaman adalah parameter DBMS sebesar 4KB atau 8KB. y Manajemen file juga berfungsi untuk melacak halaman dalam sebuah file dan mengatur record dalam halaman.
3
y Ketika sebuah record akan diproses, record tersebut
akan diambil dari disk ke main memory. Halaman dimana terdapat record tersebut akan ditentukan oleh file manager. y File manager dapat menggunakan struktur data tambahan untuk mengidentifikasi halaman dimana record tersebut berada dengan cepat. y Buffer manager akan mengambil halaman yang diminta dari disk ke buffer pool dan memberi tahu file manager mengenai lokasi dari halaman yang diminta. manager mengenai lokasi dari halaman yang diminta 4
Hi ki M Hierarki Memory
5
y Primary storage, terdiri dari cache dan main
memory, menyediakan akses cepat ke data dan bersifat volatile y Secondary storage, terdiri dari device yang lebih lambat seperti magnetic disk dan bersifat non volatile y Tertiary storage, kelas paling lambat dari tempat p y p penyimpanan seperti optical disk dan bersifat non p p volatile
6
Magnetic Disk Magnetic Disk
7
Magnetic Disk
8
y Data disimpan disk dalam unit yang disebut disk block, y y y
y
merupakan urutan byte yang ditulis dan dibaca dalam disk Block diatur dalam lingkaran disk yang disebut track dalam sebuah atau lebih platter Track dapat direkam dalam satu sisi atau dua sisi platter p p Kumpulan semua track yang mempunyai diameter yang sama disebut cylinder, dimana sebuah silinder mengandung sebuah track per permukaan platter d b h t k k l tt Setiap track terbagi dalam beberapa sector yang p berukuran tetap 9
y Disk controller merupakan antar muka dari disk y y
y y
drive ke komputer Setiap data yang ditulis dan disimpan dalam sektor akan dihitung oleh checksum Seek time adalah waktu yang diperlukan untuk mencari track dimana terdapat lokasi blok yang diinginkan Rotational delay adalah waktu tunggu yang diperlukan dalam mencari blok Transfer time adalah waktu yang diperlukan untuk membaca atau menulis data dalam sebuah blok 10
Implikasi Kinerja dari Struktur Disk Data harus berada dalam memori supaya DBMS dapat beroperasi 2. Membaca atau menulis sebuah disk block disebut M b li b h di k bl k di b operasi I/O (input/output) 3 Waktu yang diperlukan dalam membaca atau 3. menulis sebuah blok bervariasi dengan perhitungan : access time = seek time (ms) + rotational delay (RPM) + transfer time (MB/s) 1.
11
Organisasi Penyimpanan Data Efisien y Dalam sebuah hard drive, rata‐rata data mengakses CPU
setiap 14 ms, hard drive modern dapat mengeksekusi p j beberapa juta instruksi. y Biaya (cost) I/O disk menjadi faktor dominan selama pelaksanaan algoritma pengaksesan. Oleh karena itu sangat penting untuk merancang algoritma yang meminimalkan jumlah permintaan I/O disk. y Selain itu, data pada disk diatur dengan cara yang meminimalkan jumlah acak pencarian yang diperlukan untuk menyelesaikan semua permintaan I/O, dengan mempertimbangkan bahwa permintaan beberapa pengguna mungkin tertunda untuk waktu tertentu pengguna mungkin tertunda untuk waktu tertentu. 12
Sequential Versus I/O Acak (Random) y Banyak operasi database, seperti penyortiran relasi
pada atribut tertentu, memerlukan pembacaan terus menerus dan penulisan data dalam jumlah besar menerus dan penulisan data dalam jumlah besar. y Efisiensi operasi tersebut dapat secara substansial ditingkatkan dengan menempatkan secara strategis data yang dibaca atau ditulis bersama‐sama, di lokasi tetangga (berdekatan) pada disk. y Idealnya adalah meminimalkan gerakan total disk head untuk melaksanakan semua yang diperlukan oleh permintaan I/O untuk menyelesaikan operasi oleh permintaan I/O untuk menyelesaikan operasi. 13
y Contoh silinder miring. Sebuah blok data disimpan
dalam trek yang berurutan, di mana sektor pertama per track miring sehubungan dengan trek sebelumnya untuk mengurangi latency rotasi.
14
Algoritma Penjadwalan Disk y Selain operasi database besar yang memerlukan akses
sekuensial data, beban kerja DBMS melibatkan beberapa permintaan pengguna secara simultan beberapa permintaan pengguna secara simultan. y Beban kerja dari disk drive melibatkan data yang tersebar pada disk dan hampir semua dari hasil waktu tersebar pada disk, dan hampir semua dari hasil waktu dalam sejumlah besar I/O yang acak.
15
Algoritma Penjadwalan Disk adalah : y First Come First Served (FCFS). Dalam FCFS tidak ada upaya dilakukan untuk meminimalkan gerakan disk head. y Shortest Seek Time First (SSTF) yaitu pendekatan yang lebih Sh S k Ti Fi (SSTF) i d k l bih baik untuk menurunkan waktu respon rata‐rata per permintaan. Mengingat antrian I/O permintaan, SSTF memilih dari antrian permintaan yang menghasilkan paling sedikit gerakan disk head, mengingat lokasi disk head. y Algoritma elevator atau SCAN yaitu pendekatan yang berbeda yang menghindari starvation. Algoritma ini tidak melakukan gerakan acak dari disk head sama sekali. Sebaliknya, secara k k d i di k h d k li S b lik kontinyu bergerak kepala di disk dari silinder dalam ke luar dan sebaliknya, dan melayani berikutnya I/O permintaan ke arah g gerakan disk head. 16
File dan Records y DBMS menyimpan relasi dalam penyimpanan sekunder
sebagai file. Sebuah file terdiri dari beberapa halaman (p g ) (page), di mana setiap halaman mencakup sejumlah tetap p p j p sektor (misalnya, ukuran halaman yang biasa adalah 8 kilobyte untuk total 16 sektor per halaman). y Setiap record dari relasi disimpan dalam satu atau beberapa halaman. Setiap record terkait dengan penyimpanan sekunder yang memiliki alamat unik, yang merupakan kombinasi dari identifier file yang sesuai dengan relasi bahwa catatan milik, halaman dalam file ini, dan offset dalam halaman ini. Alamat fisik juga disebut record identifier record identifier. 17
DBMS menghadapi sejumlah masalah ketika mengatur catatan ke file dan halaman, masalah yang paling penting adalah: y Secara efektif mewakili record dengan bermacam jenis f k f kl dd b data. y Record Packing ke halaman dengan meminimalkan ruang yang tidak terpakai. id k k i y Mengorganisir record dalam halaman untuk menangani update record efisien. y Penanganan record yang terdapat dalam beberapa halaman. y Mengorganisir halaman dalam file. 18
Representasi Fisik dari Record SQL statements
Fixed‐ length Record Variable‐length Record dengan header untuk Name & Address 19
Pengorganisasian Record Ke Halaman Pengorganisasian Record Ke Halaman (Page) y Halaman ini dapat dianggap sebagai mengandung
sejumlah slot dengan ukuran tetap. y Header halaman berisi jumlah record yang tersimpan H d h l b i i j l h d i saat ini dalam halaman dan bitmap menandakan apakah slot memegang record atau tidak apakah slot memegang record atau tidak. y Total jumlah record berguna untuk dengan cepat menentukan apakah sebuah halaman memiliki slot p kosong atau tidak.
20
Pengorganisasian Record Ke g g Halaman (Page)
Page untuk g Fixed‐length Record
Page untuk Variable‐ length Record dengan header 21
Pengorganisasian Halaman Ke File y Sebuah file basis data dapat tumbuh atau menyusut
dalam ukuran sebagai data yang dimasukkan atau dihapus, dan karenanya menjadi struktur data dinamis yang perlu dipertahankan secar efisien. y Organisasi berkas sederhana, tumpukan (pile) file, adalah kumpulan yang memanfaatkan halaman. d l h k l f k h l y Konsistensi file dicapai baik dengan menghubungkan setiap halaman ke halaman berikutnya dalam daftar yang dihubungkan dengan menggunakan pointer, atau dengan mempertahankan halaman struktur direktori yang melacak halaman dalam disk direktori yang melacak halaman dalam disk. 22
Buffer Manager y Semua catatan disimpan pada disk sebagai file
paginasi. Tugas buffer manajer untuk mempertahankan salinan beberapa halaman dalam buffer memori utama. y Atas permintaan halaman, dilakukan pemeriksaan Atas permintaan halaman dilakukan pemeriksaan pada buffer manajer jika halaman yang sudah ada terdapat di dalam buffer. Jika ya, disk I/O dapat dihindari. Jika tidak, halaman tersebut diambil dari disk langsung ke buffer.
23
Kebijakan penggantian Secara umum ketika DBMS perlu memilih halaman penyangga untuk penggantian ada beberapa strategi yang p g p g dapat digunakan. Setiap strategi memiliki kelebihan dan kekurangan, tergantung pada distribusi akses data untuk beban kerja tertentu, kemudahan implementasi, biaya p g pengelolaan halaman buffer, dan faktor lainnya. Kebijakan , y j penggantian yang paling sering digunakan adalah: y First In First Out (FIFO), y Least Recently Used (LRU), Least Recently Used (LRU) y Most Recently Used (MRU), y Least Frequently Used (LFU). q y 24
