الدرس · الذاكرة الافتراضية · IT1260

مقدمة الفصل

ماذا ستتعلم في هذا الفصل

Virtual memory terminology, why it works (locality) and the danger of thrashing.
Hardware and control structures: page tables, inverted page tables, the TLB, page size, segmentation.
Operating system software: fetch, placement and replacement policies; frame locking; the optimal, LRU and FIFO algorithms.

أقسام الفصل

1Virtual memory terminologyمصطلحات الذاكرة الافتراضية
2The breakthrough: executing a process partly in memoryالنقلة: تنفيذ العملية وجزء منها فقط في الذاكرة
3Thrashing and the principle of localityالانشغال بالتبديل ومبدأ المحلية
4Page tables, hierarchical and inverted page tablesجداول الصفحات الهرمية والمقلوبة
5Translation lookaside buffer (TLB)ذاكرة الترجمة السريعة (TLB)
6Page sizeحجم الصفحة
7Segmentation and combined paging/segmentationالتقطيع والدمج بين التصفيح والتقطيع
8OS policies: fetch, placement, replacement, frame lockingسياسات النظام: الجلب والوضع والاستبدال وقفل الإطارات
9Replacement algorithms: optimal, LRU, FIFOخوارزميات الاستبدال: الأمثل وLRU وFIFO

تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.

Virtual memory terminologyالمصطلحات

Table 8.1 Virtual Memory Terminology (slide 3)

Termالمصطلح	Meaning (Table 8.1, slide 3)المعنى
Virtual memory	Secondary memory addressed as though it were part of main memory limited by the addressing scheme and secondary memory, not by the number of main storage locations
Virtual address	The address assigned to a location in virtual memory so it can be accessed as though it were part of main memory
Virtual address space	The virtual storage assigned to a process
Address space	The range of memory addresses available to a process
Real address	The address of a storage location in main memory

Slide 9

Real memoryالذاكرة الحقيقية

Main memory, the actual RAM

Virtual memoryالذاكرة الافتراضية

Memory on disk
Allows for effective multiprogramming and relieves the user of tight constraints of main memory

The breakthrough in memory managementفكرة الذاكرة الافتراضية

The breakthrough: executing a process partly in memory

Key points in memory management (slide 4)

1. Memory references are logical addresses dynamically translated into physical addresses at run time.
2. A process may be broken up into pieces that do not need to be located contiguously in main memory.

Breakthrough (slide 5)

If both characteristics are present, it is not necessary that all of the pages or all of the segments of a process be in main memory during execution — if the next instruction and the next data location are in memory, execution can proceed, at least for a time.

Execution of a processتنفيذ العملية

The breakthrough: executing a process partly in memory

Resident set

The portion of the process that is in main memory.

When a needed address is not in main memory (slides 6–7)

1
An interrupt is generated; the OS places the process in a blocking state.
2
The OS issues a disk I/O read request for the piece containing the logical address.
3
Another process is dispatched to run while the disk I/O takes place.
4
An interrupt is issued when the disk I/O completes; the OS places the affected process in the Ready state.

Implications (slide 8)

More processes may be maintained in main memory → very likely a process will be Ready at any time.
A process may be larger than all of main memory.

Thrashing and localityالمحلية والانشغال بالتبديل

Thrashing and the principle of locality

Thrashing

A state in which the system spends most of its time swapping pieces rather than executing instructions. To avoid it, the OS guesses which pieces are least likely to be used in the near future — based on recent history.

Principle of locality

Program and data references within a process tend to cluster → only a few pieces are needed over a short period → intelligent guesses about future needs are possible → virtual memory may work efficiently.

Support needed for virtual memory (slide 12)

Hardware must support paging and segmentation.
The OS must manage the movement of pages and/or segments between secondary memory and main memory.

Page tablesجداول الصفحات

Each process has its own page table; each entry contains the frame number of the corresponding page in main memory.

Two extra bits in each page table entry (slide 13)

Whether the page is in main memory or not
Whether the contents of the page have been altered since it was last loaded

Page tables are also stored in virtual memory; when a process is running, part of its page table is in main memory (slide 16).
Slides 17–18: a two-level hierarchical page table.
Drawback: their size is proportional to that of the virtual address space → alternative: inverted page tables (slide 19).

Inverted page tableالجدول المقلوب

