SISTIM OPERASI (Operating System) IKI-20230 Memory: Part – 2 Ch. 8 Johny Moningka (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001
Memory Management Latar Belakang Address space: lojik vs fisik Swapping Contiguous Allocation Paging Segmentation Segmentation dengan Paging
OS/ JM -2001/v1.1/2
1
Review: load-time binding n n
Link => beri daftar referensi untuk alamat absolut Saat load => dimana proses berada di memori dan ubah alamat tersebut sesuai dengan lokasi.
static a.out 0x3000
OS a.out’ jump 0x5000
jump 0x2000
0x1000
0x6000 0x4000
OS/ JM -2001/v1.1/3
Excecution:base + limit register n
Gunakan bantuan h/w: setiap load dan store ke memori. n
relocation: physical addr = virtual addr + base register
n
protection: check that address falls in [base, base+limit)
OS
a.out 0x3000
a.out jump 0x2000
jump 0x2000
0x1000
0x6000 0x4000
When process runs, base register = 0x3000, limit register = 0x6000. Jump addr = 0x2000 + 0x4000 = 0x5000 OS/ JM -2001/v1.1/4
2
Some terminology n
Definitions: Alamat program: logical atau virtual addresses (LA) Alamat sesungguhnya: physical addresses (PA)
n n
n
Translation (or relocation) mechanism: MMU
Physical addrs
logical addrs CPU
MMU
memory
Dynamic relocation: Setiap instruksi mesin (CPU) dalam bentuk: virtual address => diterjemahkan ke physical address MMU (memory management unit) Setiap proses: mempunyai view (akses dan alokasi) memori fisik yang unik, dikenal address spaces.
n
n
OS/ JM -2001/v1.1/5
Allocation: contiguous n
Memori utama biasanya terbagi dalam dua bagian: n
Bagian rutin/dukungan untuk OS (berada terus di memori => resident): biasanya disimpan dalam memori beralamat rendah (low memory) • Termasuk alamat (list) untuk interrupt vector. • Hardware driver atau interface
n
Bagian proses user (contiguous allocation): • Alokasikan dengan besaran tetap (setiap proses => max. besarnya program).
n
Issue: proteksi untuk setiap area => sederhana n
Termudah: dilakukan partisi (fixed allocation) => kurang flexible, alokasi tidak optimal.
OS/ JM -2001/v1.1/6
3
Hardware support
Range address?
Base address?
Register
Register
Limit
relokasi
Address
Addres
lojik
fisik <
CPU
+
Memori (Physical)
Trap: “Addressing error” OS/ JM -2001/v1.1/7
Example: n
Misal: n
Register relokasi (base register) = 100.040 Register limit (limit register) = 300.000
n
Address lojik = 10.200 (dari CPU) Address fisik = 110.240 (akses ke physical memory)
n
address lojik = 810.000 address fisik= error
OS/ JM -2001/v1.1/8
4
Multiple-Partition Allocation n
n
Partisi Fixed-Sized (MFT) n
Memori dibagi menjadi beberapa blok dengan ukuran tertentu yang seragam
n
Jumlah proses yang bisa running max hanya sejumlah blok yang disediakan(misal IBM OS/360)
Partisi Variabel-Size (MVT) n
Pembagian memori sesuai dengan request dari proses-proses yang ada. • Lebih rumit karena ukuran alokasi (partisi) memori dapat bervariasi
n
Peranan memori manajemen semakin penting: list dari partisi yang digunakan, free dll.
OS/ JM -2001/v1.1/9
Example: multiple allocation OS
OS
OS
OS
OS
P1
P1
P1
Free
P5 Free
P2
Free
P4
P4
P4
P3 Free
P3 Free
Free P3 Free
Free P3 Free
Free P3 Free
P2 selesai
P4 masuk P1 selesai
P5 masuk
OS/ JM -2001/v1.1/10
5
Fragmentasi (issue) n
n
External (masalah variable sized partition): n
Ruang memori free, namun tidak contiguous.
n
Hole-hole ada di antara proses-proses berturutan.
n
Tidak dapat digunakan karena proses terlalu besar untuk menggunakannya.
Internal (masalah fixed size): n
Sifat program dinamis (alokasi dan dealokasi).
n
Memori yang teralokasi mungkin lebih besar dari memori yang diminta (wasted).
OS/ JM -2001/v1.1/11
Paging n
Membagi memori fisik ke dalam blok (page, frame) dengan ukuran tertentu (fixed) yang seragam. n n n
n
Memudahkan manajemen free memory (hole) yang dapat bervariasi. Tidak perlu menggabungkan hole menjadi blok yang besar seperti pada variable partition (compaction). OS lebih sederhana dalam mengontrol (proteksi dan kebijakan) pemakaian memori untuk satu proses.
Standard ukuran blok memori fisik yang dialokasikan (de-alokasi) untuk setiap proses. n
Ukuranya (tergantung OS): 512 byte s/d 16 KB.
OS/ JM -2001/v1.1/12
6
Page Allocation n
Alokasi: n
n n
n
Terdapat “free list” yang menyimpan informasi “frame” di memori fisik yang tidak digunakan Tergantung besarnya proses => memerlukan n pages Alokasi frame diberikan sesuai dengan permintaan (demand, expand).
Implikasi: n
n
User’s (program) view (logical address): memori dialokasikan secara sinambung (contiguous) Fakta (physical address): memori fisik tersebar (noncontiguous) sesuai dengan frame yang dialokasikan.
OS/ JM -2001/v1.1/13
Paging Scheme n
n
Bagaimana menjembatani antara “user’s view” dan alokasi memori sebenarnya? n
Penerjemahan (translasi) alamat logical ke alamat fisik => tugas dari OS (user/program “transparant”).
n
Perlu dukungan hardware (CPU) => address translation.
Setiap proses mempunyai informasi “pages” yang dialokasikan oleh OS n n n
Mapping setiap alamat logical ke alamat fisik Issue: mekanisme mudah, cepat dan efisien. Page table: berisi “base address” (alamat fisik) dari frame yang telah dialokasikan ke proses tsb.
OS/ JM -2001/v1.1/14
7
Page table n n
Setiap OS mempunyai cara menyimpan page table untuks setiap proses Page table bagian dari setiap proses. n
n
n
Page table berada di memori, saat proses tersebut dieksekusi. Informasi page table disimpan oleh PCB: pointer ke page table dari proses tersebut. Setiap kali terjadi context switch => informasi page table untuk proses yang baru harus di restore (misalkan referensi/pointer lokasi page table tsb. di memori).
OS/ JM -2001/v1.1/15
Page table (h/w support) n
Menggunakan “fast register” n
n
n
Contoh: DEC PDP11 : 16 bit address (logical 216 ): 64K, page size 8K (213 ). Memerlukan page table dengan: 8 entry (dapat diterapkan pada hardware register, hanya 3 bit)
Untuk komputer modern sulit menggunakan fast register n
n
Pentium : 32 bit address logical (total: 4 GB), page size (8K), maka mempunyai potensi entry: 524.288 entry. Page table disimpan pada memori (bagian program) dengan menggunakan page table base register • Page-table base register (PTBR) : pointer ke page-table di memori. • Page-table length register (PTLR) : besarnya ukuran page table (karena tidak semua proses memerlukan ukuran page tabel max.)
OS/ JM -2001/v1.1/16
8
Paging: translation •
Address logik dari CPU dianggap terdiri atas dua bagian: •
Page number (p): merupakan indeks dalam tabel yang berisi base address dari tiap page dalam memori fisik
•
Page offset (d): menunjukkan lokasi address memori berdasarkan “base address” pada page tersebut. Page number Page offset p m-n
d n
OS/ JM -2001/v1.1/17
Address: hardware support
Adress
Adress CPU
lojik p
fisik d
f
d
Index: p Memori f
Base address: frame f
fisik
Page Table OS/ JM -2001/v1.1/18
9
Paging Example
logical address
physical address
allocate dynamically
OS/ JM -2001/v1.1/19
Model Paging 0 1 Page 0
Page 2
0 1 2 3
Page 3
Page table
Page 1
1 4 3 7
Memori lojik
Address (p, d) dipetakan ke table index (p) + d (offset)
Page 0
2 3
Page 2
4
Page 1
5 6 7
Memori Page 3
fisik
OS/ JM -2001/v1.1/20
10
Example: n
Misalkan LA: 4 bits (max. logical addres: 16 lokasi)
n
Page size => 4 bytes (ditentukan oleh designer OS). n
n
2 bits: menunjuk ke alamat dari masing-masing byte dalam setiap page tersebut.
Page table: tersisa 2 bits n
Max. 4 entry
n
Jadi setiap proses max. akan menggunakan 4 pages => mencakup seluruh alamat logical.
OS/ JM -2001/v1.1/21
Example: simple (2) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
a b c d e f g h i j k l m n o p
Memori lojik
OS/ JM -2001/v1.1/22
0 1 2 3
4 5 1 2
Page table
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Frame 0 i j k l m n o p
Frame 1 Frame 2 dst.
a b c d e f g h
Memori fisik
11
Example: simple (3) n n
Logical address: 11 10 (program view: 14 desimal => “o”) Page translation (physical memory allocation): n
n
n
Bagian: p (index page) => base address dari frame. Binary 11 => 3 (index = 3 dari page table) => berisi base address untuk frame 2 di memori. Bagian offset: d (displacement) Binary 10 => 2 Alamat fisik: base address frame 2 : 2 * 4 => 8; => 8 + 2 = 10 (berisi “o”).
OS/ JM -2001/v1.1/23
Frame table n
OS harus mempunyai informasi “frame” dari memori fisik: n n
n
n
Berapa banyak frame yang bebas? Mana saja frame yang bebas (identifikasi) => frame table (list) Informasi hubungan antara satu frame dengan page mana dari proses yang aktif List ini akan terus di-update, misalkan jika proses terminate maka semua frame yang dialokasikan akan di kembalikan ke free list.
OS/ JM -2001/v1.1/24
12
Page size n
Fragmentasi internal pada page terakhir n n n
Tidak ada fragmentasi eksternal Fragmentasi internal bisa terjadi Worst-case: • Untuk proses yang memerlukan n page + 1 byte • bila ukuran page = 4096 byte maka akan terbuang 4095 byte / process
n
Besarnya ukuran pages n n
Independent dari program/proses (system wide) Intuitif: small pages preferable • Apakah keuntungan ukuran pages kecil?
n
Page table entry dapat dikurangi dengan memperbesar ukuan pages • Apakah keuntungan ukuran pages besar?
n
Umumnya page disesuaikan dengan kapasitas memori (tipikal) pada sistim (range: 2 – 8 Kbytes)
OS/ JM -2001/v1.1/25
Multilevel Paging n
n
Address logical besar => page table menjadi besar. n
Misalkan: LA => 32 bits, dan ukuran page frame: 12 bits, maka page table: 20 bits (2^20 => 1 MB).
n
Page table dapat dipisah dalam bentuk pages juga, sehingga tidak semua page table harus berada di memori.
Address lojik terdiri atas: section number s, page number p, offset d n
s indeks ke dalam outer page table dan p displacement dalam page table Section number Page number Page offset
OS/ JM -2001/v1.1/26
s
p
d
13
Two level page table 1
.. .
500
.. .
100
.. . Outer-page table
.. .
929
.. .
708
.. .
900
Page table
Page 0 Page 1
.. .
Page 100
.. .
Page 500
.. .
Page 708
.. .
Page 900
.. .
Page 929
.. .
Memori fisik OS/ JM -2001/v1.1/27
Translation: multilevel
pages of page table
OS/ JM -2001/v1.1/28
14
Segmentation n Bagaimana
supaya programmer dapat mengontrol/view memori? (pemetaan program) n
A program is a collection of segments. A segment is a logical unit such as: main program, procedure, function, local variables, global variables, common block, stack,
n
Idea: proses dapat dibagi penyimpanan ke memori sesuai dengan programmer view => proteksi, sharing,
OS/ JM -2001/v1.1/29
Logical View of Segmentation Note: besarnya segment bervariasi 1 4
1 2
shared 3
2 4
text/instruction
data
user space
3 3
physical memory space
OS/ JM -2001/v1.1/30
15
Segment Table n
Big-idea: setiap proses dapat mempunyai lebih dari satu base dan limit register => n n
n
Masing-masing menunjuk ke memori dari segment yang diberikan. Disimpan pada segment table (kumpulan segment dari sebuah proses).
Dimana segment table berada? n n n n
Di memori (sama seperti page table). Segment-table base register (STBR): pointer ke lokasi segment table di memori. Segment-table length register (STLR): besarnya jumlah segment yang digunakan oleh program. Keduanya bagian dari PCB.
OS/ JM -2001/v1.1/31
Segmentation Architecture n
Logical address consists of a two tuple: <segment-number, offset>, n
n
n
Harus diset oleh programmer atau compiler untuk menyatakan berapa besar segment tersebut Implikasi: segment bervariasi besarnya (bandingkan dengan page table: fixed dan single/flat address space => hardware yang menentukan berapa size)
Segment table – mapping dari LA ke PA n
n
base table – berisi lokasi awal dari physical address dimana segment berada di memori. limit table – berisi panjang (besar) dari segmen tersebut.
OS/ JM -2001/v1.1/32
16
Segmentation with Paging n
Intel 386 n
Logical address (32 bits) dibagi atas 2: • Selector: Segment: S (13 bits), Descriptor Table (1 bit: Local or Global); Protection ( 2 bits) • Offset: 16 bits
n
Melalui Descriptor table • Selector menentukan entry pada table, melihat protection, dan menguji limit (tabel berisi informasi limit) • Menghasilkan linear address: Base address segment + offset
n
Logical Linear address: paging (besar page: 4 K), 2 level (10 bits untuk direktori dan 10 bits untuk page number), offset: 12 bits.
OS/ JM -2001/v1.1/33
Intel 30386 address translation
OS/ JM -2001/v1.1/34
17
