 |
| Gambar Sistem Buddy |
Karena UNIX dimaksudkan untuk tidak tergantung pada mesin, skema memory manajemen nya akan bervariasi dari satu sistem ke yang lain. Versi sebelumya dari UNIX secara langsung menggunakan partisi variable tanpa skema virtual memori. Implementasi saat ini dari UNIX dan Solaris menggunakan virtual memory yang sudah dipage.
Dalam SVR4 dan Solaris, sebenarnya terdapat dua skema manajemen memori yang terpisah. Paging system menyediakan sebuah kemampuan virtual memory yang menyediakan page frame dalam main memory untuk process dan juga menyediakan page frame untuk buffer pada blok disk(piringan harddisk). Walaupun ini adalah sebuah skema manajemen memory yang efektif untuk process pengguna dan I/O disk, skema virtual memori yang sudah dipage kurang cocok untuk mengelola alokasi memori untuk kernel. Untuk tujuan yang berikutnya, sebuah kernel memory allocator digunakan. Kita akan membahas kedua mekanisme sesuai urutan.
Paging System
Struktur Data untuk paged memori virtual , UNIX menggunakan sejumlah struktur data yang dengan sedikit penyesuaian bersifat machine independent :
- Page table: secara khusus, akan ada satu page table per process, dengan satu entry untuk tiap page dalam virtual memory untuk process tersebut.
- Disk block descriptor: Berhubungan dengan tiap page dari sebuah process adalah sebuah entry dalam tabel ini yang menjelaskan salinan disk dari virtual page.
- Page frame data table: menjelaskan tiap frame dari memory yang sebenarnya dan diindeks oleh nomer frame. Tabel ini digunakan oleh algoritma replacement(penggantian).
- Swap-use table: terdapat satu tabel swap-use untuk tiap device swap, dengan satu entri untuk tiap page pada device.
Kebanyakan field yang dijelaskan dalam tabel parameter manajemen memori sudah cukup jelas. Beberapa menyediakan penjelasan yang cukup untuk komentar lebih jauh. Field Age dalam entry tabel page adalah menandakan seberapa lama entri tersebut telah ada sejak sebuah program dirujuk pada frame ini. Namun, jumlah bit dan frekuensi update dari field ini tergatung pada implementasi. Sehingga, tidak ada penggunaan UNIX yang universal dari field ini untuk policy(kebijakan) page replacement.
Field Type of Storage dala disk block descriptor dibutuhkan untuk alasan berikut: ketika file executable pertama kali digunakan untuk menciptakan sebuah process baru, hanya sebuah bagian dari program dan data untuk file tersebut bisa dimasukkan ke dalam memori yang sebenarnya. Kemudian, ketika kesalahan page terjadi, bagian baru dari program dan data dimasukkan. Hanya pada saat pertama kali memasukka,n page virtual memori tersebut dibuat dan ditugaskan pada lokasi pada salah satu device yang digunakan untuk swapping. Pada saat tersebut, OS dikatakan apakah harus membersihkan (diset ke 0) lokasi dalam fram page sebelum loading pertama kali untuk blok program atau data.
Table Parameter Manajemen Memori pada UNIX SVR4
Page Table Entry
Page frame number
Merujuk pada frame dalam memori yang sebenarnya.
Age
Menunjukkan seberapa lama page tersebut telah berada dalam memory tanpa dirujuk. Panjang dan isi field ini tergantung pada processor.
Copy on write
Dinyalakan ketika lebih dari satu proses berbagi sebuah page, sebuah salinan page terpisah harus dibuat untuk semua process yang lain yang berbagi page tersebut. Fiitur ini memungkinkan operasi copy untuk ditunda sampai dibutuhkan dan dihindari dalam kasus dimana fitur tersebut menjadi tidak dibutuhkan.
Modify
Menandakan page telah dimodifikasi
Reference
Menandakan page telah dirujuk. Bit ini akan diset ke 0 ketika page pertamakali dimasukkan dan mungkin secara periodis me-reset algoritma penggantian page.
Valid
menandakan page terdapat dalam main memory.
Protect
Menandakan apakah diperbolehkan melakukan operasi write
Disk Block Descriptor
Swap device number
Nomer logika device dari device sekunder yang menyimpan page yang berpasangan. Nomer ini memungkinkan lebih dari satu devi untuk digunakan untuk swapping.
Device block number
Lokasi Blok dari page pada device yang digunakan untuk swap.
Type of storage
Penyimpanan mungkin berupa unit swap atau file yang bisa dieksekusi. Dalam kasus lainnya, terdapat sebuah indikasi apakah memori virtual yang akan dialokasikan harus dibersihkan terlebih dahulu.
Page Frame Data Table Entry
Page State
Menandakan apakah fram ini tersedia atau mempunyai sebuah page yang berhubungan. Dalam kasus lebih lanjut, status dari page ini dikhususkan: pada device swap, dalam file yang bisa dieksekusi, atau dalam DMA dalam progress.
Reference count
Jumlah process yang merujuk pada page.
Logical device
Device logika yang menyimpan sebuah salinan page
Block number
Lokasi blok dari salinan page pada device logis
Pfdata pointer
Pointer pada pfdata entri tabel yang yang lainnya pada daftar page yang bebas dan pada sebuah antrian hash dari page.
Swap-Use Table Entry
Reference count
Jumlah entri pada tabel page yang merujuk pada sebuah page pada device swap.
Page/storage unit number
Tanda pengenal Page pada unit penyimpanan.
Page Replacement(Penggantian Page)
Tabel data frame page digunakan untuk penggantian page. Beberapa penunjuk digunakan untuk menciptakan daftar dalam tabel ini. Semua frame yang tersedia terhubung bersama dalam sebuah fram yang bebas tersedia untuk membawa masuk page. Ketika jumlah frame yang tersedia turun dibawah ambang batas tertentu, kernel akan mengambil sejumlah frame sebagai ganti.
Algoritma penggantian page yang digunakan dalam SVR4 adalah pemurnian dari algoritma clock policy di gambar di bawah, yang dikenal sebagai algoritma dua tangan. Algoritma tersebut menggunakan bit rujukan dalam entry table page untuk tiap page dalam memory yang pantas (tidak terkunci) untuk di-swap keluar. Bit ini diisi dengan 0 ketika page pertama dibawa masuk dan diisi ke 1 ketika page dirujuk untuk sebuah operasi pembacaan atau penulisan.
Satu tangan dalam algoritma clock yaitu tangan depan menyapu melalui page pada daftar page yang pantas dan mengisi page rujukan menjadi 0 untuk tiap page. Beberapa waktu kemudian, tangan belakang menyapu melalui daftar yang sama dan memeriksa bit rujukan. Jika bit diisi 1 maka page telah dirujuk karena fronthand(tangan depan) telah menyapunya; frame-frame ini dibiarkan. Jika bit rujukan masih berisi 0, maka page belum dirujuk dalam jangka waktu antara kunjungan fronthand dan backhand(tangan belakang); page-page ini ditempatkan pada sebuah daftar untuk di-page out-kan.
Gambar algoritma clock
Dua parameter yang menentukan operasi algoritma tersebut:- Scanrate: laju atau kecepata pada kondisi dimana dua tangan memeriksa daftar page, dalam satuan page per detik.
- Handspread: celah antara fronthand dan backhand.
Dua parameter ini mempunyai nilai default yang diset pada saat boot berdasar pada jumlah memori fisik. Parameter scanrate bisa diubah untuk memenuhi perubahan kondisi. Parameter tersebut bisa beragam secara linear antara nilai slowscan dan fastscan(yang diset saat waktu konfigurasi) karena jumlah memory yang terbebas beragam antara nilai lotsfree dan minfree. Dengan kata lain, karena jumlah memori yang bebas mengecil, hand dari clock bergerak lebih cepat untuk membebaskan lebih banyak page. Parameter Handspread menentukan celah antara fronthand dan backhand dan karena itu bersama dengan scanrate, menentukan jendela kemungkinan untuk menggunakan sebuah page sebelum page diswap keluar karena kurang penggunaan.
Kernel Memory Allocator
Kernel membuat dan menghancurkan tabel dan buffer secara rutin selama masa eksekusi, tiap eksekusi membutuhkan alokasi memori dinamis. Daftar nya berupa contoh berikut.
- Routing translasi pathname bisa mengalokasikan sebuah buffer untuk menyalin sebuah pathname dari ruang user.
- Routine allocb() mengalokasikan buffer STREAM dengan ukuran bebas.
- Banyak implementasi UNIX mengalokasikan struktur zombie untuk mempertahankan status exit dan informasi penggunaan resource tentang process yang sudah mati.
- Dalam SVR4 dan Solaris, kernel mengalokasikan banyak objek seperti struktur proc, vnodes, dan file descriptor block secara bebas ketika dibutuhkan.
Sebagian besar blok ini secara signifikan lebih kecil daripada ukuran mesin pada umumnya, dan oleh karena itu mekanisme paging akan menjadi tidak efisien untuk alokasi memori kernel dinamis. Untuk SVR4, sebuah modifikasi pada sistem buddy digunakan.
Dalam sistem buddy, biaya untuk melakukan alokasi dan membebaskan sebuah blok memori adalah sangat rendah jika dibandingkan dengan kebijkan best-fit atau first-fit. Namun, dalam kasus manajemen memori kernel, alokasi dan operasi pembebasan harus dibuat secepat mungkin. Kekurangan dari sistem buddy adalah waktu yang dibutuhkan untuk memecah dan menggabungkan blok.
Barkley dan Lee di AT&T mengusulkan sebuah variasi yang dikenal sebagai sistem lazy buddy, dan hal ini merupakan teknik yang diadaptasi untuk SVR4. Mereka mengamati bahwa UNIX sering menunjukkan tingkah laku yang steady-state dalam permintaan memory kernel; yaitu jumlah permintaan untuk blok dengan ukuran tertentu yang berubah secara perlahan dalam waktu. Oleh karena itu, jika sebuah blok ukuran 2i dilepaskan dan segera bergabung dengan temannya dengan ukuran blok 2i+1, kernel mungkin berikutnya meminta sebuah blok dengan ukuran 2i yang manan membutuhkan pemisahan blok yang lebih besar lagi. Untuk menghindari penggabungan dan pemisahan yang tidak berguna ini, sistem lazy buddy menunda penggabungan sampai terlihat akan dibutuhkan dan kemudian bergabung dengan sebanyak mungkin blok.
Sistem lazy buddy menggunakan parameter berikut:
Ni = jumlah blok berukuran 2i saat ini.
Ai = jumlah blok berukuran 2i yang teralokasikan (terpakai) saat ini.
Gi = jumlah blok berukuran 2i yang bebas saat ini; ini merupakan blok yang cocok untuk penggabungan; jika si buddy dari blok seperti itu menjadi bebas secara global, maka dua blok akan bergabung menjadi sebuah blok yang secara global bebas dengan ukuran 2i+1. Semua blok yang bebas (hole) dalam standar sistem buddy bisa dianggap bebas secara global.
Li = jumlah blok saat ini dengan ukuran 2i yang bebas secara local; blok-blok ini adalah blok yang tidak cocok untuk digabung. Bahkan jika buddy dari blok tersebut menjadi bebas, dua blok tersebut tidak digabungkan. Daripada itu, blok local yang bebas ditahan untuk antisipasi permintaan untuk blok dengan ukuran tersebut di masa depan.
Nilai awal Di adalah 0
Setelah sebuah operasi, nilai Di diperbaharui seperti berikut
(I) If operasi berikutnya adalah sebuah request alokasi blok:
If terdapat blok bebas, pilih salah satu untuk dialokasikan
If blok yang terpilih bebas secara local
Then Di := Di +2
Else Di := Di +1
Jika tidak
Pertama dapatkan dua blok dengan membagi sebuah blok besar menjadi dua (operasi rekursif)dan alokasikan satu blok dan tandai blok bebas local lainnya
Di tetap tidak berubah (namun D bisa berubah untuk ukuran blok lainnya karena panggilan rekursif)
(II) If operasi berikutnya adalah request blok bebas
Case Di ≥ 2
Tandai blok tersebut bebas local dan bebaskan secara local
Di :=2
Case Di = 1
Tandai blok tersebut bebas global dan bebas kan secara global; gabungkan jika memungkinkan
Di := 0
Case Di = 0
Tandai blok tersebut bebas global dan bebas kan secara global; gabungkan jika memungkinkan
Pilih salah satu blok bebas local dengan ukuran 2i dan bebaskan secara global; gabungkan jika memungkinkan
Di := 0
Gambar Algoritma Sistem Lazy Buddy
Sehingga aturan berikut berlaku:
Ni =Ai + Gi + Li
Secara umum, sistem lazy buddy, mencoba untuk menyimpan sejumlah blok yang bebas local dan hanya memanggil penggabungan jika jumlah blok bebas lok melampaui sebuah ambang batas. Jika terlalu banyak blok bebas local, maka ada kesempatan bahwa aka nada sebuah kekurangan blok bebas pada level berikutnya untuk memenuhi permintaan. Kebanyakan saat ini, ketika sebuah blok dibebaskan, penggabungan tidak terjadi, tidak ada perbedaan yang dibuat antara blok bebas local dan global, sekali lagi, hal ini meminimalkan penyimpanan catatan. kriteria yang digunakan untuk penggabungan adalah jumlah blok bebas local dari sebuah ukuran yang diberikan tidak seharusnya melampaui jumlah blok yang dialokasikan untuk ukuran tersebut (contoh kita harus puany Li ≤ Ai). ini adalah panduan yang memungkinkan untuk pembatasan pertumbuhan blok bebas local, dan percobaan menyimpulkan bahwa skema ini hasil penghematannya bisa dirasakan.
Untuk menerapkan skema ini, penulis mendefinisikan sebuah variable delay sebagai berikut:
Di =Ai - Li = Ni - 2Li - Gi
No comments:
Post a Comment