Bab 8: Manajemen Memori. Latar Belakang

Bab 8: Manajemen Memori  Latar Belakang  Swapping  Alokasi Berurutan ((Contiguous g Allocation))  Paging  Segmentasi  Segmentasi dengan Paging

Operating System Concepts

9.1

Silberschatz, Galvin and Gagne 2002

Latar Belakang  Program harus dibawa ke dalam memori dan

ditempatkan dalam sebuah proses untuk dijalankan  Input queue (antrian input) – kumpulan proses pada disk

yang menunggu dibawa ke memori untuk menjalankan program  Program user melalui beberapa langkah sebelum

dijalankan


9.2


1

Pengikatan instruksi dan data ke memori Pengikatan alamat instruksi dan data ke alamat dapat terjadi dalam 3 bentuk yang berbeda  Waktu Kompilasi (Compile time): Jika lokasi memori

diketahui sebelumnya, kode absolut dapat dibangkitkan; harus kompilasi ulang kode tsb jika terjadi perubahan lokasi awal.  Waktu Load (Load time): Harus membangkitkan kode relocatable (relocatable code) jika lokasi memori tidak diketahui pada waktu kompilasi.  Waktu Eksekusi (Execution time): Pengikatan alamat ditunda sampai waktu runtime jika prose dapat dipindah selama eksekusi program dari satu segmen memori ke segmen memori lain. Memerlukan dukungan hardware untuk pemetaan alamat (contoh : register base dan limit).


9.3


Langkah Pemrosesan Program User


9.4


2

Loading Dinamis (Dynamic Loading)  Rutin tidak di-load sampai dipanggil  Utilitas ruang memori yang lebih baik; rutin yang

tidakdigunakan tidak pernah di-load.  Berguna ketika kode dalam jumlah besar diperlukan untuk menangani kasus yang tidak sering terjadi.  Tidak memerlukan dukungan khusus dari sistem operasi yang diimplementasikan dalam desain program.


9.5


Linking Dinamis (Dynamic Linking)  Proses linking ditunda sampai waktu eksekusi  Merupakan kode dalam bentuk kecil (stub), digunakan

untuk meletakkan rutin librari yang residen di memori yang diperlukan.  Stub mengubah alamat rutin dan mengeksekusi rutin  Sistem operasi melakukan cek apakah rutin sedang memproses alamat memori  Linking dinamis terutama berguna untuk library


9.6


3

Overlay  Menyimpan hanya instruksi dan data dalam memori

hanya yang diperlukan pada waktu tertentu.  Diperlukan jika proses lebih besar daripada jumlah

alokasi memori untuk proses tersebut.  Diimplementasikan oleh user tidak ada dukungan khusus

dari sistem operasi, desain sistem dari strukutr overlay sangat komplek.


9.7


Overlay untuk Two-Pass Assembler


9.8


4

Ruang alamat Logika dan Fisik  Konsep ruang alamat logika yang membungkus ruang

alamat fisik adalah bentuk utama dari manajemen memori.  Alamat logika – dibangkitkan oleh CPU; juga disebut alamat

virtual.  Alamat Fisik – alamat yang terlihat pada unit memori.

 Alamat logika dan fisik mempunyai skema yang sama

dalam pengikatan alamat pada waktu kompilasi dan waktu load; alamat logika dan fisik mempunyai skema yang berbeda dalam pengikatan alamat pada waktu eksekusi.


9.9


Memory-Management Unit (MMU)  Perangkat hardware yang memetakan alamat virtual ke

alamat fisik.  Dalam skema MMU, nilai dalam register relokasi

ditambahkan ke setiap alamat yang dibangkitkan oleh proses user pada waktu dikirim ke memori.  Program user melihat alamat logika; tidak pernah melihat

alamat fisik.


9.10


5

Relokasi Dinamis menggunakan register relokasi


9.11


Swapping  Sebuah porses dapat ditukar sementara keluar dari memori ke

backing store, dan kemudian dibawa kembali ke memori untuk melanjutkan eksekusi.  Backing store – disk ukuran cukup besar dan cepat untuk

mengakomodasi duplikasi dari semua gambaran memori untuk semua user; harus tersedia akses langsung ke memori tersebut.  Roll out, roll in – swapping menggunakan algoritma

