Bagaimana cara kerja paging x86?

Question 1

Pertanyaan ini dimaksudkan untuk mengisi kekosongan informasi gratis yang baik tentang subjek.

Saya percaya bahwa jawaban yang baik akan cocok dengan satu jawaban SO yang besar atau setidaknya dalam beberapa jawaban.

Tujuan utamanya adalah memberikan informasi yang cukup kepada pemula yang lengkap sehingga mereka dapat mengambil manualnya sendiri, dan dapat memahami konsep OS dasar yang terkait dengan halaman.

Pedoman yang disarankan:

jawaban harus ramah pemula:
- konkret, tetapi contoh yang mungkin disederhanakan sangatlah penting
- penerapan konsep yang ditampilkan dipersilakan
mengutip sumber daya yang bermanfaat itu bagus
penyimpangan kecil tentang bagaimana OS menggunakan fitur paging dipersilakan
Penjelasan PAE dan PSE dipersilakan
penyimpangan kecil ke x86_64 dipersilakan

Pertanyaan terkait dan mengapa menurut saya mereka tidak tertipu:

Bagaimana cara kerja tabel halaman x86? : judulnya hampir sama dengan pertanyaan ini, tetapi body menanyakan pertanyaan spesifik terkait cr3 dan TLB. Pertanyaan itu adalah bagian dari pertanyaan ini.
Bagaimana cara kerja virtualisasi x86 : body hanya meminta sumber.

Question 2

Versi jawaban ini dengan TOC yang bagus dan lebih banyak konten .

Saya akan memperbaiki kesalahan yang dilaporkan. Jika Anda ingin membuat modifikasi besar atau menambahkan aspek yang hilang, buatlah sesuai dengan jawaban Anda sendiri untuk mendapatkan perwakilan yang layak. Pengeditan kecil dapat digabungkan langsung di.

Kode sampel

Contoh minimal: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Seperti semua hal lain dalam pemrograman, satu-satunya cara untuk benar-benar memahami ini adalah bermain dengan sedikit contoh.

Yang menjadikan ini subjek yang "sulit" adalah contoh minimalnya besar karena Anda perlu membuat OS kecil Anda sendiri.

Manual Intel

Meskipun tidak mungkin untuk memahami tanpa contoh dalam pikiran, cobalah untuk memahami manual secepat mungkin.

Intel menjelaskan paging dalam Panduan Pemrograman Sistem Volume 3 Manual Intel - 325384-056US September 2015 Bab 4 "Paging".

Yang menarik adalah Gambar 4-4 "Format CR3 dan Paging-Structure Entries dengan 32-Bit Paging", yang memberikan struktur data kunci.

MMU

Paging dilakukan oleh bagian Memory Management Unit (MMU) dari CPU. Seperti banyak lainnya (misalnya x87 co-processor , APIC ), ini dulunya dengan chip terpisah pada masa-masa awal, yang kemudian diintegrasikan ke dalam CPU. Namun istilah tersebut masih digunakan.

Fakta umum

Alamat logis adalah alamat memori yang digunakan dalam kode lahan pengguna "biasa" (misalnya, isi rsidalam mov eax, [rsi]).

Segmentasi pertama menerjemahkannya menjadi alamat linier, lalu paging kemudian menerjemahkan alamat linier menjadi alamat fisik.

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

Seringkali, kita dapat menganggap alamat fisik sebagai pengindeksan sel memori perangkat keras RAM yang sebenarnya, tetapi ini tidak 100% benar karena:

Paging hanya tersedia dalam mode terlindungi. Penggunaan paging dalam mode terlindung adalah opsional. Paging aktif jika PGbit cr0register disetel.

Paging vs segmentasi

Satu perbedaan utama antara paging dan segmentasi adalah:

paging membagi RAM menjadi potongan berukuran sama yang disebut halaman
segmentasi membagi memori menjadi potongan-potongan dengan ukuran yang berubah-ubah

Ini adalah keuntungan utama paging, karena potongan berukuran sama membuat segalanya lebih mudah dikelola.

Paging menjadi jauh lebih populer sehingga dukungan untuk segmentasi dihilangkan di x86-64 dalam mode 64-bit, mode operasi utama untuk perangkat lunak baru, yang hanya ada dalam mode kompatibilitas, yang mengemulasi IA32.

Aplikasi

Paging digunakan untuk mengimplementasikan proses ruang alamat virtual pada OS modern. Dengan alamat virtual, OS dapat memuat dua atau lebih proses bersamaan pada satu RAM dengan cara yang:

kedua program tidak perlu tahu apa-apa tentang yang lain
memori dari kedua program dapat bertambah dan menyusut sesuai kebutuhan
peralihan antar program sangat cepat
satu program tidak pernah bisa mengakses memori dari proses lain

Paging secara historis muncul setelah segmentasi, dan sebagian besar menggantikannya untuk implementasi memori virtual di OS modern seperti Linux karena lebih mudah untuk mengelola potongan memori halaman berukuran tetap daripada segmen panjang variabel.

Implementasi perangkat keras

Seperti segmentasi dalam mode terlindungi (di mana memodifikasi register segmen memicu beban dari GDT atau LDT), perangkat keras paging menggunakan struktur data dalam memori untuk melakukan tugasnya (tabel halaman, direktori halaman, dll.).

Format struktur data tersebut ditetapkan oleh perangkat keras , tetapi terserah pada OS untuk menyiapkan dan mengelola struktur data tersebut pada RAM dengan benar, dan memberi tahu perangkat keras di mana menemukannya (melalui cr3).

Beberapa arsitektur lain meninggalkan paging hampir sepenuhnya di tangan perangkat lunak, jadi kesalahan TLB menjalankan fungsi yang disediakan OS untuk berjalan di tabel halaman dan memasukkan pemetaan baru ke dalam TLB. Hal ini membuat format tabel halaman dipilih oleh OS, tetapi tidak memungkinkan perangkat keras untuk dapat tumpang tindih saat berjalan di halaman dengan eksekusi instruksi lain yang tidak teratur, seperti yang dapat dilakukan x86 .

Contoh: skema halaman satu tingkat yang disederhanakan

Ini adalah contoh bagaimana paging beroperasi pada versi arsitektur x86 yang disederhanakan untuk mengimplementasikan ruang memori virtual.

Tabel halaman

OS dapat memberi mereka tabel halaman berikut:

Tabel halaman diberikan untuk proses 1 oleh OS:

RAM location        physical address   present
-----------------   -----------------  --------
PT1 + 0       * L   0x00001            1
PT1 + 1       * L   0x00000            1
PT1 + 2       * L   0x00003            1
PT1 + 3       * L                      0
...                                    ...
PT1 + 0xFFFFF * L   0x00005            1

Tabel halaman yang diberikan untuk proses 2 oleh OS:

RAM location       physical address   present
-----------------  -----------------  --------
PT2 + 0       * L  0x0000A            1
PT2 + 1       * L  0x0000B            1
PT2 + 2       * L                     0
PT2 + 3       * L  0x00003            1
...                ...                ...
PT2 + 0xFFFFF * L  0x00004            1

Dimana:

PT1dan PT2: posisi awal tabel 1 dan 2 pada RAM.

Nilai sampel: 0x00000000, 0x12345678, dll

Ini adalah OS yang menentukan nilai-nilai itu.
L: panjang entri tabel halaman.
present: menunjukkan bahwa halaman tersebut ada di memori.

Tabel halaman berada di RAM. Misalnya, mereka dapat ditempatkan sebagai:

--------------> 0xFFFFFFFF


--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1


--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2

--------------> 0x0

Lokasi awal pada RAM untuk kedua tabel halaman bersifat arbitrer dan dikontrol oleh OS. Terserah OS untuk memastikan bahwa mereka tidak tumpang tindih!

Setiap proses tidak dapat menyentuh tabel halaman apa pun secara langsung, meskipun dapat membuat permintaan ke OS yang menyebabkan tabel halaman dimodifikasi, misalnya meminta tumpukan yang lebih besar atau segmen heap.

Halaman adalah potongan 4KB (12 bit), dan karena alamat memiliki 32 bit, hanya 20 bit (20 + 12 = 32, sehingga 5 karakter dalam notasi heksadesimal) diperlukan untuk mengidentifikasi setiap halaman. Nilai ini ditetapkan oleh perangkat keras.

Entri tabel halaman

Tabel halaman adalah ... tabel entri tabel halaman!

Format yang tepat dari entri tabel diperbaiki oleh perangkat keras .

Pada contoh yang disederhanakan ini, entri tabel halaman hanya berisi dua bidang:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

jadi dalam contoh ini para perancang perangkat keras bisa memilih L = 21.

Sebagian besar entri tabel halaman nyata memiliki bidang lain.

