ISU DISAIN SISTEM PAGING

1.  Model Working Set

Ø  Dalam bentuk paging murni, proses dimulai dengan memori kosong, dan page-page dimasukkan ke dalamnya setelah diminta. Cara ini disebut demand paging.

Ø  Locality of reference: Kecenderungan proses untuk memakai satu set page yang sama selama beberapa saat.

Ø  Satu set page tersebut di atas membentuk working set. Dalam hal ini, yang diusahakan oleh sistem operasi adalah agar working set berada utuh di memori pada saat eksekusinya.

Ø  Jika ukuran memori terlalu kecil untuk working set, akan seringkali terjadi page fault. Hal ini disebut thrashing.

Ø  Banyak sistem paging yang mengusahakan agar working set sudah ada di memori sebelum proses dimulai. Pendekatan ini disebut model working set. Tujuannya adalah untuk memperkecil jumlah terjadinya page fault (page yang diminta tidak ada di memori).

Ø  Memasukkan page ke memori sebelum proses dimulai juga disebut prepaging.

Ø  Untuk pertama kali menentukan working set, dipakai sistem aging untuk mengetahui berapa kali jumlah pemakaian setiap page.

2. Alokasi Global dan Lokal

o    Pada sistem timesharing, isi memori bisa seperti pada Gambar a.

o    Misalkan diminta page A6. Jika dikeluarkan A5 untuk memberi tempat ke A6, berarti dilakukan alokasi lokal. Bila yang dikeluarkan adalah B3, dilakukan alokasi global.

o    Algoritma lokal berhubungan dengan pemberian jumlah frame yang sama untuk setiap proses, sementara algoritma global secara dinamis mengalokasikan frame untuk proses yang berjalan.

	Age
A0	10	A0		A0
A1	7	A1		A1
A2	5	A2		A2
A3	4	A3		A3
A4	6	A4		A4
A5	3	A5 -> A6		A5
B0	9	B0		B0
B1	4	B1		B1
B2	6	B2		B2
B3	2	B3		B3 -> A6
B4	5	B4		B4
B5	6	B5		B5
B6	12	B6		B6
C1	3	C1		C1
C2	5	C2		C2
C3	6	C3		C3

                            (a)                                     (b)                                   (c)

Penggantian page global vs. lokal. (a) Konfigurasi awal.

(b) Penggantian page lokal. (c) Penggantian page global.

3.  Ukuran Page

o    Ukuran page merupakan salah satu parameter yang ditentukan oleh perancang sistem operasi.

o    Penentuan ukuran page yang optimum harus menyeimbangkan beberapa faktor.

o    Rata-rata, page terakhir hanya akan terisi setengah (fragmentasi internal), berarti page sebaiknya kecil. Tetapi page yang kecil akan menghasilkan tabel page yang panjang.

Ø  s (byte)        =     ukuran proses rata-rata

Ø  p (byte)        =     ukuran page

Ø  e (byte)        =     ukuran setiap page entry

Ø  s/p              =     perkiraan jumlah page yang dibutuhkan per-proses

Ø  se/p (byte)   =     ruang untuk tabel page

Ø  p/2              =     memori yang terbuang karena fragmentasi

Ø  overhead     =     memori yang terpakai untuk tabel page dan fragmen internal.

overhead = se/p + p/2

Ø  Ukuran tabel page besar jika ukuran page kecil. Fragmen internal besar jika ukuranb page besar. Optimum harus ada di antaranya. Dengan mengambil penurunan pertama terhadap p dan menyemakan dengan nol:            -se/p² + ½ = 0

Ø  Dari persamaan ini, ukuran page optimum adalah: p = Ö(2se)

Ø  Sebagian besar komputer komersial menggunakan ukuran page antara 512 byte – 8K.

4.         Isu Implementasi

Ø  Instruction backup