penjadwalan berbasis prioritas; prose dengan prioritas rendah ditukar keluar sehingga proses dengan prioritas tinggi dapat diload dan dieksekusi.  Bagian terbesar dari waktu swap adalah waktu transfer; total

waktu transfer proporsional dengan jumlah memori yang diswap  Versi modifikasi dari swappling ditemukan pada beberapa

sistem, misalnya UNIX, Linux dan Windows.


9.12


6

Skema Swapping


9.13


Alokasi Berurutan (Contiguous Allocation)  Memori utaa biasanya dibagi menjadi 2 bagian:  Sistem operasi yang residen; biasanya diletakkan memori bagian rendah dengan vektor interrupt  Program user diletakkan di memori bagian lebih tinggi.  Alokasi Single-partition (partisi tunggal)  Skema register relokasi digunakan untuk melindungi proses user dari proses user lain, dan dari perubahan kode dan data sistem operasi.  Register relokasi berisi nilai dari alamat fisik terkecil; register limit berisi jangkauan alamat logika – setiap alamat logika harus lebih kecil daripada register limit.


9.14


7

Dukungan Hardware untuk Register Relokasi dan Register Limit



9.15

Alokasi Berurutan (Contiguous Allocation) lanj  Alokasi Multiple-partition (partisi banyak)  Hole (lubang) – adalah blok dari memori yang tersedia; lubang dengan ukuran berbeda berada di dalam memori.  Bila proses datang, akan dialokasikan ke memory pada lubang yang cukup untuk proses.  Sistem operasi memelihara informasi tentang: a) partisi yang dialokasikan b) partisi bebas (hole)

OS

OS

OS

OS

process 5

process 5

process 5

process 5

process 9

process 9

process 8 process 2


process 10 process 2

process 2

9.16

process 2


8

Alokasi Multiple Partition  Sebagai ilustrasi, perhatikan contoh berikut :  Diasumsikan tersedia memori 2560K dan untuk OS 400K. Sisa 2160K di digunakan k untuk t k user proses  Diasumsikan terdapat 5 job (P1 s/d P5) terdapat pada input queue.  Diasumsikan penjadwalan FCFS digunakan untuk load job ke memori. Penjadwalan CPU secara round-robin (quantum time = 1) untuk penjadwalan job yang sudah terdapat di memori



9.17

Alokasi Multiple Partition (lanj.) 0

Operating p g system

Proses

400K

2160K

Job queue memory

time

P1

600K

10

P2

1000K

5

P3

300K

20

P4

700K

8

P5

500K

15

2560K Operating System Concepts

9.18


9

Alokasi Multiple Partition (lanj.) 0

Operating system

400K

0 400K

Operating system t

1000K P2

1000K

P2

Alokasi

2000K

P3

2300K 2560K

2560K Operating System Concepts

400K

Operating system

0

Operating system

400K P5 900K 1000K

1000K P4

P1

P4

terminate

P4 1700K P3

0

P1

1000K

terminate

2300K

400K

Operating system

P1

P1

2000K

0

P3

2300K 2560K

2300K 2560K

9.19

P4

P5

2000K

2000K

Alokasi

2000K P3

2300K

P3

2560K


Permasalahan alokasi ruang dinamis Bagaimana memenuhi permintaan ukuran n dari daftar lubang yang bebas  First-fit: alokasi lubang pertama yang cukup untuk proses.  Best-fit: alokasi lubang terkecil yang cukup untuk proses;

harus mencari ke seluruh daftar; berdasarkan urutan ukuran. Menghasilkan lubang sisa yang terkecil.  Worst-fit: mengalokasikan lubang terbesar; harus juga mencari ke seluruh daftar. Menghasilkan lubang sisa terbesar. First-fit dan best-fit lebih baik daripada worst-fit dalam hal kecepatan dan utilitas ruang penyimpan.


9.20


10

Fragmentasi  Fragmentasi Eksternal – ruang alamat memori total

yang ada memenuhi permintaan, tetapi letaknya tidak berurutan.  Fragmentasi Internal – pengalokasian memori mungkin lebih besar daripada memori yang diminta; tetapi sisanya terlalu kecil yang tidak dapat digunakan.  Menurunkan fragmentasi eksternal dengan cara pemadatan  Memindahkan isi memori dan meletakkan semua memori

bebas dalam satu blok besar.  Pemadatan mungkin hanya jika relokasi dinamis dan

