SISTEM SEGMENTASI

Segmentasi adalah satu aspek penting dari managemen memori yang tidak dapat dihindari dari pemberian halaman, pemisahan cara pandang pengguna dengan tentang bagaimana memori dipetakan dengan keadaan yang sebenarnya. Pada kenyataannya pemetaan tersebut memperbolehkan pemisahan antara memori lois dan memori fisik.

Metode Dasar

Bagaimanakah cara pandang pengguna tentang bagaimana memori dipetakan? Apakah pengguna menganggap bahwa memori dianggap sebagai sebuah kumpulan dari byte-byte, yang mana sebagian berisi instruksi dan sebagian lagi merupakan data, atau apakah ada cara pandang lain yang lebih layak digunakan? Ternyata programmer dari sistem tidak menganggap bahwa memori adalah sekumpulan byte-byte yang linear. Akan tetapi, mereka lebih senang dengan menganggap bahwa memori adalah sebagai kumpulan dari segmen-segmen yang berukuran beragam tanpa adanya pengurutan penempatan dalam memori fisik. Ketika kita menulis suatu program, kita akan menganggapnya sebagai sebuah program dengan sekumpulan dari subrutin, prosedur, fungsi, atau variabel. mungkin juga terdapat berbagai macam struktur data seperti: tabel, array, stack, variabel, dsb. Tiap-tiap modul atau elemen-elemen dari data ini dapat di-referensikan dengan suatu nama, tanpa perlu mengetahui dimana alamat sebenarnya elemen-elemen tersebut disimpan di memori. dan kita juga tidak perlu mengetahui apakah terdapat urutan penempatan dari program yang kita buat. Pada kenyataannya, elemen-elemen yang terdapat pada sebuah segmen dapat ditentukan lokasinya dengan menambahkan offset dari awal alamat segmen tersebut.

Segmentasi adalah sebuah bagian dari managemen memori yang mengatur pengalamatan dari memori yang terdiri dari segmen-segmen. logical address space adalah kumpulan dari segmen-segmen yang mana tiap-tiap segmen mempunyai nama dan panjang. alamat tersebut menunjukkan alamat dari segmen tersebut dan offset-nya didalam segmen-segmen tersebut. pengguna kemudian menentukan pengalamatan dari setiap segmen menjadi dua bentuk, nama segmen dan offset dari segmen tersebut (Hal ini berbeda dengan pemberian halaman, dimana pengguna hanya menentukan satu buah alamat, dimana pembagian alamat menjadi dua dilakukan oleh perangkat keras, semua ini tidak dapat dilihat oleh user). Untuk kemudahan pengimplementasian, segmen-segmen diberi nomor dan direferensikan dengan menggunakan penomoran tersebut, daripada dengan menggunakan nama. maka, logical address space terdiri dari dua tuple yaitu: (nomor-segmen, offset) Pada umumnya, program dari pengguna akan dikompilasi, dan kompilator tersebut akan membuat segmen-segmen tersebut secara otomatis. Jika mengambil contoh kompilator dari Pascal, maka kemungkinan kompilator tersebut akan membuat beberapa segmen yang terpisah untuk

1. Variabel Global;

2. Prosedur dari pemanggilan stack, utk menyimpan parameter dan pengembalianalamat;

3. Porsi dari kode untuk setiap prosedur atau fungsi; dan

4. Variabel lokal dari setiap prosedur dan fungsi.

Perangkat Keras
 

Walau pun pengguna sekarang dapat mengacu ke suatu objek yang berada di dalam program dengan menggunakan pengalamatan secara dua dimensi, akan tetapi, pada kenyataannya tetap saja pada memori fisik akan dipetakan ke dalam pengalamatan satu dimensi yang terdiri dari urutan dari byte-byte. Maka, kita harus mendefinisikan suatu implementasi untuk memetakan pengalamatan dua dimensi yang dilakukan oleh pengguna ke dalam pengalamatan satu dimensi yang terdapat di memori fisik. pemetaan ini dapat di lakukan dengan menggunakan tabel segmen. Setiap anggota dari tabel segmen mempunyai basis dan limit yang akan menentukan letak dari segmen tersebut di dalam memori.  

 

Kegunaan tabel segmen dapat dilihat pada gambar Gambar 4-10 alamat logis terdiri dari dua bagian: bagian segmen, s, dan bagian offsetnya, d. Nomor dari segmen tersebut akan digunakan sebagai index di dalam tabel segmen. Offset dari d di alamat logis sebaiknya tidak melebihi limit dari alamat segmen, jika ini terjadi, maka sistem operasi sebaiknya dapat mengatasi hal ini, dengan melakukan trap

 

