Sistem Operasi – 13 – Memory 1: Address Translation and Virtual Memory

Sebuah metode memory management yang menyediakan ilusi kepada program akan adanya dedicated memory, dan memory yang sangat besar (virtually unlimited)

Read more: Sistem Operasi – 13 – Memory 1: Address Translation and Virtual Memory

Sumber Utama

Time seek	Note: CS162 Lecture 13: Memory 1: Address Translation and Virtual Memory
25:10	Program loading, compiling, linking, and apply address translation.
31:28	From program to process
57:01	Hardware accelerated address translation: intel x86 special registers.
57:48	Simulation of multi-segment address translation.
1:13:00	Page table
1:26:00	Linux 32-bit memory layout (pre-meltdown patch!)

Time seek	Note: CS162 Lecture 14: Memory 2: Virtual Memory (Con’t), Caching and TLBs
45:14	last read (sharing with multilevel page tables)
26:57	two-level page table
31:32	example multi level page table: x86 classic 32 bit
35:50	page table entry
51:30	example multi page table: x86 model with segmentation (16/32-bit)
58:00	x86_64 four level page table
1:06:56	Where and what is the MMU

Poin-poin Penting

• Jika memory-address memiliki panjang k bit, maka maksimal terdapat 2^k slot memory yang dapat dialamatkan.
• Misalnya jika sebuah program diberikan virtual address space dari 0000 sampai dengan FFFF, maka copy of that program juga akan mendapatkan virtual address space yang sama, akan mendapatkan layout memory yang sama, meskipun physical address nya berbeda.
• Keuntungan:
  • Dalam hal sistem operasi menjalankan beberapa program sekaligus (orkestrasi), address translation memberikan memory layout yang sama:
    • programmer tidak peduli dengan physical address. program copy 1 dan copy 2 akan memiliki virtual address space yang sama, sehingga assembly code yang sama dapat berjalan sekaligus beberapa instance.
    • maka ini dikatakan address translation memberikan ilusi dedicated machine pada semua program.
  • memory protection, dimana sebuah program tidak bisa menakses address space untuk program yang lain, karena program melihat address space virtual, bukan physical. Sedangkan algoritma address translation menjamin tidak ada collision pada address pace.
  • Ilusi unlimited memory. Dalam hal memory tidak cukup, maka sistem operasi dapat memindahkan address space yang ditempati program yang tidak sedang jalan (thread in sleep state) ke disk. proses ini disebut dengan swapping. Dan jika thread yang sedang sleep ini berubah jadi ready to run, maka memory yg ada di disk akan dipindahkan kembali ke address space semula, dan ada kemungkinan jika tidak cukup, program lain juga harus di swap memory nya ke disk.
• Kapan terjadinya translation:
  • saat proses linking
  • menggunakan hardware khusus (MMU: memory management unit), translation terjadi setiap instruction fetch:
    • prosesor selalu melihat address sebagai virtual address, dan tidak pernah aware dengan address translation. jika prosesor melakukan fetch ke DRAM, barulah terjadi translation tanpa sepengetahuan prosesor.
    • jika prosesor mengambil data dari pointer, misalnya load constant ke suatu register, maka tidak terjadi fetch ke DRAM, maka tidak terjadi translation. dan lagi-lagi prosesor tidak aware dengan tidak adanya address translation.
• Sistem operasi dapat mendeteksi kurangnya alokasi memori untuk sebuah program. Misalnya sebuah instruction melakukan fetch ke virtual address, kemudian di-translate oleh MMU, tapi hasilnya melebihi bound-nya, ini pertanda alokasi memory nya kurang besar.

---

Latar Belakang

Adanya kebutuhan untuk virtualisasi resources. Kenyataan menunjukkan tiap-tiap process/thread akan saling berbagi hardware yang sama:

• Kebutuhan untuk multiplexing CPU → sudah dibahas di bab sebelumnya.
• Kebutuhan untuk multiplexing Memory → akan dibahas di bab ini.
• Kebutuhan untuk multiplexing disk dan devices → akan dibahas di bab berikutnya.

Apa yang perlu diperhatikan dalam sharing memory

Complete state yang merepresentasikan process/thread baik user process maupun kernel process, adalah data yang tersimpan di memory dan register.

Tiap tiap process/thread akan memiliki memory address space yang terpisah (protection), dan bergantian menempati register.

Konsekuensinya: perlu kepastian sebuah process/thread tidak dapat mengakses memory pada address space untuk process/thread yang lain (protection), kecuali diizinkan (inter-process communication). Dengan kata lain, 2 process yang berbeda tidak bisa menempati lokasi memory yang sama.

Dengan adanya virtualisasi, maka dari sudut pandang process, memory address akan sama. misalnya process A menempati address space 0000 sampai FFFF, begitu juga process B. Namun, physical address space yang disediakan sistem operasi untuk process A berbeda dengan process B, dan tidak ada irisannya.

Ingat kembali 4 konsep utama dalam sistem operasi

1. Thread: execution context → representasi program dalam bentuk instruction, data (heap and stack), program counter, register, execution flag.
2. address space → instruction dan data menempati address space tertentu.
3. Process: protected address space + 1 atau lebih thread.
4. dual mode operation: kernel mode vs user mode.
   • hanya kernel mode yang memiliki akses ke resources tertentu (misalnya: disk)
   • jika dikombinasi dengan memory translation, akan menghasilkan isolation, artinya sebuah process tidak bisa mengakses address space process yang lain (protection), dan juga dapat memisahkan OS (kernel) dan user process.

Konsep dasar: address space

Konstruksi fisik RAM

Hardware RAM (Random Access Memory), ada kata random disana memiliki makna kalau setiap alamat memory dapat diakses secara langsung. Kita bebas mengakses sebuah memori di alamat tertentu, secara langsung kapan saja. Jadi maksud random adalah bebas mengakses yang mana saja kapan saja. Hal ini kontras dengan spinning disk, dimana harus menunggu head tepat pada posisi sebelum melakukan pembacaan.

Perhatikan konstruksi RAM (oversimplified) dibawah ini:

Untuk mengakses memory dalam RAM, harus ditentukan dulu alamat mana yang akan dibaca. Pada diagram diatas, alamat ini diterima RAM melalui data bus dengan panjang 32 bit, yang secara fisik berupa 32 pin (electronic pinout).

Pada diagram konstruksi diatas, input yang diterima RAM diubah oleh multiplexer menjadi kabel mana yang akan diaktifkan, sesuai input yang diterima, sehingga alamat memori tersebut bisa diakses.

Dengan konfigurasi data bus 32 bit (32 pinout), masing-masing pin mewakili 1 bit biner, sehingga 32 pin ini memiliki maksimal kombinasi data biner sebanyak 2³² = 4,294,967,296 alamat = 4,194,304K = 4,096M = 4G. Catatan: 2¹⁰ = 1024 = 1K.

Pada diagram diatas 1 alamat memory memiliki kapasitas 8 bit, ini disebut dengan 8 bit word = 1 byte word. Jika RAM memilki 32 bit memory address, dan 1 byte word, maka maksimal kapasitas RAM yang bisa didukung adalah 4G * 1 Byte = 4GB.

Formula diatas bisa dibali, misalnya jika ada RAM 1 byte word dengan kapasitas 32GB, berapa jumlah bit minimal yang diperlukan untuk mengakses semua memori tersebut?

32GB / 1 Byte = 32G = 34,359,738,368 = 2³⁵ → 35 bit.

Dari contoh diatas menjadi masuk akal jika sistem 32 bit tidak mendukung RAM 32GB.

Ilustrasi berapa banyak addressable memory dari sistem memory k-bit digambarkan dibawah ini:

Sebagai gambaran berapa besar memory yang kita jelaskan diatas, kita akan mencoba menempatkan berapa banyak variable int yang bisa disimpan dalam RAM tersebut. Dengan konfigurasi RAM yang memiliki 32 bit address dengan 1 byte word, maka maksimal kapasitasnya adalah 4TB. Seandainya 1 variable int membutuhkan memory sebanyak 32 bit, maka 1 variable int ini akan menempati 4 byte memory, alias 4 slot address dalam konfigurasi RAM ini. Sehingga berapa banyak variable int yang bisa disimpan:

2³² / 4 = 2³² / 2² = 2³⁰ = 1,073,741,824 = 1,048,576K = 1,024M = 1G.

Bagaimana prosesor memanfaatkan RAM

Pada prosesor, terdapat register-register special, misanya PC (program counter) yang menunjukkan opcode (operation code) mana yang akan dieksekusi. Atau SP (stack pointer) yang menunjukkan stack terakhir ada dimana. Pada gambar diatas menunjukkan register pada processor berisi alamat memory di RAM. Pada pengaturan memory diatas, stack segment tumbuh keatas seiring dalamnya function call, sedangkan heap tumbuh kebawah seiring banyaknya memory allocation.

Memory protection

Proses dapat terdiri dari 1 atau lebih thread sebagaimana gambar berikut:

Setiap proses memiliki register, stack, code, dan data sendiri. Sementara pada proses dengan multithread, mereka sharing code, data, dan files. Namun demikian, tiap thread punya register dan stack masing masing. Memory protection diperlukan untuk mencegah akses private memory oleh proses yang lain, sehingga:

1. beberapa page of memory yang khusus, mendapatkan perlakuan khusus, misalnya: read-only, tidak kelihatan dari user program (tapi kelihatan oleh kernel), dll.
2. data pada kernel tidak bisa diakses user program

Address space translation

Merupakan kemampuan untuk men-translate dari sebuah address-space ke address-space yang lain. Misalnya, dari virtual address-space di-translate menjadi physical address-space. Jika tersedia, maka prosesor dapat menggunakan virtual address space sementara RAM menggunakan physical address space.

Manfaat

1. Sistem operasi dapat memberikan layout memory yg sama untuk sema program.

Seperti gambar dibawah ini:

Semua program akan mendapatkan memory dengan alamat awal 0000 0000 0000 0000 dan berakhir di FFFF FFFF FFFFF FFFF, meskipun secara aktual, alamat di physical memory akan berbeda antara 1 program dengan program yang lain.

2. Controlled overlap

Jika dilakukan secara terkontrol dan benar, maka beberapa thread dapat mengakses memory yang sama, makan akan terbentuk channel komunikasi antara thread yang satu dengan yang lain. Misalnya thread A menulis data di shared memory, kemudian thread B membacanya.

Kerugian

1. Collide in physical memory

Resiko overlap jika proses translation ada kesalahan, sehingga address-space nya bertabrakan. Yaitu, adanya kesempatan thread A dapat mengakses memory thread B pada physical address yang sama, tanpa disadari.

Address space saat program mulai di eksekusi

Program awalnya hanya sekumpulan byte-code di storage. Saat kita perintahkan sistem operasi untuk menjalankan sebuah program, maka byte-code akan dipindahkan dari diskstorage ke RAM, kemudian menempatkan program counter dan stack pointer ke alamat dimana byte-code tersebut dipindahkan. Kegiatan ini disebut dengan loading. Dan boom, seketika prosesor menjalankan program tersebut.

Salah satu yang dilakukan sistem operasi ketika loading adalah linking. Yaitu men-translate alamat memory dalam byte-code yang masih berbentuk simbol, diubah menjadi physical memory address. Proses ini juga merubah symbol yg berupa function call (baik system call – misalnya file read; maupun user lib call misalnya memanggil java String lib), menjadi pemanggilan function di physical memory address dimana function tersebut berada. Hal ini dikenal juga sebagai proses binding instruction dan data to memory: sekarang instruction dan data sudah siap dalam bentuk physical address, dan dan instruction juga siap dalam bentuk physical address, siap di-loading ke physical memory, seperti pada gambar dibawah ini:

Pada gambar diatas, tadinya byty-code program hanya berisi serangkaian perintah (assembly code), kemudian dilakukan process linking sehingga byte-code yang berupa assembly code berubah menjadi kombinasi physical address dan instruction/data. Pada gambar, hal ini tercermin di bagian tengah: physical address. Kemudian sistem operasi melakukan proses loading, sehingga terpindahkan dari physical address ke physical memory, sesuai gambar sebelah kanan.

Bayangkan jika kita menjalankan sebuah multithread program, dimana serangkaian byte-code akan dijalankan secara concurrent. Maka, tidak mungkin proses linking menerapkan pada physical memory yang sama. Maka, pada proses linking, terjadi process address translation, seperti gambar dibawah ini:

Perhatikan, byte code yang sama dengan 1st program, tapi sekarang mulainya di 0x1300. Address translation memetakan dari 0x0300 ke 0x1300, tanpa disadari program. process view of memory-nya tetap sama. Sehingga, program menikmati layout memory yang sama, meski physical memory-nya berbeda.

Ketika proses linking juga mencakup address translation, yang mana boleh jadi melibatkan hardware accelerated translation, maka hasil dari proses linking yang mana menghasilkan address space yang berbeda sama sekali (kecuali dikehendaki ada sharing memory) berbeda dengan 1st program, menghasilkan 2 address space yang tidak beririsan, dan tetap konsisten. Sehingga 2nd program tetap menikmati layout memory yang sama denga 1st program, menjadikan programming lebih mudah karena ada abstraction tersendiri yang mengelola translate dari process view of memory, menjadi physical address.

Dengan demikian, kita sudah mengetahui alur dari sebuah program dalam bentuk byte-code pada storage, sampai dia menempati address-space di physical memory, menjadi sebuah process, yang siap dieksekusi processor, alias From Program to Process.

Contoh Implementasi

Windows 3.1, Cray-1 supercomputer

Tiap program mendapatkan contiguous physical address space. Kelebihan: cepat. Kekurangan: jika dalam run-time kurang alokasi memory, maka keseluruhan data dan instruction yang sudah di load, harus dipindakan ke address space lain yang lebih besar → lambat. Teknik ini disebut Base and Bound (BNB).

Kelemahan base-and-bound

Fragmentation

Seiring berjalan waktu, dimana ada program yang di-load, ada program yang sudah selesai, maka akan terjadi fragmentasi memory, sedemikian hingga tidak ada free-space yang contiguous yang cukup untuk menjalankan loading process berikutnya:

Sulit komunikasi antar proses

Dikarenakan tiap proses memiliki based-and-bound, tidak ada cara bagi proses A untuk mengakses address space process B.

Tidak mendukung space address space

Base-and-bound punya konsekuensi 1 process akan memiliki 1 saja memory segmen. Sebuah program membutuhan beberapa segmen memory: code, data, stack, heap, dll, yang ukurannya beda beda.

Hardware accelerated address translation

Ide dasarnya adalah processor tidak tahu adanya hardware tambahan yang fungsinya untuk address translation. Processor tetap menggunakan virtual address, tetapi tidak mengakses memori secara langsung melainkan lewat hadware MMU (Memory Management Unit):

Skenario diatas menghasilkan 2 konsekuensi:

1. dari sudut pandang CPU: apa yang dilihat program adalah virtual address
2. dari sudut pandang MMU: menerima input berupa virtual address, kemudian di-translate, menghasilkan physical address space.

Simulasi prosesor menjalankan program menggunakan MMU

Baris #1

