Sistem Operasi Komputer. Pertemuan VIII Manajemen Memori

Sistem Operasi Komputer

Sistem Operasi Komputer Pertemuan VIII – Manajemen Memori

Pembahasan Manajemen Memori • • • • • • •

Latar belakang dan konsep dasar Strategi Ruang alamat lojik dan fisik Swapping Pencatatan pemakaian memori Monoprogramming Contiguous allocation: partisi statis, partisi dinamis, sistem Buddy • Non-contiguous allocation: paging, segmentation

Universitas Kristen Maranatha -- IT Department

1


Konsep dasar • Von Neumann system data dan program harus tersimpan dalam lokasi yang sama (memori), dengan urutan instruction, fetch, execution • Meningkatkan utilitas CPU • Data dan instruksi dapat diakses dengan cepat • Efisiensi pemakaian memori • Efisiensi transfer data dari/ke memori utama ke/dari CPU CPU

Mem.utama RAM

Mem. Sekunder DISK

Penggunaan CPU dan memori


2


Syarat manajemen memori • Relokasi translasi memori referensi ke alamat fisik • Proteksi user tidak dapat mengakses bagian system • Sharing sharing area pada memori utama • Organisasi lojik SOK dan hardware berhubungan dengan program user dalam satu modul • Organisasi fisik pengaturan memori utama dan sekunder pada long-term scheduling

Hirarki manajemen memori • Register • Cache • Memori utama • Magnetic disk • Magnetic tape Semakin ke bawah: – – – –

Biaya per bit semakin rendah Kapasitas semakin besar Waktu akses semakin besar Frekuensi pengaksesan memori oleh prosesor semakin rendah


3


Konsep binding • Proses penempatan (perpindahan alamat) suatu item ke dalam lokasi memori tertentu, dapat terjadi pada saat: – Compile time: lokasi memori diketahui sebelumnya, contoh: pada DOS (*.com) – Load time: relocatable code – Execution time: memerlukan dukungan hardware dalam pemetaan alamat, contoh: base dan limit register

Pemrosesan bertingkat program user


4


Ruang alamat lojik dan fisik • Alamat lojik (logical address) diturunkan oleh CPU • Alamat fisik (physical address) alamat yang berada dalam memori • Compile time alamat lojik dan fisik sama • Execution time – Alamat lojik virtual address – Kumpulan alamat lojik yang diturunkan dari program lojik adress space – Alamat fisik yang berhubungan dengan alamat lojik physical address space

• Run time pemetaan alamat virtual ke alamat fisik oleh memory management unit (MMU) dari hardware

Relokasi dinamis ruang alamat

execution time


run time

5


Dynamic Loading • Hanya bagian program yang penting saja yang tinggal di memori • Suatu routine tidak akan dipanggil sampai ia dibutuhkan • Tidak perlu campur tangan SOK, tergantung pada user • SOK menyediakan library

Dynamic Linking • Konsep sama dengan dynamic loading, penekanan pada linking • Memungkinkan adanya share library antar program user • Contoh: *.dll, *.sys, *.drv • SOK dibutuhkan untuk mengakses memori pada alamat-alamat yang sama dari beberapa proses


6


Overlay • Membagi program yang besar menjadi bagian-bagian yang lebih kecil sehingga dapat dimuat dalam memori utama (jika proses lebih besar dari kapasitas memori) • Program penggerak berada dalam memori utama • Bagian pendukung diletakkan dalam memori sekunder

Swapping • Pengalihan proses dari memori ke tempat penyimpanan sementara • Dipanggil lagi ke memori jika diperlukan • Contoh: multiprogramming dengan algoritma RR • Tanpa swapping monoprogramming dan multiprogramming dengan partisi statis • Swapping multiprogramming dengan partisi dinamis • Ditemukan dalam banyak sistem: Linux, Unix dan Windows 2000 • Tantangan: transfer time proporsional dengan jumlah data yang di-swap


7


Swapping backing store dalam disk

Pencatatan pemakaian alokasi memori (1) • Peta bit (Bit map) – – – – –

Memori dibagi dalam beberapa alokasi unit Tiap unit terdiri dari beberapa word sampai beberapa kByte Tiap unit berhubungan dengan 1 bit, 0 jika kosong, 1 jika terisi Ukuran unit sangat penting 32n bit unit memori memerlukan n bit map

A

B

C

D

1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1

Bit map 1 unit memori dengan 32 bit

0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1


8


