Relocatable Partition Allocation

• Mengumpulkan semua partisi

Contoh :
yang berisikan job ke sebuah
area yang berdekatan, sehingga OS OS
seluruh partisi kosong juga
terkumpul dalam area yang lain Job 1 (20 Kb) Job 1 (20 Kb)
• Proses ini disebut dengan proses
Job 2 (50 Kb) Job 2 (50 Kb)
“COMPACTION” atau
“RECOMPACTION” jika dilakukan Compaction Job 3 (25 Kb)
berulang Free 30 Kb
• Mengakibatkan free area yang
tersedia lebih besar Job 3 (25 Kb) Job 4 (45 Kb)
• Namun tidak selalu menjamin Free 15 Kb
bahwa semua job yang tadinya
tidak bisa dialokasikan, akan Free 45 Kb
Job 4 (45 Kb)
langsung bisa di alokasian
setelah proses compaction

1
 Relocatable Partition Allocation
Kelemahan :
1. Instruksi operating system lebih rumit, karena harus memindahkan
alamat.
2. Memperlambat waktu pemrosesan karena menyita waktu processor
3. Ada kemungkinan free partisi yang terbentuk tetap tidak bisa ditempati,
karena job yang akan dialokasikan relatif lebih besar.

Kelebihan :
Mengurangi fragmentasi, sehingga banyak job yang bisa dialokasikan.
Latihan :

OS Gambarkan perubahan yang terjadi pada memory jika

terjadi event-event seperti dibawah ini dengan
Job P 100 Kb menggunakan metode dynamic partition allocation (First
Fit, Best Fit dan Worst Fit) :
Free Area 250
Kb 1. Job A = 200 Kb
Job Q 100 Kb 2. Job B = 100 Kb
Job R 75 Kb 3. Job R terminated
4. Job C = 50 Kb
Job S 200 Kb
5. Compaction
Free Area 225 Kb
6. Job D = 100 Kb
Job T 100 Kb 7. Job T terminated
Job U 150 Kb
8. Job E = 225 Kb
 PAGE
• Page  job yang dibagi kedalam ukuran yang sama
• Block  memory yang dibagi ke dalam ukuran yang sama
• Satu block hanya untuk satu page
• Sebuah page dapat dialokasikan ke dalam lebih dari satu block
• Page Map Table (PMT)  tabel yang berisikan informasi tentang alamat
PAGE di dalam memory untuk menghubungkan page dan block

PMT Memory
Job A P B OS
Page 0 p0 3 Free area Block 0
Page1 p1 7
Page 1 Block 1
Job B Page 0 Block 2
Page0 p0 2 Page 0 Block 3
Page1 p1 1
Page2 p2 4 Page 2 Block 4
Free area Block 5
Free area Block 6
Page 1 Block 7

4
 PAGE
• Page  job yang dibagi kedalam ukuran yang sama
• Block  memory yang dibagi ke dalam ukuran yang sama
• Satu block hanya untuk satu page
• Sebuah page dapat dialokasikan ke dalam lebih dari satu block
• Page Map Table (PMT)  tabel yang berisikan informasi tentang alamat
PAGE di dalam memory untuk menghubungkan page dan block

5
 PAGE
Kelebihan :
1. Mengurangi fragmentasi
2. Meningkatkan level multiprogramming
3. Penggunaan processor dan memory lebih optimal

Kekurangan :
1. Ruang memory banyak ditempati oleh PMT
2. Pemrosesan relatif lebih lambat (slow down) atau overhead processor
banyak terpakai untuk menangani (mengubah) isi PMT
 PAGE
Pada teknik page ini masih terdapat masalah fragmentasi, khususnya internal
fragmentasi. Fragmentasi yang terjadi karena :
1. Ukuran page lebih kecil dari ukuran block
OS
Page 0 (100 Kb)
Page 1 (100 Kb) Page 0 (100 Kb) Block 0
Free

Page 1 (100 Kb)

Block 1
Free

2. Ukuran page lebih besar dari ukuran block

Page 0 (150 Kb) OS

Page 0 Block 0

Page 1 (150 Kb) Page 0

Free
Block 1

Page 1 Block 2

Page 1
Free Block 3
 DEMAND PAGE
• Page yang dialokasikan ke dalam block hanyalah page yang
dibutuhkan oleh processor
• Page yang tidak dibutuhkan akan disimpan di dalam auxilliary
memory

AM MM CPU

• Page Reference
• Page Fetch
• Page Replacement
• Page Faulted
• Page Successive

8
 Teknik Pengalokasian Block pada Demand Page
• First In First Out (FIFO)
Yaitu : Page yang harus digantikan posisinya oleh page lain yang dibutuhkan
oleh processor / dikembalikan ke Auxiliari Memory (AM) adalah page yang
pertama kali masuk ke dalam block.

• Least Recently Used (LRU)

Yaitu : Page yang harus digantikan posisinya oleh page lain yang dibutuhkan
oleh processor / dikembalikan ke Auxiliari Memory (AM) adalah page yang
telah lama digunakan oleh processor.

