程序代写代做 assembly clock case study data structure file system C cache kernel algorithm go CPSC 313 April 1

CPSC 313 April 1
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
1

Unit 5
Operating Systems & Virtual Memory
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory © 2019 Donald Acton

Today • Learning Outcomes
– Define:
• Process
• Address space
• Process isolation • Virtual memory
– Explain how virtual memory provides process isolation. CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
3

Trivial Programs
hello.c
#include
int main(int argc, char *argv[]) { } printf(“Hello, world!\n”);
All code is in margo’s code repository, linked off the schedule page: https://github.com/margoseltzer/cs313-coderepo
goodbye.c
#include
int main(int argc, char *argv[]) { printf(“Goodbye, world!\n”);
}
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
4

Strange Phenomena
Reading symbols from hello… (gdb) b main
Breakpoint 1 at 0x400430: file hello.c, line 3.
(gdb) run
Starting program: /home/m/mseltzer/313/cs313- coderepo/mar30/hello
Missing separate debuginfos, use: zypper install glibc-debuginfo-2.26- lp151.18.7.x86_64
Breakpoint 1, main (argc=1, argv=0x7fffffffe248) at hello.c:3
3 int main(int argc, char *argv[]) { (gdb)
All code is in margo’s code repository, linked off the schedule page: https://github.com/margoseltzer/cs313-coderepo
Reading symbols from goodbye…
(gdb) b main
Breakpoint 1 at 0x400430: file
goodbye.c, line 3.
(gdb) run
Starting program:
/home/m/mseltzer/313/cs313-
coderepo/mar30/goodbye
Missing separate debuginfos, use:
zypper install glibc-debuginfo-2.26-
lp151.18.7.x86_64
Breakpoint 1, main (argc=1,
argv=0x7fffffffe248) at goodbye.c:3
3 int main(int argc, char *argv[]) {
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
5

Why don’t these programs affect each other?
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 6

Why don’t these programs affect each other?
• Programs run in different processes.
• Each process has its own address space.
• Address spaces provide process isolation.
• Process Isolation:
– Anything one process does should not affect what another process does, unless the processes agree (e.g., set up a communication channel).
– Each process behaves as if it controls the entire machine’s resources. CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
7

0xFFFF
0x0
Recall
Stack
Heap
Text
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
8

Program 1
Program 2
The Illusion
You’re both wrong – I have the whole address space
Program 3
I have the entire address space to myself!
Stack
Heap
Text
Stack
Heap
Text
Stack
Heap
Text
0xFFFF
0xFFFF
0xFFFF
0x0
0x0
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
9

It’s all a lie! • There are two different kinds of addresses:
– Physical addresses*:
• Refer to specific locations in the actual memory (DRAM).
• You may very well have less physical memory than your virtual address space can address.
• E.g., you can have a 32-bit machine with less than 4 GB of memory.
• E.g., you can certainly have a 64-bit machine (with a 64-bit address space) that has less than 64 EB (Exabytes).
– Virtual addresses:
• These are the addresses that programs use.
• Require that there is a mapping from virtual addresses to physical addresses.
* It turns out that this is all a lie too: out of scope for this course, but if you’re interested, check out https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-gerber.pdf
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
10

CPSC 313 April 1
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
11

Upcoming
• Quiz 5 – last one
– Opens on Friday at 5:00 due Monday @23:59
– Coverage all of file systems
– This section up to today (sort of)
• Assignment 4 –
– Due the April 10th
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
12

CPSC 313
Today • Learning Outcomes
– Explain how the operating system is “special” relative to regular applications.
– Explain what supervisor mode and privilege mean.
– Explain how and when the operating system gets to run.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
13

Virtual Address
Magic
How?
Memory
CPU
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
14
Physical Address

How?
Memory
Virtual Address
MMU
Memory Management Unit
CPU
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
15
Physical Address

How VM Provides Process Isolation
Program 2
Memory
Stack
Heap
Text
Stack
Heap
Text
0xFFFF
0x0
Program 1
0xFFFF
0x0
VA 0x0010, please
MMU
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
16

0xFFFF
0x0
Program 1
0xFFFF
Protection
Program 2
Memory
Stack
Heap
Text
Stack
Heap
Text
VA 0x0010, please
MMU
Sure!
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
17

Protection
Program 2
Memory
Stack
Heap
Text
Heh, heh, yeah, I’d like that data too!
0xFFFF
0xFFFF
0x0
VA 0x0010, please
VA 0x0010, please
MMU
Sure!
Program 1
Stack
Heap
Text
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
18

Heh, heh, yeah, I’d like that data too!
0xFFFF
0xFFFF
Program 1
Stack
Heap Text
0x0
VA 0x0010, please
0x0
Protection
Program 2
Stack
Heap Text
VA 0x0010, please
MMU
Sure!
Memory
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
19

VM: A Hardware/Software Partnership • We need hardware support to provide virtual memory.
– Why?
• Weneedsomeentitytoperformthetranslation;ifit’snotHW,thenitwouldhavetobesoftware,
and that software would have to be the OS.
• Invokingtheoperatingsystemoneveryaddressaccesswouldbetooslow.
• Questionsyoushouldbeasking: 1. Why does it have to be the OS 2. Why would that be slow?
• The Hardware
– Provides a (fast) mechanism to map from a virtual address to a physical address
• The Software
– Sets up the mappings that the hardware will execute – Manages the allocation of physical memory
– Implements policies about how memory is shared.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
20

Constraining the Mapping
• Recallthatdifferentpartsofanaddressspacesupportdifferent operations:
– Read-only text/data: cannot be modified
• Implication: We must not be able to write certain parts of memory.
– Data should not be executed:
• Implication: Not all parts of memory should be enabled for execution.
• Theoperatingsystemisspecialsoftware
– We want the operating system to do many things that we don’t want normal processes to do: interact with devices, touch any process’s memory, etc.
• Implication: The OS should have access to some memory locations that are inaccessible to regular processes.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
21

Putting it all Together
• Weaskthehardwaretomapatripleof: – Virtual address
– Type of access (read, write, execute) – Privilege level
• Thehardwarewilleither:
– Produce a physical address
– Fault, due to:
• The type of access is not allowed to the memory requested
• The process requesting access does not have the appropriate privilege level to access the memory.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
22

What is special about the operating system?
Protection Boundary
Applications
file system
device drivers processes
networking
virtual memory
Operating System
HW/SW Interface
Hardware
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
23

Protection Boundaries
• Modernhardwarehasmultipleprivilegelevels.
• Differentsoftwarecanrunwithdifferentprivileges.
• Processorhardwaretypicallyprovides(atleast)twodifferent modes of operation:
• User mode: how all “regular programs” run.
• Kernel mode or supervisor mode: how the OS runs.
• Most processors have only two modes; x86 has four; some older machines had 8!
• Themodeinwhichapieceofsoftwareisrunningdetermines: – What instructions may be executed.
– How addresses are translated.
– What memory locations may be accessed (enforced through translation).
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
24

Example: Intel
– Ring 0: Most privileged: OS (usually) runs here
– Rings 1 & 2:Ignored in many environments, although, can run less privileged code (e.g., third party device drivers; possibly some parts of virtual machine monitors)
– Ring 3: Application code
• Memory is described in chunks called segments
– Each segment also has a privilege level (0 through 3)
– Processor maintains a “current protection level” (CPL) – usually the protection
level of the segment containing the currently executing instruction.
– Program can read/write data in segments of less privilege than CPL
– Program cannot directly call code in segments with more privilege.
• Four protection levels
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
25

Example: MIPS
• Standard two mode processor
– User mode: access to CPU/FPU registers and flat, uniform virtual memory address space.
– Kernel mode: can access memory mapping hardware and special registers.
– Kernel mode: can issue (execute) privileged instructions.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
26

So, how do we change the privilege level?
• Must answer two fundamental questions:
– How do we transfer control between applications and the kernel? – When do we transfer control between applications and the kernel?
• How: Fundamental mechanism that transfers control from less privileged to more privileged is called a trap.
• There are different kinds of traps:
– System calls: An application might want the operating system to do something on its behalf.
– Exceptions: An application unintentionally does something that requires OS assistance (e.g., divide by 0, read a page not in memory).
– Interrupts: An asynchronous event (e.g., I/O completion). CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
27

So, when do we change the privilege level?
• Must answer two fundamental questions:
– How do we transfer control between applications and the kernel? – When do we transfer control between applications and the kernel?
• How: Fundamental mechanism that transfers control from less
privileged to more privileged is called a trap. • There are different kinds of traps:
When a process does something
– System calls: An application might want the operating system to do something on its behalf.
– Exceptions: An application unintentionally does something that requires OS assistance (e.g., divide by 0, read a page not in memory).
– Interrupts: An asynchronous event (e.g., I/O completion). CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
28

But what if a process never does one of those things?
• Must answer two fundamental questions:
– How do we transfer control between applications and the kernel? – When do we transfer control between applications and the kernel?
• How: Fundamental mechanism that transfers control from less
privileged to more privileged is called a trap. • There are different kinds of traps:
When a process does something
– System calls: An application might want the operating system to do something on its behalf.
– Exceptions: An application unintentionally does something that requires OS assistance (e.g., divide by 0, read a page not in memory).
– Interrupts: An asynchronous event (e.g., I/O completion). CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
29

The OS can guarantee that it eventually runs
• Processors have timers.
• Timers have the property that they either count up to some value or down to zero and then …
… generate an interrupt!
• So, to ensure that the OS gets to run, it schedules a timer interrupt, and if nothing else happens before that timer interrupt happens, the OS knows it will get to run when the timer expires.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
30

Control Transfer
• Regardless of why and when control must transfer to the operating system, the mechanism is the same.
• First, we’ll talk about what must happen in the abstract (i.e., not in the context of any particular processor).
• Then, we’ll step talk about the x86 transfer control mechanism specifically.
• Key points:
– We can invoke the operating system explicitly via a system call.
– The operating system can be invoked implicitly via an exception (sometimes called a software interrupt), such as a divide by zero, or a bad memory reference.
– The operating system can be invoked asynchronously via (hardware) interrupts, such as a timer, an I/O device, etc.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
31

Trap Handling: In the abstract
• Each type of trap is assigned a number. For example: – 1=systemcall
– 2=timerinterrupt
– 3=diskinterrupt
– 4=interprocessorinterrupt
• At startup, the operating system sets up a table, indexed by trap number, that contains the address of the code to be executed whenever that kind of trap happens.
• These pieces of code are called “trap handlers.”
1. I’m done!
2. WAKEUP! (interrupt)
Trap handler table
Trap handler for trap 1
Trap handler for trap 3
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
33

X86 Trap Handling
• Interrupt Descriptor Registers (IDT): Plays the role of the trap handler table
– Contains special objects called gates.
– Gatesprovideaccessfromlowerprivilegedsegmentstohigherprivilegedsegments.
• When a low-privilege segment invokes a gate, it automatically raises the CPL (current privilege level) to the
higher level.
• When returning from a gate, the CPL drops to its original level.
– First 32 gates reserved for hardware defined traps.
– Remaining entries are available to software using the INT (interrupt) instruction.
• Hardware register traditionally called PIC (Programmable Interrupt Controller), then APIC (advanced PIC) and most recently LAPIC (local advanced PIC, one per CPU in the system)
– Haswirestoupto16devices
– Maps wires to particular locations in IDT.
– PIC sends the appropriate value for the interrupt handler dispatch to the processor.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
34

x86 System Calls
• There are multiple ways to handle system calls and different operating systems use different ways (these are all assembly instructions):
– Old Linux systems use a single designated INTinstruction (triggers a software interrupt) and then dispatches again within a single handler.
• Return from privileged to unprivileged via IRET.
– Modern Linux systems use the SYSENTER/SYSEXIT calls.
– Depending on the processor on which you are running (Intel or AMD) and other details, sometimes Linux uses SYSCALL/SYSRET.
– (You don’t need to know the details here, just that there are special instructions that let you invoke privileged code.)
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
35

CPSC 313 April 3
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
36

Admin
• Quiz 5 – available today at 5:00 due Monday at 23:59
• Assignment 4 – due next Friday
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
37

Today
• Roadmap:
– We’re going to use virtual memory as a case study of how the OS and
hardware work together.
– To do that, we’re going to first dive into how VM works.
– Then we’ll come back to tracking a VM fault (a kind of exception) through all the trap stuff we talked about on Wednesday.
• Learning Outcomes
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
38

Quick Recap
• The operating system is just a bunch of code that sits around waiting for something to do (e.g., help out a user process, respond to a hardware device, process a timer interrupt, etc).
• The operating system runs in privileged (or supervisor) mode.
• Hardware provides some sort of mechanism to transfer control from one
• We use the term trap to refer to any mechanism that transfers control into the operating system.
privilege level to another.
• There are different kinds of traps:
– System calls: intentional requests of the operating system on behalf of a
program; synchronous with respect to the program)
– Exceptions (software interrupts; synchronous with respect to programs) – Interrupts (caused by hardware; asynchronous)
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
39

Also Recall
• Weaskthehardwaretomapatripleof: – Virtual address
– Type of access (read, write, execute) – Privilege level
• Thehardwarewilleither:
– Produce a physical address
– Fault, due to:
• The type of access is not allowed to the memory requested
• The process requesting access does not have the appropriate privilege level to access the memory.
• Whenthehardwarefaults:Software(theOStakesover). CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
40

A Mapping Table: The Dumbest Solution Ever
• Conceptually,weneedamapfromtriplestophysicaladdresses(or faults)
(VA, access, privilege) => (PA/fault)
• Proposal:
– Store a mapping for every byte in the virtual address space.
– Critique:
– The mapping table would be huge!
1. We know all about caching: if you mapped every byte, you’d have different mappings for elements in a cache line; that seems like a bad idea too.
2. Even a different mapping for each cache line seems like it wouldn’t be a good idea
3. File systems and file system pages (blocks/sectors) are even bigger than cache lines
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
42

A Mapping Table: Slightly Better
• Conceptually, we need a map from triples to physical addresses (or faults)
(VA, access, privilege) => (PA/fault) • Proposal:
– Just like we divide a file up into blocks; let’s divide both address spaces and memory (DRAM) into blocks that we’re going to call pages.
– Store one mapping for each page. – Critique:
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
43

A Mapping Table: Slightly Better
• Conceptually,weneedamapfromtriplestophysicaladdresses(or faults)
(VA, access, privilege) => (PA/fault) • Proposal:
– Just like we divide a file up into blocks; let’s divide both address spaces and memory (DRAM) into blocks that we’re going to call pages.
– Store one mapping for each page.
– Critique:
• That seems far more sensible
• How large are pages?
• How do you implement this map?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
44

Dividing the bits in an address: x86
On x86:
• Pages are 4 KB
• How many bits do we
need to represent 4 KB?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
45

Dividing the bits in an address: x86 – 32
On x86:
• Pages are 4 KB
• How many bits do we
need to represent 4 KB? 12
20 bit virtual page number
12-bit offset
MMU
20 bit physical page number
12-bit offset
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
46

But wait …
• What if we have a 32-bit VAS, but our machine has more than 4 GB of memory?
20 bit virtual page number
12-bit offset
MMU
25
20 bit physical page number
12-bit offset
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
47

But wait …
• What if we have a 32-bit VAS, but our machine has more than 4 GB of memory?
• Why would this make sense?
– You may have multiple processes and you need to fit all of them in.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
48

But wait …
• What if we have a 64-bit VAS, while our machine has much less than that much main/physical memory DRAM.
52 bit virtual page number 12-bit offset MMU
25 bit physical page number 12-bit offset CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
49

Takeaway
• Virtual page numbers and physical page numbers can be different sizes.
• Virtual pages and physical pages are the same size.
– The virtual page size is set by the hardware.
– The (maximum) size of the virtual address space is also determined by the hardware.
– Therefore the number of bits or size of a virtual page number is also determined by the hardware.
• The maximum number of physical pages and therefore the size of physical page numbers is also determined by the hardware.
• The actual number of physical pages is specific to a particular machine. CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
50

Example: x86 – 3.3 GHz Dual-Core Intel Core i5 (intel)
– 64-bit processor (Kaby Lake) • 4KBpagesize
• Of the 64 bits in the virtual address pace: – 12 bits are page offset
– 16 bits are unused
– 36 bits are the virtual page number
– 16 GB 2133 MHz LPDDR3 (DRAM)
• How many bits of physical page number do we need for this machine?
• My machine:
16-bit unused
36-bit page number
12-bit offset
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
51

Example: x86 – 3.3 GHz Dual-Core Intel Core i5 (intel)
– 64-bit processor (Kaby Lake) • 4KBpagesize
• Of the 64 bits in the virtual address pace: – 12 bits are page offset
– 16 bits are unused
– 36 bits are the virtual page number
– 16 GB 2133 MHz LPDDR3 (DRAM)
• How many bits of physical page number do we need for this machine?
• 16 GB => 24 bits; of those 12 must be the page offset; remaining 12 are physical page #
• My machine:
16-bit unused
36-bit page number
12-bit offset
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
52

Program 1
Back to Address Spaces
Stack
Heap
Text
0xFFFF
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
53

0xFFFF
Back to Address Spaces
Program 1
Stack
Heap
Text
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
54

0xFFFF
Program 1
Back to Address Spaces
Stack
Heap
Text
Pages
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
55
…

0xFFFF
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
Program 1
Back to Address Spaces
Stack
Heap
Text
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
56

0xFFFF
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
(VA, access, privilege) => (PA/fault)
Mappings: Recall (from slide 6)
Program 1
Stack
Heap
Text
Triple consisting of a:
• Virtual address (VA)
• Access (read, write, execute) • Privilege (user, supervisor)
And what would we call that fault?
An exception!
Physical address OR
Fault (turns control over to the operating system
0x0
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
57

0xFFFF
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
Page Tables: Data Structure for mapping Program 1
Stack
Heap
Text
Page Table
user/supervisor
Type of access: read, write, execute
PTE: Page Table Entry
Logic in MMU
PC: 0x0
Physical page number (PPN)
Exception
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
58

0xFFFF
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
• • •
There is no mapping for this page (e.g., VPN A)
I have a mapping, but the page is not in memory I have a mapping, but the permissions are wrong
Page Tables: Data Structure for mapping
Program 1
Exceptions:
Stack
Heap
Text
Page Table
user/supervisor
PTE: Page Table Entry
Logic in MMU
Type of access: read, write, execute
PC: 0x0
Physical page number (PPN)
Exception
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
59

Page Tables: Inside the black box
VPN
PPN
Invalid
0x0000A
0x1100B
0x98765
0xCAFE0
0xFACE1
0xC0FFF
Invalid
Invalid
Invalid
Invalid
Invalid
Invalid
0x50505
0x12345
0x24680
Access
Read, Execute
Read, Execute
Read, Execute
Read, Execute
Read, Write
Read, Write
Read, Write
Read, Write
Read, Write
Privilege
U
U
U
U
U
U
U
U
U
Program 1
0 1 2 3 4 5 6 7 8
0xFFFF
VPN F
VPN E
VPN D
VPN C
VPN B
VPN A
VPN 9
VPN 8
VPN 7
VPN 6 9 VPN 5 A VPN 4 B VPN 3 C VPN 2 D
Stack
Heap
Text
Earlier versions had PBN here
PBN = Physical Block Number
PPN = Physical Page number They mean the same thing
PC: VPN 1 E 0x0 VPN 0 F
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
60

Address Translation
0xFFFF
Program 1
Stack
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
VPN PPN
Assume we are running in user mode 0 Invalid xor %rax, %rax 1 0x0000A mrmovq 0xFEED(%rax), %rbx 2 0x1100B
3 0x98765 What virtual address are we accessing? 4 0xCAFE0
5 0xFACE1
What is the VPN to translate? 6 0xC0FFF
7 Invalid
8 Invalid
What is the corresponding PTE? 9 Invalid
A Invalid
Do we have the proper permissions? B Invalid C Invalid
Access
Read, Execute Read, Execute Read, Execute Read, Execute Read, Write Read, Write
Privilege
U U U U U U
Heap Text
PC: 0x0
What is the PA for the data?
D 0x50505
E 0x12345
F 0x24680
Read, Write Read, Write Read, Write
U U U
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
61

CPSC 313
62
0xFFFF
Program 1
Stack
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
Assume we are running in user mode
xor %rax, %rax
mrmovq 0xFEED(%rax), %rbx
What virtual address are we accessing?
0 + 0xFEED = 0xFEED
What is the VPN to translate?
F
What is the corresponding PTE?
0x24680, Read/Write, U
Do we have the proper permissions?
Yes: we can read it from USER mode
What is the PA for the data?
VPN PPN
0 Invalid 1 0x0000A 2 0x1100B 3 0x98765 4 0xCAFE0 5 0xFACE1 6 0xC0FFF 7 Invalid 8 Invalid 9 Invalid
A Invalid B Invalid C Invalid D 0x50505 E 0x12345
Access
Read, Execute Read, Execute Read, Execute Read, Execute Read, Write Read, Write
Privilege
U U U U U U
PC: 0x0
0x24680EED F 0x24680 CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
Read, Write Read, Write Read, Write
U U U
Heap Text
Address Translation

CPSC 313 April 3
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
63

Today – Course & TA evaluations are due.
– We take your input seriously and would very much appreciate your taking the time to fill them out.
– Let us know what worked for you, both while we were meeting in the real and virtual worlds. – No need to thank us for giving you answers to the midterm!
page numbers.
– Todaywe’lllearnhowtoorganizepagetables
• Learning Outcomes
– Whycan’twejustimplementabigflattableforapagetable?
• Reminder:
– Quiz5duetonight
• Roadmap:
– Friday we learned about how page tables facilitate mapping virtual page numbers to physical
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
64

Address Translation With a Page Table
Virtual address
Virtual page number (VPN)
Virtual page offset (VPO)
Page table
Valid Physical page number (PPN)
Physical page number (PPN)
Physical page offset (PPO)
Valid bit = 0: page not in memory (page fault)
Physical address
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
65

0xFFFF
Program 1
Stack
VPN F VPN E VPN D VPN C VPN B VPN A VPN 9 VPN 8 VPN 7 VPN 6 VPN 5 VPN 4 VPN 3 VPN 2 VPN 1 VPN 0
Assume we are running in user mode
xor %rax, %rax
mrmovq 0xFEED(%rax), %rbx
What virtual address are we accessing?
0 + 0xFEED = 0xFEED
What is the VPN to translate?
F
What is the corresponding PTE?
0x24680, Read/Write, U
Do we have the proper permissions?
Yes: we can read it from USER mode
What is the PA for the data?
VPN PPN
0 Invalid 1 0x0000A 2 0x1100B 3 0x98765 4 0xCAFE0 5 0xFACE1 6 0xC0FFF 7 Invalid 8 Invalid 9 Invalid
A Invalid B Invalid C Invalid D 0x50505 E 0x12345
Access
Read, Execute Read, Execute Read, Execute Read, Execute Read, Write Read, Write
Privilege
U U U U U U
PC: 0x0
0x24680EED F 0x24680 CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
Read, Write Read, Write Read, Write
U U U
Address Translation – 12 bit page offset
Heap Text
66

Implementing Page Tables
• There is one page-table per process.
• The OS has to keep track of page tables for all running processes.
• So, how big would those page tables be?
• Assume Intel x86-64 – 4 KB pages
– 48 bit address space
– How many entries would we need in our page table?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
67

Observations about Address Spaces
• What do we know about address spaces that might allow us to do something more clever than have one (huge) table, indexed by virtual pages number?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
69

How do we represent a sparse address space? • Requirements:
– The data structure has to be simple enough that we can look things up in hardware.
– It has to work well in the case where the address space is small – I has to support a large address space
• Insight:
– This is similar to the problem we had with representing files: it had to be
– We were able to ignore whole chunks of the logical block number space by having NULL values for indirect block addresses.
efficient for both small and large files.
– Maybe we could do something similar?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
71

X86 Address Translation
64-bit Virtual Address
72

X86 Address Translation
64-bit address
52 Remaining bits
Offset
Bits 0-11
12 bits
73

X86 Address Translation
64-bit address
Unused
Bits 48-63
36 Remaining bits
Offset
Bits 0-11
16 bits
12 bits
74

X86 Address Translation
64-bit address
Unused
Bits 48-63
36-bit Virtual Page Number
Offset
Bits 0-11
16 bits
12 bits
75

X86 Address Translation
64-bit address
16 bits 9 bits 9 bits 9 bits 9 bits 12 bits
Unused
Bits 48-63
L1 Index Bits 39-47
L2 Index Bits 30-38
L3 Index Bits 21-29
L4 Index Bits 12-20
Offset
Bits 0-11
76

X86 Address Translation
Unused
Bits 48-63
16 bits
L1 Index Bits 39-47
9 bits
L2 Index Bits 30-38
9 bits
L3 Index Bits 21-29
9 bits
L4 Index Bits 12-20
9 bits
Offset
Bits 0-11 12 bits
64-bit address
Each of these 9-bit chunks is going to be an index into a part of a page table.
Analogy to indirect blocks:
• An L4 index points into an actual page table containing PTEs
• An L3 index points into a page table containing pointers to L4 page tables (e.g., a single indirect block) • An L2 index points into a page table containing pointers to L3 page tables (e.g., a double indirect block) • An L1 index points into a page table containing pointers to L2 page tables (3.g., a triple indirect block)
78

X86 Address Translation
64-bit address
16 bits 9 bits 9 bits 9 bits 9 bits
12 bits
Unused
Bits 48-63
L1 Index Bits 39-47
L2 Index Bits 30-38
L3 Index Bits 21-29
L4 Index Bits 12-20
Offset
Bits 0-11
L4 page table
Contains 512 PTEs
79

X86 Address Translation
64-bit address
Unused
Bits 48-63
L1 Index Bits 39-47
L2 Index Bits 30-38
L3 Index Bits 21-29
L4 Index Bits 12-20
Offset
Bits 0-11
16 bits
9 bits
9 bits
9 bits
9 bits
12 bits
L3 page table
L4 page table
Contains 512 pointers to L4 page tables
Contains 512 PTEs
Physical blocks
81
…

X86 Address Translation
64-bit address
Unused
Bits 48-63
L1 Index Bits 39-47
L2 Index Bits 30-38
L3 Index Bits 21-29
L4 Index Bits 12-20
Offset
Bits 0-11
16 bits
9 bits
9 bits
9 bits
9 bits
12 bits
L2 page table
L3 page table
L4 page table
Contains 512 pointers to L3 page tables
Contains 512 pointers to L4 page tables
Contains 512 PTEs
Physical blocks
82
…

X86 Address Translation
64-bit address
Unused
Bits 48-63
L1 Index Bits 39-47
L2 Index Bits 30-38
L3 Index Bits 21-29
L4 Index Bits 12-20
Offset
Bits 0-11
16 bits
9 bits
9 bits
9 bits
9 bits
12 bits
L1 page table
L2 page table
L3 page table
L4 page table
Contains 512 pointers to L2 page tables
Contains 512 pointers to L3 page tables
Contains 512 pointers to L4 page tables
Contains 512 PTEs
Physical blocks
83
…

X86 Address Translation
Unused
Bits 48-63
16 bits
L1 Index Bits 39-47
9 bits
L2 Index Bits 30-38
9 bits
L3 Index Bits 21-29
9 bits
L4 Index Bits 12-20
9 bits
Offset
Bits 0-11 12 bits
CR3 register
Contains 512 pointers to L2 page tables
Contains 512 pointers to L3 page tables
Contains 512 pointers to L4 page tables
Contains 512 PTEs
L1 page table
L2 page table
L3 page table
L4 page table
64-bit address
…
Physical blocks
84

A Closer Look at PTEs
• Levels 1, 2, and 3 each refer to other page tables:
XD Unused Page table physical base address Unused PS A CD ST U/S R/W P 63 52-62 12-51 9-11 876543210
XD: Execute disable (can be used to disable instruction fetches from, e.g., stack)
Bits 12-51 contain the Physical page number of the page table referenced by this PTE
PS: Page size (you can ignore this; if you’re interested, come to office hours)
A: Reference bit (used for page replacement; stay tuned until Wednesday); set on every access CD: Are we allowed to cache the page table we reference
WT: Write through or write-back cache policy for the child page table
U/S: User or Supervisor mode for all pages reachable by the child table
R/W: Read-only or read/write permissions for all reachable pages
P: Is the child table present in main memory?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
85

A Closer Look at PTEs
• Levels 1, 2, and 3 each refer to other page tables:
XD Unused Page table physical base address Unused PS A CD ST U/S R/W P
63 52-62 12-51 9-11 876543210
If P = 0, that says that the page table is not in memory (DRAM); the OS is free to use the rest of the entry in whatever way it wants; what kinds of information do you think the OS wants to put there?
The OS can do whatever it wants with these bits! Bits 1-63
P 0
86

A Closer Look at PTEs
• Level 4’s PTEs will refer to pages that belong to the process’ Virtual Address Space (VAS)
XD Unused Page physical base address Unused G PS D A CD ST U/S R/W P
63 52-62 12-51 9-11 876543210
XD: Execute disable (can be used to disable instruction fetches from, e.g., stack)
Bits 12-51 contain the Physical page number of the page referenced by this PTE
G: Global page (is not evicted from TLB On a process switch)
PS: Page size (you can ignore this; if you’re interested, go to Margo’s office hours)
D: Dirty bit (set on every write)
A: Reference bit (used for page replacement; stay tuned until Wednesday); set on every access CD: Are we allowed to cache the page table we reference
WT: Write through or write-back cache policy for the child page table
U/S: User or Supervisor mode for all pages reachable by the child table
R/W: Read-only or read/write permissions for all reachable pages
P: Is the page present in main memory?
87

Questions to test your understanding:
• Try to answer these before you look at the following slides (which won’t be here until after class)!
1. Must cr3 contain a physical or virtual address? Why?
2. How large is a single page table? Why?
3. Why do PTEs contain physical page numbers?
4. Why don’t PTEs need an offset? (I.e., why is a page number sufficient?)
5. For each level page table, how much memory is reachable?
88

1. Must cr3 contain a physical or virtual address?
• cr3 had better contain a physical address.
• It is needed to translate a virtual address to a physical one
• If cr3 contained a virtual address, how would it translate that address?
89

2. Howlargeisasinglepagetable?Why?
• Each page table has 512 entries
• Each entry is 64 bits (8-bytes)
• Therefore a page table takes up 4 KB
• Isn’t that convenient, since the page size is also 4 KB!
90

3. Why do PTEs contain physical page numbers?
• The answer here is pretty similar to the on for #1.
• Since we have to use the PTEs during address translation, if they contained virtual addresses, we might find ourselves in an infinite loop trying to translate addresses.
91

4. Why don’t PTEs need an offset?
• What is a PTE referencing?
• It is referencing either:
• A page in memory
• A page table in memory – which happens to also be precisely one page large.
• Pages are, by definition, aligned on 4 KB boundaries (because each page is 4 KB).
• Therefore, the low 12 order bits are always 0 for the beginning of a page or a page table.
92

5. For each level page table, how much memory is reachable? (part 1)
• Let’s start with L4:
• Each entry references a single page (of 4 KB) • There are 512 entries in a page table
• Awholepagetable:512*4KB=2MB.
• L3:
• Each entry references an entire L4 page table, so an entry reaches 2 MB (see
above).
• There are 512 entries.
• Awholepagetable:512*2MB=1GB
93

5.
• L2: •
• •
• L1: •
• •
For each level page table, how much memory is reachable? (part 2)
Each entry references an entire L3 page table, so an entry reaches 1 GB (see previous slide)
There are 512 entries. Awholepagetable:512*1GB=512GB(=1⁄2TB)
Each entry references an entire L2 page table, so an entry reaches 512 GB (see previous slide)
There are 512 entries. Awholepagetable:512*512GB=256TB
• The L1 should access the entire address space. That’s 48 bits on the x86-64, and conveniently, 48 bits is 256 TB. Whew!
94

CPSC 313 – End of the Road
CPSC 313 95

Today
• Reminder: Please fill out evaluations! & MT2 experience survey
• Tutorials: This afternoon (basically office hours).
• Office hours of instructors and TAs during exam period will be announced later
• Roadmap:
• Recall that when we talked about protected control transfer, I promised we’d come
back to it in the context of virtual memory – that’s today!
• Learning Outcomes
• Step through page fault handling.
• Identify similarities between file caching and memory management.
• Explain how the clock algorithm relates to LRU.
• Explain why the OS cannot efficiently implement policies such as LRU, LFU, etc.
CPSC 313
96

Intel core i7 address translation
9 9 9 9 12
Virtual address
VPN 1
VPN 2
L2 PTE
VPN 3
L3 PTE
VPN 4
VPO
40
L1 PT
Page global directory
L2 PT
Page upper 40 directory
L3 PT
Page middle 40 directory
L4 PT
Page table
40 CR3/ / / /
L4 PTE
Physical address o f L 1 P T
/9 /9
512 GB region per entry
/9
/9
/ 1 2
Offset into
p h y s i c a l a n d virtual page
L1 PTE
1 GB region per entry
2 MB region per entry
4 KB region per entry
40 /
Physical address of page
40
12
Physical address
PPN
PPO
97

Wrapping Up
• Page tables are the data structure that maps from virtual addresses to physical addresses.
• The x86-64 implements 4-level page tables to conserve memory.
• While a complete flat page table would require 512 GB of memory, a tiny process can make do with far less using 4-level page tables:
• 1 L1 page table (4 KB) • 1 L2 page table (4 KB) • 1 L3 page table (4 KB) • 1 L4 page table (4 KB) • Total: 16 KB
98

Recall: Trap Handling (in the abstract)
Trap handler table
Trap handler for trap 1
Trap handler for trap 3
1. I’m done!
2. WAKEUP! (interrupt)
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
99

Interrupt Dispatch Table
Trap handler for trap 1
Trap handler for trap 3
1. I’m done!
2. WAKEUP! (interrupt)
Trap Handling (x86)
Gates: allow transfer between different privilege levels, e.g., user to supervisor.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
100

Let’s Apply this to Page Faults • What is a page fault?
– The exception that happens when a process tries to access a page that is not currently in memory.
– For now: let’s assume that all the page tables are in memory, but the page in a process’ address space is not.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
101

Page Fault Handling
VPN
L1 page table L2 page table
L4 page table
DRAM
L3 page table
Physical blocks
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
102
…

HW Page Fault Handling: PTE says block not present (1)
VPN
L1 page table L2 page table
DRAM
L3 page table
L4 page table
The OS can do whatever it wants with these bits!
P
Bits 1-63
0
Physical blocks
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
103

HW Page Fault Handling: PTE says block not present (2)
VPN
L1 page table
L2 page table
DRAM
L3 page table
L4 page table
The OS can do whatever it wants with these bits!
P
Bits 1-63
0
CR3 register
Physical blocks
1. User program tries to read/write a memory address in the page referenced by the PTE above.
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 104

CR3 register
2a. Use CR3 to find L1 page table
MMU functionality
L1 page table
2b. Using VA bits 39-47 to indexintoL1. Reads PTE; produces address of L2 PT
VPN
L2 page table
2c. Using VA bits30-38 to index into L2 PT. Reads PTE; produces address of L3 PT
L3 page table
L4 page table
2e. Using VA bits 12-20 to indexintoL4 PT. Reads PTE…
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 105
HW Page Fault Handling: PTE says block not present (3)
DRAM
2d. Using VA bits21-29 to index into L3 PT. Reads PTE; produces address of L4 PT
Physical blocks
1. User program tries to read/write a memory address in the page referenced by the PTE above.
2. MMU traverses hierarchical page tables.
The OS can do whatever it wants with these bits! P Bits 1-63 0

HW Page Fault Handling: PTE says block not present (4)
VPN
L1 page table L2 page table
2b. Using VA DRAM 2e. Using VA 2c. Using VA 2d. Using VA
L3 page table
L4 page table
The OS can do whatever it wants with these bits!
P
Bits 1-63
0
CR3 register
2a. Use CR3 to find L1 page table
bits39-47to index into L1. Reads PTE; produces address of L2 PT
bits30-38 to index into L2 PT. Reads PTE; produces address of L3 PT
bits21-29 to index into L3 PT. Reads PTE; produces address of L4 PT
bits12-20 to index into L4 PT. Reads PTE…
Physical blocks
1. User program tries to read/write a memory address in the page referenced by the PTE above.
2. MMU traverses hierarchical page tables.
3. L4 PTE indicates page not in memory produces an exception.
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 106

CR3 register
2a. Use CR3 to find L1 page table
L1 page table
2b. Using VA bits 39-47 to indexintoL1. Reads PTE; produces address of L2 PT
VPN
L2 page table
2c. Using VA bits30-38 to index into L2 PT. Reads PTE; produces address of L3 PT
L3 page table
L4 page table
2e. Using VA bits 12-20 to indexintoL4 PT. Reads PTE…
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 107
HW Page Fault Handling: PTE says block not present (5)
DRAM
2d. Using VA bits21-29 to index into L3 PT. Reads PTE; produces address of L4 PT
Physical blocks
1. User program tries to read/write a memory address in the page referenced by the PTE above.
2. MMU traverses hierarchical page tables.
3. L4 PTE indicates page not in memory produces an exception.
4. Control transfers to the OS (supervisor) mode, specifies the address causing the fault and the instruction in which
it happened
The OS can do whatever it wants with these bits! P Bits 1-63 0

CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 108
1. InterpretthePTE to determine if the virtual address has a backing page.
DRAM: Each block is a physical page
SW Page Fault Handling: (1)
Some magic number here that says “no backing page” P Bits 1-63 0
OR
Information here that says: device/block OR 0-fill P Bits 1-63 0
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages

1. InterpretthePTE to determine if the virtual address has a backing page.
SW Page Fault Handling: (2)
DRAM: Each block is a physical page
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
OR OS kills process: segfault!
Some magic number here that says “no backing page”
P
Bits 1-63
0
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 109

1. InterpretthePTEto determine if the virtual address has a backing page.
2. Findafreephysical page.
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
SW Page Fault Handling: (3)
DRAM: Each block is a physical page
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 110

1. InterpretthePTEto determine if the virtual address has a backing page.
2. Findafreephysical page.
3. Placepagecontents into page.
DRAM: Each block is a physical page
SW Page Fault Handling: (4)
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 111

1. InterpretthePTEto determine if the virtual address has a backing page.
2. Findafreephysical page.
3. Placepage contents into page.
DRAM: Each block is a physical page
SW Page Fault Handling: (5)
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 112

1. Interpret the PTE to determine if the virtual address has a backing page.
2. Find a free physical page.
3. Place page contents into page.
4. Fill in PTE
5. Restart instruction
DRAM: Each block is a physical page
SW Page Fault Handling: (6)
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 113

1. InterpretthePTE to determine if the virtual address has a backing page.
2..PFiciknadpaagfreeteo evict. physical page.
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
Piggy process
SW Page Fault Handling: (3b)
DRAM: Each block is a physical page
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 114

1. InterpretthePTEto determine if the virtual address has a backing page.
2. Pickapagetoevict.
2b. If dirty, write it out.
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
Piggy process
SW Page Fault Handling: (3c)
DRAM: Each block is a physical page
Information here that says: device/block OR 0-fill
P
Bits 1-63
0
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 115

CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 116
1. Interpret the PTE to determine if the virtual address has a backing page.
2. Pick a page to evict.
2b. If dirty, write it out.
3. Place page contents into page.
4. Fill in PTE
5. Restart instruction
DRAM: Each block is a physical page
SW Page Fault Handling: (6)
Pages owned by the OS
Pages owned by process A
Pages owned by process B
Pages owned by process C
Free Pages
Piggy process
Same as before

Memory Eviction Policies
• We got this! We can use: – LRU
– LFU – MRU
• Or not? Why might those not be practical? – The OS does not see every access to a page.
CPSC 313
– Most accesses are handled by the MMU, so we don’t have time to update counts (LFU) or recently (LRU/MRU).
– What is an OS to do?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 118

What does the hardware provide?
• Precisely two things:
– Access bits per PTE (sometimes called use bits) – Dirty bits per PTE
• Ideally an algorithm will:
– Do something that approximates LRU (after all LRU is really just an
approximation for Belady’s algorithm)
– Take advantage of the information the HW does provide
– Make sure there are lots of clean pages available, so we don’t get stuck always doing a write before a read.
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
119

Intuition from LRU
• LRU is trying to select the page that hasn’t been used for the longest time.
• Since we have a lot of main memory pages, maybe it’s OK to pick a page that hasn’t been used for a long time.
• How can we take advantage of use bits to determine pages that have not been used in a long time?
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
120

Introducing Clock
1. Imagine that all your physical pages are arranged around a clock.
2. Right now, we have virtual pages 1- 11 in memory and their use bits are all 0.
3. We have a clock hand that suggests the next page for eviction.
4. Each time a page is accessed, the HW will set its use bit to be 1.
5. When we need to evict a page, we look at the page under the hand: a) If itsusebit=1,clearitand
move the hand, repeat step 5
b) If its use bit = 0, evict it.
1
Use bit = 0 Use bit = 1
11
2
10
3
4
9
8
7
5 6
121