How it is used (slides 20, 22)

1
The page number portion of a virtual address is mapped into a hash value.
2
The hash value points to the inverted page table (one entry for each physical memory frame).
3
The matching entry gives the frame number, which with the offset forms the real address.

Used on PowerPC, UltraSPARC and IA-64.
A fixed proportion of real memory is required for the tables regardless of the number of processes.

Page number

The virtual page in this entry.

Process identifier

The process that owns this page (the table is for all processes).

Control bits

Flags such as valid, referenced; locking.

Chain pointer

The index value of the next entry in the chain.

Translation lookaside buffer (TLB)TLB

TLB

A high-speed cache for page table entries, containing the entries most recently used — because each virtual memory reference can cause two physical memory accesses (the page table, then the data).

TLB operation (slides 24–25)

1
Given a virtual address, the processor examines the TLB.
2
TLB hit: the frame number is retrieved and the real address is formed.
3
TLB miss: the page number is used to index the process page table.
4
The page table check: is the page already in main memory? If not, a page fault is issued.
5
The TLB is updated to include the new page entry.

Associative mappingالربط الترابطي

Translation lookaside buffer (TLB)

The TLB only contains some of the page table entries, so we cannot simply index into the TLB based on the page number.
Each TLB entry must include the page number as well as the complete page table entry.
The processor can simultaneously query numerous TLB entries to determine if there is a page number match.

Page size trade-offsحجم الصفحة

Smaller pagesصفحات أصغر

Less internal fragmentation
More pages per process → larger page tables → a large portion of page tables in virtual memory
Many pages in main memory, near recent references → page faults low

Larger pagesصفحات أكبر

Secondary memory transfers large blocks efficiently → a large page size is better for it
Pages contain locations further from any recent reference → page faults rise

Segmentation in virtual memoryالتقطيع

Segmentation and combined paging/segmentation

Segmentation (slide 36)

Lets the programmer view memory as multiple address spaces or segments — may be unequal, dynamic size.
Simplifies handling of growing data structures.
Allows programs to be altered and recompiled independently.
Lends itself to sharing data among processes and to protection.

Segment table entry (slide 37)

Starting address of the segment in main memory
Length of the segment
A bit: is the segment already in main memory?
A bit: has the segment been modified since it was loaded?

Combined paging and segmentation (slide 40)

Paging

Transparent to the programmer

Segmentation

Visible to the programmer
Each segment is broken into fixed-size pages

Fetch and placement policiesالجلب والوضع

OS policies: fetch, placement, replacement, frame locking

Memory management decisions (slide 44)

Whether or not to use virtual memory techniques
The use of paging or segmentation or both
The algorithms employed

1. Fetch policy — when a page should be brought into memory (slides 45–46)

Demand pagingالجلب عند الطلب

Only brings pages in when a reference is made to a location on the page
Many page faults when the process is first started

Prepagingالجلب المسبق

Brings in more pages than needed
More efficient to bring in pages that reside contiguously on the disk
Don't confuse with "swapping"

2. Placement policy

Determines where in real memory a process piece is to reside; important in a segmentation system; with paging (or paging combined with segmentation) hardware performs address translation.

Replacement policy and frame lockingالاستبدال والقفل

OS policies: fetch, placement, replacement, frame locking

3. Replacement policy

When all frames are occupied and a new page must be brought in, it determines which page currently in memory is to be replaced — ideally the page least likely to be referenced in the near future (principle of locality; predict the future from past behavior).

Frame locking

If a frame is locked, it may not be replaced. A lock bit is associated with each frame.

Locked frames (slide 50)

Kernel of the operating system
Key control structures
I/O buffers

Optimal, LRU and FIFOخوارزميات الاستبدال

Replacement algorithms: optimal, LRU, FIFO

Basic replacement algorithms (slides 53, 55, 57)

Algorithmالخوارزمية	Replacesتستبدل	Note on the slidesملاحظة الشرائح
Optimal	The page for which the time to the next reference is the longest	Impossible to have perfect knowledge of future events
LRU	The page that has not been referenced for the longest time	Difficult to implement tagging each page with the time of last reference requires a great deal of overhead
FIFO	The page that has been in memory the longest (circular buffer, round-robin style)	Simplest to implement the page may be needed again very soon

Page replacement exampleمثال الاستبدال