dilakukan pada waktu eksekusi


9.21


Pemadatan  Solusi untuk masalah fragmentasi eksternal adalah “compaction”

(p (pemadatan) )  Compaction tidak selalu dapat dipakai. Agar proses dapat

dieksekusi pada lokasi baru, semua alamat internal harus direlokasi. Jika relokasi statik dan dikerjakan pada load time, compaction tidak dapat dilakukan  Compaction mungkin hanya jika relokasi dinamis dan dikerjakan pada execution time. Karena relokasi membutuhkan pemindahan program dan data dan kemudian mengubah register basis (atau relokasi) yang mencerminkan alamat basis baru  Terdapat beberapa cara compaction


9.22


11

Pemadatan lanj. 0 400K

0

Operating system

400K

P5

P5

900K 1000K

900K

100K P4

P4 1600K

2000K 2300K 2560K

Operating system

300K

P3

1900K

P3 660K 260K

2560K

Contoh Compaction Operating System Concepts


9.23

Pemadatan lanj.

0 300K 500K 600K

Operating system t P1 P2 400K

1000K 1200K

P3

0 300K 500K 600K 800K

0

Operating system t

300K

P1

500K

P2

600K

P3

Operating system t P1 P2

0 300K 500K 600K

Operating system t P1 P2

P4 1000K

P4 1200K

1200K

900K

P3

300K 1500K

900K

P4 1900K

900K

P3 2100K

2100K Alokasi asal


P4

1900K

200K

2100K

1500K

Dipindah 600K 9.24

2100K Dipindah 400K

Dipindah 200K


12

Paging  Ruang alamat logika dari proses dapat tidak berurutan; proses

diletakkan di memori fisik jika tersedia  Membagi memori fisik ke dalam blok ukuran tetap yang disebut

    

frame (ukurannya adalah pangkat dari 2 2, antara 512 bytes dan 8192 bytes). Membagi memori logika ke dalam blok ukuran sama yang disebut page. Menyimpan semua frame bebas. Untuk menjalankan sebuah program ukuran n page, perlu menemukan frame bebas sebanyak n dan load program. Set page table (tabel page) untuk menterjemahkan alamat logika ke alamat fisik. Kemungkinan terjadi fragmentasi internal.


9.25


Skema Menterjemahkan Alamat  Alamat yang dibangkitkan oleh CPU terdiri dari:  Page number (p) – digunakan sebagai indeks dalam page table yang berisi alamat base dari setiap page dalam memori fisik. fisik  Page offset (d) – dikombinasikan dengan alamat base untuk

menentukan alamat fisik yang dikirim ke unit memori.


9.26


13

Arsitektur Penterjemah Alamat


9.27


Contoh Paging


9.28


14

Contoh Paging


9.29


Frame Bebas

Sebelum alokasi


Setelah alokasi

9.30


15

Implementasi Page Table  Page table disimpan dalam memori utama.  Page-table base register (PTBR) menunjuk ke page table.  Page-table g length g register g ((PRLR)) merupakan p ukuran p page g

table.  Pada skema ini, setiap akses data/instruksi membutuhkan

dua kali akses memori. Satu untuk mengakses page table dan satu untuk mengakses data/instruksi.  Permasalahan akses kedua memori dapat dipecahkan dengan menggunakan fast-lookup hardware cache khusus yang disebut associative memory or translation look-aside buffers (TLBs)



9.31

Associative Memory  Associative memory – pencarian paralel Page #

Frame #

Terjemahan alamat (A´, A´´)  Jika A´ berada dalam associative register, dapatkan frame #  Jika tidak, dapatkan frame # dari page table dalam memori


9.32


16

Paging Hardware dengan TLB


9.33


Effective Access Time  Pencarian pada Associative register =  unit waktu  Diasumsikan waktu akses memori adalah 1 microsecond  Hit ratio – p persentasi waktu sebuah nomor p page g

ditemukan dalam associative registers; rasio berhubungan dengan jumlah associative register.  Hit ratio =   Effective Access Time (EAT) EAT = (1 + )  + (2 + )(1 – ) =2+–


9.34


17

Proteksi Memori  Proteksi memori diimplementasikan dengan proteksi bit

untuk setiap frame.  Bit Valid-invalid diberikan untuk setiap masukan dalam