Instruksi yang menyebabkan referensi ke page yang belum ada di memori (menyebabkan page fault) harus diulang ketika page tersebut telah tersedia. Beberapa sistem operasi meng-copy setiap instruksi sebelum dilaksanakan sehingga hal ini tidakmakan waktu terlalu lama.

Ø  Locking pages in memory

Pada saat satu proses menjalani tahap I/O, proses lain bisa dijalankan. Yang mungkin terjadi ialah page proses I/O tersebut digantikan oleh proses yang kedua ini (jika dipakai alokasi global). Jalan keluarnya ialah dengan me-lock page-page proses I/O.

Ø  Shared pages

Dua atau lebih proses bisa memakai bersama page-page yang berasal dari editor yang mereka pakai. Penutupan salah satu proses ini tanpa disengaja bisa mengosongkan juga page yang dipakai bersama tersebut. Diperlukan suatu struktur data khusus untuk memantau page-page yang dipakai bersama ini.

Ø  Backing Store

Pada disk, disediakan area untuk menampung page yang dikeluarkan dari memori (paged out) yang disebut swap area. Setiap proses memiliki swap area di disk. Swap area ada yang statis ada juga yang dinamis.

Ø  Paging Daemon

Untuk meyakinkan tersedianya frame bebas yang cukup banyak, banyak sistem paging yang menggunakan proses background yang disebut paging daemon. Jika jumlah frame bebas terlalu sedikit, paging daemon akan mengosongkan beberapa page setelah menulisnya ke disk jika pernah dimodifikasi.

Ø  Penanganan Page Fault

Urutan langkah-langkah penanganan adalah sebagai berikut:

1.       Hardware melakukan trap ke kernel, program counter di-save ke stack. Pada banyak mesin, beberapa informasi tentang status instruksi saat itu di-save di register-register khusus CPU.

2.       Rutin kode assembly dimulai untuk men-save register-register umum dan informasi lain yang bisa berubah, agar sistem operasi tidak merusaknya. Rutin ini memanggil sistem operasi sebagai suatu prosedur.

3.       Sistem operasi menemukan bahwa terjadi page fault, dan mencoba menemukan page virtual mana yang diperlukan. Seringkali salah satu register hardware berisi informasi ini. Jika tidak, sistem operasi harus menarik program counter, mengambil instruksi, dan melakukan parsing pada software untuk mengetahui apa yang dilakukan sebelum terjadi fault.

4.       Begitu alamat virtual yang menyebabkan fault diketahui, sistem operasi memeriksa apakah alamat ini valid dan proteksinya konsisten dengan akses. Jika tidak, proses dikirimi sinyal atau ditutup. Jika alamat valid dan tidak ada pelanggaran proteksi, sistem berusaha untuk mendapatkan frame page dari daftar frame bebas. Jika tidak ada frame yang bebas, dijalankan algoritma penggantian page untuk mencari yang bisa ditukar.

5.       Jika frame page yang dipilih telah dimodifikasi, page dijadwalkan untuk ditransfer ke disk, dan terjadi pertukaran proses, menghentikan sementara proses yang fault dan membiarkan yang lainnya berjalan hingga transfer disk selesai. Frame ditandai terpakai untuk mencegah dipakai untuk tujuan lain.

6.       Begitu frame page bersih (apakah langsung atau setelah disave ke disk), sistem operasi menelusuri alamat disk di mana page diperlukan, dan menjadwalkan operasi disk untuk memasukkannya. Sementara page dimasukkan, proses yang mengalami fault dihentikan sejenak dan yang lainnya dijalankan, jika ada.

7.       Ketika disk interrrupt menandai bahwa page telah ada, tabel page di-update untuk menunjukkan posisinya, dan frame ditandai berada dalam status normal.

8.       Instruksi yang menyebabkan fault di-back-up ke status mulainya dan program counter di-reset untuk menunjuk ke instruksi tersebut.