Watch Clock Run
1. Imagine that all your physical pages are arranged around a clock.
2. Each time a page is accessed, the HW will set its use bit to be 1.
3. Right now, we have virtual pages 1- 11 in memory and their use bits are all 0.
1
Use bit = 0 Use bit = 1
11
525
10
3
4
9
8
7
5 6
Pagereferencestream 1 3 1 1 6 55 4 5 77
123

Test your understanding • Can this loop infinitely?
• In clock, what does it mean if the clock hand is sweeping very slowly?
• What if the hand is sweeping very quickly?
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 124

Test your understanding • Can this loop infinitely?
No!
– If all the use bits are set, you’ll cycle once around the clock and then be able to evict pages.
• In clock, what does it mean if the clock hand is sweeping very slowly?
• What if the hand is sweeping very quickly?
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 125

Test your understanding • Can this loop infinitely? No!
– If all the use bits are set, you’ll cycle once around the clock and then be able to evict pages.
• In clock, what does it mean if the clock hand is sweeping very slowly?
– You have plenty of memory.
– Your system is not taking many page faults. – This is a good situation.
• What if the hand is sweeping very quickly?
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 126

Test your understanding
• Can this loop infinitely? No!
– If all the use bits are set, you’ll cycle once around the clock and then be able to evict pages.
• In clock, what does it mean if the clock hand is sweeping very slowly? – You have plenty of memory.
– Your system is not taking many page faults.
– This is a good situation.
• What if the hand is sweeping very quickly?
– You don’t have enough memory.
– You are thrashing. (Wasting a lot of time moving pages back and forth to memory.)
CPSC 313
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory 127

Final Exam
• Regardless of where you are it will be written on April 23 12:00 PM (noon) PDT.
• Exact method of delivery and format will be informed by the results of the survey of your Midterm 2 experience and guidance from the Faculty of Science
• Coverage will be the full course with extra emphasis on the material since the last midterm (i.e. file systems and virtual memory)
CPSC 313 – 2019W2 Social Distancing – Process Isolation & Virtual Memory
128

Related Posts