• Optimal Replacement (OR)

Yaitu : Page yang harus digantikan posisinya oleh page lain yang dibutuhkan
oleh processor / dikembalikan ke Auxiliari Memory (AM) adalah page yang
masih lama lagi akan dialokasikan / digunakan oleh processor.
Perbandingan tersebut dilakukan dengan melihat page reference yang ada.

9
Contoh :
1. Main memory yang berkapasitas 1 MB (1 MB = 1024 Kb)
dibagi dalam bentuk block-block yang sama besar sebanyak 8
Block dengan ukuran sama besar. Terdapat 2 antrian job-job
yaitu : Job A = 2 page dan Job B = 3 page.
Dimana PMT masing-masing job adalah :
a. PMT Job A alokasi page pada block 3, 7
b. PMT Job B alokasi page pada block 2, 1, 4
Gambarkan bentuk bagan memory setelah dialokasikan Job A
dan B.
Tentukan berapakan jumlah block kosong dan total ukuran
block kosong tersebut.

10
Contoh :
1. Main memory yang berkapasitas 2 MB (1 MB = 1024 Kb)
dibagi dalam bentuk block-block yang sama besar sebanyak
12 Block. Sisa memory digunakan untuk Sistem Operasi
sebesar 248 Kb. Terdapat 3 antrian job-job yaitu : Job X(600
Kb) = 4 page, Job Y (300 Kb) = 2 page, Job Z (450 Kb) = 3 page.
Dimana PMT masing-masing job adalah :
a. PMT Job X alokasi page pada block 11, 3, 5, 1
b. PMT Job Y alokasi page pada block 2, 0
c. PMT Job Z alokasi page pada block 4, 6, 8
Gambarkan bentuk bagan memory setelah dialokasikan Job X,
Y dan Z.
Tentukan berapakan jumlah block kosong dan total ukuran
block kosong tersebut.

11
Contoh :
1. Main memory yang berkapasitas 2 MB (1 MB = 1024 Kb) dibagi dalam bentuk
block-block yang sama besar sebanyak 12 Block. Sisa memory digunakan untuk
Sistem Operasi sebesar 248 Kb. Terdapat 3 antrian job-job yaitu : Job X(600 Kb) = 4
page, Job Y (300 Kb) = 2 page, Job Z (450 Kb) = 3 page.
Dimana PMT masing-masing job adalah :
a. PMT Job X alokasi page pada block 11, 3, 5, 1
b. PMT Job Y alokasi page pada block 2, 0
c. PMT Job Z alokasi page pada block 4, 6, 8
Gambarkan bentuk bagan memory setelah dialokasikan Job X, Y dan Z.
Tentukan berapakan jumlah block kosong dan total ukuran block kosong tersebut.

2. Berdasarkan soal no. 1, setelah job X, Y, dan Z dialokasikan ada Job W datang yang
terdiri dari 5 page (0, 1, 2, 3, 4) dengan ukuran yang sama masing-masing 150 Kb.
Job tersebut juga akan dialokasikan pada block kosong menggunakan Demand
Page dengan Page Reference sebagai berikut : 0 1 3 4 2 0 1 2 3 0 4 2 1 3 1 4 3 2 1 3.
Tentukan jumlah Page Successive, Page Faulted (PF) dan Page Fetch (PFe) yang
terjadi dengan menggunakan salah satu teknik (FIFO/LRU/OR).

12
Soal
1. Main Memori berkapasitas 2 MB dibagi dalam 16 block dan sisa memori digunakan
untuk OS sebesar 448K, terdapat antrian dari beberapa Job.
Dimana PMT masing-masing job adalah :
a. PMT untuk Job A pada block 1, 4, 7, 9, 12
b. PMT untuk Job B pada block 2, 6, 8,10
c. PMT untuk Job C pada block 5, 11, 13, 3
Buatkan bagan memori setelah alokasi Job A, B dan C. Tentukan berapa jumlah
dan ukuran block kosong!

2. Setelah Job A, B, dan C dialokasikan ada beberapa block yang kosong. Kemudian
muncul Job D dengan 5 page (0, 1, 2, 3, 4). Job tersebut akan dialokasikan pada
block yang kosong menggunakan metode Demand Page dengan Page Reference : 1
2 4 0 3 2 1 0 4 3 2 1 3 2 4. Tentukan jumlah Page Succesive (PS), Page Fault (PF) dan
Page Fetch (PFe) dengan menggunakan teknik FIFO/LRU/OR!

13
 SEGMENT
Pada teknik ini digunakan cara program overlays, artinya ketika program ditulis,
dibagi-bagi menjadi suatu program utama (main program) dan beberapa program
bagian (program overlay)

Main memory dibagi ke dalam beberapa area yang disebut dengan SEGMENT
yaitu :
* Main program area  untuk program utama
* Program Overlay Area  untuk program overlay, dapat dipakai
bergantian dengan program overlay lain.
Program Memory

Program OS
Utama

Program Main Program

Segment
Overlay Area

Program Program
Segment
Overlay Overlay Area
14