Register utamanya disebut register relokasi. Nilai pada register relokasi bertambah setiap alamat dibuat oleh
proses pengguna, pada waktu yang sama alamat ini dikirim ke memori. Program pengguna tidak dapat langsung
mengakses memori. Ketika ada program yang menunjuk ke alamat memori, kemudian mengoperasikannya, dan
menaruh lagi di memori, akan di lokasikan awal oleh MMU, karena program pengguna hanya berinterkasi
dengan alamat logika. Pengubahan dari alamat logika ke alamat fisik adalah pusat dari managemen memori.
5.1.4. Pemanggilan Dinamis
Telah kita ketahui seluruh proses dan data berada memori fisik ketika dieksekusi. Ukuran dari memori fisik
terbatas. Untuk mendapatkan utilisasi ruang memori yang baik, kita melakukan pemanggilan dinamis. Dengan
pemanggilan dinamis, sebuah rutin tidak akan dipanggil sampai diperlukan. Semua rutin diletakkan di disk,
dalam format yang dapat dialokasikan ulang. Program utama di tempatkan di memori dan dieksekusi. Jika
sebuah rutin memanggil rutin lainnya, maka akan dicek dulu apakah rutin yang dipanggil ada di dalam memori
atau tidak, jika tidak ada maka linkage loader dipanggil untuk menempatkan rutin yang diinginkan ke memori
dan memperbaharui tabel alamat program untuk menyesuaikan perubahan. Kemudian kontrol diletakan pada
rutin yang baru dipanggil.
Keuntungan dari pemanggilan dinamis adalah rutin yang tidak digunakan tidak pernah dipanggil. Metode ini
berguna untuk kode dalam jumlah banyak, ketika muncul kasus-kasus yang tidak lazim, seperti rutin yang salah.
Dalam kode yang besar, walaupun ukuran kode besar, tapi yang dipanggil dapat jauh lebih kecil.
155Bab 5. Managemen Memori
Pemanggilan Dinamis tidak memerlukan bantuan sistem operasi. Ini adalah tanggung jawab para pengguna
untuk merancang program yang mengambil keuntungan dari metode ini. Sistem operasi dapat membantu
pembuat program dengan menyediakan kumpulan data rutin untuk mengimplementasi pemanggilan dinamis.
5.1.5. Penghubungan Dinamis dan Perpustakaan Bersama
Pada proses dengan banyak langkah, ditemukan juga penghubungan-penghubungan perpustakaan yang dinamis,
dimana menghubungkan semua rutin yang ada di perpustakaan. Beberapa sistem operasi hanya mendukung
penghubungan yang statis, dimana seluruh rutin yang ada dihubungkan ke dalam suatu ruang alamat. Setiap
program memiliki salinan dari seluruh perpustakaan. Konsep penghubungan dinamis, serupa dengan konsep
pemanggilan dinamis. Pemanggilan lebih banyak ditunda selama waktu eksekusi, dari pada lama penundaan
oleh penghubungan dinamis. Keistimewaan ini biasanya digunakan dalam sistem kumpulan perpustakaan,
seperti perpustakaan bahasa subrutin. Tanpa fasilitas ini, semua program dalam sebuah sistem, harus mempunyai
salinan dari pustaka bahasa mereka (atau setidaknya referensi rutin oleh program) termasuk dalam tampilan yang
dapat dieksekusi. Kebutuhan ini sangat boros baik untuk disk, maupun memori utama. Dengan pemanggilan
dinamis, sebuah potongan dimasukkan ke dalam tampilan untuk setiap rujukan perpustakaan subrutin. Potongan
ini adalah sebuah bagian kecil dari kode yang menunjukan bagaimana mealokasikan perpustakaan rutin di
memori dengan tepat, atau bagaimana menempatkan pustaka jika rutin belum ada.
Ketika potongan ini dieksekusi, dia akan memeriksa dan melihat apakah rutin yang dibutuhkan sudah ada di
memori. Jika rutin yang dibutuhkan tidak ada di memori, program akan menempatkannya ke memori. Jika rutin
yang dibutuhkan ada di memori, maka potongan akan mengganti dirinya dengan alamat dari rutin, dan
mengeksekusi rutin. Demikianlah, berikutnya ketika segmentasi kode dicapai, rutin pada perpustakaan
dieksekusi secara langsung, dengan begini tidak ada biaya untuk penghubungan dinamis. Dalam skema ini semua
proses yang menggunakan sebuah kumpulan bahasa, mengeksekusi hanya satu dari salinan kode perpustakaan.
Fasilitas ini dapat diperluas menjadi pembaharuan perpustakaan. Sebuah kumpulan data dapat ditempatkan lagi
dengan versi yang lebih baru dan semua program yang merujuk ke perpustakaan akan secara otomatis
menggunakan versi yang baru. Tanpa pemanggilan dinamis, semua program akan akan membutuhkan
pemanggilan kembali, untuk dapat mengakses perpustakaan yang baru. Jadi semua program tidak secara sengaja
mengeksekusi yang baru, perubahan versi perpustakaan, informasi versi dapat dimasukkan ke dalam memori,
dan setiap program menggunakan informasi versi untuk memutuskan versi mana yang akan digunakan dari
salinan perpustakaan. Sedikit perubahan akan tetap meggunakan nomor versi yang sama, sedangkan perubahan
besar akan menambah satu versi sebelumnya. Karenanya program yang dikompilasi dengan versi yang baru akan
dipengaruhi dengan perubahan yang terdapat di dalamnya. Program lain yang berhubungan sebelum pustaka baru
diinstal, akan terus menggunakan pustaka lama. Sistem ini juga dikenal sebagai berbagi pustaka. Jadi seluruh
pustaka yang ada dapat digunakan bersama-sama. Sistem seperti ini membutuhkan bantuan sistem operasi.
5.1.6. Overlays
Overlays berguna untuk memasukkan suatu proses yang membutuhkan memori lebih besar dari yang tersedia.
Idenya untuk menjaga agar di dalam memori berisi hanya instruksi dan data yang dibutuhkan dalam satuan
waktu. Rutinnya dimasukkan ke memori secara bergantian.
156Bab 5. Managemen Memori
Gambar 5-2. Two-Pass Assembler
ini merupakan skema dari two-Pass Assembler
Sebagai contoh, sebuah two-pass assembler. Selama pass1 dibangun sebuah tabel simbol, kemudian selama
pass2, akan membuat kode bahasa mesin. Kita dapat mempartisi sebuah assembler menjadi kode pass1, kode
pass2, dan simbol tabel, dan rutine biasa digunakan untuk kedua pass1 dan pass2.
Untuk menempatkan semuanya sekaligus, kita akan membutuhkan 200K memori. Jika hanya 150K yang
tersedia, kita tidak dapat menjalankan proses. Bagaimana pun perhatikan bahwa pass1 dan pass2 tidak harus
berada di memori pada saat yang sama. Kita mendefinisikan dua overlays. Overlays A untuk pass1, tabel simbol
dan rutin, overlays dua untuk simbol tabel, rutin, dan pass2.
Kita menambahkan sebuah driver overlays (10K) dan mulai dengan overlays A di memori. Ketika selesai pass1,
pindah ke driver, dan membaca overlays B ke dalam memori, menimpa overlays A, dan mengirim kontrol ke
pass2. Overlays A butuh hanya 120K, dan B membutuhkan 150K memori. Kita sekarang dapat menjalankan
assembler dalam 150K memori. Pemanggilan akan lebih cepat, karena lebih sedikit data yang ditransfer sebelum
eksekusi dimulai. Jalan program akan lebih lambat, karena ekstra I/O dari kode overlays B melalui overlays A.
Seperti dalam pemanggilan dinamis, overlays tidak membutuhkan bantuan dari sistem operasi. Implementasi
dapat dilakukan secara lengkap oleh pengguna dengan berkas struktur yang sederhana, membaca dari berkas ke
memori, dan pindah dari memori tersebut, dan mengeksekusi instruksi yang baru dibaca. Sistem operasi hanya
memperhatikan jika ada lebih banyak I/O dari biasanya.
Di sisi lain pemrogram harus merancang program dengan struktur overlays yang layak. Tugas ini membutuhkan
pengetahuan yang lengkap tentang struktur dari program, kode dan struktur data.
Pemakaian dari overlays, dibatasi oleh komputer mikro, dan sistem lain yang mempunyai batasan jumlah
memori fisik, dan kurangnya dukungan perangkat keras, untuk teknik yang lebih maju. Teknik otomatis
157Bab 5. Managemen Memori
menjalankan program besar dalam dalam jumlah memori fisik yang terbatas, lebih diutamakan.
5.2. Penukaran dan Alokasi Memori
5.2.1. Penukaran
Sebuah proses harus berada di dalam memori untuk dapat dieksekusi. Sebuah proses, bagaimanapun juga, dapat
ditukar sementara keluar memori ke sebuah penyimpanan sementara, dan kemudian dibawa masuk lagi ke
memori untuk melanjutkan pengeksekusian. Sebagai contoh, asumsikan sebuah multiprogramming environment,
dengan penjadualan algoritma penjadualan CPU round-robin. Ketika kuantum habis, pengatur memori akan
mulai menukar proses yang telah selesai, dan memasukkan proses yang lain ke dalam memori yang sudah bebas.
Sementara di saat yang bersamaan, penjadual CPU akan mengalokasikan waktu untuk proses lain di dalam
memori. Ketika waktu kuantum setiap proses sudah habis, proses tersebut akan ditukar dengan proses lain.
Idealnya, manajer memori dapat melakukan penukaran proses-proses tersebut dengan cukup cepat sehingga
beberapa proses akan selalu berada di dalam memori dan siap untuk dieksekusi saat penjadual CPU hendak
menjadual CPU. Lama kuantum pun harus cukup besar sehingga jumlah komputasi yang dilakukan selama
terjadi pertukaran cukup masuk akal.
Variasi dari kebijakan swapping ini, digunakan untuk algoritma penjadualan berbasis prioritas. Jika proses
dengan prioritas lebih tinggi tiba dan meminta layanan, manajer memori dapat menukar keluar proses-proses
yang prioritasnya rendah, sehingga proses-proses yang prioritasnya lebih tinggi tersebut dapat dieksekusi.
Setelah proses-proses yang memiliki prioritas lebih tinggi tersebut selesai dieksekusi, proses-proses dengan
prioritas rendah dapat ditukar kembali ke dalam memori dan dilanjutkan eksekusinya. Cara ini disebut juga
dengan metoda roll out, roll in.
Pada umumnya, proses yang telah ditukar keluar akan ditukar kembali menempati ruang memori yang sama
dengan yang ditempatinya sebelum proses tersebut keluar dari memori. Pembatasan ini dinyatakan menurut
metoda pemberian alamat. Apabila pemberian alamat dilakukan pada saat waktu pembuatan atau waktu
pemanggilan, maka proses tersebut tidak dapat dipindahkan ke lokasi memori lain. Tetapi apabila pemberian
alamat dilakukan pada saat waktu eksekusi, maka proses tersebut dapat ditukar kembali ke dalam ruang memori
yang berbeda, karena alamat fisiknya dihitung pada saat pengeksekusian.
Penukaran membutuhkan sebuah penyimpanan sementara. Penyimpanan sementara pada umumnya adalah
sebuah fast disk, dan harus cukup untuk menampung salinan dari seluruh gambaran memori untuk semua
pengguna, dan harus mendukung akses langsung terhadap gambaran memori tersebut. Sistem mengatur ready
queue yang berisikan semua proses yang gambaran memorinya berada di memori dan siap untuk dijalankan.
Saat sebuah penjadual CPU ingin menjalankan sebuah proses, ia akan memeriksa apakah proses yang mengantri
di ready queue tersebut sudah berada di dalam memori tersebut atau belum. Apabila belum, penjadual CPU akan
melakukan penukaran keluar terhadap proses-proses yang berada di dalam memori sehingga tersedia tempat
untuk memasukkan proses yang hendak dieksekusi tersebut. Setelah itu register dikembalikan seperti semula dan
proses yang diinginkan akan dieksekusi.
Waktu pergantian isi dalam sebuah sistem yang melakukan penukaran pada umumnya cukup tinggi. Untuk
mendapatkan gambaran mengenai waktu pergantian isi, akan diilustrasikan sebuah contoh. Misalkan ada sebuah
proses sebesar 1 MB, dan media yang digunakan sebagai penyimpanan sementara adalah sebuah hard disk
dengan kecepatan transfer 5 MBps. Waktu yang dibutuhkan untuk mentransfer proses 1 MB tersebut dari atau ke
dalam memori adalah:
1000 KB/5000 KBps = 1/5 detik = 200 milidetik
Apabila diasumsikan head seek tidak dibutuhkan dan rata-rata waktu latensi adalah 8 milidetik, satu proses
penukaran memakan waktu 208 milidetik. Karena kita harus melakukan proses penukaran sebanyak 2 kali,
158Bab 5. Managemen Memori
(memasukkan dan mengeluarkan dari memori), maka keseluruhan waktu yang dibutuhkan adalah 416 milidetik.
Untuk penggunaan CPU yang efisien, kita menginginkan waktu eksekusi kita relatif panjang apabila
dibandingkan dengan waktu penukaran kita. Sehingga, misalnya dalam penjuadualan CPU menggunakan
metoda round robin, kuantum yang kita tetapkan harus lebih besar dari 416 milidetik.
Bagian utama dari waktu penukaran adalah waktu transfer. Besar waktu transfer berhubungan langsung dengan
jumlah memori yang di-tukar. Jika kita mempunyai sebuah komputer dengan memori utama 128 MB dan sistem
operasi memakan tempat 5 MB, besar proses pengguna maksimal adalah 123 MB. Bagaimanapun juga, proses
pengguna pada kenyataannya dapat berukuran jauh lebih kecil dari angka tersebut. Bahkan terkadang hanya
berukuran 1 MB. Proses sebesar 1 MB dapat ditukar hanya dalam waktu 208 milidetik, jauh lebih cepat
dibandingkan menukar proses sebesar 123 MB yang akan menghabiskan waktu 24.6 detik. Oleh karena itu,
sangatlah berguna apabila kita mengetahui dengan baik berapa besar memori yang dipakai oleh proses
pengguna, bukan sekedar dengan perkiraan saja. Setelah itu, kita dapat mengurangi besar waktu penukaran
dengan cara hanya menukar proses-proses yang benar-benar membutuhkannya. Agar metoda ini bisa dijalankan
dengan efektif, pengguna harus menjaga agar sistem selalu memiliki informasi mengenai perubahan kebutuhan
memori. Oleh karena itu, proses yang membutuhkan memori dinamis harus melakukan pemanggilan sistem
(permintaan memori dan pelepasan memori) untuk memberikan informasi kepada sistem operasi akan perubahan
kebutuhan memori.
Penukaran dipengaruhi oleh banyak faktor. Jika kita hendak menukar suatu proses, kita harus yakin bahwa proses
tersebut siap. Hal yang perlu diperhatikan adalah kemungkinan proses tersebut sedang menunggu I/O. Apabila
I/O secara asinkron mengakses memori pengguna untuk I/O buffer, maka proses tersebut tidak dapat ditukar.
Bayangkan apabila sebuah operasi I/O berada dalam antrian karena peralatan I/O-nya sedang sibuk. Kemudian
kita hendak mengeluarkan proses P1 dan memasukkan proses P2. Operasi I/O mungkin akan berusaha untuk
memakai memori yang sekarang seharusnya akan ditempati oleh P2. Cara untuk mengatasi masalah ini adalah:
1. Hindari menukar proses yang sedang menunggu I/O.
2. Lakukan eksekusi operasi I/O hanya di buffer sistem operasi.
Hal tersebut akan menjaga agar transfer antara buffer sistem operasi dan proses memori hanya terjadi saat si
proses ditukar kedalam.
Pada masa sekarang ini, proses penukaran secara dasar hanya digunakan di sedikit sistem. Hal ini dikarenakan
penukaran menghabiskan terlalu banyak waktu tukar dan memberikan waktu eksekusi yang terlalu kecil sebagai
solusi dari managemen memori. Akan tetapi, banyak sistem yang menggunakan versi modifikasi dari metoda
penukaran ini.
Salah satu sistem operasi yang menggunakan versi modifikasi dari metoda penukaran ini adalah UNIX.
Penukaran berada dalam keadaan non-aktif, sampai apabila ada banyak proses yang berjalan yang menggunakan
memori yang besar. Penukaran akan berhenti lagi apabila jumlah proses yang berjalan sudah berkurang.
Pada awal pengembangan komputer pribadi, tidak banyak perangkat keras (atau sistem operasi yang
memanfaatkan perangkat keras) yang dapat mengimplementasikan memori managemen yang baik, melainkan
digunakan untuk menjalankan banyak proses berukuran besar dengan menggunakan versi modifikasi dari
metoda penukaran. Salah satu contoh yang baik adalah Microsoft Windows 3.1, yang mendukung eksekusi
proses berkesinambungan. Apabila suatu proses baru hendak dijalankan dan tidak terdapat cukup memori,
proses yang lama perlu dimasukkan ke dalam disk. Sistem operasi ini, bagaimanapun juga, tidak mendukung
penukaran secara keseluruhan karena yang lebih berperan menentukan kapan proses penukaran akan dilakukan
adalah pengguna dan bukan penjadual CPU. Proses-proses yang sudah dikeluarkan akan tetap berada di luar
memori sampai pengguna memilih proses yang hendak dijalankan. Sistem-sistem operasi Microsoft selanjutnya,
seperti misalnya Windows NT, memanfaatkan fitur Unit Managemen Memori.
159Bab 5. Managemen Memori
5.2.2. Alokasi Memori Berkesinambungan
Memori utama harus dapat melayani baik sistem operasi maupun proses pengguna. Oleh karena itu kita harus
mengalokasikan pembagian memori seefisien mungkin. Salah satunya adalah dengan cara alokasi memori
berkesinambungan. Alokasi memori berkesinambungan berarti alamat memori diberikan kepada proses secara
berurutan dari kecil ke besar. Keuntungan menggunakan alokasi memori berkesinambungan dibandingkan
menggunakan alokasi memori tidak berkesinambungan adalah:
1. Sederhana
2. Cepat
3. Mendukung proteksi memori
Sedangkan kerugian dari menggunakan alokasi memori berkesinambungan adalah apabila tidak semua proses
dialokasikan di waktu yang sama, akan menjadi sangat tidak efektif sehingga mempercepat habisnya memori.
Alokasi memori berkesinambungan dapat dilakukan baik menggunakan sistem partisi banyak, maupun
menggunakan sistem partisi tunggal. Sistem partisi tunggal berarti alamat memori yang akan dialokasikan untuk
proses adalah alamat memori pertama setelah pengalokasian sebelumnya. Sedangkan sistem partisi banyak
berarti sistem operasi menyimpan informasi tentang semua bagian memori yang tersedia untuk dapat diisi oleh
proses-proses (disebut lubang). Sistem partisi banyak kemudian dibagi lagi menjadi sistem partisi banyak tetap,
dan sistem partisi banyak dinamis. Hal yang membedakan keduanya adalah untuk sistem partisi banyak tetap,
memori dipartisi menjadi blok-blok yang ukurannya tetap yang ditentukan dari awal. Sedangkan sistem partisi
banyak dinamis artinya memori dipartisi menjadi bagian-bagian dengan jumlah dan besar yang tidak tentu.
Untuk selanjutnya, kita akan memfokuskan pembahasan pada sistem partisi banyak.
Sistem operasi menyimpan sebuah tabel yang menunjukkan bagian mana dari memori yang memungkinkan
untuk menyimpan proses, dan bagian mana yang sudah diisi. Pada intinya, seluruh memori dapat diisi oleh
proses pengguna. Saat sebuah proses datang dan membutuhkan memori, CPU akan mencari lubang yang cukup
besar untuk menampung proses tersebut. Setelah menemukannya, CPU akan mengalokasikan memori sebanyak
yang dibutuhkan oleh proses tersebut, dan mempersiapkan sisanya untuk menampung proses-proses yang akan
datang kemudian (seandainya ada).
Saat proses memasuki sistem, proses akan dimasukkan ke dalam antrian masukan. Sistem operasi akan
menyimpan besar memori yang dibutuhkan oleh setiap proses dan jumlah memori kosong yang tersedia, untuk
menentukan proses mana yang dapat diberikan alokasi memori. Setelah sebuah proses mendapat alokasi
memori, proses tersebut akan dimasukkan ke dalam memori. Setelah proses tersebut dimatikan, proses tersebut
akan melepas memori tempat dia berada, yang mana dapat diisi kembali oleh proses lain dari antrian masukan.
Sistem operasi setiap saat selalu memiliki catatan jumlah memori yang tersedia dan antrian masukan. Sistem
operasi dapat mengatur antrian masukan berdasarkan algoritma penjadualan yang digunakan. Memori
dialokasikan untuk proses sampai akhirnya kebutuhan memori dari proses selanjutnya tidak dapat dipenuhi
(tidak ada lubang yang cukup besar untuk menampung proses tersebut). Sistem operasi kemudian dapat
menunggu sampai ada blok memori cukup besar yang kosong, atau dapat mencari proses lain di antrian masukan
yang kebutuhan memorinya memenuhi jumlah memori yang tersedia.
Pada umumnya, kumpulan lubang-lubang dalam berbagai ukuran tersebar di seluruh memori sepanjang waktu.
Apabila ada proses yang datang, sistem operasi akan mencari lubang yang cukup besar untuk menampung
memori tersebut. Apabila lubang yang tersedia terlalu besar, akan dipecah menjadi 2. Satu bagian akan
dialokasikan untuk menerima proses tersebut, sementara bagian lainnya tidak digunakan dan siap menampung
proses lain. Setelah proses selesai, proses tersebut akan melepas memori dan mengembalikannya sebagai
lubang-lubang. Apabila ada dua lubang yang kecil yang berdekatan, keduanya akan bergabung untuk
membentuk lubang yang lebih besar. Pada saat ini, sistem harus memeriksa apakah ada proses yang menunggu
yang dapat dimasukkan ke dalam ruang memori yang baru terbentuk tersebut.
160Bab 5. Managemen Memori
Hal ini disebut Permasalahan alokasi penyimpanan dinamis, yakni bagaimana memenuhi permintaan sebesar
n dari kumpulan lubang-lubang yang tersedia. Ada berbagai solusi untuk mengatasi hal ini, yaitu:
1. First fit: Mengalokasikan lubang pertama ditemukan yang besarnya mencukupi. Pencarian dimulai dari awal.
2. Best fit: Mengalokasikan lubang dengan besar minimum yang mencukupi permintaan.
3. Next fit: Mengalokasikan lubang pertama ditemukan yang besarnya mencukupi. Pencarian dimulai dari akhir
pencarian sebelumnya.
4. Worst fit: Mengalokasikan lubang terbesar yang ada.
Gambar 5-3. Permasalahan alokasi penyimpanan dinamis
Disadur dari berbagai sumber di internet
Memilih yang terbaik diantara keempat metoda diatas adalah sepenuhnya tergantung kepada pengguna, karena
setiap metoda memiliki kelebihan dan kekurangan masing-masing. Menggunakan best fit dan worst fit berarti
kita harus selalu memulai pencarian lubang dari awal, kecuali apabila lubang sudah disusun berdasarkan ukuran.
Metode worst fit akan menghasilkan sisa lubang yang terbesar, sementara metoda best fit akan menghasilkan sisa
lubang yang terkecil.
5.2.3. Alokasi Memori dan Fragmentasi
Fragmentasi adalah munculnya lubang-lubang yang tidak cukup besar untuk menampung permintaan dari
proses. Fragmentasi dapat berupa fragmentasi internal maupun fragmentasi eksternal. Fragmentasi ekstern
muncul apabila jumlah keseluruhan memori kosong yang tersedia memang mencukupi untuk menampung
permintaan tempat dari proses, tetapi letaknya tidak berkesinambungan atau terpecah menjadi beberapa bagian
kecil sehingga proses tidak dapat masuk. Sedangkan fragmentasi intern muncul apabila jumlah memori yang
161Bab 5. Managemen Memori
diberikan oleh penjadual CPU untuk ditempati proses lebih besar daripada yang diminta proses karena adanya
selisih antara permintaan proses dengan alokasi lubang yang sudah ditetapkan.
Algoritma alokasi penyimpanan dinamis manapun yang digunakan, tetap tidak bisa menutup kemungkinan
terjadinya fragmentasi. Bahkan hal ini bisa menjadi fatal. Salah satu kondisi terburuk adalah apabila kita
memiliki memori terbuang setiap dua proses. Apabila semua memori terbuang itu digabungkan, bukan tidak
mungkin akan cukup untuk menampung sebuah proses. Sebuah contoh statistik menunjukkan bahwa saat
menggunakan metoda first fit, bahkan setelah dioptimisasi, dari N blok teralokasi, sebanyak 0.5N blok lain akan
terbuang karena fragmentasi. Jumlah sebanyak itu berarti kurang lebih setengah dari memori tidak dapat
digunakan. Hal ini disebut dengan aturan 50%.
Fragmentasi ekstern dapat diatasi dengan beberapa cara, diantaranya adalah:
1. Pemadatan, yaitu mengatur kembali isi memori agar memori yang kosong diletakkan bersama di suatu
bagian yang besar, sehingga proses dapat masuk ke ruang memori kosong tersebut.
2. Penghalamanan.
3. Segmentasi.
Fragmentasi intern hampir tidak dapat dihindarkan apabila kita menggunakan sistem partisi banyak berukuran
tetap, mengingat besar hole yang disediakan selalu tetap.
5.3. Pemberian Halaman
Yang dimaksud dengan pemberian halaman adalah suatu metoda yang memungkinkan suatu alamat fisik memori
yang tersedia dapat tidak berurutan. Pemberian halaman bisa menjadi solusi untuk pemecahan masalah luar.
Untuk bisa mengimplementasikan solusi ini adalah melalui pengunaan dari skema pemberian halaman. Dengan
pemberian halaman bisa mencegah masalah penting dari pengepasan besar ukuran memori yang bervariasi
kedalam penyimpanan cadangan. Ketika beberapa pecahan kode dari data yang tersisa di memori utama perlu
untuk ditukar keluar, harus ditemukan ruang untuk penyimpanan cadangan. Masalah pemecahan kode
didiskusikan dengan kaitan bahwa pengaksesannya lebih lambat. Biasanya bagian yang menunjang untuk
pemberian halaman telah ditangani oleh hardware. Bagaimanapun, desain yang ada baru-baru ini telah
mengimplementasikan dengan menggabungkan hardware dan sistem operasi, terutama pada 64 bit
microprocessor.
5.3.1. Metode Dasar
Jadi metoda dasar yang digunakan adalah dengan memecah memori fisik menjadi blok-blok berukuran tetap
yang akan disebut sebagai frame. selanjutnya memori logis juga dipecah menjadi blok-blok dengan ukuran yang
sama disebut sebagai halaman. Selanjutnya kita membuat suatu tabel halaman yang akan menterjemahkan
memori logis kita kedalam memori fisik. Jika suatu proses ingin dieksekusi maka memori logis akan melihat
dimanakah dia akan ditempatkan di memori fisik dengan melihat kedalam tabel halamannya.
Untuk jelasnya bisa dilihat pada Gambar 5-4. Kita lihat bahwa setiap alamat yang dihasilkan oleh CPU
dibagi-bagi menjadi dua bagian yaitu sebuah nomor halaman (p) dan sebuah offset halaman (d). Nomor halaman
ini akan digunakan sebagai indeks untuk tabel halaman. Tabel halaman mengandung basis alamat dari tiap-tiap
halaman di memori fisik. Basis ini dikombinasikan dengan offset halaman untuk menentukan alamat memori
fisik yang dikirim ke unit memori.
162Bab 5. Managemen Memori
Gambar 5-4. Penerjemahan Halaman
Sumber: Silberschatz et. al.
5.3.2. Dukungan Perangkat Keras
Setiap sistem operasi mempunyai caranya tersendiri untuk menyimpan tabel halaman. Biasanya sistem operasi
mengalokasikan sebuah tabel halaman untuk setiap proses. sebuah penunjuk ke tabel halaman disimpan dengan
nilai register yang lain didalam blok pengontrol proses.
salah satu dukungan perangkat keras adalah dengan menggunakan apa yang dinamakan TLB (translation look
aside-buffer). TLB adalah asosiatif, memori berkecepatan tinggi.
Setiap bagian di TLB terdiri dari kunci dan nilai. Ketika kita ingin mendapatkan alamat fisik memori maka
alamat logikal dari CPU akan dibandingkan dengan nilai yang ada di TLB. jika nilainya ketemu maka dinamakan
TLB hit dan jika nilainya tidak ketemu dinamakan TLB miss. Biasanya ukurannya kecil antara 64 sampai 1024.
Persentasi dari beberapa kali TLB hit adalah disebut hit ratio. 80% dari hit ratio adalah kita menemukan nomor
halaman yang ingin kita cari didalam TLB sebesar 80%. Jika waktu akses ke TLB memakan waktu 20 nanodetik
dan akses ke memori memakan waktu sebesar 100 nanodetik maka total waktu kita memetakan memori adalah
120 nanodetik jika TLB hit. dan jika TLB miss maka total waktunya adalah 220 nanodetik. Jadi untuk
mendapatkan waktu akses memori yang efektif maka kita harus membagi-bagi tiap kasus berdasarkan
kemungkinannya:
waktu akses yang efektif = 80% x 120 x 20% x 220 = 140 nanodetik
5.3.3. Proteksi
Proteksi memori dilingkungan halaman bisa dilakukan dengan cara memproteksi bit-bit yang berhubungan
dengan setiap frame. Biasanya bit-bit ini disimpan didalam sebuah tabel halaman. satu bit bisa didefinisikan
sebagai baca-tulis atau hanya baca saja. Setiap referensi ke memori menggunakan tabel halaman untuk
163Bab 5. Managemen Memori
menemukan nomor frame yang benar. pada saat alamat fisik sedang dihitung, bit proteksi bisa mengecek bahwa
kita tidak bisa menulis ke mode tulis saja.
5.3.4. Keuntungan dan Kerugian Pemberian Halaman
• Jika kita membuat ukuran dari masing-masing halaman menjadi lebih besar.
Keuntungan:
Akses memori akan relatif lebih cepat.
Kerugian:
Kemungkinan terjadinya fragmentasi intern sangat. besar
• Jika kita membuat ukuran dari masing-masing halaman menjadi lebih kecil.
Keuntungan:
Kemungkinan terjadinya internal Framentasi akan menjadi lebih kecil.
Kerugian:
Akses memori akan relatif lebih lambat.
5.4. Struktur Tabel Halaman
Sebagian besar komputer modern memiliki perangkat keras istimewa yaitu unit managemen memori (MMU).
Unit tersebut berada diantara CPU dan unit memori. Jika CPU ingin mengakses memori (misalnya untuk
memanggil suatu instruksi atau memanggil dan menyimpan suatu data), maka CPU mengirimkan alamat memori
yang bersangkutan ke MMU, yang akan menerjemahkannya ke alamat lain sebelum melanjutkannya ke unit
memori. Alamat yang dihasilkan oleh CPU, setelah adanya pemberian indeks atau aritmatik ragam
pengalamatan lainnya disebut alamat logis (virtual address). Sedangkan alamat yang didapatkan setelah
diterjemahkan oleh CPU disebut alamat fisik (physical address).
Biasanya, penterjemahan dilakukan di granularitas dari suatu halaman. Setiap halaman mempunyai pangkat 2
bytes, diantara 1024 dan 8192 bytes. Jika alamat logis p dipetakan ke alamat fisik f (dimana p adalah kelipatan
dari ukuran halaman), maka alamat p+o dipetakan ke alamat fisik f+o untuk setiap ofset o kurang dari ukuran
halaman. Dengan kata lain, setiap halaman dipetakan ke contigous region di alamat fisik yang disebut frame.
MMU yang mengizinkan contigous region dari alamat logis dipetakan ke frame yang tersebar disekitar alamat
fisik membuat sistem operasi lebih mudah pekerjaannya saat mengalokasikan memori. Lebih penting lagi, MMU
juga mengizinkan halaman yang tidak sering digunakan bisa disimpan di disk. Cara kerjanya adalah sbb: Tabel
yang digunakan oleh MMU mempunyai bit sahih untuk setiap halaman di bagian alamat logis. Jika bit tersebut
di set, maka penterjemahan oleh alamat logis di halaman itu berjalan normal. Akan tetapi jika dihapus, adanya
usaha dari CPU untuk mengakses suatu alamat di halaman tersebut menghasilkan suatu interupsi yang disebut
page fault trap. Sistem operasi telah mempunyai interrupt handler untuk kesalahan halaman, juga bisa
digunakan untuk mengatasi interupsi jenis yang lain. Handler inilah yang akan bekerja untuk mendapatkan
halaman yang diminta ke memori.
164Bab 5. Managemen Memori
Untuk lebih jelasnya, saat kesalahan halaman dihasilkan untuk halaman p1, interrupt handler melakukan hal-hal
berikut ini:
• Mencari dimana isi dari halaman p1 disimpan di disk. Sistem operasi menyimpan informasi ini di dalam tabel.
Ada kemungkinan bahwa halaman tersebut tidak ada dimana-mana, misalnya pada kasus saat referensi
memori adalah bug. Pada kasus tersebut , sistem operasi mengambil beberapa langkah kerja seperti
mematikan prosesnya. Dan jika diasumsikan halamannya berada dalam disk:
• Mencari halaman lain yaitu p2 yang dipetakan ke frame lain f dari alamat fisik yang tidak banyak
dipergunakan.
• Menyalin isi dari frame f keluar dari disk.
• Menghapus bit sahih dari halaman p2 sehingga sebagian referensi dari halaman p2 akan menyebabkan
kesalahan halaman.
• Menyalin data halaman p1 dari disk ke frame f .
• Update tabel MMU sehingga halaman p1 dipetakan ke frame f .
• Kembali dari interupsi dan mengizinkan CPU mengulang instruksi yang menyebabkan interupsi tersebut.
Gambar 5-5. Struktur MMU
Sumber: Operating System karya Avi Silberschatz, Peter Galvin, dan Greg Gagne, 2000
165Bab 5. Managemen Memori
5.4.1. Tabel Halaman
Pada dasarnya MMU terdiri dari tabel halaman yang merupakan sebuah rangkaian array dari masukan-masukan
(entries) yang mempunyai indeks berupa nomor halaman (p). Setiap masukan terdiri dari flags (contohnya bit
sahih dan nomor frame). Alamat fisik dibentuk dengan menggabungkan nomor frame dengan ofset, yaitu bit
paling rendah dari alamat logis.
Setiap sistem operasi mempunyai metodenya sendiri untuk menyimpan tabel halaman. Sebagian besar
mengalokasikan tabel halaman untuk setiap proses. Penunjuk ke tabel halaman disimpan dengan nilai register
yang lain (seperti pencacah instruksi) di blok kontrol proses. Ketika pelaksana dispatcher mengatakan untuk
memulai proses, maka harus disimpan kembali register-register pengguna dan mendefinisikan nilai tabel
halaman perangkat keras yang benar dari tempat penyimpanan tabel halaman dari pengguna.
Gambar 5-6. Skema Tabel Halaman Dua tingkat
http://www.cs.wisc.edu/~solomon/cs537/paging.html
5.4.2. Pemberian Page Secara Multilevel
Idenya adalah dengan menambahkan tingkatan secara tidak langsung dan memiliki tabel halaman yang terdiri
dari pointer-pointer ke tabel halaman.
• Bayangkan suatu tabel halaman yang besar.
• Panggil tabel halaman dua tingkat dan potong menjadi bagian-bagian untuk setiap ukuran dari halaman
tersebut.
• Sebagai catatan bahwa anda bisa mendapatkan banyak PTE-PTE dalam satu halaman maka anda akan
mempunyai jauh lebih sedikit dari halaman tersebut daripada yang dimiliki oleh PTE.
• Sekarang buatlah tabel halaman satu tingkat yang terdiri dari PTE-PTE yang memiliki pointer ke halaman
tersebut.
• Tabel halaman satu tingkat ini cukup kecil untuk disimpan di memori.
166Bab 5. Managemen Memori
• Jika kita telah memiliki tabel halaman dua tingkat maka pekerjaan akan jauh lebih mudah.
• Jangan menyimpan semua reference PTE ke memori yang tidak terpakai dalam memori tabel halaman dua
tingkat. Hal tersebut menggunakan permintaan halaman pada tabel halaman dua tingkat.
• Untuk tabel halaman dua tingkat, alamat logis dibagi menjadi tiga bagian yaitu P#1, P#2, dan Ofset
• P#1 menunjukkan indeks menuju tabel halaman satu tingkat.
• Ikuti penunjuk pada PTE yang berkaitan untuk meraih frame yang terdiri dari tabel halaman dua tingkat yang
relevan.
• P#2 menunjukkan indeks menuju tabel halaman dua tingkat.
• Ikuti pointer pada PTE yang berkaitan untuk meraih frame yang terdiri dari frame asli yang diminta.
• Ofset menunjukkan ofset dari frame dimana terdapat lokasi adanya permintaan kata.
Banyak sistem komputer modern mendukung ruang alamat logis yang sangat luas (2 pangkat 32 sampai 2
pangkat 64). Pada lingkungan seperti itu tabel halamannya sendiri menjadi besar sekali. Untuk contoh, misalkan
suatu sistem dengan ruang alamat logis 32-bit. Jika ukuran halaman di sistem seperti itu adalah 4K byte (2
pangkat 12), maka tabel halaman mungkin berisi sampai 1 juta masukan ((2^32)/(2^12)). Karena masing-masing
masukan terdiri atas 4 byte, tiap-tiap proses mungkin perlu ruang alamat fisik sampai 4 megabyte hanya untuk
tabel halamannya saja. Jelasnya, kita tidak akan mau mengalokasi tabel halaman secara berdekatan di dalam
memori. Satu solusi sederhananya adalah dengan membagi tabel halaman menjadi potongan-potongan yang
lebih kecil lagi. Ada beberapa cara yang berbeda untuk menyelesaikan ini.
167Bab 5. Managemen Memori
Gambar 5-7. Tabel Halaman secara Multilevel
Sumber: allan.ultra.nyu.edu/~gottlieb/courses/1999-00-spring/ os/lecture-11.html
5.4.3. Tabel Halaman secara Inverted
Biasanya, setiap proses mempunyai tabel halaman yang diasosiasikan dengannya. Tabel halaman hanya punya
satu masukan untuk setiap halaman proses tersebut sedang digunakan (atau satu slot untuk setiap alamat maya,
tanpa meperhatikan validitas terakhir). Semenjak halaman referensi proses melalui alamat maya halaman, maka
representasi tabel ini adalah alami. Sistem operasi harus menterjemahkan referensi ini ke alamat memori fisik.
Semenjak tabel diurutkan berdasarkan alamat maya, sistem operasi dapat menghitung dimana pada tabel yang
diasosiasikan dengan masukan alamat fisik, dan untuk menggunakan nilai tersebut secara langsung. Satu
kekurangan dari skema ini adalah masing-masing halaman mungkin mengandung jutaan masukan. Tabel ini
mungkin memakan memori fisik dalam jumlah yang besar, yang mana dibutukan untuk tetap menjaga
bagaimana memori fisik lain sedang digunakan.
168Bab 5. Managemen Memori
Gambar 5-8. Tabel Halaman secara Inverted
Sumber: Operating System karya Avi Silberschatz, Peter Galvin, dan Greg Gagne, 2000
5.4.4. Berbagi Halaman
Keuntungan lain dari pemberian halaman adalah kemungkinannya untuk berbagi kode yang sama. Pertimbangan
ini terutama sekali penting pada lingkungan yang berbagi waktu. Pertimbangkan sebuah sistem yang mendukung
40 pengguna, yang masing-masing menjalankan aplikasi pengedit teks. Jika editor teks tadi terdiri atas 150K
kode dan 50K ruang data, kita akan membutuhkan 8000K untuk mendukung 40 pengguna. Jika kodenya
dimasukan ulang, bagaimana pun juga dapat dibagi-bagi, seperti pada gambar. Disini kita lihat bahwa tiga
halaman editor (masing-masing berukuran 50K; halaman ukuran besar digunakan untuk menyederhanakan
gambar) sedang dibagi-bagi diantara tiga proses. Masing-masing proses mempunyai halaman datanya sendiri.
5.5. Segmentasi
Segmentasi adalah skema managemen memori dengan cara membagi memori menjadi segmen-segmen. Dengan
demikian, sebuah program dibagi menjadi segmen-segmen. Segmen adalah sebuah unit logis, yaitu unit yang
terdiri dari beberapa bagian yang berjenis yang sama. Contoh: program utama, variabel lokal, procedure dan
sebagainya. Berbeda dengan halaman, ukuran tiap segmen tidak harus sama dan memiliki ’ciri’ tertentu. Ciri
tertentu itu adalah nama segmen dan panjang segmen. Nama segmen dirujuk oleh nomor segmen sedangkan
panjang segmen ditentukan oleh offset.
5.5.1. Arsitektur Segmentasi
Ukuran tiap segmen tidak harus sama. Saat sebuah program atau proses dimasukkan ke CPU, segmen yang
berbeda dapat ditempatkan dimana saja di dalam memori utama (dapat menggunakan cara first-fit atau best-fit).
Alamat logis dari sebuah segmen adalah alamat dua dimensi, sedangkan alamat fisik memori adalah alamat satu
dimensi. Oleh karena itu, agar implementasinya menjadi mudah (dari alamat logis ke alamat fisik) diperlukan
Tabel Segmen yang yang terdiri dari base dan limit. Base menunjukkan alamat awal segmen (dari alamat fisik)
dan limit menunjukkan panjang segmen.
169Bab 5. Managemen Memori
Gambar 5-9. Arsitektur Segmentasi
alamat logisnya: s dan d, s adalah nomor segmen/index di dalam tabel segmen d adalah offset . Jika offset kurang
dari nol dan tidak lebih besar dari besarnya limit maka base akan dijumlahkan dengan d (offset), yang
dijumlahkan itu adalah alamat fisik dari segmen tersebut.
5.5.2. Saling Berbagi dan Proteksi
Segmen dapat terbagi jika terdapat elemen di tabel segmen yang berasal dari dua proses yang berbeda yang
menunjuk pada alamat fisik yang sama. Saling berbagi ini muncul di level segmen dan pada saat ini terjadi
semua informasi dapat turut terbagi. Proteksi dapat terjadi karena ada bit-proteksi yang berhubungan dengan
setiap elemen dari segmen tabel. Bit-proteksi ini berguna untuk mencegah akses ilegal ke memori. Caranya:
menempatkan sebuah array di dalam segmen itu sehingga perangkat keras managemen memori secara otomatis
akan mengecek indeks array-nya legal atau tidak.
5.5.3. Masalah Dalam Segmentasi
• Segmen dapat Membesar.
• Muncul Fragmentasi Luar.
• Bila Ada Proses yang Besar.
170Bab 5. Managemen Memori
5.5.4. Segmentasi dengan Pemberian Halaman
Kelebihan Pemberian Halaman: tidak ada fragmentasi luar-alokasinya cepat.
Kelebihan Segmentasi: saling berbagi-proteksi.
Gambar 5-10. Segmentasi dengan Pemberian Halaman
171Bab 5. Managemen Memori
5.5.5. Penggunaan Segmentasi
MULTICS
Gambar 5-11. Penggunaan Segmentasi dengan Pemberian Halaman pada MULTICS
172Bab 5. Managemen Memori
INTEL
Gambar 5-12. Penggunaan Segmentasi dengan Pemberian Halaman pada INTEL 30386
5.6. Memori Virtual dan Demand Paging
5.6.1. Pengertian
Managemen memori pada intinya adalah menempatkan semua bagian proses yang akan dijalankan kedalam
memori sebelum proses itu dijalankan. Untuk itu, semua bagian proses itu harus memiliki tempat sendiri di
dalam memori fisik.
Tetapi tidak semua bagian dari proses itu akan dijalankan, misalnya:
173Bab 5. Managemen Memori
• Pernyataan atau pilihan yang hanya akan dieksekusi pada kondisi tertentu. Contohnya adalah: pesan-pesan
error yang hanya muncul bila terjadi kesalahan saat program dijalankan.
• Fungsi-fungsi yang jarang digunakan.
• Pengalokasian memori yang lebih besar dari yang dibutuhkan. Contoh: array, list dan tabel.
Pada memori berkapasitas besar, hal-hal ini tidak akan menjadi masalah. Akan tetapi, pada memori yang sangat
terbatas, hal ini akan menurunkan optimalisasi utilitas dari ruang memori fisik. Sebagai solusi dari
masalah-masalah ini digunakanlah konsep memori virtual.
Memori virtual adalah suatu teknik yang memisahkan antara memori logis dan memori fisiknya. Teknik ini
menyembunyikan aspek-aspek fisik memori dari pengguna dengan menjadikan memori sebagai lokasi alamat
virtual berupa byte yang tidak terbatas dan menaruh beberapa bagian dari memori virtual yang berada di memori
logis.
Berbeda dengan keterbatasan yang dimiliki oleh memori fisik, memori virtual dapat menampung program dalam
skala besar, melebihi daya tampung dari memori fisik yang tersedia.
Prinsip dari memori virtual yang patut diingat adalah bahwa: "Kecepatan maksimum eksekusi proses di memori
virtual dapat sama, tetapi tidak pernah melampaui kecepatan eksekusi proses yang sama di sistem tanpa
menggunakan memori virtual."
Konsep memori virtual pertama kali dikemukakan Fotheringham pada tahun 1961 pada sistem komputer Atlas di
Universitas Manchester, Inggris (Hariyanto, Bambang: 2001).
174Bab 5. Managemen Memori
Gambar 5-13. Memori Virtual
Silberschatz, Galvin and Gagne @ 2002
Sebagaimana dikatakan di atas bahwa hanya sebagian dari program yang diletakkan di memori fisik. Hal ini
memberikan keuntungan:
• Berkurangnya proses I/O yang dibutuhkan (lalu lintas I/O menjadi rendah). Misalnya untuk program butuh
membaca dari disk dan memasukkan dalam memory setiap kali diakses.
• Ruang menjadi lebih leluasa karena berkurangnya memori fisik yang digunakan. Contoh, untuk program 10
MB tidak seluruh bagian dimasukkan dalam memori fisik. Pesan-pesan error hanya dimasukkan jika terjadi
error.
• Meningkatnya respon, karena menurunnya beban I/O dan memori.
• Bertambahnya jumlah pengguna yang dapat dilayani. Ruang memori yang masih tersedia luas memungkinkan
komputer untuk menerima lebih banyak permintaan dari pengguna.
Gagasan utama dari memori virtual adalah ukuran gabungan program, data dan stack melampaui jumlah memori
fisik yang tersedia. Sistem operasi menyimpan bagian-bagian proses yang sedang digunakan di memori fisik
(memori utama) dan sisanya diletakkan di disk. Begitu bagian yang berada di disk diperlukan, maka bagian di
175Bab 5. Managemen Memori
memori yang tidak diperlukan akan dikeluarkan dari memori fisik (swap-out) dan diganti (swap-in) oleh bagian
disk yang diperlukan itu.
Memori virtual diimplementasikan dalam sistem multiprogramming. Misalnya: 10 program dengan ukuran 2 Mb
dapat berjalan di memori berkapasitas 4 Mb. Tiap program dialokasikan 256 KByte dan bagian-bagian proses
swap in) masuk ke dalam memori fisik begitu diperlukan dan akan keluar (swap out) jika sedang tidak
diperlukan. Dengan demikian, sistem multiprogramming menjadi lebih efisien.
Memori virtual dapat dilakukan melalui dua cara:
• Permintaan pemberian halaman (demand paging).
• Permintaan segmentasi (demand segmentation). Contoh: IBM OS/2. Algoritma dari permintaan segmentasi
lebih kompleks, karena itu jarang diimplementasikan.
5.6.2. Demand Paging
Demand paging atau permintaan pemberian halaman adalah salah satu implementasi dari memori virtual yang
paling umum digunakan. (Demand paging) pada prinsipnya hampir sama dengan permintaan halaman (paging)
hanya saja halaman (page) tidak akan dibawa ke ke dalam memori fisik sampai ia benar-benar diperlukan. Untuk
itu diperlukan bantuan perangkat keras untuk mengetahui lokasi dari halaman saat ia diperlukan.
Karena demand paging merupakan implementasi dari memori virtual, maka keuntungannya sama dengan
keuntungan memori virtual, yaitu:
• Sedikit I/O yang dibutuhkan.
• Sedikit memori yang dibutuhkan.
• Respon yang lebih cepat.
• Dapat melayani lebih banyak pengguna.
Ada tiga kemungkinan kasus yang dapat terjadi pada saat dilakukan pengecekan pada halaman yang dibutuhkan,
yaitu: halaman ada dan sudah berada di memori. Statusnya valid ("1"). Halaman ada tetapi masih berada di disk
belum diberada di memori (harus menunggu sampai dimasukkan). Statusnya tidak valid ("0"). Halaman tidak
ada, baik di memori maupun di disk (invalid reference --> abort).
Saat terjadi kasus kedua dan ketiga, maka proses dinyatakan mengalami kesalahan halaman. Perangkat keras
akan menjebaknya ke dalam sistem operasi.
5.6.3. Skema Bit Valid - Tidak Valid
Dengan meminjam konsep yang sudah pernah dijelaskan dalam Bagian 5.5, maka dapat ditentukan halaman
mana yang ada di dalam memori dan mana yang tidak ada di dalam memori.
Konsep itu adalah skema bit valid-tidak valid, di mana di sini pengertian valid berarti bahwa halaman legal dan
berada dalam memori (kasus 1), sedangkan tidak valid berarti halaman tidak ada (kasus 3) atau halaman ada tapi
tidak ditemui di memori (kasus 2).
Pengesetan bit:
• Bit 1 --> halaman berada di memori
176Bab 5. Managemen Memori
• Bit 0 --> halaman tidak berada di memori.
(Dengan inisialisasi: semua bit di-set 0)
Apabila ternyata hasil dari translasi, bit halaman = 0, berarti kesalahan halaman terjadi.
5.6.4. Penanganan Kesalahan Halaman
Prosedur penanganan kesalahan halaman sebagaimana tertulis dalam buku Operating System Concept 5th Ed.
halaman 294 adalah sebagai berikut:
• Memeriksa tabel internal yang dilengkapi dengan PCB untuk menentukan valid atau tidaknya bit.
• Apabila tidak valid, program akan di terminasi (interupsi oleh illegal address trap). Jika valid tapi proses
belum dibawa ke halaman, maka kita halaman kan sekarang.
• Memilih frame kosong (free-frame), misalnya dari free-frame list. Jika tidak ditemui ada frame yang kosong,
maka dilakukan swap-out dari memori. Frame mana yang harus di-swap-out akan ditentukan oleh algoritma
(lihat sub bab penggantian halaman).
• Menjadualkan operasi disk untuk membaca halaman yang diinginkan ke frame yang baru dialokasikan.
• Ketika pembacaan komplit, ubah bit validasi menjadi "1" yang berarti halaman sudah diidentifikasi ada di
memori.
• Mengulang instruksi yang tadi telah sempat diinterupsi. Jika tadi kesalahan halaman terjadi saat instruksi
di-ambil, maka akan dilakukan pengambilan lagi. Jika terjadi saat operan sedang di-ambil, maka harus
dilakukan pengambilan ulang, dekode, dan pengambilan operan lagi.
5.6.5. Apa yang terjadi pada saat kesalahan?
Kesalahan halaman menyebabkan urutan kejadian berikut:
• Ditangkap oleh Sistem Operasi.
• Menyimpan register pengguna dan proses.
• Tetapkan bahwa interupsi merupakan kesalahan halaman.
• Periksa bahwa referensi halaman adalah legal dan tentukan lokasi halaman pada disk.
• Kembangkan pembacaan disk ke frame kosong.
• Selama menunggu, alokasikan CPU ke pengguna lain dengan menggunakan penjadualan CPU.
• Terjadi interupsi dari disk bahwa I/O selesai.
• Simpan register dan status proses untuk pengguna yang lain.
• Tentukan bahwa interupsi berasal dari disk.
• Betulkan tabel halaman dan tabel yang lain bahwa halaman telah berada di memory.
• Tunggu CPU untuk untuk dialokasikan ke proses tersebut
• Kembalikan register pengguna, status proses, tabel halaman, dan meneruskan instruksi interupsi.
177Bab 5. Managemen Memori
Pada berbagai kasus, ada tiga komponen yang kita hadapi pada saat melayani kesalahan halaman:
• Melayani interupsi kesalahan halaman
• Membaca halaman
• Mengulang kembali proses
5.6.6. Kinerja Demand Paging
Menggunakan Effective Access Time (EAT), dengan rumus:
EAT = (1-p) x ma + p x waktu kesalahan halaman
• p: kemungkinan terjadinya kesalahan halaman (0 < p < 1)
• p = 0; tidak ada kesalahan halaman
• p = 1; semuanya mengalami kesalahan halaman
• ma: waktu pengaksesan memory (memory access time)
Untuk menghitung EAT, kita harus tahu berapa banyak waktu dalam pengerjaan kesalahan halaman.
Contoh penggunaan Effective Access Time
Diketahui: Waktu pengaksesan memory = ma = 100 nanodetik Waktu kesalahan halaman = 20 milidetik
Maka, EAT = (1-p) x 100 + p (20 milidetik) = 100 - 100p + 20.000.000p = 100 + 19.999.900p (milidetik)
Pada sistem demand paging, sebisa mungkin kita jaga agar tingkat kesalahan halamannya rendah. Karena bila
Effective Access Time meningkat, maka proses akan berjalan lebih lambat.
5.6.7. Permasalahan Lain yang berhubungan dengan Demand Paging
Sebagaimana dilihat di atas, bahwa ternyata penanganan kesalahan halaman menimbulkan masalah-masalah
baru pada proses restart instruction yang berhubungan dengan arsitektur komputer.
Masalah yang terjadi, antara lain mencakup:
• Bagaimana mengulang instruksi yang memiliki beberapa lokasi yang berbeda?
• Bagaimana pengalamatan dengan menggunakan ragam pengalamatan spesial, termasuk autoincrement dan
autodecrement mode?
• Bagaimana jika instruksi yang dieksekusi panjang (contoh: block move)?
Masalah pertama dapat diatasi dengan dua cara yang berbeda.
• komputasi microcode dan berusaha untuk mengakses kedua ujung dari blok, agar tidak ada modifikasi
halaman yang sempat terjadi.
• memanfaatkan register sementara (temporary register) untuk menyimpan nilai yang sempat tertimpa/
termodifikasi oleh nilai lain.
178Bab 5. Managemen Memori
Masalah kedua diatasi dengan menciptakan suatu status register spesial baru yang berfungsi menyimpan nomor
register dan banyak perubahan yang terjadi sepanjang eksekusi instruksi. Sedangkan masalah ketiga diatasi
dengan men-set bit FPD (first phase done) sehingga restart instruction tidak akan dimulai dari awal program,
melainkan dari tempat program terakhir dieksekusi.
5.6.8. Persyaratan Perangkat Keras
Pemberian nomor halaman melibatkan dukungan perangkat keras, sehingga ada persyaratan perangkat keras
yang harus dipenuhi. Perangkat-perangkat keras tersebut sama dengan yang digunakan untuk paging dan
swapping, yaitu:
• tabel halaman "bit valid-tidak valid"
• Valid ("1") artinya halaman sudah berada di memori
• Tidak valid ("0") artinya halaman masih berada di disk.
• Memori sekunder, digunakan untuk menyimpan proses yang belum berada di memori.
Lebih lanjut, sebagai konsekuensi dari persyaratan ini, akan diperlukan pula perangkat lunak yang dapat
mendukung terciptanya pemberian nomor halaman.
5.7. Aspek Permintaan Halaman: Pembuatan Proses
Sistem permintaan halaman dan memori virtual memberikan banyak keuntungan selama pembuatan proses
berlangsung. Pada sub-bab ini, akan dibahas mengenai dua teknik yang disediakan oleh memori virtual untuk
meningkatkan kinerja pembuatan dan pengeksekusian suatu proses.
5.7.1. Copy-On-Write
Dengan memanggil sistem pemanggilan fork(), sistem operasi akan membuat proses anak sebagai salinan dari
proses induk. Sistem pemanggilan fork() bekerja dengan membuat salinan alamat proses induk untuk proses
anak, lalu membuat salinan halaman milik proses induk tersebut.Tapi, karena setelah pembuatan proses anak
selesai, proses anak langsung memanggil sistem pemanggilan exec() yang menyalin alamat proses induk yang
kemungkinan tidak dibutuhkan.
Oleh karena itu, lebih baik kita menggunakan teknik lain dalam pembuatan proses yang disebut sistem
copy-on-write. Teknik ini bekerja dengan memperbolehkan proses anak untuk menginisialisasi penggunaan
halaman yang sama secara bersamaan. halaman yang digunakan bersamaan itu, disebut dengan "halaman
copy-on-write", yang berarti jika salah satu dari proses anak atau proses induk melakukan penulisan pada
halaman tersebut, maka akan dibuat juga sebuah salinan dari halaman itu.
Sebagai contoh, sebuah proses anak hendak memodifikasi sebuah halaman yang berisi sebagian dari stack.
Sistem operasi akan mengenali hal ini sebagai copy-on-write, lalu akan membuat salinan dari halaman ini dan
memetakannya ke alamat memori dari proses anak, sehingga proses anak akan memodifikasi halaman salinan
tersebut, dan bukan halaman milik proses induk. Dengan tekik copy-on-write ini, halaman yang akan disalin
179Bab 5. Managemen Memori
adalah halaman yang dimodifikasi oleh proses anak atau proses induk. Halaman-halaman yang tidak
dimodifikasi akan bisa dibagi untuk proses anak dan proses induk.
Saat suatu halaman akan disalin menggunakan teknik copy-on-write, digunakan teknik zero-fill-on-demand
untuk mengalokasikan halaman kosong sebagai tempat meletakkan hasil duplikat. Halaman kosong tersebut
dialokasikan saat stack atau heap suatu proses akan diperbesar atau untuk mengatur halaman copy-on-write.
Halaman Zero-fill-on-demand akan dibuat kosong sebelum dialokasikan, yaitu dengan menghapus isi awal dari
halaman. Karena itu, dengan copy-on-write, halaman yang sedang disalin akan disalin ke sebuah halaman
zero-fill-on.
Teknik copy-on-write digunakan oleh beberapa sistem operasi seperti Windows 2000, Linux, dan Solaris2.
5.7.2. Memory-Mapped Files
Kita dapat menganggap berkas I/O sebagai akses memori rutin pada teknik memori virtual. Cara ini disebut
dengan "pemetaan memori" sebuah berkas yang mengizinkan sebuah bagian dari alamat virtual dihubungkan
dengan sebuah berkas. Dengan teknik pemetaan memori sebuah blok disk dapat dipetakan ke ke sebuah halaman
pada memori.
Proses membaca dan menulis sebuah berkas ditangani oleh akses memori rutin agar memudahkan mengakses
dan menggunakan sebuah berkas yaitu dengan mengizinkan manipulasi berkas melalui memori dibandingkan
memanggil dengan sistem pemanggilan read() dan write().
Beberapa sistem operasi menyediakan pemetaan memori hanya melalui sistem pemanggilan yang khusus dan
menjaga semua berkas I/O yang lain dengan menggunakan sistem pemanggilan yang biasa.
Proses diperbolehkan untuk memetakan berkas yang sama ke dalam memori virtual dari masing-masing berkas,
agar data dapat digunakan secara bersamaan. Memori virtual memetakan tiap proses ke dalam halaman yang
sama pada memori virtual, yaitu halaman yang menyimpan salinan dari blok disk.
Dengan sistem pemetaan memori, sistem pemangggilan dapat juga mendukung fungsi copy-on-write, yang
mengizinkan proses untuk menggunakan sebuah berkas secara bersamaan pada keadaan read only, tapi tetap
memiliki salinan dari data yang diubah.
Berikut ini merupakan bagan dari proses memory-mapped files.
180Bab 5. Managemen Memori
Gambar 5-14. Bagan proses memory-mapped files
Gambar ini diambil dari buku Applied Operating System, Silberchatz, Galvin, Gagne, edisi VI tahun 2002.
5.8. Konsep Dasar Pemindahan Halaman
Masalah kesalahan halaman pasti akan dialami oleh setiap halaman minimal satu kali. Akan tetapi, sebenarnya
sebuah proses yang memiliki N buah halaman hanya akan menggunakan N/2 diantaranya. Kemudian permintaan
halaman akan menyimpan I/O yang dibutuhkan untuk mengisi N/2 halaman sisanya. Dengan demikian utilisasi
CPU dan throughput dapat ditingkatkan.
181Bab 5. Managemen Memori
Gambar 5-15. Kondisi yang memerlukan Pemindahan Halaman
Gambar di atas diambil dari buku Applied Operating System, Silberchatz, Galvin, Gagne, edisi VI tahun 2002.
Upaya yang dilakukan oleh permintaan halaman dalam mengatasi kesalahan halaman didasari oleh pemindahan
halaman. Sebuah konsep yang akan kita bahas lebih lanjut dalam subbab ini.
Pendekatan untuk pemindahan halaman: "Jika tidak ada frame yang kosong, cari frame yang tidak sedang
digunakan atau yang tidak akan digunakan dalam jangka waktu yang lama, lalu kosongkan dengan
memindahkan isinya ke dalam ruang pertukaran dan ubah semua tabelnya sebagai indikasi bahwa halaman
tersebut tidak akan lama berada di dalam memori."
Dalam pemindahan halaman, frame kosong seperti tersebut di atas, akan digunakan sebagai tempat penyimpanan
dari halaman yang salah.
182Bab 5. Managemen Memori
Gambar 5-16. Pemindahan halaman
Gambar di atas diambil dari buku Applied Operating System, Silberchatz, Galvin, Gagne, edisi VI tahun 2002.
Rutinitas yang dilakukan dalam pemindahan halaman antara lain:
• Mencari lokasi dari halaman yang diinginkan pada disk.
• Mencari frame yang kosong:
• Jika ada, maka gunakan frame tersebut.
• Jika tidak ada, maka tentukan frame yang tidak sedang dipakai atau yang tidak akan digunakan dalam
jangka waktu lama, lalu kosongkan frame tersebut. Gunakan algoritma pemindahan halaman untuk
menentukan frame yang akan dikosongkan.
Usahakan agar tidak menggunakan frame yang akan digunakan dalam waktu dekat. Jika terpaksa, maka
sebaiknya segera masukkan kembali frame tersebut agar tidak terjadi overhead.
• Tulis halaman yang dipilih ke disk, ubah tabel halaman dan tabel frame.
• Membaca halaman yang diinginkan ke dalam frame kosong yang baru.
• Mengulangi proses pengguna dari awal.
183Bab 5. Managemen Memori
Rutinitas di atas belum tentu berhasil. Jika kita tidak dapat menemukan frame yang kosong atau akan
dikosongkan, maka sebagai jalan keluarnya kita dapat melakukan pentransferan dua halaman (satu masuk, satu
keluar). Cara ini akan menambah waktu pelayanan kesalahan halaman dan waktu akses efektif. Olehkarena itu,
perlu digunakan bit tambahan untuk masing-masing halaman dan frame yang diasosiasikan dalam perangkat
keras.
Sebagai dasar dari permintaan halaman, pemindahan halaman merupakan "jembatan pemisah" antara memori
logis dan memori fisik. Mekanisme yang dimilikinya memungkinkan memori virtual berukuran sangat besar
dapat disediakan untuk pemrogram dalam bentuk memori fisik yang berukuran lebih kecil.
Dalam permintaan halaman, jika kita memiliki banyak proses dalam memori, kita harus menentukan jumlah
frame yang akan dialokasikan ke masing-masing proses. Ketika pemindahan halaman diperlukan, kita harus
memilih frame yang akan dipindahkan(dikosongkan). Masalah ini dapat diselesaikan dengan menggunakan
algoritma pemindahan halaman.
Ada beberapa macam algoritma pemindahan halaman yang dapat digunakan. Algoritma yang terbaik adalah
yang memiliki tingkat kesalahan halaman terendah. Selama jumlah frame meningkat, jumlah kesalahan halaman
akan menurun. Peningkatan jumlah frame dapat terjadi jika memori fisik diperbesar.
Evaluasi algoritma pemindahan halaman dapat dilakukan dengan menjalankan sejumlah string acuan di memori
dan menghitung jumlah kesalahan halaman yang terjadi. Sebagai contoh, suatu proses memiliki urutan alamat:
0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101,
0609, 0102, 0105; per 100 bytes-nya dapat kita turunkan menjadi string acuan: 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1.
5.9. Algoritma Pemindahan Halaman
Pemindahan halaman diimplementasikan dalam algoritma yang bertujuan untuk menghasilkan tingkat kesalahan
halaman terendah. Ada beberapa algoritma pemindahan halaman yang berbeda. Pemilihan halaman yang akan
diganti dalam penggunaan algoritma-algoritma tersebut bisa dilakukan dengan berbagai cara, seperti dengan
memilih secara acak, memilih dengan berdasarkan pada penggunaan, umur halaman, dan lain sebagainya.
Pemilihan algoritma yang kurang tepat dapat menyebabkan peningkatan tingkat kesalahan halaman sehingga
proses akan berjalan lebih lambat.
5.9.1. Algoritma First In First Out (FIFO)
Prinsip yang digunakan dalam algoritma FIFO yaitu halaman yang diganti adalah halaman yang paling lama
berada di memori. Algoritma ini adalah algoritma pemindahan halaman yang paling mudah diimplementasikan,
akan tetapi paling jarang digunakan dalam bentuk aslinya, biasanya dikombinasikan dengan algoritma lain.
Pengimplementasian algoritma FIFO dilakukan dengan menggunakan antrian untuk menandakan halaman yang
sedang berada di dalam memori. Setiap halaman baru yang diakses diletakkan di bagian belakang (ekor) dari
antrian. Apabila antrian telah penuh dan ada halaman yang baru diakses maka halaman yang berada di bagian
depan (kepala) dari antrian akan diganti.
Kelemahan dari algoritma FIFO adalah kinerjanya yang tidak selalu baik. Hal ini disebabkan karena ada
kemungkinan halaman yang baru saja keluar dari memori ternyata dibutuhkan kembali. Di samping itu dalam
beberapa kasus, tingkat kesalahan halaman justru bertambah seiring dengan meningkatnya jumlah frame, yang
dikenal dengan nama anomali Belady.
184Bab 5. Managemen Memori
Gambar 5-17. Contoh Algoritma FIFO
Gambar di atas terinspirasi dari buku Applied Operating System, Silberchatz, Galvin, Gagne, edisi VI tahun
2002.
5.9.2. Algoritma Optimal
Algoritma optimal pada prinsipnya akan mengganti halaman yang tidak akan digunakan untuk jangka waktu
yang paling lama. Kelebihannya antara lain dapat menghindari terjadinya anomali Belady dan juga memiliki
tingkat kesalahan halaman yang terendah diantara algoritma-algoritma pemindahan halaman yang lain.
Meskipun tampaknya mudah untuk dijelaskan, tetapi algoritma ini sulit atau hampir tidak mungkin untuk
diimplementasikan karena sistem operasi harus dapat mengetahui halaman-halaman mana saja yang akan diakses
berikutnya, padahal sistem operasi tidak dapat mengetahui halaman yang muncul di waktu yang akan datang.
Komentar
Posting Komentar