Pemeliharaan dan Pembagian

Dengan dilakukannya pengelompokan antara segmen-segmen yang sama, maka pemeliharaan dari segmen tersebut dapat menjadi lebih mudah, walau pun didalam segmen tersebut sebagian berisi instruksi dan sebagian lagi berisi data. Dalam arsitektur modern, instruksi-instruksi yang digunakan tidak dapat diubah tanpa campur tangan pengguna, oleh karena itu, segmen yang berisi instruksi dapat diberi labe read only atau hanya dapat dijalankan saja. Perangkat keras yang bertugas untuk melakukan pemetaan ke memori fisik akan melakukan pemeriksaan terhadap bit proteksi yang terdapat pada segmen, sehingga pengaksesan memori secara ilegal dapat dihindari, seperti suatu usaha untuk menulis ke area yang berstatus tidak boleh dimodifikasi. Keuntungan lain dari segmentasi adalah menyangkut masalah pembagian penggunaan kode atau data. Setiap proses mempunyai tabel segmennya sendiri, dimana ini akan digunakan oleh dispatcher untuk menentukan tabel segmen dari perangkat keras yang mana akan digunakan ketika proses yang bersangkutan di eksekusi oleh CPU. Segmen akan berbagi ketika anggota dari elemen tabel segmen yang berasal dari dua proses yang berbeda menunjuk ke lokasi fisik yang sama. Pembagian tersebut terjadi pada level segmen, maka, informasi apa pun dapat dibagi jika didefinisikan pada level segmen. Bahkan beberapa segmen pun dapat berbagi, sehingga sebuah program yang terdiri dari beberapa segmen pun dapat saling berbagi pakai.

 

 

Fragmentasi

Penjadwalan jangka-panjang harus mencari dan mengalokasikan memori untuk semua segmen dari program pengguna. Situasi ini mirip dengan pemberian halaman kecuali bahwa segmen-segmen ini mempunyai panjang yang variabel; sedangkan pada halaman, semua mempunyai ukuran yang sama. maka, masalah yang dihadapi adalah pengalamatan memori secara dinamis, hal ini biasanya dapat diselesaikan dengan menggunakan algoritma best-fit atau algoritma first-fit. Segmentasi dapat menyebabkan terjadi fragmentasi eksternal, ini terjadi ketika semua blok memori yang dapat dapat dialokasikan terlalu sedikit untuk mengakomodasi sebuah segmen. Dalam kasus ini, proses hanya harus menunggu sampai terdapat cukup tempat untuk menyimpan segmen tersebut di memori, atau, melakukan suatu pemampatan dapat digunakan untuk membuat ruang kosong dalam memori menjadi lebih besar. Karena segmentasi pada dasarnya adalah algoritma penempatan secara dinamis, maka kita dapat melakukan pemampatan memori kapan saja kita mau. Jika CPU Scheduler harus menunggu untuk satu proses, karena masalah pengalokasian memori, ini mungkin akan dilewati untuk mencari proses yang berprioritas lebih kecil untuk dieksekusi lebih dulu untuk membebaskan ruang kosong dalam memori.

Seberapa seriuskah masalah fragmentasi eksternal dalam segmentasi? Jawaban dari pertanyaan ini tergantung kepada besarnya rata-rata segmen yang tersimpan didalam memori. Jika ukuran rata-rata dari segmen menggunakan sedikit tempat di memori, maka fragmentasi eksternal yang dilakukan juga akan sedikit terjadi.

 Segmentasi Dengan Pemberian Halaman

 

Metode segmentasi dan paging yang telah dijelaskan pada sub bab sebelumnya masing-masing memiliki keuntungan dan kerugian. Selain kedua metode itu ada metode pengaturan memori lainyang berusaha menggabungkan metode segmentasi dan paging. Metode ini disebut dengan segmentation with paging.

 

Dengan metode ini jika ukuran segmen melebihi ukuran memori utama maka segmen tersebut dibagi-bagi jadi ukuran-ukuran halaman yang sama ==> paging

Kelebihan Segmentasi dengan Pemberian Halaman

Sesuai dengan definisinya yang merupakan gabungan dari segmentasi dan paging, maka metode ini memiliki keunggulan yang dimiliki baik oleh metode segmentasi mau pun yang dimiliki oleh paging. Tetapi selain itu segmentasi dengan pemberian halaman ini juga memiliki beberapa kelebihan yang tidak dimiliki oleh kedua metode tersebut. Kelebihan-kelebihan segmentasi dengan pemberian halaman antara lain :

 

•  Dapat dibagi.

•  Proteksi.

• Tidak ada fragmentasi luar