Ini akan menjadi tidak praktis untuk menyelaraskan sesuatu pada 21 bit karena memori dapat dialamatkan oleh byte dan bukan bit. Oleh karena itu, meskipun hanya dibutuhkan 21 bit dalam kasus ini, perancang perangkat keras mungkin akan memilih L = 32untuk membuat akses lebih cepat, dan hanya menyimpan bit bit yang tersisa untuk penggunaan nanti. Nilai sebenarnya Lpada x86 adalah 32 bit.

Terjemahan alamat dalam skema satu tingkat

Setelah tabel halaman disiapkan oleh OS, terjemahan alamat antara alamat linier dan fisik dilakukan oleh perangkat keras .

Ketika OS ingin mengaktifkan proses 1, ia menetapkan cr3ke PT1, awal tabel untuk proses pertama.

Jika Proses 1 ingin mengakses alamat linier 0x00000001, rangkaian perangkat keras paging secara otomatis melakukan hal berikut untuk OS:

pisahkan alamat linier menjadi dua bagian:
```
| page (20 bits) | offset (12 bits) |
```
Jadi dalam hal ini kami akan memiliki:
- halaman = 0x00000
- offset = 0x001
lihat ke tabel Halaman 1 karena cr3menunjuk ke sana.
lihat entri 0x00000karena itu adalah bagian halaman.

Perangkat keras mengetahui bahwa entri ini terletak di alamat RAM PT1 + 0 * L = PT1.
karena ada, akses tersebut valid
dengan tabel halaman, lokasi nomor halaman 0x00000berada di 0x00001 * 4K = 0x00001000.
untuk menemukan alamat fisik akhir kita hanya perlu menambahkan offset:
```
  00001 000
+ 00000 001
  -----------
  00001 001
```
karena 00001alamat fisik halaman yang dicari di tabel dan 001offset.

Seperti yang ditunjukkan oleh namanya, offset selalu ditambahkan dengan alamat fisik halaman.
perangkat keras kemudian mendapatkan memori di lokasi fisik tersebut.

Dengan cara yang sama, terjemahan berikut akan terjadi untuk proses 1:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00002 000
FFFFF 000  00005 000

Misalnya, saat mengakses alamat 00001000, bagian halaman adalah 00001perangkat keras yang mengetahui bahwa entri tabel halamannya terletak di alamat RAM: PT1 + 1 * L( 1karena bagian halaman), dan di sanalah ia akan mencarinya.

Ketika OS ingin beralih ke proses 2, yang perlu dilakukan hanyalah cr3menunjuk ke halaman 2. Sesederhana itu!

Sekarang terjemahan berikut akan terjadi untuk proses 2:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00003 000  00003 000
FFFFF 000  00004 000

Alamat linier yang sama diterjemahkan ke alamat fisik yang berbeda untuk proses yang berbeda , tergantung hanya pada nilai di dalamnya cr3.

Dengan cara ini, setiap program dapat mengharapkan datanya dimulai 0dan diakhiri FFFFFFFF, tanpa mengkhawatirkan alamat fisik yang tepat.

Kesalahan halaman

Bagaimana jika Proses 1 mencoba mengakses alamat di dalam halaman yang tidak ada?

Perangkat keras memberi tahu perangkat lunak melalui Pengecualian Kesalahan Halaman.

Kemudian biasanya tergantung pada OS untuk mendaftarkan penangan pengecualian untuk memutuskan apa yang harus dilakukan.

Ada kemungkinan bahwa mengakses halaman yang tidak ada di tabel adalah kesalahan pemrograman:

int is[1];
is[2] = 1;

tetapi mungkin ada kasus di mana ini dapat diterima, misalnya di Linux ketika:

program ingin meningkatkan tumpukannya.

Ini hanya mencoba untuk mengakses byte tertentu dalam kisaran yang mungkin diberikan, dan jika OS senang itu menambahkan halaman itu ke ruang alamat proses.
halaman telah ditukar ke disk.

OS perlu melakukan beberapa pekerjaan di belakang proses untuk mengembalikan halaman ke RAM.

OS dapat menemukan bahwa hal ini terjadi berdasarkan konten dari sisa entri tabel halaman, karena jika bendera saat ini jelas, entri lain dari entri tabel halaman sepenuhnya diserahkan kepada OS untuk apa yang diinginkannya.

Di Linux misalnya, saat ada = 0:
- jika semua bidang entri tabel halaman adalah 0, alamat tidak valid.
- lain, halaman telah ditukar ke disk, dan nilai sebenarnya dari kolom tersebut menyandikan posisi halaman di disk.

Bagaimanapun, OS perlu mengetahui alamat mana yang menghasilkan Page Fault untuk dapat mengatasi masalah tersebut. Inilah sebabnya mengapa para pengembang IA32 yang baik menetapkan nilai cr2ke alamat itu setiap kali Page Fault terjadi. Penangan pengecualian kemudian dapat melihat ke dalam cr2untuk mendapatkan alamatnya.

Penyederhanaan

Penyederhanaan realitas yang membuat contoh ini lebih mudah dipahami:

semua sirkuit paging nyata menggunakan paging multi-level untuk menghemat ruang, tetapi ini menunjukkan skema satu level yang sederhana.
tabel halaman hanya berisi dua field: alamat 20 bit dan flag 1 bit present.

Tabel halaman riil berisi total 12 bidang, dan oleh karena itu fitur lain yang telah dihilangkan.

Contoh: skema halaman multi-level

Masalah dengan skema paging satu level adalah bahwa ini akan memakan terlalu banyak RAM: entri 4G / 4K = 1 juta per proses. Jika setiap entri panjangnya 4 byte, itu akan menghasilkan 4M per proses , yang terlalu banyak bahkan untuk komputer desktop: ps -A | wc -lmengatakan bahwa saya sedang menjalankan 244 proses sekarang, jadi itu akan memakan sekitar 1GB RAM saya!

Karena alasan ini, pengembang x86 memutuskan untuk menggunakan skema multi level yang mengurangi penggunaan RAM.

Kelemahan dari sistem ini adalah waktu aksesnya sedikit lebih tinggi.

Dalam skema paging 3 level sederhana yang digunakan untuk prosesor 32 bit tanpa PAE, 32 bit alamat dibagi sebagai berikut:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Setiap proses harus memiliki satu dan hanya satu direktori halaman yang terkait dengannya, sehingga akan berisi setidaknya 2^10 = 1K entri direktori halaman, jauh lebih baik daripada minimum 1M yang diperlukan pada skema level tunggal.

Tabel halaman hanya dialokasikan sesuai kebutuhan oleh OS. Setiap tabel 2^10 = 1Khalaman memiliki entri direktori halaman

Direktori halaman berisi ... entri direktori halaman! Entri direktori halaman sama dengan entri tabel halaman kecuali yang menunjuk ke alamat RAM tabel halaman, bukan alamat fisik tabel . Karena alamat tersebut hanya lebarnya 20 bit, tabel halaman harus di awal halaman 4KB.

cr3 sekarang menunjuk ke lokasi pada RAM dari direktori halaman dari proses saat ini, bukan tabel halaman.

Entri tabel halaman tidak berubah sama sekali dari skema tingkat tunggal.

Tabel halaman berubah dari skema tingkat tunggal karena:

setiap proses dapat memiliki hingga 1K tabel halaman, satu per entri direktori halaman.
setiap tabel halaman berisi persis 1K entri, bukan 1 juta entri.

Alasan untuk menggunakan 10 bit pada dua tingkat pertama (dan bukan, katakanlah, 12 | 8 | 12) adalah karena setiap entri Tabel Halaman panjangnya 4 byte. Kemudian 2 ^ 10 entri direktori Halaman dan Tabel Halaman akan cocok dengan baik ke dalam halaman 4Kb. Ini berarti lebih cepat dan lebih mudah untuk mengalokasikan dan membatalkan alokasi halaman untuk tujuan itu.

Terjemahan alamat dalam skema multi-level

Direktori halaman diberikan untuk proses 1 oleh OS:

RAM location     physical address   present
---------------  -----------------  --------
PD1 + 0     * L  0x10000            1
PD1 + 1     * L                     0
PD1 + 2     * L  0x80000            1
PD1 + 3     * L                     0
...                                 ...
PD1 + 0x3FF * L                     0