Pencatatan pemakaian alokasi memori (2) • Linked list – Setiap node terdiri atas informasi Process (P) atau Hole (H), lokasi awal dan panjang lokasi – Penggunaan memori lebih kecil – Tidak perlu perhitungan blok lubang memori – Dealokasi sulit dilaksanakan (karena terjadi penggabungan atau pemekaran beberapa node) P 0

5

H

5 3

P 18 7

P 8

H 25 3

8

H 16 2

P 28 4

Pengalokasian Memori • Monoprogramming • Multiprogramming – Berurutan (Contiguous Allocation) • Partisi Statis • Partisi Dinamis • Sistem Buddy

– Tidak Berurutan (Non Contiguous Allocation) • Paging • Segmentasi


9


Monoprogramming • Pengalokasian memori ke suatu proses relatif sederhana, hanya satu proses menggunakan memori pada setiap saat • Penggunaan ROM dan RAM, untuk program user dan sistem operasi Sistem operasi di RAM

Sistem operasi di RAM User program di RAM

User program di RAM

User program di RAM Sistem operasi di ROM

Device driver di ROM

Hardware support relokasi dan limit register

• Jika SOK diletakkan pada lokasi memori rendah, perlu adanya proteksi terhadap memori • Menggunakan base dan limit register secara dinamis (nilai alamat berubah-ubah) • Operasi transient penghilangan fasilitas layanan SOK sementara dari memori, lokasi digunakan untuk proses lain dari user


10


Pengalokasian Berurutan (Contiguous Allocation)

• Multiprogramming system – Residen alokasi untuk SOK (di alamat rendah/atas atau alamat tinggi/bawah) 0 Sistem operasi – User program

• Strategi: – Partisi statis – Partisi dinamis – Sistem Buddy

User program

512

Multiprogramming Partisi Statis • Membagi memori dalam beberapa partisi dengan ukuran tetap • Beberapa proses dalam waktu bersamaan menggunakan memori memori dibagi dalam partisi dengan ukuran tertentu • Tiap partisi digunakan oleh satu proses • Jika telah selesai dapat digunakan oleh proses lain • Contoh SOK: IBM OS2/360, dengan memori management Multiprogramming with a Fixed Number of Tasks (MFT)


11


Partisi Statis Ukuran Sama • Proses-proses yang hendak masuk memori diletakkan pada sembarang partisi kosong • Ukuran request lebih besar dari partisi tidak dialokasikan, perlu dibuat overlay • Dapat timbul sisa-sisa yang memboroskan (internal fragmentation), jika alokasi proses-proses kurang dari kapasitas partisi SOK Partisi 1

256 Kbyte

Partisi 2

256 Kbyte

Partisi 3

256 Kbyte

Partisi 4

256 Kbyte

Partisi Statis Ukuran Tidak Sama (1) • Tiap partisi memiliki ukuran yang tidak sama • Banyak antrian (satu antrian untuk tiap partisi) – Proses ditempatkan pada partisi dengan ukuran terkecil yang dapat memuatnya – Ada partisi tertentu yang panjang antriannya – Ada partisi yang kosong – Meminimumkan pemborosan memori

• Satu antrian untuk seluruh partisi – Proses yang memiliki ukuran kecil ditempatkan pada partisi dengan ukuran besar (internal fragmentasi) – Fleksibel implementasi – Operasi minimum (hanya satu antrian)


12


Partisi Statis Ukuran Tidak Sama (2)

P5

P2

P3

P1

P4

P6

SOK

SOK

Partisi 1

Partisi 1

Partisi 2

Partisi 2

Partisi 3

Partisi 4

P3 P4 P5

Partisi 5

P2

P1

Partisi 3

Partisi 4

Partisi 5

P6

Multiprogramming Partisi Dinamis (1) • Partisi baru akan dibuat setelah suatu proses masuk ke memori • Problem: – Muncul lubang-lubang kecil antara 2 proses yang ditempatkan – Menyulitkan dalam alokasi dan dealokasi – External fragmentation ada beberapa lubang dengan kapasitas total yang cukup besar untuk suatu proses, namun lubang-lubang tidak saling berdekatan – Diperlukan compaction, penempatan ulang proses yang ada dalam memori dan diatur sedemikian rupa sehingga posisi lubang berdekatan – Compaction dapat dilakukan jika relokasi bersifat dinamis dan dilakukan pada saat compile time – Adanya segmen data yang berkembang sebagai akibat heap atau stack yang memanggil prosedur atau variabel lokal


13


Multiprogramming Partisi Dinamis (2) Job Queue Proses Memory Request Waktu (ms)

0

P1

600 K

10

P2

1000 K

5

P3

300 K

20

P4

700 K

8

P5

500 K

15

0

400

SOK

400

P1 1000

SOK P1