9.       Proses yang fault tersebut dijadwalkan, dan sistem operasi kembali ke rutin bahasa assembly yang memanggilnya.

10.     Rutin ini mengembalikan register dan informasi lainnya ke keadaan semula , dan kembali ke user untuk melanjutkan eksekusi, seakan-akan tidak ada fault yang terjadi.

SEGMENTASI

Compiler bisa memiliki beberapa tabel dengan alamat virtual yang terpisah, misalnya terdiri dari tabel-tabel untuk:

1.      Source text,

2.      Tabel simbol,

3.      Tabel untuk semua konstanta integer dan floating point,

4.      Parse tree, berisi analisis sintaksis program, dan

5.      Stack yang digunakan untuk pemanggilan prosedur.

Tabel 1 s/d 4 bisa bertambah pada saat kompilasi berjalan, sehingga dengan sistem paging yang berukuran tetap, batas satu page bisa terlampaui.

Dengan alasan ini dipakai bagian-bagian dengan alamat yang relatif independen, yang disebut segmen. Setiap segmen mempunyai ukuran yang berbeda dengan yang lain. Panjang segmen juga bisa berubah selama eksekusi.

Program harus menyediakan alamat yang terdiri dari dua bagian:

-        nomer segmen

-        alamat di dalam segmen

Segmentasi juga memberikan fasilitas pemakaian bersama prosedur atau data antar beberapa proses. Contoh umumnya adalah shared library.

	Segmen		Segmen		Segmen		Segmen		Segmen
	0		1		2		3		4
0		0		0	Konstanta	0		0
4K		4K				4K		4K
			Source				Parse		Call
			text				tree		stack
8K		8K				8K		8K
	Tabel
	simbol
12K		12K				12K		12K
16K						16K
20K

Memori yang tersegmentasi memungkinkan setiap tabel bertambah atau berkurang.

Pertimbangan	Paging	Segmentasi
Apakah programmer harus menyadari bahwa teknik ini sedang digunakan?	Tidak	Ya
Berapa banyak ruang alamat linier yang ada?	1	Banyak
Dapatkah ruang alamat total melebihi ukuran memori fisik?	Ya	Ya
Apakah tabel yang ukurannya berubah-ubah dapat diakomodasi?	Tidak	Ya
Dapatkan prosedur dan data dibedakan dan diproteksi secara terpisah?	Tidak	Ya
Adakah fasilitas pemakaian bersama prosedur antar user?	Tidak	Ya
Mengapa teknik ini diciptakan?	Untuk mendapatkan ruang alamat linier yang besar tanpa harus membeli memori fisik tambahan	Untuk memungkinkan program dan data dibagi menjadi ruang alamat yang secara logik independen dan untuk membantu pemakaian bersama dan proteksi

Perbandingan paging dan segmentasi.

Checkerboarding: Timbulnya blok-blok memori yang kosong (hole) pada saat isi segmen dikeluarkan. Hal ini diatasi dengan pemampatan (compaction).

Segmentasi dengan Paging : Setiap segmen dapat dianggap sebagai satu virtual memori, dan masing-masing dibagi menjadi page-page.

Salah satu mesin yang memakai cara ini adalah MULTICS. Setiap program MULTICS memiliki satu tabel segmen, dengan satu descriptor per segmen. Segmen descriptor berisi keterangan apakah segmen yang bersangkutan ada di memori atau tidak.

Segmen descriptor		Tabel page untuk segmen 0
36 bit		Page 0 entry
Descriptor segmen 0		Page 1 entry		Pointer-
Descriptor segmen 1		Page 2 entry		pointer
Descriptor segmen 2		Page 3 entry		ke page
Descriptor segmen 3
Descriptor segmen 4
Descriptor segmen 5		Tabel page untuk segmen 1
Descriptor segmen 6		Page 0 entry
Descriptor segmen 7		Page 1 entry
		Page 2 entry
		Page 3 entry
		Page 4 entry
		Page 5 entry