BAB 6
MANAJEMEN MEMORI
6.12 Terjadi lubang-lubang kecil memori
+---------------------------+ +---------------------------+
:Memori untuk sistem operasi: :Memori untuk sistem operasi:
+---------------------------+ +---------------------------+
: Proses 0 : Proses 1 : Proses 0 :
+---------------------------+ berakhir +---------------------------+
: Proses 1 : dan mem- : Bebas :
+---------------------------+ bebaskan +---------------------------+
: Proses 2 : memorinya : Proses 2 :
+---------------------------+ +---------------------------+
: Proses 3 : : Proses 3 :
+---------------------------+ +---------------------------+
: Proses 4 : : Proses 4 :
+---------------------------+ +---------------------------+
: Proses 5 : : Proses 5 :
+---------------------------+ +---------------------------+
: Proses 6 : : Proses 6 :
+---------------------------+ +---------------------------+
(a) (b)
+---------------------------+ +---------------------------+
:Memori untuk sistem operasi: :Memori untuk sistem operasi:
+---------------------------+ +---------------------------+
: Proses 0 : Proses 3 : Proses 0 :
+---------------------------+ berakhir +---------------------------+
: Bebas : dan mem- : Bebas :
+---------------------------+ bebaskan +---------------------------+
: Proses 2 : memorinya : Proses 2 :
+---------------------------+ +---------------------------+
: Bebas : : Bebas :
+---------------------------+ Proses 5 +---------------------------+
: Proses 4 : berakhir : Proses 4 :
+---------------------------+ dan mem- +---------------------------+
: Proses 5 : bebaskan : Bebas :
+---------------------------+ memorinya +---------------------------+
: Proses 6 : : Proses 6 :
+---------------------------+ +---------------------------+
(c) (d)
Gambar 6.9 : Alokasi memori secara dinamis.
Contoh terjadinya lubang-lubang di antara partisi-partisi adalah gambar 6.9 :
* Gambar 6-9(a) adalah konfigurasi awal, terdapat 7 proses di ruang memori.
Setelah proses 1 berakhir, konfigurasi memori menjadi gambar 6-9(b).
* Begitu proses 3 berakhir, konfigurasi memori menjadi gambar 6-9(c).
* Proses 5 berakhir, menghasilkan konfigurasi gambar 6-9(d). Memori dipenuhi lubang-lubang memori yang tak terpakai.
Lubang-lubang (yaitu kelompok blok-blok memori yang tidak digunakan) kecil
di antara blok-blok memori yang digunakan dapat diatasi dengan pemadatan
memori (memory compaction). Pemadatan memori adalah operasi menggabungkan
semua lubang kecil menjadi satu lubang besar dengan memindahkan semua
proses agar saling berdekatan.
+---------------------------+ +---------------------------+
:Memori untuk sistem operasi: :Memori untuk sistem operasi:
+---------------------------+ +---------------------------+
: Proses 0 : : Proses 0 :
+---------------------------+ +---------------------------+
: Bebas : +------->: Proses 2 :
+---------------------------+ | +---------------------------+
: Proses 2 :==+ +----->: Proses 4 :
+---------------------------+ | +---------------------------+
: Bebas : | +--->: Proses 6 :
+---------------------------+ | | +---------------------------+
: Proses 4 :====+ | : :
+---------------------------+ | : :
: Bebas : | : BEBAS :
+---------------------------+ | : :
: Proses 6 :======+ : :
+---------------------------+ +---------------------------+
(a) (b)
Gambar 6.10 : Lubang-lubang memori dan pemadatan memori.
Gambar 6-10 menunjukkan skema pemadatan memori. Proses 2, 4, dan 6
dipindahkan agar menampati ruang-ruang berturutan dengan proses 0 sehingga
diperoleh lubang memori besar. Lubang memori besar ini dapat ditempati
proses yang akan masuk.
Kelemahan utama teknik pemadatan memori :
* Memerlukan waktu yang sangat banyak.
* Sistem harus menghentikan sementara semua proses selagi melakukan
pemadatan. Hal in meningkatkan waktu tanggapan di sistem interaktif dan
tak mungkin digunakan di sistem waktu nyata real.
6.13 Proses tumbuh berkembang
Masalah lain pada pemartisian dinamis adalah proses dapat tumbuh berkembang.
Segmen data proses dapat tumbuh, misalnya karena :
* Heap untuk data dinamis berkembang.
* Stack untuk pemanggilan prosedur dan variabel lokal.
Solusi masalah ini adalah bila proses bersebelahan dengan lubang memori tak
dipakai, proses tumbuh memakai lubang itu. Masalah menjadi parah bila proses
bersebelahan dengan proses-proses lain.
Peringkat alternatif penyelesaian adalah :
* Bila masih terdapat lubang besar yang dapat memuat proses, maka proses
dipindah ke lubang memori yang cukup dapat memuat.
* Satu proses atau lebih di swap ke disk agar memberi lubang cukup besar
untuk proses yang berkembang.
* Jika proses tidak dapat tumbuh di memori dan daerah swap di disk telah
penuh, proses harus menunggu atau disingkirkan.
6.14 Pencatatan pemakain memori
Memori yang tersedia harus dikelola, dilakukan dengan pencatatan pemakaian
memori. Terdapat dua cara utama pencatatan pemakaian memori, yaitu :
1. Pencatatan memakai peta bit.
Memori dibagi menjadi unit-unit alokasi,berkorespondensi dengan tiap unit
alokasi adalah satu bit pada bit map.
* Nilai 0 pada peta bit berarti unit itu masih bebas.
* Nilai 1 berarti unit digunakan.
+--------------------------------------------------------------------+
| A B C |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | - | - | | | |
+--------------------------------------------------------------------+
/\ /\ /\
:: :: ::
--+ :: ::
:: :: ::
:: 0 1 2 3 4 ::5 ::6 7
+-------------------------------+
0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 | 0 | 0 | - | - |
2 | 1 | 1 | 1 | 1 | 1 | 0 | - | - |
3 | - | - | - | - | - | - | - | - |
4 | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - |
n | - | - | - | - | - | - | - | - |
+-------------------------------+
Gambar 6-11 : Peta bit untuk pengelolaan pemakaian memori.
Gambar 6-11 menunjukkan skema peta bit untuk pencatatan pemakaian memori.
Elemen peta bit bernilai 1 menunjukkan blok tersebut telah digunakan oleh
proses dan bernilai 0 yang berarti belum digunakan oleh proses.
Masalah
Masalah pada peta bit adalah penetapan mengenai ukuran unit alokasi
memori, yaitu :
* Unit lokasi memori berukuran kecil berarti membesarkan ukuran peta bit.
* Unit alokasi memori n berukuran besar berarti peta bit kecil tapi
memori banyak disiakan pada unit terakhir jika ukuran proses bukan
kelipatan unit alokasi.
Keunggulan :
* Dealokasi dapat dilakukan secara mudah, hanya tinggal menset bit yang
berkorespondensi dengan unit yang telah tidak digunakan dengan 0.
Kelemahan :
* Harus dilakukan penghitungan blok lubang memori saat unit memori bebas.
* Memerlukan ukutan bit map besar untuk memori yang besar.
2. Pencatatan memakai senarai berkait.
Sistem operasi mengelola senarai berkait (linked list) untuk segmen-
segmen memori yang telah dialokasikan dan bebas. Segmen memori menyatakan
memori untuk proses atau memori yang bebas (lubang). Senarai segmen
diurutkan sesuai alamat blok.
+--------------------------------------------------------------------+
| A B C |
| 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | - | - | | | |
+--------------------------------------------------------------------+
Process Starts-at 0 Length Hole
: : : :
: +------+ : :
: : +------------------+ :
v v v v
------- ------- ------- ------- ------- -------
|P|0|5|--->|H|5|2|--->|P|7|5|--->|H|9|2|--->|P|7|2|--->|-|-|-|--->
------- ------- ------- ------- ------- -------
Gambar 6-12 : Pengelolaan pemakaian memori dengan senarai berkait.
Keunggulan :
* Tidak harus dilakukan perhitungan blok lubang memori karena sudah
tercatat di node.
* Memori yang diperlukan relatif lebih kecil.
Kelemahan :
* Dealokasi sulit dilakukan karena terjadi berbagai operasi penggabungan
node-nude di senarai.
6.15 Strategi alokasi memori
Terdapat berbagai strategi alokasi proses ke memori. Alokasi harus mencari
sekumpulan blok memori yang ukurannya mencukupi memuat proses yaitu lubang
kosong yang sama atau lebih besar dibanding ukuran memori yang diperlukan
proses.
Beragam algoritma itu antara lain :
* First-fit algorithm.
Strategi in dapat dilakukan pada pencatatan memori dengan bit map maupun
senarai berkait. Manajer memori menscan sampai menemukan lubang besar yang
mencukupi penempatan proses. Lubang dibagi dua, untuk proses dan lubang
tak digunakan, kecuali ketika lubang tersebut tepat sama dengan ukuran
yang diperlukan proses.
Keunggulan :
· Algoritma ini akan menemukan lubang memori paling cepat dibanding
algoritma-algoritma lain.
* Next-fit algorithm.
Strategi ini dapat dilakukan pada pencatatan memori dengan bit-map maupun
senarai berkait. Mekanisme algoritma ini sama dengan algoritma first fit
algorithm, hanya tidak dimulai di awal tapi dari posisi terakhir kali
menemukan segmen paling cocok.
Simulasi oleh Bays (1977) menunjukkan next-fit algorithm berkinerja lebih
buruk dibanding first-fit algorithm.
* Best-fit algorithm.
Strategi ini dapat dilakukan pada pencatatan memori dengan bit-map maupun
senarai berkait. Algoritma mencari sampai akhir dan mengambil lubang
terkecil yang dapat memuat proses. Algoritma ini mencoba menemukan lubang
yang mendekati ukuran yang diperlukan.
* Worst-fit algorithm.
Strategi ini dapat dilakukan pada pencatatan memori dengan bit-map maupun
senarai berkait. Selalu mencari lubang besar yang tersedia sehingga lubang
dapat dipecah menjadi cukup besar, agar berguna untuk proses-proses
berikutnya. Simulasi menunjukkan worst-fit algorithm bukan gagasan yang
bagus.
* Quick-fit algorithm.
Strategi ini hanya untuk pencatatan memori dengan senarai berkait.
Keempat algoritma dapat dipercepat dengan mengelola dua senarai, yaitu :
· Senarai untuk proses.
· Senarai untuk lubang memori.
Dengan cara ini, saat alokasi hanya perlu menginspeksi senarai lubang,
tidak perlu senarai proses.
Keunggulan :
· Teknik ini mempercepat pencarian lubang atau penempatan proses.
Kelemahan :
· Kompleksitas dealokasi memori bertambah dan melambatkan dealokasi memori
karena memori yang dibebaskan harus dipindahkan dari senarai proses ke
senarai lubang.
* Quick fit.
Cara diatas dapat diperluas, algoritma mengelola sejumlah senarai lubang
memori dengan beragam ukuran yang paling sering diminta.
Contoh :
Algoritma mengelola senarai lubang sebagai berikut :
· Senarai 8 Kb.
· Senarai 12 Kb.
· Senarai 20 Kb.
· Senarai 40 Kb.
· Senarai 60 Kb.
· Dan seterusnya.
Senarai mencatat lubang-lubang memori sesuai ukuran lubang. Lubang-lubang
memori dimuat di senarai sesuai ukuran terdekat, misalnya lubang memori
42 dimuat pada senarai 40 Kb. Dengan beragam senarai maka alokasi memori
dapat dilakukan dengan cepat yaitu tinggal mencarai senarai terkecil yang
dapat menampung proses tersebut.
Keunggulan :
· Algoritma ini sangat cepat dalam alokasi proses.
Kelemahan :
· Dealokasi sulit dilakukan.
Ketika proses berakhir atau dipindah keluar (swap-out) maka menemukan
tetangga-tetangga memori yang dipakai proses untuk penggabungan adalah
sangat mahal/lama. Jika penggabungan tidak dilakukan, memori akan segera
menjadi banyak lubang kecil yang tak berguna.
6.16 Sistem Buddy
Sistem buddy adalah algoritma pengelolaan memori yang memanfaatkan kelebihan
penggunaan bilangan biner dalam pegalamatan memori. Karakteristik bilangan
biner digunakan untuk mempercepat penggabungan lubang-lubang berdekatan
ketika proses terakhir atau dikeluarkan.
Manajer memori mengelola senarai blok-blok bebas berukuran 1, 2, 4, 8, 16
byte dan seterusnya sampai kapasita memori. Pada komputer dengan 1 Mbyte
memori maka dapat terdapat 21 senarai yaitu dari 1 byte sampai 1 Mbyte.
+---------------------------------------------------------------------+
| | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|lubang|
+---------------------------------------------------------------------+
|Semula | | | | | | | | | | | | | | | | | 1 |
|Minta 85 kb | A | | | | | | | | | | | | | | | - |
|Minta 45 kb | A | B| | | | | | | | | | | | | | - |
|Minta 75 kb | A | B| | C | | | | | | | | | | | - |
|A didealokasi | | | B| | C | | | | | | | | | | | - |
|Minta 55 kb | | | B| D| C | | | | | | | | | | | - |
|B didealokasi | | | | D| C | | | | | | | | | | | - |
|D didealokasi | | | | | C | | | | | | | | | | | - |
|C didealokasi | | | | | | | | | | | | | | | | | - |
+---------------------------------------------------------------------+
Gambar 6.13 : Pengelolaan memori dengan sistem Buddy.
Mekanisme pengelolaan :
· Awalnya semua memori adalah bebas dan hanya satu senarai 1 Mbyte yang
terisi berisi satu isian tunggal satu lubang 1 Mbyte. Senarai-senarai
lain adalah kosong.
Misalnya proses baru berukuran 85 Kbyte mekanisme yang dijalankan adalah sbb :
· Karena hanya terdapat senarai berisi 2k, maka permintaan 85 kb dialokasikan
ke yang terdekat yaitu berarti 128 kb, 2k terkecil yang mampu memuat.
· Karena tidak tersedia blok berukuran 128 kb, atau 256 kb atau 512 kb, maka
blok 1 Mb dipecah menjadi dua blok 512 kb. Blok-blok pecahan ini disebut
buddies. Satu beralamat mulai dari 0 dan lainnya mulai alamat 512 k.
· Salah satu blok 512 kb yang beralamat 0 dipecah lagi menjadi dua blok
buddies 256 kb. Satu beralamat mulai dari 0 dan lainnya mulai alamat 256 kb.
· Blok 256 pada alamat 0, kemudian dipecah menjadi 2 blok buddies 128 kb.
· Blok yang pertama dialokasikan ke proses yang baru.
Keunggulan :
· Sistem buddy mempunyai keunggulan dibanding algoritma-algoritma yang
mengurutkan blok-blok berdasarkan ukuran. Ketika blok berukuran 2k
dibebaskan, maka manajer memori hanya mencari pada senarai lubang 2k
untuk memeriksa apakah dapat dilakukan penggabungan. Pada algoritma-
algoritma lain yang memungkinkan blok-blok memori dipecah dalam sembarang
ukuran, seluruh senarai harus dicari.
· Dealokasi pada sistem buddy dapat dilakukan dengan cepat.
Kelemahan :
· Utilisasi memori pada sistem buddy sangat tidak efisien.
Masalah ini muncul dari dari kenyataan bahwa semua permintaan dibulatkan
ke 2k terdekat yang dapat memuat. Proses berukuran 35 kb harus dialokasikan
di 64 kb, terdapat 29 kb yang disiakan. Overhead ini disebut fragmentasi
internal karena memori yang disiakan adalah internal terhadap segmen-segmen
yang dialokasikan.
6.17 Alokasi ruang swap pada disk
Strategi dan algoritma yang dibahas adalah untuk mencatat memori utama.
Ketika proses akan dimasukkan ke memori utama (swap-in), sistem dapat
menemukan ruang untuk proses-proses itu.
Terdapat dua strategi utama penempatan proses yang dikeluarkan dari memori
utama (swap-out) ke disk, yaitu :
· Ruang disk tempat swap dialokasikan begitu diperlukan.
Ketika proses harus dikeluarkan dari memori utama, ruang disk segera
dialokasikan sesuai ukuran proses. Untuk itu diperlukan algoritma untuk
mengelola ruang disk seperti untuk mengelola memori utama. Ketika proses
dimasukkan kembali ke memori utama segera ruang disk untuk swap
didealokasikan.
· Ruang disk tempat swap dialokasikan lebih dulu.
Saat proses diciptakan, ruang swap pada disk dialokasikan. Ketika proses
harus dikeluarkan dari memori utama, proses selalu ditempatkan ke ruang
yang telah dialokasikan, bukan ke tempat-tempat berbeda setiap kali
terjadi swap-out. Ketika proses berakhir, ruang swap pada disk
didealokasikan.
Ke awal
DAFTAR PUSTAKA
1. Hariyanto, Bambang, Ir., Sistem Operasi, Penerbit Informatika, Bandung,
1999
2. Tanenbaum, Andrew S., Modern Operating Systems, Prentice Hall Inc., 1992
Ke Menu
Last updated : 14 Juni 2000