•  Alokasi yang cepat.

•  Banyak variasinya.

•  Biaya kinerja yang kecil.

 

Perbedaan Segmentasi dan Paging

Ada beberapa perbedaan antara Segmentasi dan Paging diantaranya adalah:

 

1. Segmentasi melibatkan programer (programer perlu tahu teknik yang digunakan), sedangkan dengan paging programer tidak perlu tahu teknik yang digunakan

2. Pada segmentasi kompilasi dilakukan secara terpisah sedangkan pada paging, kompilasinya tidak terpisah.

3. Pada segmentasi proteksinya terpisah sedangkan pada paging proteksinya tidak terpisah.
4. Pada segmentasi ada shared code sedangkan pada paging tidak ada shared code.

5. Pada segmentasi terdapat banyak ruang alamat linier sedangkan pada paging hanya terdapat satu ruang alamat linier.

6. Pada segmentasi prosedur dan data dapat dibedakan dan diproteksi terpisah sedangkan pada paging prosedur dan data tidak dapat dibedakan dan diproteksi terpisah.

7. Pada segmentasi pengubahan ukuran tabel dapat dilakukan dengan mudah sedangkan pada Paging pengubahan ukuran tabel tidak dapat dilakukan dengan mudah.

8. Segmentasi digunakan untuk mengizinkan program dan data dapat dipecahkan jadi ruang alamat mandiri dan juga untuk mendukung sharing dan proteksi sedangkan paging digunakan untuk mendapatkan ruang alamat linier yang besar tanpa perlu membeli memori fisik lebih.

 

SISTEM PAGING

Sistem Paging Adalah sistem manajemen pada sistem operasi dalam mengatur program yang sedang berjalan. Program yang berjalan harus dimuat di memori utama. Kendala yang terjadi apabila suatu program lebih besar dibandingkan dengan memori utama yang tersedia.

Untuk mengatasi hal tersebut Sistem Paging mempunyai 2 solusi, yaitu:

- Konsep Overlay
Dimana program yang dijalankan dipecah menjadi beberapa bagian yang dapat dimuat memori (overlay). Overlay yang belum diperlukan pada saat program berjalan (tidak sedang di eksekusi) disimpan di disk, dimana nantinya overlay tersebut akan dimuat ke memori begitu diperlukan dalam eksekusinya.

- Konsep Memori Maya (virtual Memory)
Adalah kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Konsep ini pertama kali dikemukakan Fotheringham pada tahun 1961 untuk sistem komputer Atlas di Universitas Manchester, Inggris.