Pada baris pertama, program counter berada pada 0x240, prosesor harus load instruction pada virtual address 0x240. Maka 0x240 dikonversi menjadi bit → 0000 0010 0100 0000. perhatikan, 2 bit pertama adalah 00, artinya ini code-segment. Maka, menggunakan MMU, 0x240 akan dipecah menjadi 00 – 00 0010 0100 0000, dimana 00 adalah segment ID, dan sisanya 00 0010 0100 0000 adalah offset nya. MMU akan melihat pada tabel translation, mendapati base 0x4000, maka physical address menjadi 0x4000+240 = 0x4240. maka DRAM akan membaca instruction pada alamat 0x4240. Dari sana, hasilnya adalah la $a0, varx

Selanjutnya, prosesor menjalankan instruction yang sudah di-fetch, yaitu load isi dari varx ke $a0. varx berisi pointer merujuk alamat 0x4050. apakah terjadi translation dari virtual address 0x4050 ke physical address? tidak! karena tidak terjadi fetch ke DRAM, ini adalah proses load constant di 0x4050 ke register $a0. Sehingga $a0 akan berisi 0x4050 (tidak di-translate).

Prosesor selalu melihat virtual address, tidak pernah melakukan translation sendiri. translation terjadi karena prosesor melakukan fetch, sehingga berinteraksi dengan DRAM, maka baru terjadi translation.

Berikutnya, prosesor lanjut pada instruction beriktunya dengan menambahkan 4 pada program counter: PC+4→PC, sekarang PC berisi 0x244, dan prosesor siap untuk baris 2.

Baris #2

Setelah PC berisi 0x244, proses berulang, yaitu fetch next instruction di 0x244, dan terjadi translate sehingga physical memory adalah 0x4244, dan prosesor mendapati instruction adalah jal strlen. artinya, jump ke strlen. sebelum melakukan jump, return address diisi dengan +4 dari PC yang sekarang, sehingga return address adalah 0x248. Baru kemudian PC diisi dengan strlen, yaitu 0x360. ini adalah mekanisma call function.

Baris #3

PC berisi 0x360, proses berulang, yaitu fecth next instruction di 0x360, dan terjadi translate sehingga physical memory adalah 0x4360, dan prosesor mendapati instruction adalah li $v0, 0. artinya load 0x0000 ke register $v0. kemudian PC disi dengan +4 dari PC yang sekarang, sehingga PC = 0x364.

Baris #4

PC berisi 0x364, proses berulang, yaitu fecth next instruction di 0x364, dan terjadi translate sehingga physical memory adalah 0x4364, dan prosesor mendapati instruction adalah lb $t0, ($a0). artinya load byte $a0 ke register $t0. Pada baris pertama, kita dapati register $a0 berisi 0x4050, dan perintah load byte artinya ambil data (dalam byte) ke DRAM, maka terjadi translation 0x4050 ke physical address:

0x4050 = 0100 0000 0101 0000. virtual segment: 01. offset: 0x50. dari table translation, didapati segmen 01 adalaha data segment, dengan base 0x4800, sehingga physical address: 0x4800+0x50 = 0x4850. sehingga prosesor akan melakukan:

load byte from 0x4850 → $t0, move PC+4 → PC

Sekarang PC = 0x368.

Kesimpulan terkait multi-segment address-translation

Bagaimana jika stack takes fault (segmentation fault)

Misalnya akses memory diluar base and bound, sistem otomatis membesarkan ukuran stack segment. Tapi bagaimana caranya?

• terjadi segmentation fault, sistem operasi menerima interupt.
• sistem operasi menyimpan state, put the thread as sleep
• sistem operasi membersarkan stack, terjadi O(n) operation karena harus memindahkan isi stack dari space address lama ke space address baru.
• sistem operasi memindahkan state dari sleep menjadi ready-to-run.

Bagaimana jika tidak semua segmen muat dalam memory yang tersisa