page table:  “valid” mengindikasikan bahwa page terhubung dalam

alamat memori logika dan merupakan page yang legal.  “invalid” mengindikasikan bahwa page tidak berada di ruang

alamat logika.


9.35


Bit Valid (v) atau invalid (i) Bit dalam Page Table


9.36


18

Contoh Two-Level Paging  Alamat logika (pada mesin 32-bit dengan ukuran page 4K) dibagi

ke dalam:  Sebuah page number ukuran 0 bit.  Sebuah S b h page offset ff t ukuran12 k 12 bit bit.

 Ketika page table dilakukan page, page number lebih lanjut

dibagi dalam :  Sebuah page number 10-bit.  Sebuah page offset 10-bit.

 Sehingga alamat logika menjadi:

page number pi 10

page offset

p2

d

10

12

dimana pi adalah indek ke outer page table, dan p2 adalah displacement dalam page dari outer page table. Operating System Concepts

9.37


Skema Two-Level Page-Table


9.38


19

Skema Penterjemah Alamat  Skema Penterjemah alamat untuk arsitektur two-level

paging 32-bit


9.39


Shared Page  Shared code  Satu copy dari kode read-only yang digunaka bersamasama diantara beberapa proses (seperti text editors, compilers window compilers, indo systems). s stems)  Shared code harus muncul pada lokasi yang sama dalam ruang alamat logika untuk semua proses.  Private code dan data  Setiap proses menyimpan copy dari kode dan data yang terpisah  Page dari private code dan data dapat muncul dimanapun dalam ruang alamat logika.


9.40


20

Contoh Shared Page


9.41


Segmentasi  Skema manajemen memori yang memperlihatkan memori dari

sisi pandangan user.  Sebuah program adalah kumpulan segmen. Sebuat segmen

adalah unit logika g seperti p : main program, procedure, function, method, object, local variables, global variables, common block, stack stack, symbol table, arrays


9.42


21

Pandangan user terhadap Program


9.43


Segmentasi secara Logika 1 4

1 2

3

2

4

3

Ruang User


Ruang alamat Fisik

9.44


22

Arsitektur Segmentasi  Alamat logika terdiri dari dua bagian:

<segment-number, offset>,  Segment g table – memetakan alamat fisik 2 dimensi;; setiap tabel mempunyai:  base – terdiri dari alamat fisik awal dimana segmen berada

di memori.  limit – menentukan panjang segmen.

 Segment-table base register (STBR) menunjuk ke lokasi

segment table dalam memori.  Segment-table g length g register g ((STLR)) merupakan p nomor

segmen yang digunakan oleh ; nomor segmen s adalah legal jika s < STLR.


9.45


Arsitektur Segmentasi (lanj)  Relokasi.  Dinamis  Oleh segmen table  Sharing.  Membagi segment bersama-sama  Nomor segment sama  Alokasi.  first fit/best fit  Fragmentasi eksternal


9.46


23

Arsitektur Segmentasi (lanj)  Proteksi. Dalam setiap masukan ke segment table

dihubungkan dengan:  Bit validasi= 0  segmen ilegal  Mode akses read/write/execute

 Bit proteksi dihubungkan dengan segmen; kode yang

digunakan bersama-sama terjadi pada level segmen  Karena segmen mempunyai ukuran yang bervariasi,

alokasi memori adalah permasalahan alokasi penyimpanan dinamis


9.47


Hardware Segmentasi


9.48


24

Contoh Segmentasi


9.49


Sharing Segmen


9.50


25

Segmentasi dengan Paging – MULTICS  Sistem MULTICS memecahkan permasalahan

fragmentasi eksternal dan pada saat pencarian dengan paging pada segmen  Solusi berbeda dengan segmentasi asli, di dalam

segment-table, masukan tidak terdiri dari alamat base dari segmen, tetapi alamat base dari page table untuk segmen tersebut.


9.51


Skema Penterjeman Alamat pada MULTICS


9.52


26

Segmentasi dengan Paging – Intel 386

 Sebagaimana ditunjukkan pada diagram berikut, Intel 386

menggunakan segmentasi dalam paging untuk manajemen memori dengan skema two-level paging


9.53


Penterjeman Alamat pada Intel 30386


9.54


27

Bab 8: Manajemen Memori. Latar Belakang

Recommend Documents