1000 P2 selesai

P2 2000 2300

400

2000

P3

2300

2560

2560

P3

SOK P1

1000 Alokasi P4 1700 2000 2300

400 P1 selesai

SOK

1000

P4

1700 2000

P3

2300

2560

P4 P3

2560

400 Alokasi P5 900 1000 1700 2000 2300

SOK P5 P4 P3

2560

Compaction 0 300 500 600

SOK

SOK

SOK

SOK

P1 P2

P1 P2 P3

P1 P2

P1 P2

400 K 1000 1200 1500 1900 2100

P3 300 K P4

P4

900 K

P4 P3

900 K

900 K

P4

200 K

P3 Pindah P3 dan P4 (600K)


Pindah P4 (400K)

Pindah P3 (200K)

14


Strategi compaction • First fit pencarian dari awal, berhenti jika ditemukan lokasi pertama yang cukup besar • Next fit sama dengan first fit, namun pencarian tidak dimulai dari awal, tapi dari lokasi terakhir menemukan segmen yang cocok • Best fit pencarian dari awal, dan akan berhenti jika ditemukan lokasi terkecil pertama yang cukup • Worst fit pencarian dari awal, dan akan berhenti jika ditemukan lokasi yang terbesar yang cukup • Quick fit cocok untuk pencatatan dengan linked list. Algoritma dirancang dengan membuat list lubang. Lubang memori dimuat di list sesuai dengan ukuran terdekatnya. Contoh: list lubang 8, 12, 20, 40 dan 60 Kb. Jika ada lubang memori sebesar 42 Kb, akan ditempatkan di list 40

Sistem Buddy • Pengelolaan memori dengan memanfaatkan kelebihan bilangan binair (2k; k = 0,1,2,… ) • Dealokasi proses dapat berlangsung cepat • Terjadi internal fragmentation Semula Alokasi proses A (90 Kb)

A

Alokasi proses B (50 Kb)

A

B

Alokasi proses C (72 Kb)

A

Dealokasi proses A

B B

Alokasi proses D (35 Kb)

B

Dealokasi proses B

C C D

C

D

C

Dealokasi proses D

C

Dealokasi proses C 0

128


256

512

1M

15


Non Contiguous Allocation Paging • Memori logika dibagi dalam blok-blok (page) • Memori fisik dibagi dalam blok-blok dengan ukuran tertentu (frame) • Setiap alamat yang diberikan CPU – Nomor page (p) – Nomor offset (d)

• p digunakan sebagai indeks dari page table yang berisi base address untuk tiap page pada memori fisik • Base address dikombinasikan dengan offset untuk mendapatkan alamat fisik memori • Ukuran frame dan page (ukuran keduanya sama !!), ditentukan oleh hardware, bervariasi antara 29 sampai 213 tergantung arsitektur komputer

Skema Paging Nomor page Nomor offset

p m-n

d n

2m = ukuran alamat lojik 2n = ukuran satu page m dan n dalam satuan word atau byte


16


Contoh paging (1)

Contoh paging (2) • Ukuran page = 4 byte

• Ukuran memori fisik = 32 byte (8 frame) • Alamat lojik 0 ada di page 0, offset 0 • Pada page table terlihat page 0, dipetakan ke frame 5, dengan alamat fisik ((5 * 4) + 0 = 20) • Alamat lojik 3 (page 0, offset 3), dipetakan ke alamat fisik ((5 * 4) + 3) = 23


17


Frame bebas • Jika proses datang untuk eksekusi, maka ukurannya diekspresikan dengan page • Setiap page butuh satu frame

Sebelum alokasi

Setelah alokasi

Implementasi Page Table (1) -- PTBR • Page table disimpan dalam memori • Page table base register (PTBR): – Instruksi untuk load atau modifikasi dilakukan secara privileged – Contoh pada DEC-PDP 11 mini computer – Entry page table harus dibatasi relatif kecil (misalnya 256 entry)

• Butuh 2 kali akses ke memori: – 1 untuk entry page table – 1 untuk byte – Akses diperlambat sebagai fungsi 2k


18


Implementasi Page Table (2) -- TLB • Transaction Look-Aside Buffer (TLB) atau associative memory, sebagai perbaikan dari perlambatan akses ke memori pada PTBR • Kumpulan dari register pada cache atau memori berkecepatan tinggi #Page #Frame

Translasi alamat (A´, A´´) – Jika A’ pada register asosiatif A’’ , ambil #Frame – Jika tidak, ambil #Frame dari page table di memori

Implementasi Page Table (3) -- TLB


19