Solusi yang ekstrim adalah sistem operasi memindahkan address space sebuah program yang sedang sleep atau tidak dalam ready-to-run state, ke dalam disk. Ini adalah solusi yang sangat mahal (when we use disk, it’s IO intentive operation, loosing million instruction execution worth of time) karena terjadi process swapping dari RAM ke disk, dan jika thread ini akan revive, maka harus di swapping lagi dari disk ke RAM.

Kelemahan terkait multi-segment address translation

Solusi mengatasi kelemahan pada multi-segment address translation

Membuat memory chunk size menjadi lebih kecil (lebih lanjut disebut dengan page-table):

Page Table

Ide dasarnya adalah membuat segmentation memiliki ukuran yang sama. Ukurannya harus cukup kecil supaya fragmentation sebagaimana terjadi pada metode base-and-bound, biasanya 1k-16k per table. Sehingga ada konsekuensi tiap segmen membutuhkan beberapa page. Misalnya stack segment membutuhkan sekian page.

Misalnya ukuran per segmen adalah 4, maka 2 bit terakhir adalah offset, dan sisanya adalah virtual page pointer. Contoh: virtual address: 0011 0001 1100 0110, maka 2 bit terkahir adalah offset: 0011 0001 1100 0110. sehingga virtual page pointer adalah 0011 0001 1100 01.

Proses translate adalah dengan cara melihat di page table, index ke 0011 0001 1100 01, itu base nya berapa (bound nya pasti 4, sesuai ukuran page nya). kemudian setelah base diddapat, tambahkan dengan offset, jadilah physical address, sesuai ilustrasi berikut ini:

Sharing memory dengan page-table

Dua proses bisa sharing memory dengan cara membuat salah satu (atau beberapa) segmen pada page-table pointing ke physical memory yang sama, sesuai ilustrasi berikut:

Ketika proses A mengakses page 2, dia akan di-translate menjadi sebuah physical address, misalnya address x. Disisi lain, proses B mengakses page 4, dan di-translate menjadi sebuah physical address, misalnya address x, sehingga proses A dan B mengakses physical address yang sama, sehingga dikatakan terjadi sharing memory.

Sharing memory dipakai dibanyak tempat, misalnya ketika user memanggil system call, maka sistem operasi memindahkan mode dari user mode ke kernel mode, dan ketika kernel mode selesai, maka dia harus memberi tahu user kalau sudah selesai dan ini hasilnya, maka informasi itu di tulis di memory yg physical address nya sama sama bisa diakses oleh user dan kernel. contoh lain ada digambar dibawah ini:

Kelemahan page-table

• dalam hal address space jarang diisi (sparse), misalnya di sistem operasi UNIX, dimana code start di 0000, dan stack start di 2³¹-1, maka bagian tegahnya kosong tapi tetep harus ada page-table nya.
• jika table yang mendefinisikan page-table ini sangat besar, tidak semua page dipakai, akan lebih bagus kalau punya collection of working pages.

Kelebihan page-table

• simple
• mudah untuk sharing memory

2 Level Page-table

tujuannya untuk mengatasi kelemahan 1 level page table: tidak cocok untuk address space yang jarang diisi (sparse). namun, punya kelemahan: karena 2 level, jadi ada 1 tambahan indirection, membuat akses memory menjadi slow. sehingga, multi level (dengan level >2) page-table, menjadi tidak cocok, karena akan sangat lambat. pada arsitektur 32 bit, umum nya dibuat 2 level page table dengan rule 10-10-12. artinya page table level 1: 10bit, level 2: 10bit, offset 12 bit.

4 Level Page-table

pada arsitektur 64 bit, dibuatlah page table 4 level dengan rule 9 9 9 9 12, dimana keempat page table dari level 1 sampai level 4 itu 9 bit, dan offset 12 bit. kenapa tidak 64 bit? ini untuk cadangan pengembangan kedepan. 48bit address space sudah sangat banyak (256TB of DRAM).