Review: Memory & File System SISTIM OPERASI (Operating System) IKI-20230 Johny Moningka (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia Semester 2000/2001
Review: MM n
Apakah fungsi main-memory (user’s view)? n
Memori sebagai tempat penyimpanan instruksi/data dari program • Storage yang cepat sehingga dapat mengimbangi kecepatan eksekusi instruksi CPU • Terdiri dari “array of words/bytes” yang besar • Address digunakan untuk mengakses data (shared oleh CPU dan I/O devices)
n
Management Memory n n
Melacak dan proteksi pemakaian memori (siapa dan berapa besar?). Memilih program mana yang akan diload ke memori dari disk.
1
Problem: Multiprogramming n
Misalkan terdapat 3 program (proses) di memori: 0x0000 OS gcc netscape vi
0x4000 0x7000 0x9000 0xA000
• Kapan gcc diberikan informasi akan diekesekusi pada lokasi 0x4000? • Apa yang harus dilakukan jika gcc memerlukan memory tambahan? • Bagaimana jika yang diperlukan lebih dari memory yang tersisa? • Jika netscape terjadi error dan menulis pada alamat 0x4100? • Apa yang terjadi jika program berhenti eksekusi terminated? Review MM JM -2000/v1.1/3
R: Address Translation n
Apakah perbedaan antara “logical address” dan “physical address”? n
Address lojik: address yang di-generate oleh CPU (disebut juga virtual address) berdasarkan kode/urutan address dari eksekusi proses saat itu. • Independent dari “lokasi” program tersebut berada di memori. • Lokasi eksekusi “code” program, hanya berarti untuk proses tersebut yang sedang dieksekusi.
n
Address fisik: address yang sebenarnya berada pada memori fisik (storage). • Lokasi tertentu yang telah diberikan kepada proses (setiap proses mempunyai alokasi memori tertentu). • Lokasi ini harus diproteksi oleh memory management. Review MM JM -2000/v1.1/4
2
Review: Relocation n
Bagaimana program gcc dapat dieksekusi pada “address fisik” di memori? n n
Saat program di “load ke memori” (load time binding). Menggunakan base register (contiguous allocation). Note: Hal yang sama berlaku untuk dynamic relocation (segementation), hanya bedanya informasi base lokasi memori (address space) telah disimpan pada process table (PCB) dan setiap context switch informasi tersebut di update.
Review MM JM -2000/v1.1/5
Review: load-time binding n
n
Saat linking (build) => generate daftar referensi untuk alamat absolut (symbol table). Saat load => lokasi program di memori (telah diketahui), dan ubah alamat tersebut sesuai dengan lokasi.
OS static gcc 0x3000
0x4000
gcc jump 0x5000
jump 0x2000
0x1000
0x7000
Review MM JM -2000/v1.1/6
3
Base Register n
Gunakan bantuan register (relocation register): setiap akses ke memori. • Base register: berisi informasi relokasi program di memori fisik. • relocation: physical addr = virtual addr + base register
OS
a.out 0x3000
0x4000
a.out jump 0x2000
jump 0x2000
0x7000
0x1000 MMU: base register proses gcc: 0x400
jump 0x6000
When process runs, base register = 0x4000, Jump addr = 0x2000 + 0x4000 = 0x6000 Review MM JM -2000/v1.1/7
Review: Protection n
Jika netscape terjadi error dan menulis pada alamat 0x4100? Bagaimana melakukan proteksi? n
Saat program di “load ke memori” (load time binding): • Dapat diketahui maximum memori yang telah dialokasi => limit address yang dapat diakses. • Simpan limit address => limit register. • Proses hanya dapat mengakses “range”: base address s/d limit address. Jika error tidak mengganggu proses lain.
n
Note: Mekanisme ini menciptakan konsep dasar: segment (range address yang bervariasi) dan paging (range address yang tetap besarnya). Review MM JM -2000/v1.1/8
4
Contoh Kerja MMU
Base register 14000
CPU
Address lojik
Address fisik
346
14346
memori
+ range? Limit register 24000 MMU Review MM JM -2000/v1.1/9
Review: Base & Limit Register n
Keuntungan base & limit register (contiguous allocation): n n
n
Kerugian: hanya ada satu “segment” lokasi memori untuk satu proses!!. n
n
n
n
Sederhana (hardware dan programming): diperlukan 2 register, di update saat context switch dari proses. Relokasi dan proteksi: cepat, hanya perlu addition dan comparison.
Problem 1: growing processes (data bertambah) How to expand gcc? Problem 2: how to share code and data?? Bagaimana gcc dapat menggunakan “code library” yang sama?? Free space How to separate code and data?
Salah satu solusi: multiple segments n “segmentation”
netscape1 gcc netscape 2 p2
Review MM JM -2000/v1.1/10
5
What does a process look like? (Unix) n
Process address space logically divided into “segments”: text (code), data, heap (dynamic data), and stack
function call, return parameter etc
stack
address 2^n-1
malloc(), free()
heap initialized data
address >= 0
code Review MM JM -2000/v1.1/11
Review: Linker n
Apakah perbedaan static shared lib dan dynamic shared lib?
n
Static shared lib: • Define a “shared library segment” at same address in every program’s address space • Every shared lib is allocated a unique range in this seg, and computes where its external defs reside
Review MM JM -2000/v1.1/12
6
Static Linking
0xffe0000 0xfff0000
0xffe0000 0xfff0000
ls
gcc
0xffe0000 0xfff0000
hello 0xffe0000 0xfff0000
libc.a … math.a …
Review MM JM -2000/v1.1/13
Linking variation 2: dynamic shared libs n
Problem: static shared libraries require systemwide pre-allocation address space: kaku tidak flexible! n
n
We want to link code anywhere in address space
Problem 1: linker won’t know how to resolve refs n n n
do resolution at runtime link in stubs that know where to get code from program calls stub, goes and gets code
Review MM JM -2000/v1.1/14
7
Dynamic Linking ls “/usr/shrd-lib/libc.a”
4500
printf: printf_stub: scanf_stub: ...
sscanf:
gcc 9000
...
libc.a
printf_stub: scanf_stub: ...
...
Review MM JM -2000/v1.1/15
Problem 2: Dynamic shared libraries n n
Code must simultaneously run at different locations! Sol’n: make lib code “position independent” n
n
n
refer to routines, data using relative addressing (base + constant offset) rather than absolute addresses 0xf00 printf: ... call 0xf44 0xf44 write: … ...
Example:
libc.a
0x0
printf: ... call libc_base+0x44 0x44 write: …
...
n
internal call “call 0xf44” become “call lib_base + 0x44”
n
“lib_base” contains the base address of library (private to each process) & 0x44 is called routine’s internal offset Review MM JM -2000/v1.1/16
8
Segmentation n
Ide: Proses mempunyai “base + limit” lebih dari satu. n
n
n n
Proses address space dibangun dari sekumpulan “segments” yang tersebar (tidak perlu contiguos allocation untuk proses). Setiap segment menempati alokasi memori yang contiguous, dan ukurannya dapat bervariasi (tidak tetap). Setiap segment mempunyai proteksi sendiri. Setiap segment dapat di “share” (programmer’s view) dengan proses lain.
Review MM JM -2000/v1.1/17
Segmentation Real memory
gcc 0x1000
0x3000
0x5000
0x2000
Text seg r/o
Stack seg r/w 0x6000
0x3000
0x6000 Seg. text: Base:… Limit:.. Protection: read only Shared: yes
0x8000
Seg. stack: base: .. limit: .. Protection: read write Shared: No Review MM JM -2000/v1.1/18
9
Segmentation n
Bagaimana proses melakukan mapping untuk semua segment yang ada (address translation)? n
n
n
Segment table: Setiap proses mempunyai deretan segment yang disimpan pada table. Misalkan: row pada table, berisi informasi untuk satu segment (base, limit, protection, dll). Setiap memori reference menunjukkan pointer ke segment pada table dan offset. • Logical address terbagi dua field: nomor segment pada table dan offset pada segment tersebut. Note: nomor segment => implementasi nomor index pada entry segment table (menghemat bit dan comparison, searching). Review MM JM -2000/v1.1/19
Example: fault Virtual addr 4
no ?
128
Seg# offset
Seg table Prot base len
yes
mem + Seg 4 0x1000
4
0x1000 512
128
Range?
Review MM JM -2000/v1.1/20
10
Segmentation example n
2-bit segment number (1st digit), 12 bit offset (last 3)
Seg base 0 0x4000 1 0x0000 2 0x3000 3 n n n n n
limit 0x6ff 0x4ff 0xfff
rw 10 11 11 00
where is 0x0240? 0x1108? 0x265c? 0x3002? Fault 0x1600? Fault
physical
logical 0x4000
0x4700
0x3000
0x4000
0x2000
0x3000
0x1500 0x1000 0x0700
0x500
0x0000
0x0
Review MM JM -2000/v1.1/21
Segmentation Tradeoffs n
Pro: n n n
Tidak perlu contiguous allocation: Multiple segments per process Allows sharing! (how?) Don’t need entire process in memory!!!
gcc code n
Con: n n
gcc
where? vi
Extra layer of translation speed = hardware support More subtle: an “n” byte segment requires n *contigious* bytes of physical memory. (why?) Makes fragmentation a real problem. Review MM JM -2000/v1.1/22
11
Review: Fragmentation n
Apakah yang dimaksud “fragmentasi” memori? n
n
Ketidak-mampuan OS menggunakan memori yang “tidak digunakan” (free memory).
Terangkan 2 jenis fragmentasi yang ada: n
External fragmentation: • Variable sized allocation (segment): Tersebar “variable sized” yang kecil dari memory yang free, tapi tidak mencukupi untuk alokasi satu segment.
n
Internal fragmentation. • Fixed sized allocation (paging): bagian memori yang tidak digunakan oleh proses tapi telah di-alokasikan. Review MM JM -2000/v1.1/23
Fragmentation
vi
??
External fragmentation
gcc emacs
allocated
stack
Unused (“internal fragmentation”)
doom
Review MM JM -2000/v1.1/24
12
Paging n
Pembagian memori dalam ukuran tertentu (“pages”)
Pages typical: 4k-8k
gcc
vi n
internal frag
Tradeoff: n n n
pro: eliminates external fragmentation pro: simplifies allocation, free and swapping con: internal fragmentation Review MM JM -2000/v1.1/25
Paging:mechanism n
Memory dibagi dalam ukuran tertentu dan tetap (pages) n
n
Setiap proses mempunyai table (“page table”) yang menyimpan informasi pages yang dialokasikan ke proses tersebut. Entry pada page table: mapping virtual page number (VPN) ke physical page number (PPN) • PT entry also includes protection bits (r, w, valid)
n
n
Addressing: virtual address => terbagi atas 2 field: VPN dan offset (max. ukuran pages).
Q: Misalkan MIPS, addressing 32 bit dan besarnya pages: 4 KB, berapa bit untuk VPN dan berapa untuk offset? Review MM JM -2000/v1.1/26
13
Example: Besarnya ukuran pages: 4 KB => 12 bits Jadi offset: 12 bits, VPN: 32 – 12 bits = 20 bits. Virtual addr 3
mem offset: 128
128 (12bits)
VPN
page offset
128
page table Prot
VPN
0x1000
page PPN
?
PPN
“invalid” r pages belum ada di memori fisik!
3
1
Review MM JM -2000/v1.1/27
Page tables (vs segmentation) n
Good: n n
n
Mudah untuk alokasi: karena ukuran tetap, operasi dapat dilakukan dengan bantuan hardware untuk mapping VA ke PA. Manajemen pages: daftar pages yang free dapat dikumpulkan dalam free list.
Bad: n
Ukuran page table: PTs memerlukan satu entry untuk setiap page => perlu storage lebih besar untuk menyimpan informasi PT. • e.g., given a range [0x0000, 0xffff => 64 KB] need one segment descriptor but, assuming 4K pages, 16 page table entries
B=0x0,len=0xffff
0x0000
Page table
0xFFFF Review MM JM -2000/v1.1/28
14
Page size tradeoffs
More
Overhead &
locality
Internal frag & writeback cost
page size n
Small page = large PT overhead: n n
n
32-bit address space with 1k pages. How big PT? Lokalitas program tidak terakomodasi tersebar ke banyak pages => page faults dapat meningkat.
Large page = internal frag (doesn’t match info. size) n n
Transfer time 1 pages at page faults? Write back untuk satu pages yang telah diupadte => lama Review MM JM -2000/v1.1/29
15