Proteksi memori • Dengan cara menambahkan satu bit proteksi pada tiap frame: Read/Write atau Read Only • Pada page table diberi tambahan valid/invalid bit • Valid page ada pada kawasan ruang alamat lojik • Invalid page tidak ada

Valid/Invalid Page Table


20


Struktur Page Table – Multilevel • Membagi ruang alamat lojik ke dalam beberapa page tables • Misal: – Komputer 32 bit – Ukuran page 4 Kbyte – Alamat lojik dibagi menjadi suatu nomor page 20 bit, dan page offset 12 bit – Nomor page dibagi lagi menjadi 10 bit nomor page dan 10 bit page offset page number pi 10

page offset

p2

d

10

12

pi indeks ke page table yang lebih luar, dan p2 adalah yang ditunjuk dari page table yang lebih luar tersebut

Page table 2 level


21


Struktur Page Table – Hashed Page Table

Struktur Page Table – Inverted Page Table


22


Sharing Kode (Multiuser Environment)

Non Contiguous Allocation Segmentasi • User view memori utama sebagai kumpulan segmen dengan ukuran berbeda dari suatu program • Segmen adalah unit lojik seperti: – – – – – – – – –

main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table, arrays


23


Alamat Ruang lojik

Cara pandang user Pada saat user program di1 compile, terbentuk segmensegmen yang merefleksikan 4 1 input program. Contoh pada Pascal: 2 (1) Varibel global (2) Procedure call stack yang 3 2 menyimpan parameter dan 4 alamat kembali 3 (3) Porsi kode untuk tiap prosedur dan fungsi (4) Variabel lokal untuk prosedur user space physical memory space dan fungsi Tiap segmen dituliskan sebagai identitas dan offset: <segment-number, offset>


24


Pemetaan segmen • Pemetaan ke alamat fisik dilakukan dengan menggunakan tabel segmen • Tiap entry berisi base dan limit

Contoh segmentasi


25


Segmentasi – proteksi dan sharing • Kumpulan proteksi terhadap segmen – Memberi array untuk tiap-tiap segmen – Pengaturan memori hardware secara otomatis – Array yang ditunjuk legal atau tidak (tidak melebihi limit register)

• Sharing kode atau data – Dua proses yang berbeda akan menempati lokasi yang sama pada lokasi fisik

Segmentasi – Sharing dan proteksi


26


Latihan Soal (1) 1. Sebutkan hal-hal yang perlu dipertimbangkan dalam melakukan manajemen memori! 2. Berikan alasan mengapa suatu SOK tidak menggunakan metode pemetaan bit dalam melakukan pencatatan alokasi memori! 3. Berikan alasan mengapa suatu SOK menggunakan sistem paging dalam melakukan manajemen memori! 4. Apakah tugas utama dari MMU (Memory Management Unit)?

Latihan Soal (2) 5.

Suatu sistem komputer memiliki memori utama dengan kapasitas sebesar 16 Mbyte. Diketahui ukuran page sebesar 64 byte. 1. Berapa jumlah frame yang tersedia ? 2. Jika suatu Program ABC berukuran 914 byte, berapa page yang dibutuhkan ? 3. Apabila diketahui page table sebagai berikut: Nomor page

Nomor frame

0

8

1

2

2

10

3

22

4

12

5

1

…

…

dengan asumsi bahwa program memerlukan page secara berurutan dari 0 sampai n, dimanakah letak alamat fisik dari alamat logika: 10, 101 dan 350?


27


KUIS Paging and Segmentation (1) 1.

Paging: Diketahui suatu ruang alamat lojik sebesar 8 pages dengan masingmasing memuat 1024 bytes. Alamat lojik ini dipetakan pada alamat fisik dengan ruang alamat fisik sebesar 32 frame. a. Berapa bit dibutuhkan untuk menuliskan alamat lojik ? b. Berapa bit dibutuhkan untuk menuliskan alamat fisik ? c. Berapakah alamat fisik untuk alamat-alamat lojik berikut ini: 2110 dan 44. Nomor page Nomor frame Diketahui page table sbb: 0 8 1

2

2

18

…

…

d. Berapakah total ruang alamat fisik yang tersedia ?

KUIS Paging and Segmentation (2) 2.

Segmentation: Physical address =Base address + Logical Address Diketahui segment table sbb Segment 0 1 2 3

Base 219 2300 90 1327

Length 600 14 100 580

4

1952

96

segment offset

Apakah alamat fisik dari alamat lojik berikut ini: 0(430), 1(10), 2(500), 3(400), 4(112)


28

Sistem Operasi Komputer. Pertemuan VIII Manajemen Memori

Recommend Documents