Tabel halaman yang diberikan untuk proses 1 oleh OS pada PT1 = 0x10000000( 0x10000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT1 + 0     * L   0x00001            1
PT1 + 1     * L                      0
PT1 + 2     * L   0x0000D            1
...                                  ...
PT1 + 0x3FF * L   0x00005            1

Tabel halaman yang diberikan untuk proses 1 oleh OS pada PT2 = 0x80000000( 0x80000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT2 + 0     * L   0x0000A            1
PT2 + 1     * L   0x0000C            1
PT2 + 2     * L                      0
...                                  ...
PT2 + 0x3FF * L   0x00003            1

dimana:

PD1: posisi awal direktori halaman proses 1 pada RAM.
PT1dan PT2: posisi awal tabel halaman 1 dan tabel halaman 2 untuk proses 1 pada RAM.

Jadi dalam contoh ini direktori halaman dan tabel halaman dapat disimpan dalam RAM seperti:

----------------> 0xFFFFFFFF


----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2

----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1


----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1

----------------> 0x0

Mari terjemahkan alamat linier 0x00801004langkah demi langkah.

Kami berasumsi bahwa cr3 = PD1, maksudnya, ini menunjuk ke direktori halaman yang baru saja dijelaskan.

Dalam biner alamat liniernya adalah:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Pengelompokan sebagai pemberian 10 | 10 | 12:

0000000010 0000000001 000000000100
0x2        0x1        0x4

pemberian yang mana:

entri direktori halaman = 0x2
entri tabel halaman = 0x1
offset = 0x4

Jadi perangkat keras mencari entri 2 dari direktori halaman.

Tabel direktori halaman mengatakan bahwa tabel halaman berada di 0x80000 * 4K = 0x80000000 . Ini adalah proses akses RAM pertama.

Karena entri tabel halaman adalah 0x1, perangkat keras melihat entri 1 dari tabel halaman di 0x80000000, yang memberi tahu bahwa halaman fisik terletak di alamat0x0000C * 4K = 0x0000C000 . Ini adalah proses akses RAM kedua.

Akhirnya, perangkat keras paging menambahkan offset, dan alamat akhirnya adalah 0x0000C004 .

Contoh lain dari alamat yang diterjemahkan adalah:

linear    10 10 12 split   physical
--------  ---------------  ----------
00000001  000 000 001      00001001
00001001  000 001 001      page fault
003FF001  000 3FF 001      00005001
00400000  001 000 000      page fault
00800001  002 000 001      0000A001
00801008  002 001 008      0000C008
00802008  002 002 008      page fault
00B00001  003 000 000      page fault

Kesalahan halaman terjadi jika entri direktori halaman atau entri tabel halaman tidak ada.

Jika OS ingin menjalankan proses lain secara bersamaan, itu akan memberikan proses kedua direktori halaman terpisah, dan menautkan direktori itu ke tabel halaman terpisah.

Arsitektur 64-bit

64 bit masih terlalu banyak alamat untuk ukuran RAM saat ini, jadi kebanyakan arsitektur akan menggunakan lebih sedikit bit.

x86_64 menggunakan 48 bit (256 TiB), dan PAE mode lama sudah mengizinkan alamat 52-bit (4 PiB).

12 dari 48 bit tersebut sudah disediakan untuk offset, yang menyisakan 36 bit.

Jika pendekatan 2 level diambil, pembagian terbaik adalah dua level 18 bit.

Tetapi itu berarti bahwa direktori halaman akan memiliki 2^18 = 256Kentri, yang akan memakan terlalu banyak RAM: mendekati paging level tunggal untuk arsitektur 32 bit!

Oleh karena itu, arsitektur 64 bit membuat level halaman lebih jauh, biasanya 3 atau 4.

x86_64 menggunakan 4 level dalam 9 | 9 | 9 | 12skema, sehingga level atas hanya mengambil 2^9entri level yang lebih tinggi.

PAE

Ekstensi alamat fisik.

Dengan 32 bit, hanya 4GB RAM yang bisa digunakan.

Ini mulai menjadi batasan untuk server besar, jadi Intel memperkenalkan mekanisme PAE ke Pentium Pro.

Untuk mengatasi masalah tersebut, Intel menambahkan 4 baris alamat baru, sehingga 64GB dapat ditangani.

Struktur tabel halaman juga diubah jika PAE aktif. Cara yang tepat untuk mengubahnya tergantung pada apakah PSE aktif atau nonaktif.

PAE dihidupkan dan dimatikan melalui PAEbit cr4.

Meskipun total memori yang dapat dialamatkan adalah 64 GB, proses individual masih hanya dapat menggunakan hingga 4 GB. Namun OS dapat menempatkan proses yang berbeda pada potongan 4GB yang berbeda.

PSE

Ekstensi ukuran halaman.

Mengizinkan halaman berukuran 4M (atau 2M jika PAE aktif), bukan 4K.

PSE dihidupkan dan dimatikan melalui PAEbit cr4.

Skema tabel halaman PAE dan PSE

Jika PAE dan PSE aktif, skema tingkat halaman yang berbeda digunakan:

tanpa PAE dan tanpa PSE: 10 | 10 | 12
PAE ada dan PSE: 10 | 22.

22 adalah offset dalam halaman 4Mb, karena 22 bit alamat 4Mb.
PAE dan tanpa PSE: 2 | 9 | 9 | 12

Alasan desain mengapa 9 digunakan dua kali, bukan 10 adalah bahwa sekarang entri tidak dapat lagi masuk ke dalam 32 bit, yang semuanya diisi oleh 20 bit alamat dan 12 bit flag yang bermakna atau dicadangkan.

Alasannya adalah bahwa 20 bit tidak cukup lagi untuk mewakili alamat tabel halaman: 24 bit sekarang diperlukan karena 4 kabel tambahan ditambahkan ke prosesor.

Oleh karena itu, desainer memutuskan untuk meningkatkan ukuran entri menjadi 64 bit, dan untuk membuatnya sesuai dengan tabel halaman tunggal, perlu mengurangi jumlah entri menjadi 2 ^ 9 daripada 2 ^ 10.

Awal 2 adalah tingkat Halaman baru yang disebut Tabel Penunjuk Direktori Halaman (PDPT), karena menunjuk ke direktori halaman dan mengisi alamat linier 32 bit. PDPT juga memiliki lebar 64 bit.

cr3sekarang menunjuk ke PDPT yang harus berada di atas empat memori 4GB dan diselaraskan pada kelipatan 32 bit untuk menangani efisiensi. Ini berarti bahwa sekarang cr3memiliki 27 bit signifikan, bukan 20: 2 ^ 5 untuk 32 kelipatan * 2 ^ 27 untuk menyelesaikan 2 ^ 32 dari 4GB pertama.
PAE dan PSE: 2 | 9 | 21

Desainer memutuskan untuk menyimpan bidang lebar 9 bit agar sesuai dengan satu halaman.

Ini menyisakan 23 bit. Meninggalkan 2 untuk PDPT agar semuanya tetap seragam dengan case PAE tanpa PSE menyisakan 21 untuk offset, yang berarti bahwa halaman memiliki lebar 2M, bukan 4M.

TLB

The Translation Lookahead Buffer (TLB) adalah cache untuk alamat paging.

Karena ini adalah cache, ia berbagi banyak masalah desain dari cache CPU, seperti tingkat keterkaitan.

Bagian ini akan menjelaskan TLB asosiatif penuh yang disederhanakan dengan 4 entri alamat tunggal. Perhatikan bahwa seperti cache lainnya, TLB asli biasanya tidak sepenuhnya asosiatif.

Operasi dasar

Setelah terjadi terjemahan antara alamat linier dan fisik, itu disimpan di TLB. Misalnya, 4 entri TLB dimulai dalam kondisi berikut:

  valid   linear   physical
  ------  -------  ---------
> 0       00000    00000
  0       00000    00000
  0       00000    00000
  0       00000    00000

Itu > menunjukkan entry ini harus diganti.

dan setelah alamat linier halaman 00003diterjemahkan ke alamat fisik 00005, TLB menjadi:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
> 0       00000    00000
  0       00000    00000
  0       00000    00000

dan setelah terjemahan kedua 00007untuk 00009menjadi:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
  1       00007    00009
> 0       00000    00000
  0       00000    00000

Sekarang jika 00003perlu diterjemahkan lagi, perangkat keras pertama-tama mencari TLB dan menemukan alamatnya dengan satu akses RAM 00003 --> 00005.

Tentu saja, 00000tidak ada di TLB karena tidak ada entri valid yang berisi 00000sebagai kunci.

Kebijakan penggantian

Saat TLB diisi, alamat lama ditimpa. Sama seperti untuk cache CPU, kebijakan penggantian adalah operasi yang berpotensi kompleks, tetapi heuristik yang sederhana dan masuk akal adalah dengan menghapus entri yang paling terakhir digunakan (LRU).

Dengan LRU, mulai dari negara bagian:

  valid   linear   physical
  ------  -------  ---------
> 1       00003    00005
  1       00007    00009
  1       00009    00001
  1       0000B    00003

menambahkan 0000D -> 0000Aakan memberi:

  valid   linear   physical
  ------  -------  ---------
  1       0000D    0000A
> 1       00007    00009
  1       00009    00001
  1       0000B    00003

CAM

Menggunakan TLB membuat terjemahan lebih cepat, karena terjemahan awal mengambil satu akses per tingkat TLB , yang berarti 2 pada skema 32 bit sederhana, tetapi 3 atau 4 pada arsitektur 64 bit.

TLB biasanya diimplementasikan sebagai jenis RAM mahal yang disebut memori beralamat konten (CAM). CAM mengimplementasikan peta asosiatif pada perangkat keras, yaitu struktur yang diberi kunci (alamat linier), mengambil nilai.

Pemetaan juga dapat diterapkan pada alamat RAM, tetapi pemetaan CAM mungkin memerlukan entri yang jauh lebih sedikit daripada pemetaan RAM.

Misalnya, peta di mana:

kedua kunci dan nilai memiliki 20 bit (kasus skema halaman sederhana)
paling banyak 4 nilai perlu disimpan setiap saat

dapat disimpan di TLB dengan 4 entri:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
FFFFF    00000

Namun, untuk mengimplementasikan ini dengan RAM, perlu memiliki 2 ^ 20 alamat :

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
... (from 00011 to FFFFE)
FFFFF    00000

yang akan lebih mahal daripada menggunakan TLB.

Entri tidak valid

Saat cr3berubah, semua entri TLB tidak valid, karena tabel halaman baru untuk proses baru akan digunakan, jadi sepertinya tidak ada entri lama yang memiliki arti.

X86 juga menawarkan invlpginstruksi yang secara eksplisit membatalkan satu entri TLB. Arsitektur lain menawarkan lebih banyak instruksi untuk entri TLB yang tidak valid, seperti membatalkan semua entri pada rentang tertentu.

Beberapa CPU x86 melampaui persyaratan spesifikasi x86 dan memberikan lebih banyak koherensi daripada yang dijaminnya, antara memodifikasi entri tabel halaman dan menggunakannya, ketika belum di-cache di TLB . Rupanya Windows 9x mengandalkan itu untuk kebenaran, tetapi CPU AMD modern tidak menyediakan perjalanan halaman yang koheren. CPU Intel melakukannya, meskipun mereka harus mendeteksi spekulasi yang salah untuk melakukannya. Mengambil keuntungan dari ini mungkin merupakan ide yang buruk, karena mungkin tidak banyak keuntungan yang didapat, dan risiko besar menyebabkan masalah sensitif waktu yang tidak kentara yang akan sulit di-debug.

Penggunaan kernel Linux

Kernel Linux menggunakan fitur paging x86 secara ekstensif untuk memungkinkan proses switch yang cepat dengan fragmentasi data yang kecil.

Masuk v4.2, lihat di bawah arch/x86/:

include/asm/pgtable*
include/asm/page*
mm/pgtable*
mm/page*

Tampaknya tidak ada struct yang didefinisikan untuk mewakili halaman, hanya makro: include/asm/page_types.hmenarik secara khusus. Kutipan:

#define _PAGE_BIT_PRESENT   0   /* is present */
#define _PAGE_BIT_RW        1   /* writeable */
#define _PAGE_BIT_USER      2   /* userspace addressable */
#define _PAGE_BIT_PWT       3   /* page write through */

arch/x86/include/uapi/asm/processor-flags.hmendefinisikan CR0, dan khususnya PGposisi bit:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliografi

Gratis:

rutgers-pxk-416 bab "Manajemen memori: catatan kuliah"

Tinjauan sejarah yang baik tentang teknik organisasi memori yang digunakan oleh OS lama.

Tidak gratis:

bovet05 bab "Pengalamatan memori"

Pengalamatan memori x86 yang wajar. Kehilangan beberapa contoh yang bagus dan sederhana.

Question 3

Berikut adalah jawaban tingkat tinggi yang sangat singkat:

Prosesor x86 beroperasi dalam salah satu dari beberapa mode yang memungkinkan (kira-kira: nyata, dilindungi, 64-bit). Setiap mode dapat menggunakan salah satu dari beberapa kemungkinan model pengalamatan memori (tetapi tidak setiap mode dapat menggunakan setiap model), yaitu: pengalamatan mode-nyata, pengalamatan tersegmentasi, dan pengalamatan linier datar.

Di dunia modern, hanya pengalamatan linier datar dalam mode terproteksi atau 64-bit yang relevan, dan kedua mode pada dasarnya sama, dengan perbedaan utama adalah ukuran kata mesin dan dengan demikian jumlah memori yang dapat dialamatkan.

Sekarang, mode pengalamatan memori memberi arti pada operan memori dari instruksi mesin (seperti mov DWORD PTR [eax], 25, yang menyimpan dwordinteger 32-bit (alias ) dengan nilai 25 ke dalam memori yang alamatnya disimpan dalam eaxregister 32-bit). Dalam pengalamatan linier datar, angka ini di eaxdiizinkan untuk berjalan di atas satu rentang yang berdekatan, dari nol hingga nilai maksimal (dalam kasus kami, itu adalah 2 ³² - 1).

Namun, datar-linear mengatasi dapat baik paged atau tidak paged . Tanpa paging, alamat langsung merujuk ke memori fisik. Dengan paging, unit manajemen memori prosesor (atau MMU) secara transparan memasukkan alamat yang diinginkan (sekarang disebut alamat virtual ) ke dalam mekanisme pencarian, yang disebut tabel halaman , dan mendapatkan nilai baru, yang diartikan sebagai alamat fisik. Operasi asli sekarang beroperasi pada alamat baru yang diterjemahkan ini dalam memori fisik, meskipun pengguna hanya pernah melihat alamat virtual.

Manfaat utama paging adalah bahwa tabel halaman dikelola oleh sistem operasi. Dengan demikian sistem operasi dapat memodifikasi dan mengganti tabel halaman secara sewenang-wenang, seperti saat "berpindah tugas". Ia dapat menyimpan seluruh koleksi tabel halaman, satu untuk setiap "proses", dan kapan pun ia memutuskan bahwa proses tertentu akan berjalan pada CPU tertentu, ia memuat tabel halaman proses ke dalam MMU CPU itu (setiap CPU memiliki sendiri set tabel halaman). Hasilnya adalah setiap proses melihat ruang alamat virtualnya sendiri yang terlihat sama terlepas dari halaman fisik mana yang kosong ketika OS harus mengalokasikan memori untuknya. Ia tidak pernah tahu tentang memori proses lain, karena ia tidak dapat mengakses memori fisik secara langsung.

Tabel halaman adalah struktur data seperti pohon bersarang yang disimpan dalam memori normal, ditulis oleh OS tetapi dibaca langsung oleh perangkat keras, sehingga formatnya diperbaiki. Mereka "dimuat" ke MMU dengan mengatur register kontrol CPU khusus untuk menunjuk ke tabel tingkat atas. CPU menggunakan cache yang disebut TLB untuk mengingat pencarian, jadi akses berulang ke beberapa halaman yang sama jauh lebih cepat daripada akses yang tersebar, karena alasan tidak-ketinggalan TLB serta alasan cache data biasa. Istilah "entri TLB" biasa digunakan untuk merujuk ke entri tabel laman meskipun mereka tidak di-cache di TLB.

Dan jika Anda khawatir bahwa suatu proses mungkin hanya menonaktifkan paging atau mencoba dan mengubah tabel halaman: Ini tidak diizinkan, karena x86 menerapkan tingkat hak istimewa (disebut "cincin"), dan kode pengguna dijalankan pada tingkat hak istimewa yang terlalu rendah untuk diizinkan itu untuk mengubah tabel halaman CPU.

Answer 1

92

Pertanyaan ini dimaksudkan untuk mengisi kekosongan informasi gratis yang baik tentang subjek.

Saya percaya bahwa jawaban yang baik akan cocok dengan satu jawaban SO yang besar atau setidaknya dalam beberapa jawaban.

Tujuan utamanya adalah memberikan informasi yang cukup kepada pemula yang lengkap sehingga mereka dapat mengambil manualnya sendiri, dan dapat memahami konsep OS dasar yang terkait dengan halaman.

Pedoman yang disarankan:

jawaban harus ramah pemula:
- konkret, tetapi contoh yang mungkin disederhanakan sangatlah penting
- penerapan konsep yang ditampilkan dipersilakan
mengutip sumber daya yang bermanfaat itu bagus
penyimpangan kecil tentang bagaimana OS menggunakan fitur paging dipersilakan
Penjelasan PAE dan PSE dipersilakan
penyimpangan kecil ke x86_64 dipersilakan

Pertanyaan terkait dan mengapa menurut saya mereka tidak tertipu:

Bagaimana cara kerja tabel halaman x86? : judulnya hampir sama dengan pertanyaan ini, tetapi body menanyakan pertanyaan spesifik terkait cr3 dan TLB. Pertanyaan itu adalah bagian dari pertanyaan ini.
Bagaimana cara kerja virtualisasi x86 : body hanya meminta sumber.

x86 paging virtual-memory Ciro Santilli 郝海东冠状病六四事件法轮功
sumber

1

Ini harus diberi tag "faq" dan ditandai sebagai "wiki-komunitas".

Kerrek SB

@KerrekB Saya tidak begitu tahu bagaimana mengatasi pertanyaan semacam ini. Jawaban harus wiki komunitas itu? Saya tidak dapat menemukan faqtag.

Ciro Santilli 郝海东冠状病六四事件法轮功

3

Menurut saya, jawaban singkatnya adalah, "baca Vol 3, Bab 4: Paging dalam Manual Intel". Ini cukup jelas, ringkas dan ditulis dengan baik, dan tidak ada lagi otoritatif.

Kerrek SB

4

@KerrekSB Saya setuju bahwa manual ini jelas dan berwibawa, tetapi agak terlalu kasar sebagai bacaan pertama bagi saya, saya memerlukan beberapa contoh + dasar pemikiran yang sederhana dan konkret untuk memahami hal-hal dengan lebih baik.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 2

1

Ini harus diberi tag "faq" dan ditandai sebagai "wiki-komunitas".

Kerrek SB

Answer 3

@KerrekB Saya tidak begitu tahu bagaimana mengatasi pertanyaan semacam ini. Jawaban harus wiki komunitas itu? Saya tidak dapat menemukan faqtag.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 4

3

Menurut saya, jawaban singkatnya adalah, "baca Vol 3, Bab 4: Paging dalam Manual Intel". Ini cukup jelas, ringkas dan ditulis dengan baik, dan tidak ada lagi otoritatif.

Kerrek SB

Answer 5

4

@KerrekSB Saya setuju bahwa manual ini jelas dan berwibawa, tetapi agak terlalu kasar sebagai bacaan pertama bagi saya, saya memerlukan beberapa contoh + dasar pemikiran yang sederhana dan konkret untuk memahami hal-hal dengan lebih baik.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 6

Versi jawaban ini dengan TOC yang bagus dan lebih banyak konten .

Saya akan memperbaiki kesalahan yang dilaporkan. Jika Anda ingin membuat modifikasi besar atau menambahkan aspek yang hilang, buatlah sesuai dengan jawaban Anda sendiri untuk mendapatkan perwakilan yang layak. Pengeditan kecil dapat digabungkan langsung di.

Kode sampel

Contoh minimal: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Seperti semua hal lain dalam pemrograman, satu-satunya cara untuk benar-benar memahami ini adalah bermain dengan sedikit contoh.

Yang menjadikan ini subjek yang "sulit" adalah contoh minimalnya besar karena Anda perlu membuat OS kecil Anda sendiri.

Manual Intel

Meskipun tidak mungkin untuk memahami tanpa contoh dalam pikiran, cobalah untuk memahami manual secepat mungkin.

Intel menjelaskan paging dalam Panduan Pemrograman Sistem Volume 3 Manual Intel - 325384-056US September 2015 Bab 4 "Paging".

Yang menarik adalah Gambar 4-4 "Format CR3 dan Paging-Structure Entries dengan 32-Bit Paging", yang memberikan struktur data kunci.

MMU

Paging dilakukan oleh bagian Memory Management Unit (MMU) dari CPU. Seperti banyak lainnya (misalnya x87 co-processor , APIC ), ini dulunya dengan chip terpisah pada masa-masa awal, yang kemudian diintegrasikan ke dalam CPU. Namun istilah tersebut masih digunakan.

Fakta umum

Alamat logis adalah alamat memori yang digunakan dalam kode lahan pengguna "biasa" (misalnya, isi rsidalam mov eax, [rsi]).

Segmentasi pertama menerjemahkannya menjadi alamat linier, lalu paging kemudian menerjemahkan alamat linier menjadi alamat fisik.

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

Seringkali, kita dapat menganggap alamat fisik sebagai pengindeksan sel memori perangkat keras RAM yang sebenarnya, tetapi ini tidak 100% benar karena:

Paging hanya tersedia dalam mode terlindungi. Penggunaan paging dalam mode terlindung adalah opsional. Paging aktif jika PGbit cr0register disetel.

Paging vs segmentasi

Satu perbedaan utama antara paging dan segmentasi adalah:

paging membagi RAM menjadi potongan berukuran sama yang disebut halaman
segmentasi membagi memori menjadi potongan-potongan dengan ukuran yang berubah-ubah

Ini adalah keuntungan utama paging, karena potongan berukuran sama membuat segalanya lebih mudah dikelola.

Paging menjadi jauh lebih populer sehingga dukungan untuk segmentasi dihilangkan di x86-64 dalam mode 64-bit, mode operasi utama untuk perangkat lunak baru, yang hanya ada dalam mode kompatibilitas, yang mengemulasi IA32.

Aplikasi

Paging digunakan untuk mengimplementasikan proses ruang alamat virtual pada OS modern. Dengan alamat virtual, OS dapat memuat dua atau lebih proses bersamaan pada satu RAM dengan cara yang:

kedua program tidak perlu tahu apa-apa tentang yang lain
memori dari kedua program dapat bertambah dan menyusut sesuai kebutuhan
peralihan antar program sangat cepat
satu program tidak pernah bisa mengakses memori dari proses lain

Paging secara historis muncul setelah segmentasi, dan sebagian besar menggantikannya untuk implementasi memori virtual di OS modern seperti Linux karena lebih mudah untuk mengelola potongan memori halaman berukuran tetap daripada segmen panjang variabel.

Implementasi perangkat keras

Seperti segmentasi dalam mode terlindungi (di mana memodifikasi register segmen memicu beban dari GDT atau LDT), perangkat keras paging menggunakan struktur data dalam memori untuk melakukan tugasnya (tabel halaman, direktori halaman, dll.).

Format struktur data tersebut ditetapkan oleh perangkat keras , tetapi terserah pada OS untuk menyiapkan dan mengelola struktur data tersebut pada RAM dengan benar, dan memberi tahu perangkat keras di mana menemukannya (melalui cr3).

Beberapa arsitektur lain meninggalkan paging hampir sepenuhnya di tangan perangkat lunak, jadi kesalahan TLB menjalankan fungsi yang disediakan OS untuk berjalan di tabel halaman dan memasukkan pemetaan baru ke dalam TLB. Hal ini membuat format tabel halaman dipilih oleh OS, tetapi tidak memungkinkan perangkat keras untuk dapat tumpang tindih saat berjalan di halaman dengan eksekusi instruksi lain yang tidak teratur, seperti yang dapat dilakukan x86 .

Contoh: skema halaman satu tingkat yang disederhanakan

Ini adalah contoh bagaimana paging beroperasi pada versi arsitektur x86 yang disederhanakan untuk mengimplementasikan ruang memori virtual.

Tabel halaman

OS dapat memberi mereka tabel halaman berikut:

Tabel halaman diberikan untuk proses 1 oleh OS:

RAM location        physical address   present
-----------------   -----------------  --------
PT1 + 0       * L   0x00001            1
PT1 + 1       * L   0x00000            1
PT1 + 2       * L   0x00003            1
PT1 + 3       * L                      0
...                                    ...
PT1 + 0xFFFFF * L   0x00005            1

Tabel halaman yang diberikan untuk proses 2 oleh OS:

RAM location       physical address   present
-----------------  -----------------  --------
PT2 + 0       * L  0x0000A            1
PT2 + 1       * L  0x0000B            1
PT2 + 2       * L                     0
PT2 + 3       * L  0x00003            1
...                ...                ...
PT2 + 0xFFFFF * L  0x00004            1

Dimana:

PT1dan PT2: posisi awal tabel 1 dan 2 pada RAM.

Nilai sampel: 0x00000000, 0x12345678, dll

Ini adalah OS yang menentukan nilai-nilai itu.
L: panjang entri tabel halaman.
present: menunjukkan bahwa halaman tersebut ada di memori.

Tabel halaman berada di RAM. Misalnya, mereka dapat ditempatkan sebagai:

--------------> 0xFFFFFFFF


--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1


--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2

--------------> 0x0

Lokasi awal pada RAM untuk kedua tabel halaman bersifat arbitrer dan dikontrol oleh OS. Terserah OS untuk memastikan bahwa mereka tidak tumpang tindih!

Setiap proses tidak dapat menyentuh tabel halaman apa pun secara langsung, meskipun dapat membuat permintaan ke OS yang menyebabkan tabel halaman dimodifikasi, misalnya meminta tumpukan yang lebih besar atau segmen heap.

Halaman adalah potongan 4KB (12 bit), dan karena alamat memiliki 32 bit, hanya 20 bit (20 + 12 = 32, sehingga 5 karakter dalam notasi heksadesimal) diperlukan untuk mengidentifikasi setiap halaman. Nilai ini ditetapkan oleh perangkat keras.

Entri tabel halaman

Tabel halaman adalah ... tabel entri tabel halaman!

Format yang tepat dari entri tabel diperbaiki oleh perangkat keras .

Pada contoh yang disederhanakan ini, entri tabel halaman hanya berisi dua bidang:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

jadi dalam contoh ini para perancang perangkat keras bisa memilih L = 21.

Sebagian besar entri tabel halaman nyata memiliki bidang lain.

Ini akan menjadi tidak praktis untuk menyelaraskan sesuatu pada 21 bit karena memori dapat dialamatkan oleh byte dan bukan bit. Oleh karena itu, meskipun hanya dibutuhkan 21 bit dalam kasus ini, perancang perangkat keras mungkin akan memilih L = 32untuk membuat akses lebih cepat, dan hanya menyimpan bit bit yang tersisa untuk penggunaan nanti. Nilai sebenarnya Lpada x86 adalah 32 bit.

Terjemahan alamat dalam skema satu tingkat

Setelah tabel halaman disiapkan oleh OS, terjemahan alamat antara alamat linier dan fisik dilakukan oleh perangkat keras .

Ketika OS ingin mengaktifkan proses 1, ia menetapkan cr3ke PT1, awal tabel untuk proses pertama.

Jika Proses 1 ingin mengakses alamat linier 0x00000001, rangkaian perangkat keras paging secara otomatis melakukan hal berikut untuk OS:

pisahkan alamat linier menjadi dua bagian:
```
| page (20 bits) | offset (12 bits) |
```
Jadi dalam hal ini kami akan memiliki:
- halaman = 0x00000
- offset = 0x001
lihat ke tabel Halaman 1 karena cr3menunjuk ke sana.
lihat entri 0x00000karena itu adalah bagian halaman.

Perangkat keras mengetahui bahwa entri ini terletak di alamat RAM PT1 + 0 * L = PT1.
karena ada, akses tersebut valid
dengan tabel halaman, lokasi nomor halaman 0x00000berada di 0x00001 * 4K = 0x00001000.
untuk menemukan alamat fisik akhir kita hanya perlu menambahkan offset:
```
  00001 000
+ 00000 001
  -----------
  00001 001
```
karena 00001alamat fisik halaman yang dicari di tabel dan 001offset.

Seperti yang ditunjukkan oleh namanya, offset selalu ditambahkan dengan alamat fisik halaman.
perangkat keras kemudian mendapatkan memori di lokasi fisik tersebut.

Dengan cara yang sama, terjemahan berikut akan terjadi untuk proses 1:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00002 000
FFFFF 000  00005 000

Misalnya, saat mengakses alamat 00001000, bagian halaman adalah 00001perangkat keras yang mengetahui bahwa entri tabel halamannya terletak di alamat RAM: PT1 + 1 * L( 1karena bagian halaman), dan di sanalah ia akan mencarinya.

Ketika OS ingin beralih ke proses 2, yang perlu dilakukan hanyalah cr3menunjuk ke halaman 2. Sesederhana itu!

Sekarang terjemahan berikut akan terjadi untuk proses 2:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00003 000  00003 000
FFFFF 000  00004 000

Alamat linier yang sama diterjemahkan ke alamat fisik yang berbeda untuk proses yang berbeda , tergantung hanya pada nilai di dalamnya cr3.

Dengan cara ini, setiap program dapat mengharapkan datanya dimulai 0dan diakhiri FFFFFFFF, tanpa mengkhawatirkan alamat fisik yang tepat.

Kesalahan halaman

Bagaimana jika Proses 1 mencoba mengakses alamat di dalam halaman yang tidak ada?

Perangkat keras memberi tahu perangkat lunak melalui Pengecualian Kesalahan Halaman.

Kemudian biasanya tergantung pada OS untuk mendaftarkan penangan pengecualian untuk memutuskan apa yang harus dilakukan.

Ada kemungkinan bahwa mengakses halaman yang tidak ada di tabel adalah kesalahan pemrograman:

int is[1];
is[2] = 1;

tetapi mungkin ada kasus di mana ini dapat diterima, misalnya di Linux ketika:

program ingin meningkatkan tumpukannya.

Ini hanya mencoba untuk mengakses byte tertentu dalam kisaran yang mungkin diberikan, dan jika OS senang itu menambahkan halaman itu ke ruang alamat proses.
halaman telah ditukar ke disk.

OS perlu melakukan beberapa pekerjaan di belakang proses untuk mengembalikan halaman ke RAM.

OS dapat menemukan bahwa hal ini terjadi berdasarkan konten dari sisa entri tabel halaman, karena jika bendera saat ini jelas, entri lain dari entri tabel halaman sepenuhnya diserahkan kepada OS untuk apa yang diinginkannya.

Di Linux misalnya, saat ada = 0:
- jika semua bidang entri tabel halaman adalah 0, alamat tidak valid.
- lain, halaman telah ditukar ke disk, dan nilai sebenarnya dari kolom tersebut menyandikan posisi halaman di disk.

Bagaimanapun, OS perlu mengetahui alamat mana yang menghasilkan Page Fault untuk dapat mengatasi masalah tersebut. Inilah sebabnya mengapa para pengembang IA32 yang baik menetapkan nilai cr2ke alamat itu setiap kali Page Fault terjadi. Penangan pengecualian kemudian dapat melihat ke dalam cr2untuk mendapatkan alamatnya.

Penyederhanaan

Penyederhanaan realitas yang membuat contoh ini lebih mudah dipahami:

semua sirkuit paging nyata menggunakan paging multi-level untuk menghemat ruang, tetapi ini menunjukkan skema satu level yang sederhana.
tabel halaman hanya berisi dua field: alamat 20 bit dan flag 1 bit present.

Tabel halaman riil berisi total 12 bidang, dan oleh karena itu fitur lain yang telah dihilangkan.

Contoh: skema halaman multi-level

Masalah dengan skema paging satu level adalah bahwa ini akan memakan terlalu banyak RAM: entri 4G / 4K = 1 juta per proses. Jika setiap entri panjangnya 4 byte, itu akan menghasilkan 4M per proses , yang terlalu banyak bahkan untuk komputer desktop: ps -A | wc -lmengatakan bahwa saya sedang menjalankan 244 proses sekarang, jadi itu akan memakan sekitar 1GB RAM saya!

Karena alasan ini, pengembang x86 memutuskan untuk menggunakan skema multi level yang mengurangi penggunaan RAM.

Kelemahan dari sistem ini adalah waktu aksesnya sedikit lebih tinggi.

Dalam skema paging 3 level sederhana yang digunakan untuk prosesor 32 bit tanpa PAE, 32 bit alamat dibagi sebagai berikut:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Setiap proses harus memiliki satu dan hanya satu direktori halaman yang terkait dengannya, sehingga akan berisi setidaknya 2^10 = 1K entri direktori halaman, jauh lebih baik daripada minimum 1M yang diperlukan pada skema level tunggal.

Tabel halaman hanya dialokasikan sesuai kebutuhan oleh OS. Setiap tabel 2^10 = 1Khalaman memiliki entri direktori halaman

Direktori halaman berisi ... entri direktori halaman! Entri direktori halaman sama dengan entri tabel halaman kecuali yang menunjuk ke alamat RAM tabel halaman, bukan alamat fisik tabel . Karena alamat tersebut hanya lebarnya 20 bit, tabel halaman harus di awal halaman 4KB.

cr3 sekarang menunjuk ke lokasi pada RAM dari direktori halaman dari proses saat ini, bukan tabel halaman.

Entri tabel halaman tidak berubah sama sekali dari skema tingkat tunggal.

Tabel halaman berubah dari skema tingkat tunggal karena:

setiap proses dapat memiliki hingga 1K tabel halaman, satu per entri direktori halaman.
setiap tabel halaman berisi persis 1K entri, bukan 1 juta entri.

Alasan untuk menggunakan 10 bit pada dua tingkat pertama (dan bukan, katakanlah, 12 | 8 | 12) adalah karena setiap entri Tabel Halaman panjangnya 4 byte. Kemudian 2 ^ 10 entri direktori Halaman dan Tabel Halaman akan cocok dengan baik ke dalam halaman 4Kb. Ini berarti lebih cepat dan lebih mudah untuk mengalokasikan dan membatalkan alokasi halaman untuk tujuan itu.

Terjemahan alamat dalam skema multi-level

Direktori halaman diberikan untuk proses 1 oleh OS:

RAM location     physical address   present
---------------  -----------------  --------
PD1 + 0     * L  0x10000            1
PD1 + 1     * L                     0
PD1 + 2     * L  0x80000            1
PD1 + 3     * L                     0
...                                 ...
PD1 + 0x3FF * L                     0

Tabel halaman yang diberikan untuk proses 1 oleh OS pada PT1 = 0x10000000( 0x10000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT1 + 0     * L   0x00001            1
PT1 + 1     * L                      0
PT1 + 2     * L   0x0000D            1
...                                  ...
PT1 + 0x3FF * L   0x00005            1

Tabel halaman yang diberikan untuk proses 1 oleh OS pada PT2 = 0x80000000( 0x80000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT2 + 0     * L   0x0000A            1
PT2 + 1     * L   0x0000C            1
PT2 + 2     * L                      0
...                                  ...
PT2 + 0x3FF * L   0x00003            1

dimana:

PD1: posisi awal direktori halaman proses 1 pada RAM.
PT1dan PT2: posisi awal tabel halaman 1 dan tabel halaman 2 untuk proses 1 pada RAM.

Jadi dalam contoh ini direktori halaman dan tabel halaman dapat disimpan dalam RAM seperti:

----------------> 0xFFFFFFFF


----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2

----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1


----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1

----------------> 0x0

Mari terjemahkan alamat linier 0x00801004langkah demi langkah.

Kami berasumsi bahwa cr3 = PD1, maksudnya, ini menunjuk ke direktori halaman yang baru saja dijelaskan.

Dalam biner alamat liniernya adalah:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Pengelompokan sebagai pemberian 10 | 10 | 12:

0000000010 0000000001 000000000100
0x2        0x1        0x4

pemberian yang mana:

entri direktori halaman = 0x2
entri tabel halaman = 0x1
offset = 0x4

Jadi perangkat keras mencari entri 2 dari direktori halaman.

Tabel direktori halaman mengatakan bahwa tabel halaman berada di 0x80000 * 4K = 0x80000000 . Ini adalah proses akses RAM pertama.

Karena entri tabel halaman adalah 0x1, perangkat keras melihat entri 1 dari tabel halaman di 0x80000000, yang memberi tahu bahwa halaman fisik terletak di alamat0x0000C * 4K = 0x0000C000 . Ini adalah proses akses RAM kedua.

Akhirnya, perangkat keras paging menambahkan offset, dan alamat akhirnya adalah 0x0000C004 .

Contoh lain dari alamat yang diterjemahkan adalah:

linear    10 10 12 split   physical
--------  ---------------  ----------
00000001  000 000 001      00001001
00001001  000 001 001      page fault
003FF001  000 3FF 001      00005001
00400000  001 000 000      page fault
00800001  002 000 001      0000A001
00801008  002 001 008      0000C008
00802008  002 002 008      page fault
00B00001  003 000 000      page fault

Kesalahan halaman terjadi jika entri direktori halaman atau entri tabel halaman tidak ada.

Jika OS ingin menjalankan proses lain secara bersamaan, itu akan memberikan proses kedua direktori halaman terpisah, dan menautkan direktori itu ke tabel halaman terpisah.

Arsitektur 64-bit

64 bit masih terlalu banyak alamat untuk ukuran RAM saat ini, jadi kebanyakan arsitektur akan menggunakan lebih sedikit bit.

x86_64 menggunakan 48 bit (256 TiB), dan PAE mode lama sudah mengizinkan alamat 52-bit (4 PiB).

12 dari 48 bit tersebut sudah disediakan untuk offset, yang menyisakan 36 bit.

Jika pendekatan 2 level diambil, pembagian terbaik adalah dua level 18 bit.

Tetapi itu berarti bahwa direktori halaman akan memiliki 2^18 = 256Kentri, yang akan memakan terlalu banyak RAM: mendekati paging level tunggal untuk arsitektur 32 bit!

Oleh karena itu, arsitektur 64 bit membuat level halaman lebih jauh, biasanya 3 atau 4.

x86_64 menggunakan 4 level dalam 9 | 9 | 9 | 12skema, sehingga level atas hanya mengambil 2^9entri level yang lebih tinggi.

PAE

Ekstensi alamat fisik.

Dengan 32 bit, hanya 4GB RAM yang bisa digunakan.

Ini mulai menjadi batasan untuk server besar, jadi Intel memperkenalkan mekanisme PAE ke Pentium Pro.

Untuk mengatasi masalah tersebut, Intel menambahkan 4 baris alamat baru, sehingga 64GB dapat ditangani.

Struktur tabel halaman juga diubah jika PAE aktif. Cara yang tepat untuk mengubahnya tergantung pada apakah PSE aktif atau nonaktif.

PAE dihidupkan dan dimatikan melalui PAEbit cr4.

Meskipun total memori yang dapat dialamatkan adalah 64 GB, proses individual masih hanya dapat menggunakan hingga 4 GB. Namun OS dapat menempatkan proses yang berbeda pada potongan 4GB yang berbeda.

PSE

Ekstensi ukuran halaman.

Mengizinkan halaman berukuran 4M (atau 2M jika PAE aktif), bukan 4K.

PSE dihidupkan dan dimatikan melalui PAEbit cr4.

Skema tabel halaman PAE dan PSE

Jika PAE dan PSE aktif, skema tingkat halaman yang berbeda digunakan:

tanpa PAE dan tanpa PSE: 10 | 10 | 12
PAE ada dan PSE: 10 | 22.

22 adalah offset dalam halaman 4Mb, karena 22 bit alamat 4Mb.
PAE dan tanpa PSE: 2 | 9 | 9 | 12

Alasan desain mengapa 9 digunakan dua kali, bukan 10 adalah bahwa sekarang entri tidak dapat lagi masuk ke dalam 32 bit, yang semuanya diisi oleh 20 bit alamat dan 12 bit flag yang bermakna atau dicadangkan.

Alasannya adalah bahwa 20 bit tidak cukup lagi untuk mewakili alamat tabel halaman: 24 bit sekarang diperlukan karena 4 kabel tambahan ditambahkan ke prosesor.

Oleh karena itu, desainer memutuskan untuk meningkatkan ukuran entri menjadi 64 bit, dan untuk membuatnya sesuai dengan tabel halaman tunggal, perlu mengurangi jumlah entri menjadi 2 ^ 9 daripada 2 ^ 10.

Awal 2 adalah tingkat Halaman baru yang disebut Tabel Penunjuk Direktori Halaman (PDPT), karena menunjuk ke direktori halaman dan mengisi alamat linier 32 bit. PDPT juga memiliki lebar 64 bit.

cr3sekarang menunjuk ke PDPT yang harus berada di atas empat memori 4GB dan diselaraskan pada kelipatan 32 bit untuk menangani efisiensi. Ini berarti bahwa sekarang cr3memiliki 27 bit signifikan, bukan 20: 2 ^ 5 untuk 32 kelipatan * 2 ^ 27 untuk menyelesaikan 2 ^ 32 dari 4GB pertama.
PAE dan PSE: 2 | 9 | 21

Desainer memutuskan untuk menyimpan bidang lebar 9 bit agar sesuai dengan satu halaman.

Ini menyisakan 23 bit. Meninggalkan 2 untuk PDPT agar semuanya tetap seragam dengan case PAE tanpa PSE menyisakan 21 untuk offset, yang berarti bahwa halaman memiliki lebar 2M, bukan 4M.

TLB

The Translation Lookahead Buffer (TLB) adalah cache untuk alamat paging.

Karena ini adalah cache, ia berbagi banyak masalah desain dari cache CPU, seperti tingkat keterkaitan.

Bagian ini akan menjelaskan TLB asosiatif penuh yang disederhanakan dengan 4 entri alamat tunggal. Perhatikan bahwa seperti cache lainnya, TLB asli biasanya tidak sepenuhnya asosiatif.

Operasi dasar

Setelah terjadi terjemahan antara alamat linier dan fisik, itu disimpan di TLB. Misalnya, 4 entri TLB dimulai dalam kondisi berikut:

  valid   linear   physical
  ------  -------  ---------
> 0       00000    00000
  0       00000    00000
  0       00000    00000
  0       00000    00000

Itu > menunjukkan entry ini harus diganti.

dan setelah alamat linier halaman 00003diterjemahkan ke alamat fisik 00005, TLB menjadi:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
> 0       00000    00000
  0       00000    00000
  0       00000    00000

dan setelah terjemahan kedua 00007untuk 00009menjadi:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
  1       00007    00009
> 0       00000    00000
  0       00000    00000

Sekarang jika 00003perlu diterjemahkan lagi, perangkat keras pertama-tama mencari TLB dan menemukan alamatnya dengan satu akses RAM 00003 --> 00005.

Tentu saja, 00000tidak ada di TLB karena tidak ada entri valid yang berisi 00000sebagai kunci.

Kebijakan penggantian

Saat TLB diisi, alamat lama ditimpa. Sama seperti untuk cache CPU, kebijakan penggantian adalah operasi yang berpotensi kompleks, tetapi heuristik yang sederhana dan masuk akal adalah dengan menghapus entri yang paling terakhir digunakan (LRU).

Dengan LRU, mulai dari negara bagian:

  valid   linear   physical
  ------  -------  ---------
> 1       00003    00005
  1       00007    00009
  1       00009    00001
  1       0000B    00003

menambahkan 0000D -> 0000Aakan memberi:

  valid   linear   physical
  ------  -------  ---------
  1       0000D    0000A
> 1       00007    00009
  1       00009    00001
  1       0000B    00003

CAM

Menggunakan TLB membuat terjemahan lebih cepat, karena terjemahan awal mengambil satu akses per tingkat TLB , yang berarti 2 pada skema 32 bit sederhana, tetapi 3 atau 4 pada arsitektur 64 bit.

TLB biasanya diimplementasikan sebagai jenis RAM mahal yang disebut memori beralamat konten (CAM). CAM mengimplementasikan peta asosiatif pada perangkat keras, yaitu struktur yang diberi kunci (alamat linier), mengambil nilai.

Pemetaan juga dapat diterapkan pada alamat RAM, tetapi pemetaan CAM mungkin memerlukan entri yang jauh lebih sedikit daripada pemetaan RAM.

Misalnya, peta di mana:

kedua kunci dan nilai memiliki 20 bit (kasus skema halaman sederhana)
paling banyak 4 nilai perlu disimpan setiap saat

dapat disimpan di TLB dengan 4 entri:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
FFFFF    00000

Namun, untuk mengimplementasikan ini dengan RAM, perlu memiliki 2 ^ 20 alamat :

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
... (from 00011 to FFFFE)
FFFFF    00000

yang akan lebih mahal daripada menggunakan TLB.

Entri tidak valid

Saat cr3berubah, semua entri TLB tidak valid, karena tabel halaman baru untuk proses baru akan digunakan, jadi sepertinya tidak ada entri lama yang memiliki arti.

X86 juga menawarkan invlpginstruksi yang secara eksplisit membatalkan satu entri TLB. Arsitektur lain menawarkan lebih banyak instruksi untuk entri TLB yang tidak valid, seperti membatalkan semua entri pada rentang tertentu.

Beberapa CPU x86 melampaui persyaratan spesifikasi x86 dan memberikan lebih banyak koherensi daripada yang dijaminnya, antara memodifikasi entri tabel halaman dan menggunakannya, ketika belum di-cache di TLB . Rupanya Windows 9x mengandalkan itu untuk kebenaran, tetapi CPU AMD modern tidak menyediakan perjalanan halaman yang koheren. CPU Intel melakukannya, meskipun mereka harus mendeteksi spekulasi yang salah untuk melakukannya. Mengambil keuntungan dari ini mungkin merupakan ide yang buruk, karena mungkin tidak banyak keuntungan yang didapat, dan risiko besar menyebabkan masalah sensitif waktu yang tidak kentara yang akan sulit di-debug.

Penggunaan kernel Linux

Kernel Linux menggunakan fitur paging x86 secara ekstensif untuk memungkinkan proses switch yang cepat dengan fragmentasi data yang kecil.

Masuk v4.2, lihat di bawah arch/x86/:

include/asm/pgtable*
include/asm/page*
mm/pgtable*
mm/page*

Tampaknya tidak ada struct yang didefinisikan untuk mewakili halaman, hanya makro: include/asm/page_types.hmenarik secara khusus. Kutipan:

#define _PAGE_BIT_PRESENT   0   /* is present */
#define _PAGE_BIT_RW        1   /* writeable */
#define _PAGE_BIT_USER      2   /* userspace addressable */
#define _PAGE_BIT_PWT       3   /* page write through */

arch/x86/include/uapi/asm/processor-flags.hmendefinisikan CR0, dan khususnya PGposisi bit:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliografi

Gratis:

rutgers-pxk-416 bab "Manajemen memori: catatan kuliah"

Tinjauan sejarah yang baik tentang teknik organisasi memori yang digunakan oleh OS lama.

Tidak gratis:

bovet05 bab "Pengalamatan memori"

Pengalamatan memori x86 yang wajar. Kehilangan beberapa contoh yang bagus dan sederhana.

Answer 7

Jawaban yang bagus, tetapi saya masih belum jelas tentang bagaimana LRU diputuskan. Memanggil OS setiap kali halaman selain MRU diakses tampaknya mahal. Bergantian saya bisa melihat perangkat keras menyusun ulang tabel halaman untuk LRU, yang mungkin berbahaya untuk program bersamaan. Apakah salah satu dari ini benar? Bagaimana OS mengetahui halaman mana yang merupakan LRU saat terjadi kesalahan halaman?

Keynan

Answer 8

@Keynan Saya pikir itu perangkat keras yang melakukannya, jadi waktu yang dibutuhkan tidak menjadi perhatian. Mengenai konkurensi, saya tidak tahu bagaimana itu dikelola. Saya pikir ada satu CR3 dan cache per prosesor, dan OS hanya harus memastikan bahwa halaman memori tidak tumpang tindih.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 9

1

real TLBs are not usually fully associative… The TLB is usually implemented as … CAMBukankah kedua pernyataan ini bertentangan?

a3f

Answer 10

>>> x86_64 menggunakan 4 level dalam 9 | 9 | 9 | 12 skema itu harus 9 | 9 | 9 | 9 | 12？

monklof

Answer 11

@monklof Saya rasa ini benar: 9 9 9 12 sudah memungkinkan 512GB RAM. Skema 5 level adalah pengembangan yang lebih baru yang ditujukan untuk server saja, ini disebutkan dalam jawaban di situs web saya yang lebih mutakhir.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 12

Berikut adalah jawaban tingkat tinggi yang sangat singkat:

Prosesor x86 beroperasi dalam salah satu dari beberapa mode yang memungkinkan (kira-kira: nyata, dilindungi, 64-bit). Setiap mode dapat menggunakan salah satu dari beberapa kemungkinan model pengalamatan memori (tetapi tidak setiap mode dapat menggunakan setiap model), yaitu: pengalamatan mode-nyata, pengalamatan tersegmentasi, dan pengalamatan linier datar.

Di dunia modern, hanya pengalamatan linier datar dalam mode terproteksi atau 64-bit yang relevan, dan kedua mode pada dasarnya sama, dengan perbedaan utama adalah ukuran kata mesin dan dengan demikian jumlah memori yang dapat dialamatkan.

Sekarang, mode pengalamatan memori memberi arti pada operan memori dari instruksi mesin (seperti mov DWORD PTR [eax], 25, yang menyimpan dwordinteger 32-bit (alias ) dengan nilai 25 ke dalam memori yang alamatnya disimpan dalam eaxregister 32-bit). Dalam pengalamatan linier datar, angka ini di eaxdiizinkan untuk berjalan di atas satu rentang yang berdekatan, dari nol hingga nilai maksimal (dalam kasus kami, itu adalah 2 ³² - 1).

Namun, datar-linear mengatasi dapat baik paged atau tidak paged . Tanpa paging, alamat langsung merujuk ke memori fisik. Dengan paging, unit manajemen memori prosesor (atau MMU) secara transparan memasukkan alamat yang diinginkan (sekarang disebut alamat virtual ) ke dalam mekanisme pencarian, yang disebut tabel halaman , dan mendapatkan nilai baru, yang diartikan sebagai alamat fisik. Operasi asli sekarang beroperasi pada alamat baru yang diterjemahkan ini dalam memori fisik, meskipun pengguna hanya pernah melihat alamat virtual.

Manfaat utama paging adalah bahwa tabel halaman dikelola oleh sistem operasi. Dengan demikian sistem operasi dapat memodifikasi dan mengganti tabel halaman secara sewenang-wenang, seperti saat "berpindah tugas". Ia dapat menyimpan seluruh koleksi tabel halaman, satu untuk setiap "proses", dan kapan pun ia memutuskan bahwa proses tertentu akan berjalan pada CPU tertentu, ia memuat tabel halaman proses ke dalam MMU CPU itu (setiap CPU memiliki sendiri set tabel halaman). Hasilnya adalah setiap proses melihat ruang alamat virtualnya sendiri yang terlihat sama terlepas dari halaman fisik mana yang kosong ketika OS harus mengalokasikan memori untuknya. Ia tidak pernah tahu tentang memori proses lain, karena ia tidak dapat mengakses memori fisik secara langsung.

Tabel halaman adalah struktur data seperti pohon bersarang yang disimpan dalam memori normal, ditulis oleh OS tetapi dibaca langsung oleh perangkat keras, sehingga formatnya diperbaiki. Mereka "dimuat" ke MMU dengan mengatur register kontrol CPU khusus untuk menunjuk ke tabel tingkat atas. CPU menggunakan cache yang disebut TLB untuk mengingat pencarian, jadi akses berulang ke beberapa halaman yang sama jauh lebih cepat daripada akses yang tersebar, karena alasan tidak-ketinggalan TLB serta alasan cache data biasa. Istilah "entri TLB" biasa digunakan untuk merujuk ke entri tabel laman meskipun mereka tidak di-cache di TLB.

Dan jika Anda khawatir bahwa suatu proses mungkin hanya menonaktifkan paging atau mencoba dan mengubah tabel halaman: Ini tidak diizinkan, karena x86 menerapkan tingkat hak istimewa (disebut "cincin"), dan kode pengguna dijalankan pada tingkat hak istimewa yang terlalu rendah untuk diizinkan itu untuk mengubah tabel halaman CPU.

Bagaimana cara kerja paging x86?

Jawaban:

Kode sampel

Manual Intel

MMU

Fakta umum

Paging vs segmentasi

Aplikasi

Implementasi perangkat keras

Contoh: skema halaman satu tingkat yang disederhanakan

Tabel halaman

Entri tabel halaman

Terjemahan alamat dalam skema satu tingkat

Kesalahan halaman

Penyederhanaan

Contoh: skema halaman multi-level

Terjemahan alamat dalam skema multi-level

Arsitektur 64-bit

PAE

PSE

Skema tabel halaman PAE dan PSE

TLB

Operasi dasar

Kebijakan penggantian

CAM

Entri tidak valid

Penggunaan kernel Linux

Bibliografi