Implementasi algoritma dari senarai berkait linear dibidang teknik informatika adalah pada main memory.
Main Memory
a. Hashed Page Tables
Pendekatan umum untuk penanganan ruang alamat yang lebih besar dari 32 bit adalah dengan menggunakan halaman tabel hash, dengan nilai hash yang nomor halaman virtual. Setiap entri dalam tabel hash berisi daftar link dari unsur-unsur yang hash ke lokasi yang sama (untuk menangani tabrakan). Setiap elemen terdiri dari tiga bidang: (1) nomor halaman virtual, (2) nilai halaman bingkai dipetakan, dan (3) pointer ke elemen berikutnya dalam linked list.
Algoritma ini bekerja sebagai berikut: Jumlah halaman virtual pada alamat virtual akan diacak ke dalam tabel hash. Nomor halaman virtual dibandingkan dengan bidang 1 pada elemen pertama dalam linked list. Jika ada yang cocok, halaman bingkai yang sesuai (field 2) digunakan untuk membentuk alamat fisik yang diinginkan. Jika tidak ada pertandingan, entri berikutnya dalam linked list adalah mencari nomor halaman yang cocok virtual.
Sebuah variasi dari skema yang menguntungkan bagi ruang alamat 64-bit telah diusulkan. Variasi ini menggunakan berkerumun tabel halaman, yang sama dengan tabel halaman hashed kecuali bahwa setiap entri pada tabel hash mengacu pada beberapa halaman (seperti 16) daripada satu halaman. Oleh karena itu, entri halaman-tabel tunggal dapat menyimpan pemetaan untuk frame fisik-beberapa halaman. tabel halaman Clustered sangat berguna untuk ruang alamat jarang, mana referensi memori adalah noncontiguous dan tersebar di seluruh ruang alamat.
b. Inverted Page Tables
Biasanya, setiap proses mempunyai tabel halaman terkait. Tabel Halaman memiliki satu entri untuk setiap halaman bahwa proses menggunakan (atau satu slot untuk setiap alamat maya, terlepas dari validitas yang terakhir). Representasi tabel ini adalah satu alam, karena proses halaman referensi melalui alamat maya halaman ‘. Sistem operasi kemudian harus menterjemahkan referensi ini ke alamat memori fisik. Karena tabel diurutkan berdasarkan alamat maya, sistem operasi dapat menghitung dimana pada tabel entri alamat yang terkait fisik dan menggunakan nilai tersebut secara langsung. Salah satu kelemahan dari metode ini adalah bahwa setiap tabel halaman dapat terdiri dari jutaan entri. Tabel ini dapat mengkonsumsi sejumlah besar memori fisik hanya untuk melacak bagaimana memori fisik lain sedang digunakan.
Untuk mengatasi masalah ini, kita bisa. menggunakan tabel halaman yang terbalik. Sebuah tabel halaman terbalik memiliki satu entri untuk setiap halaman nyata (atau frame) dari memori. Setiap entri terdiri dari alamat virtual dari halaman yang tersimpan di lokasi memori nyata, dengan informasi tentang proses yang memiliki halaman tersebut. Dengan demikian, hanya satu tabel halaman dalam sistem, dan hanya memiliki satu entri untuk setiap halaman dari memori fisik. Gambar 8.17 menunjukkan operasi dari sebuah tabel halaman terbalik. Bandingkan dengan Gambar 8.7, yang menggambarkan sebuah tabel halaman standar dalam operasi. tabel halaman terbalik sering mengharuskan alamat-ruang identifier (Bagian 8.4.2) disimpan di setiap entri tabel halaman, karena tabel biasanya berisi beberapa ruang alamat yang berbeda pemetaan memori fisik. Menyimpan alamat-ruang identifier memastikan bahwa halaman logis untuk proses tertentu dipetakan ke halaman bingkai yang sesuai fisik. Contoh sistem yang menggunakan tabel halaman terbalik termasuk UltraSPARC 64-bit dan PowerPC.
Walaupun skema ini mengurangi jumlah memori yang diperlukan untuk menyimpan setiap tabel halaman, ia meningkatkan jumlah waktu yang diperlukan untuk mencari meja ketika referensi halaman terjadi. Karena tabel halaman terbalik diurutkan berdasarkan alamat fisik, tapi pencarian terjadi pada alamat virtual, seluruh meja mungkin perlu dicari untuk pertandingan. Pencarian ini akan memakan waktu terlalu lama. Untuk mengatasi masalah ini, kami menggunakan tabel hash, seperti yang dijelaskan dalam Bagian 8.5.2, untuk membatasi pencarian ke satu atau paling sebuah entri beberapa-halaman-tabel. Tentu saja, setiap akses ke tabel hash menambahkan referensi memori untuk prosedur, jadi suatu memori referensi-virtual memerlukan setidaknya dua memori nyata membaca-satu untuk entri hash-meja dan satu untuk tabel halaman. Untuk meningkatkan performa, ingat bahwa TLB dicari pertama, sebelum tabel hash yang dikonsultasikan.
c. Segmentation
Sebuah aspek penting dari manajemen memori yang menjadi tak terhindarkan dengan paging adalah pemisahan pandangan pengguna tentang memori dan memori fisik yang sebenarnya. Seperti yang telah kita lihat, pandangan pengguna tentang memori tidak sama dengan memori fisik yang sebenarnya. Pandangan pengguna dipetakan ke memori fisik. Pemetaan ini memungkinkan pembedaan antara memori logis dan memori fisik.
e. Basic Method
Sebagai sebuah program utama dengan serangkaian metode, prosedur, atau fungsi. Hal ini juga dapat mencakup berbagai struktur data: objek, array, stack, variabel, dan sebagainya. Masing-masing modul atau elemen data yang disebut dengan nama. Anda berbicara tentang “stack”, “perpustakaan matematika,””program utama, “tanpa peduli apa alamat dalam memori unsur-unsur menduduki Anda tidak peduli dengan apakah stack yang disimpan sebelum atau sesudah sqrt () function. Setiap segmen ini adalah variabel panjang, panjang yang intrinsik ditentukan oleh tujuan dari segmen dalam program Elemen dalam segmen yang diidentifikasi oleh mereka offset dari awal segmen:. pernyataan pertama dari program ini, kerangka ketujuh tumpukan masuk dalam tumpukan, instruksi kelima dari sqrt (), dan seterusnya.
Segmentasi merupakan skema manajemen memori yang mendukung pandangan pengguna memori. Sebuah ruang alamat logis adalah kumpulan dari segmen. Setiap segmen memiliki nama dan panjang. Alamat menetapkan kedua nama segmen dan offset dalam segmen tersebut. Pengguna Oleh karena itu menentukan setiap alamat oleh dua jumlah: nama segmen dan offset. (Kontras skema ini dengan skema paging, di mana pengguna hanya menentukan alamat tunggal, yang dipartisi oleh hardware ke nomor halaman dan offset, semua tak terlihat ke pemrogram).
f. Example: The Intel Pentium
Baik paging dan segmentasi memiliki kelebihan dan kekurangan. Bahkan, beberapa arsitektur menyediakan keduanya. Pada bagian ini, kita membahas arsitektur Intel Pentium, yang mendukung kedua segmentasi murni dan segmentasi dengan paging. Kami tidak memberikan deskripsi lengkap tentang struktur memori-pengelolaan Pentium dalam teks ini. Sebaliknya, kami menyajikan ide-ide utama yang menjadi dasarnya. Kami menyimpulkan diskusi kita dengan gambaran terjemahan alamat Linux pada sistem Pentium.
Dalam sistem Pentium, CPU menghasilkan alamat logis, yang diberikan kepada unit segmentasi. Unit segmentasi menghasilkan alamat linier untuk setiap alamat logis. Alamat linear ini kemudian diberikan kepada unit paging, yang pada gilirannya menghasilkan alamat fisik di memori utama. Dengan demikian, unit segmentasi dan paging membentuk setara unit manajemen memori (MMU).