Gagasan Memori Maya adalah ukuran gabungan program, data dan stack melampaui jumlah memori fisik yang tersedia. Sistem operasi menyimpan bagian-bagian proses yang sedang digunakan di memori utama dan sisanya di disk. Begitu bagian di disk diperlukan maka bagian memori yang tidak diperlukan disingkirkan dan diganti bagian disk yang diperlukan.(http://www.globalkomputer.com)


Nah, sekarang saatnya kita membahas lebih dalam tentang permasalahan dalam penggantian page.

Masalah Penggantian Halaman

 

Pada dasarnya, kesalahan halaman (page fault) sudah tidak lagi menjadi masalah yang terlalu dianggap serius. Hal ini disebabkan karena masing-masing halaman pasti akan mengalami paling tidak satu kali kesalahan dalam pemberian halaman, yakni ketika halaman ini ditunjuk untuk pertama kalinya. Representasi seperti ini sebenarnya tidaklah terlalu akurat. Berdasarkan pertimbangan tersebut, sebenarnya proses-proses yang memiliki 10 halaman hanya akan menggunakan setengah dari jumlah seluruh halaman yang dimilikinya. Kemudian demand paging akan menyimpan I/O yang dibutuhkan untuk mengisi 5 halaman yang belum pernah digunakan. Kita juga dapat meningkatkan derajat multiprogramming dengan menjalankan banyak proses sebanyak 2 kali.

Jika kita meningkatkan derajat multiprogramming, itu sama artinya dengan melakukan over-allocating terhadap memori. Jika kita menjalankan 6 proses, dengan masing-masing mendapatkan 10 halaman, walau pun sebenarnya yang digunakan hanya 5 halaman, kita akan memiliki utilisasi CPU dan throughput yang lebih tinggi dengan 10 frame yang masih kosong.

Lebih jauh lagi, kita harus mempertimbangkan bahwa sistem memori tidak hanya digunakan untuk menangani pengalamatan suatu program. Penyangga (buffer) untuk I/O juga menggunakan sejumlah memori. Penggunaan ini dapat meningkatkan pemakaian algoritma dalam penempatan di memori.

Beberapa sistem mengalokasikan secara pasti beberapa persen dari memori yang dimilikinya untuk penyangga I/O, dimana keduanya, baik proses pengguna mau pun subsistem dari I/O saling berlomba untuk memanfaatkan seluruh sistem memori.

 

Skema Dasar

Pemindahan halaman mengambil pendekatan seperti berikut. Jika tidak ada frame yang kosong, kita mencari frame yang tidak sedang digunakan dan mengosongkannya. Kita dapat mengosongkan sebuah frame dengan menuliskan isinya ke ruang pertukaran (swap space), dan merubah tabel halaman (juga tabel-tabel lainnya) untuk mengindikasikan bahwa halaman tesebut tidak akan lama berada di memori.

Sekarang kita dapat menggunakan frame yang kosong sebagai penyimpan halaman dari proses yang salah. Rutinitas pemindahan halaman:

1. Cari lokasi dari halaman yang diinginkan pada disk

2. Cari frame kosong:

a. Jika ada frame kosong, gunakan.

b. Jika tidak ada frame kosong, gunakan algoritma pemindahan halaman untuk menyeleksi frame yang akan digunakan.

c. Tulis halaman yang telah dipilih ke disk, ubah tabel halaman dan tabel frame.

3. Baca halaman yang diinginkan kedalam frame kosong yang baru, ubah tabel halaman dan tabel frame

 

4. Ulang dari awal proses pengguna.

Jika tidak ada frame yang kosong, pentransferan dua halaman (satu masuk, satu keluar) akan dilakukan. Situasi ini secara efektif akan menggandakan waktu pelayanan kesalahan halaman dan meningkatkan waktu akses efektif. Kita dapat mengurangi pemborosan ini dengan menggunakan bit tambahan. Masingmasing halaman atau frame mungkin memiliki bit tambahan yang diasosiasikan didalam perangkat keras. Pemindahan halaman merupakan dasar dari demand paging. Yang menjembatani pemisahan antara memori lojik dan memori fisik. Dengan mekanisme seperti ini, memori virtual yang sangat besar dapat disediakan untuk programmer dalam bentuk memori fisik yang lebih kecil. Dengan nondemand paging, alamat dari user dipetakan kedalam alamat fisik, jadi 2 set alamat dapat berbeda. Seluruh halaman dari proses masih harus berada di memori fisik. Dengan demand paging, ukuran dari ruang alamat logika sudah tidak dibatasi oleh memori fisik.

Kita harus menyelesaikan 2 masalah utama untuk mengimplementasikan demand paging. Kita harus  mengembangkan algoritma pengalokasian rame dan algoritma pemindahan halaman. Jika kita memiliki banyak proses di memori, kita harus memutuskan berapa banyak frame yang akan dialokasikan ke masing-masing proses. Lebih jauh lagi, saat pemindahan halaman diinginkan, kita harus memilih frame yang akan dipindahkan. Membuat suatu algoritma yang tepat untuk menyelesaikan masalah ini adalah hal yang sangat penting.

Ada beberapa algoritma pemindahan halaman yang berbeda. Kemungkinan setiap Sistem Operasi memiliki skema pemindahan yang unik. Algoritma pemindahan yang baik adalah yang memiliki tingkat kesalahan halaman terendah. Kita mengevaluasi algoritma dengan menjalankanny dalam string khusus di memori acuan dan menghitung jumlah kesalahan halaman.  String dari memori acuan disebut string acuan (reference string). Sebagai contoh, jika kita memeriksa proses khusus, kita mungkin akan mencatat urutan alamat seperti dibawah ini:

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103,

0104, 0101, 0609, 0102, 0105, dimana pada 100  bytes setiap halaman, diturunkan menjadi string acuan seperti berikut:

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

Perlu diperhatikan bahwa selama jumlah  frame meningkat, jumlah kesalahan halaman menurun.

Penambahan memori fisik akan meningkatkan jumlah frame.

 

 

Pemindahan Halaman Secara FIFO

Algoritma ini adalah algoritma paling sederhana dalam hal pemindahan halaman. Algoritma pemindahan

 

FIFO (First In First Out) mengasosiasikan waktu pada saat halaman dibawa kedalam memori dengan masing-masing halaman. Pada saat halaman harus dipindahkan, halaman yang paling tua yang dipilih.

Sebagai contoh:

Gambar 4-11. String Acuan. Sumber: . . .

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 4 4 4 0 0 0 7 7 7

0 0 0 3 3 3 2 2 2 1 1 1 0 0

1 1 1 0 0 0 3 3 3 2 2 2 1

frame halaman

Dari contoh diatas, terdapat 15 kesalahan halaman. Algoritma FIFO mudah untuk dipahami dan diimplementasikan. Namun performance-nya tidak selalu bagus. Salah satu kekurangan dari algoritma FIFO adalah kemungkinan terjadinya anomali Beladi, dimana dalam beberapa kasus, tingkat kesalahan akan meningkat seiring dengan peningkatan jumlah frame yang dialokasikan.

 

Pemindahan Halaman Secara Optimal

Salah satu akibat dari upaya mencegah terjadinya anomali Beladi adalah algoritma pemindahan halaman secara optimal. Algoritma ini memiliki tingkat kesalahan halaman terendah dibandingkan dengan algoritma-algoritma lainnya. Algoritma ini tidak akan mengalami anomaly Belady. Konsep utama dari algoritma ini adalah mengganti halaman yang tidak akan digunakan untuk jangka waktu yang paling lama. Algoritma ini menjamin kemungkinan tingkat kesalahan terendah untuk jumlah frame yang tetap.

 

Perlu disayangkan, algoritma optimal susah untuk diimplementasikan kedalam program, karena algoritma ini menuntut pengetahuan tentang string acuan yang akan muncul.

Pemindahan Halaman Secara LRU

Jika algoritma optimal sulit untuk dilakukan, mungkin kita dapat melakukan pendekatan terhadap algoritma tersebut. Jika kita menggunakan waktu yang baru berlalu sebagai pendekatan terhadap waktu yang akan datang, kita akan memindahkan halaman yang sudah lama tidak digunakan dalam jangka waktu yang terlama. Pendekatan ini disebut algoritma LRU

 

(Least Recently Used) Algoritma LRU mengasosiasikan dengan masing-masing halaman waktu dari halaman yang terakhir digunakan. Ketika halaman harus dipindahkan, LRU memilih halaman yang paling lama tidak digunakan pada waktu yang lalu. Inilah algoritma LRU, melihat waktu yang telah lalu, bukan waktu yang akan datang.

Untuk mengimplementasikan algoritma LRU, terdapat 2 implementasi yang dapat digunakan, yaitu dengan counter dan stack. Selain algoritma optimal, algoritma LRU juga dapat terhindar dari anomali Beladi. Salah satu kelas dari algoritma pemindahan halaman adalah algoritma  stack, yang juga tidak akan pernah mengalami anomali Beladi. Algoritma stack ini menyimpan nomor-nomor halaman pada stack. Kapan pun suatu halaman ditunjuk, halaman ini dikeluarkan dari stack dan diletakkan di blok paling atas dari stack. Dengan cara seperti ini, blok paling atas dari stack selalu berisi halaman yang baru digunakan, sedangkan blok terbawah dari stack selalu berisi halaman yang sudah lama tidak digunakan. Karena suatu halaman dalam stack dapat dikeluarkan meski pun berada ditengah-tengah stack, maka implementasi terbaik untuk algoritma ini adalah dengan daftar mata rantai ganda ( doubly linked list), dengan kepala dan ekor sebagai penunjuk. Pendekatan ini sangat tepat untuk perangkat lunak atau implementasi kode mikro dari algoritma LRU.

 

Pemindahan Halaman Secara Perkiraan LRU

Hanya sedikit sistem komputer yang menyediakan perangkat lunak yang memberikan cukup dukungan terhadap algoritma pemindahan halaman secara LRU. Banyak sistem yang tidak menyediakan perangkat lunak yang memberikan dukungan terhadap algoritma LRU, sehingga terpaksa menggunakan algoritma lain, seperti FIFO. Banyak sistem menyediakan bantuan untuk menangani masalah ini, misalnya dengan bit acuan. Bit acuan untuk halaman diset oleh perangkat lunak kapan pun halaman tersebut ditunjuk. Bit acuan diasosiasikan dengan masing-masing isi dari tabel halaman.

Awalnya, seluruh bit dikosongkan oleh sistem operasi. Selama proses pengguna dijalankan, bit yang diasosiasikan ke masing-masing halaman acuan diset menjadi 1 oleh perangkat keras. Setelah beberapa waktu, kita dapat menentukan halaman mana yang sudah digunakan dan halaman mana yang belum digunakan dengan menguji bit-bit acuan. Informasi tersebut memberikan informasi penting untuk banyak algoritma pemindahan halaman yang memperkirakan halaman mana yang sudah lama tidak digunakan.

Algoritma Additional-Reference-Bit

Kita bisa mendapatkan informasi tambahan mengenai urutan dengan mencatat bit-bit acuan pada suatu interval yang tetap. Kita dapat menyimpan 8-bit byte untuk masing-masing halaman pada tabel di memori. Pada interval tertentu, pencatat waktu (timer) melakukan interupsi dengan mentransfer kontrol kepada sistem operasi. Sistem operasi mengubah bit acuan untuk masing-masing halaman kedalam bit high-order dari 8-bit byte ini dan membuang bit low-order. Register pengganti 8-bit ini berisi sejarah penggunaan halaman dalam periode 8 waktu terakhir.Sebagai contoh, seandainya register pengganti berisi 00000000, maka itu berarti halaman sudah tidak digunakan dalam periode 8 waktu terakhir, halaman yang digunakan paling tidak 1 kali akan memiliki nilai register penggati 11111111.

Algoritma Second-Chance

'Algoritma second-chance" didasari oleh algoritma FIFO. Pada saat suatu halaman ditunjuk, kita akan menginspeksi bit acuannya. Jika bit acuan tersebut bernilai 0, kita memproses untuk membuang halaman ini. Jika bit acuan tersebut bernilai 1, kita berikan kesempatan kedua untuk halaman ini dan menyeleksi halaman FIFO selanjutnya.

Ketika suatu halaman mendapatkan kesempatan kedua, bit acuannya dikosongkan dan waktu tibanya direset menjadi saat ini. Karena itu, halaman yang mendapatkan kesempatan kedua tidak akan

dipindahkan sampai seluruh halaman dipindahkan. Tambahan lagi, jika halaman yang digunakan cukup untuk menampung 1 set bit acuan, maka halaman ini tidak akan pernah dipindahkan.

Algoritma Second-Chance (Yang Diperbaiki)

Kita dapat memperbaiki kekurangan dari algoritma  second-chance dengan mempertimbangkan 2 hal

sekaligus, yaitu bit acuan dan bit modifikasi. Dengan 2 bit ini, kita akan mendapatkan 4 kemungkinan
yang akan terjadi, yaitu:

• (0,0) tidak digunakan dan tidak dimodifikasi, bit terbaik untuk dipindahkan.

• (0,1) tidak digunakan tapi dimodifikasi, tidak terlalu baik untuk dipindahkan karena halaman ini perlu ditulis sebelum dipindahkan.

• (1,0) digunakan tapi tidak dimodifikasi, terdapat kemungkinan halaman ini akan segera digunakan lagi.

• (1,1) digunakan dan dimodifikasi, halaman ini mungkin akan segera digunakan lagi dan halaman ini perlu ditulis ke disk sebelum dipindahkan. Algoritma ini digunakan dalam skema manajemen memori virtual Macintosh.
 

Dasar Perhitungan Pemindahan Halaman

Banyak algoritma-algoritma lain yang dapat digunakan untuk pemindahan halaman. Sebagai contoh, kita dapat menyimpan counter dari nomor acuan yang sudah dibuat untuk masing-masing halaman, dan mengembangkan 2 skema dibawah ini:

ALGORITMA PEMINDAHAN HALAMAN LFU Algoritma LFU (Least Frequently Usedmeng) minginkan halaman dengan nilai terkecil untuk dipindahkan. Alasannya, halaman yang digunakan secara aktif akan memiliki nilai acuan yang besar.

ALGORITMA PEMINDAHAN HALAMAN MFU Algoritma MFU (Most Frequently Used) didasarkan pada argumen yang menyatakan bahwa halaman dengan nilai terkecil mungkin baru saja dimasukkan dan baru digunakan.

Kedua algoritma diatas tidaklah terlalu umum, hal ini disebabkan karena implementasi dari kedua algoritma diatas sangatlah mahal.
 

Algoritma Page-Buffering

Prosedur lain sering digunakan untuk menambah kekhususan dari algoritma pemindahan halaman. Sebagai contoh, pada umumnya sistem menyimpan pool dari frame yang kosong. Prosedur ini

memungkinkan suatu proses mengulang dari awal secepat mungkin, tanpa perlu menunggu halaman
yang akan dipindahkan untuk ditulis ke disk karena frame-nya telah ditambahkan kedalam pool frame kosong.Teknik seperti ini digunakan dalam sistem VAX/ VMS, dengan algoritma FIFO. Ketika algoritma FIFO melakukan kesalahan dengan memindahkan halaman yang masih digunakan secara aktif, halaman tersebut akan dengan cepat diambil kembali dari penyangga frame-kosong, untuk melakukan hal tersebut tidak ada I/O yang dibutuhkan. Metode ini diperlukan oleh VAX karena versi terbaru dari VAX tidak mengimplementasikan bit acuan secara tepat.

Alokasi Frame

Terdapat masalah dalam alokasi frame dalam penggunaan memori virtual, masalahnya yaitu bagaimana kita membagi memori yang bebas kepada berbagai proses yang sedang dikerjakan? Jika ada sejumlah frame bebas dan ada dua proses, berapakah frame yang didapatkan tiap proses?

Kasus paling mudah dari memori virtual adalah sistem satu pemakai. Misalkan sebuah sistem mempunyai memori 128K dengan ukuran halaman 1K, sehingga ada 128 frame. Sistem operasinya

menggunakan 35K sehingga ada 93 frame yang tersisa untuk proses tiap user. Untuk pure demand
paging, ke-93 frame tersebut akan ditaruh pada daftar frame bebas. Ketika sebuah proses user mulai
dijalankan, akan terjadi sederetan page fault. Sebanyak 93 page fault pertama akan mendapatkan frame dari daftar frame bebas. Saat frame bebas sudah habis, sebuah algoritma pergantian halaman akan digunakan untuk memilih salah satu dari 93 halaman di memori yang diganti dengan yang ke 94, dan seterusnya. Ketika proses selesai atau diterminasi, sembilan puluh tiga frame tersebut akan disimpan lagi pada daftar frame bebas.

Terdapat macam-macam variasi untuk strategi sederhana ini, kita bisa meminta sistem operasi untuk mengalokasikan seluruh buffer dan ruang tabel-nya dari daftar frame bebas. Saat ruang ini tidak

digunakan oleh sistem operasi, ruang ini bisa digunakan untuk mendukung paging dari user. Kita juga dapat menyimpan tiga frame bebas yang dari daftar frame bebas, sehingga ketika terjadi page fault, ada frame bebas yang dapat digunakan untuk paging. Saat pertukaran halaman terjadi, penggantinya dapat dipilih, kemudian ditulis ke disk, sementara proses user tetap berjalan.
Variasi lain juga ada, tetapi ide dasarnya tetap yaitu proses pengguna diberikan frame bebas yang mana saja. Masalah lain muncul ketika demand paging dikombinasikan dengan multiprogramming. Hal ini terjadi karena multiprogramming menaruh dua (atau lebih) proses di memori pada waktu yang
bersamaan.

Jumlah Frame Minimum

Tentu saja ada berbagai batasan pada strategi kita untuk alokasi frame. Kita tidak dapat mengalokasikan lebih dari jumlah total frame yang tersedia (kecuali ada page sharing). Ada juga jumlah minimal frame yang dapat di alokasikan. Jelas sekali, seiring dengan bertambahnya jumlah frame yang dialokasikan ke setiap proses berkurang, tingkat page fault bertambah dan mengurangi kecepatan eksekusi proses Selain hal tersebut di atas, ada jumlah minimum frame yang harus dialokasikan. Jumlah minimum ini ditentukan oleh arsitektur set instruksi. Ingat bahwa ketika terjadi page fault, sebelum eksekusi instruksi selesai, instruksi tersebut harus diulang. Sehingga kita harus punya jumlah frame yang cukup untuk menampung semua halaman yang dirujuk oleh sebuah instruksi tunggal.

Jumlah minimum frame ditentukan oleh arsitektur komputer. Sebagai contoh, instruksi move pada

PDP-11 adalah lebih dari satu kata untuk beberapa modus pengalamatan, sehingga instruksi tersebut bisa membutuhkan dua halaman. Sebagai tambahan, tiap operannya mungkin merujuk tidak langsung, sehingga total ada enam frame. Kasus terburuk untuk IBM 370 adalah instruksi MVC. Karena instruksi tersebut adalah instruksi perpindahan dari penyimpanan ke penyimpanan, instruksi ini butuh 6 bit dan dapat memakai dua halaman. Satu blok karakter yang akan dipindahkan dan daerah tujuan perpindahan juga dapat memakai dua halaman, sehingga situasi ini membutuhkan enam

frame. Kesimpulannya, jumlah minimum frame yang dibutuhkan per proses tergantung dari arsitektur komputer tersebut, sementara jumlah maksimumnya ditentukan oleh jumlah memori fisik yang tersedia. Di antara kedua jumlah tersebut, kita punya pilihan yang besar untuk alokasi frame.

Algoritma Alokasi

Cara termudah untuk membagi frame terhadap n proses adalah untuk memberikan bagian yang sama, sebanyak m/n frame untuk tiap proses. Sebagai contoh ada 93 frame tersisa dan 5 proses, maka tiap proses akanmendapatkan 18 frame. Frame yang tersisa, sebanyak 3 buah dapat digunakan sebagai frame bebas cadangan. Strategi ini disebut equal allocation. Sebuah alternatif yaitu pengertian bahwa berbagai proses akan membutuhkan jumlah memori yang berbeda. Jika ada sebuah proses sebesar 10K dan sebuah proses basis data 127K dan hanya kedua proses ini yang berjalan pada sistem, maka ketika ada 62 frame bebas, tidak masuk akal jika kita memberikan masing-masing proses 31 frame. Proses pertama hanya butuh 10 frame, 21 frame lain akan terbuang percuma. Untuk menyelesaikan masalah ini, kita menggunakan proportional allocation. Kita mengalokasikan memori yang tersedia kepada setiap proses tergantung pada ukurannya. Let the size of the virtual memory for process pi be si, and define S = si Lalu, jika jumlah total dari frame yang tersedia adalah m, kita mengalokasikan proses ai ke proses pi, dimana ai mendekati ai = si / S x m Dalam kedua strategi ini, tentu saja, alokasi untuk setiap proses bisa bervariasi berdasarkan multiprogramming level nya. Jika multiprogramming level-nya meningkat, setiap proses akan kehilangan beberapa frame guna menyediakan memori yang dibutuhkan untuk proses yang baru. Di sisi lain, jika multiprogramming level nya menurun, frame yang sudah dialokasikan pada bagian process sekarang bisa disebar ke proses-proses yang masih tersisa.

Mengingat hal itu, dengan equal atau pun proportional allocation, proses yang berprioritas tinggi diperlakukan sama dengan proses yang berprioritas rendah. Berdasarkan definisi tersebut, bagaimanapun juga, kita ingin memberi memori yang lebih pada proses yang berprioritas tinggi untuk mempercepat eksekusi-nya, to the detriment of low-priority processes. Satu pendekatan adalah menggunakan proportional allocation scheme dimana perbandingan frame-nya tidak tergantung pada ukuran relatif dari proses, melainkan lebih pada prioritas proses, atau tergantung kombinasi dari ukuran dan prioritas.

Alokasi Global lawan Local

Faktor penting lain dalam cara-cara pengalokasian frame ke berbagai proses adalah penggantian halaman. Dengan proses-proses yang bersaing mendapatkan frame, kita dapat mengklasifikasikan

algoritma penggantian halaman kedalam dua kategori broad: Penggantian Global dan Penggantian Lokal. Penggantian Global memperbolehkan sebuah proses untuk menyeleksi sebuah  frame pengganti dari himpunan semua  frame, meski pun frame tersebut sedang dialokasikan untuk beberapa proses lain; satu proses dapat mengambil sebuah frame dari proses yang lain. Penggantian Lokal mensyaratkan bahwa setiap proses boleh menyeleksi hanya dari himpunan frame yang telah teralokasi pada proses itu sendiri.Untuk contoh, pertimbangkan sebuah skema alokasi dimana kita memperbolehkan proses berprioritas tinggi untuk meyeleksi frame dari proses berprioritas rendah untuk penggantian. Sebuah proses dapat menyeleksi sebuah pengganti dari frame-nya sendiri atau dari frame-frame proses yang berprioritas lebih rendah. Pendekatan ini memperbolehkan sebuah proses berprioritas tinggi untuk meningkatkan alokasi frame-nya pada expense proses berprioritas rendah.

Dengan strategi Penggantian Lokal, jumlah frame yang teralokasi pada sebuah proses tidak berubah. Dengan Penggantian Global, ada kemungkinan sebuah proses hanya menyeleksi frame-frame yang

teralokasi pada proses lain, sehingga meningkatkan jumlah frame yang teralokasi pada proses itu sendiri (asumsi bahwa proses lain tidak memilih frame proses tersebut untuk penggantian). Masalah pada algoritma Penggantian Global adalah bahwa sebuah proses tidak bisa mengontrol page-fault nya sendiri. Himpunan halaman dalam memori untuk sebuah proses tergantung tidak hanyapada kelakuan paging dari proses tersebut, tetapi juga pada kelakuan paging dari proses lain. Karena itu,
proses yang sama dapat tampil berbeda (memerlukan 0,5 detik untuk satu eksekusi dan 10,3 detik untuk eksekusi berikutnya) due to totally external circumstances. Dalam Penggantian Lokal, himpunan halaman dalam memori untuk sebuah proses hanya dipengaruhi kelakuan paging proses itu sendiri. Penggantian Lokal dapat menyembunyikan sebuah proses dengan membuatnya tidak tersedia bagi proses lain, menggunakan halaman yang lebih sedikit pada memori. Jadi, secara umum Penggantian Global menghasilkan sistem throughput yang lebih bagus, maka itu artinya metode yang paling sering digunakan.