CS162 Operating Systems and Systems Programming Lecture 13
Memory 1:AddressTranslation andVirtual Memory
March 3rd, 2022 Prof. and http://cs162.eecs.Berkeley.edu
Copyright By PowCoder代写 加微信 powcoder
Recall: Deadlock is A Deadly type of Starvation
• Starvation: thread waits indefinitely
– Example, low-priority thread waiting for resources constantly in use by high-priority threads
• Deadlock: circular waiting for resources
– ThreadA owns Res 1 and is waiting for Res 2 Thread B owns Res 2 and is waiting for Res 1
• Deadlock ⇒ Starvation but not vice versa
– Starvation can end (but doesn’t have to)
– Deadlock can’t end without external intervention
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Four requirements for occurrence of Deadlock
• Mutual exclusion
– Only one thread at a time can use a resource.
• Hold and wait
– Thread holding at least one resource is waiting to acquire additional resources held by other threads
• No preemption
– Resources are released only voluntarily by the thread holding the resource, after thread is finished with it
• Circular wait
– There exists a set {T1, …, Tn} of waiting threads » T1 is waiting for a resource that is held by T2
» T2 is waiting for a resource that is held by T3 »…
» Tn is waiting for a resource that is held by T1
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall:Techniques for Preventing Deadlock
• Make all threads request everything they’ll need at the beginning.
– Problem: Predicting future is hard, tend to over-estimate resources
– Example:
» If need 2 chopsticks, request both at same time
» Don’t leave home until we know no one is using any intersection between here and where you want to go; only one car on the Bay Bridge at a time
• Force all threads to request resources in a particular order preventing any cyclic use of resources
– Thus, preventing deadlock
– Example (x.Acquire(),y.Acquire(),z.Acquire(),…)
» Make tasks request disk, then memory, then…
» Keep from deadlock on freeways around SF by requiring everyone to go clockwise
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Rather than:
Request Resources Atomically (1)
x.Acquire();
y.Acquire(); ……
y.Release();
x.Release();
Consider instead:
Acquire_both(x, y);
x.Release();
y.Release();
Acquire_both(y, x);
y.Acquire();
x.Acquire();
y.Release(); x.Release(); x.Release(); y.Release();
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Request Resources Atomically (2)
Or consider this:
z.Acquire();
x.Acquire();
y.Acquire();
z.Release(); …… y.Release(); x.Release(); x.Release(); y.Release();
z.Acquire();
y.Acquire();
x.Acquire();
z.Release();
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Acquire Resources in Consistent Order
Rather than:
x.Acquire();
y.Acquire(); ……
y.Release();
x.Release();
Consider instead:
x.Acquire();
y.Acquire(); …… y.Release(); x.Release(); x.Release(); y.Release();
y.Acquire();
x.Acquire();
x.Release();
y.Release();
x.Acquire();
y.Acquire();
Does it matter in which order the locks are released?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Review:Train Example (Wormhole-Routed Network)
• Circular dependency (Deadlock!)
– Each train wants to turn right
– Blocked by other trains
– Similar problem to multiprocessor networks
• Fix? Imagine grid extends in all four directions
– Force ordering of channels (tracks)
» Protocol:Always go east-west first, then north-south
– Called “dimension ordering” (X then Y)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Disallowed By Rule
Techniques for Recovering from Deadlock
• Terminate thread, force it to give up resources
– In Bridge example, Godzilla picks up a car, hurls it into the river. Deadlock solved! – Hold dining lawyer in contempt and take away in handcuffs
– But, not always possible – killing a thread holding a mutex leaves world inconsistent
• Preempt resources without killing off thread
– Take away resources from thread temporarily
– Doesn’t always fit with semantics of computation
• Roll back actions of deadlocked threads
– Hit the rewind button on TiVo, pretend last few minutes never happened
– For bridge example, make one car roll backwards (may require others behind him) – Common technique in databases (transactions)
– Of course, if you restart in exactly the same way, may reenter deadlock once again
• Many operating systems use other options
3/3/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022
Another view of virtual memory: Pre-empting Resources
AllocateOrWait(1 MB)
AllocateOrWait(1 MB)
Free(1 MB)
Free(1 MB)
AllocateOrWait(1 MB)
AllocateOrWait(1 MB)
Free(1 MB)
Free(1 MB)
• Before:With virtual memory we have “infinite” space so everything will just succeed, thus above example won’t deadlock
– Of course, it isn’t actually infinite, but certainly larger than 2MB!
• Alternative view: we are “pre-empting” memory when paging out to disk, and giving it back when paging back in
– This works because thread can’t use memory when paged out
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Techniques for Deadlock Avoidance
• Idea:When a thread requests a resource, OS checks if it would result in deadlock
– If not, it grants the resource right away
– If so, it waits for other threads to release resources
THIS DOES NOT WORK!!!!
• Example:
x.Acquire(); Blocks… y.Acquire();
y.Acquire(); x.Acquire(); Wait?
y.Release(); x.Release(); x.Release(); y.Release();
But it’s already too late…
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.11
Deadlock Avoidance:Three States
• Safe state
– System can delay resource acquisition to prevent deadlock
Deadlock avoidance: prevent system from reaching an unsafe state
• Unsafe state
– No deadlock yet…
– But threads can request resources in a pattern that unavoidably leads to deadlock
• Deadlocked state
– There exists a deadlock in the system – Also considered “unsafe”
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.12
Deadlock Avoidance
• Idea:When a thread requests a resource, OS checks if it would result in deadlock an unsafe state
– If not, it grants the resource right away
– If so, it waits for other threads to release resources
• Example:
x.Acquire();
y.Acquire(); …… y.Release(); x.Release(); x.Release(); y.Release();
y.Acquire();
x.Acquire();
Wait until Thread A releases mutex X
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Banker’s Algorithm for Avoiding Deadlock
• Toward right idea:
– State maximum (max) resource needs in advance
– Allow particular thread to proceed if:
(available resources – #requested) ≥ max remaining that might be needed by any thread
• Banker’s algorithm (less conservative):
– Allocate resources dynamically
» Evaluate each request and grant if some
ordering of threads is still deadlock free afterward
» Technique: pretend each request is granted, then run deadlock detection algorithm, substituting:
([Maxnode]-[Allocnode] <= [Avail]) for ([Requestnode] <= [Avail])
Grant request if result is deadlock free (conservative!)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Banker’s Algorithm for Avoiding Deadlock
[Avail] = [FreeResources]
• Toward right idea:
Add all nodes to UNFINISHED
d–oS{tate maximum (max) resource needs in advance
done = true
– Allow particular thread to proceed if:
Foreach node in UNFINISHED {
(available resources - #requested) ≥ max
if ([Request
remaining that might be needed by any thread
[Avail] = [Avail] + [Allocnode] done = false
] <= [Avail]) { remove node from UNFINISHED
• Banker’s algorithm (less conservative):
}– uAnlltoicla(tedorneeso)urces dynamically
» Evaluate each request and grant if some
ordering of threads is still deadlock free afterward
» Technique: pretend each request is granted, then run deadlock detection algorithm, substituting:
([Maxnode]-[Allocnode] <= [Avail]) for ([Requestnode] <= [Avail])
Grant request if result is deadlock free (conservative!)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Banker’s Algorithm for Avoiding Deadlock
[Avail] = [FreeResources]
• Toward right idea:
Add all nodes to UNFINISHED
d–oS{tate maximum (max) resource needs in advance
done = true
– Allow particular thread to proceed if:
Foreach node in UNFINISHED {
(available resources - #requested) ≥ max
if ([Max ]-[Alloc ] <= [Avail]) { node node
remaining that might be needed by any thread
remove node from UNFINISHED [Avail] = [Avail] + [Allocnode] done = false
• Banker’s algorithm (less conservative):
}– uAnlltoicla(tedorneeso)urces dynamically
» Evaluate each request and grant if some
ordering of threads is still deadlock free afterward
» Technique: pretend each request is granted, then run deadlock detection algorithm, substituting:
([Maxnode]-[Allocnode] <= [Avail]) for ([Requestnode] <= [Avail])
Grant request if result is deadlock free (conservative!)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Banker’s Algorithm for Avoiding Deadlock
• Toward right idea:
– State maximum (max) resource needs in advance
– Allow particular thread to proceed if:
(available resources - #requested) ≥ max remaining that might be needed by any thread
• Banker’s algorithm (less conservative):
– Allocate resources dynamically
» Evaluate each request and grant if some
ordering of threads is still deadlock free afterward
» Technique: pretend each request is granted, then run deadlock detection algorithm, substituting:
([Maxnode]-[Allocnode] <= [Avail]) for ([Requestnode] <= [Avail])
Grant request if result is deadlock free (conservative!)
– Keeps system in a “SAFE” state: there exists a sequence {T1,T2, ... Tn} with T1 requesting all remaining resources, finishing, then T2 requesting all remaining resources, etc..
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.17
Banker’s Algorithm Example
• Banker’s algorithm with dining lawyers
– “Safe” (won’t cause deadlock) if when try to grab chopstick either:
» Not last chopstick
» Is last chopstick but someone will have two afterwards
– What if k-handed lawyers? Don’t allow if:
» It’s the last one, no one would have k
» It’s 2nd to last, and no one would have k-1 » It’s 3rd to last, and no one would have k-2 »...
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Deadlock Summary
• Four conditions for deadlocks
– Mutual exclusion – Hold and wait
– No preemption – Circular wait
• Techniques for addressing Deadlock
– Deadlock prevention:
» write your code in a way that it isn’t prone to deadlock
– Deadlock recovery:
» let deadlock happen, and then figure out how to recover from it
– Deadlock avoidance:
» dynamically delay resource requests so deadlock doesn’t happen » Banker’s Algorithm provides on algorithmic way to do this
– Deadlock denial:
» ignore the possibility of deadlock
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Virtualizing Resources
• Physical Reality:
Different Processes/Threads share the same hardware
– Need to multiplex CPU (Just finished: scheduling) – Need to multiplex use of Memory (starting today) – Need to multiplex disk and devices (later in term)
• Why worry about memory sharing?
– The complete working state of a process and/or kernel is defined by its data in memory (and registers)
– Consequently, cannot just let different threads of control use the same memory » Physics: two different pieces of data cannot occupy the same locations in memory
– Probably don’t want different threads to even have access to each other’s memory if in different processes (protection)
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.20
Recall: Four Fundamental OS Concepts
• Thread: Execution Context
– Fully describes program state
– Program Counter, Registers, Execution Flags, Stack
• Address space (with or w/o translation)
– Set of memory addresses accessible to program (for read or write)
– May be distinct from memory space of the physical machine (in which case programs operate in a virtual address space)
• Process: an instance of a running program
– Protected Address Space + One or more Threads
• Dual mode operation / Protection
– Only the “system” has the ability to access certain resources
– Combined with translation, isolates programs from each other and the OS from programs
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.21
THE BASICS:Address/Address Space
Address Space:
2k “things”
“Things” here usually means “bytes” (8 bits)
• What is 210 bytes (where a byte is appreviated as “B”)?
– 210 B = 1024B = 1 KB (for memory, 1K = 1024, not 1000)
• How many bits to address each byte of 4KB page?
– 4KB = 4×1KB = 4× 210= 212⇒ 12 bits
• How much memory can be addressed with 20 bits? 32 bits? 64 bits?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Address Space, Process Virtual Address Space
• Definition: Set of accessible addresses and the state associated with them
– 232 = ~4 billion bytes on a 32-bit machine
• How many 32-bit numbers fit in this address space?
– 32-bits = 4 bytes, so 232/4 = 230=~1billion
• What happens when processor reads or writes to an address?
– Perhaps acts like regular memory
– Perhaps causes I/O operation » (Memory-mapped I/O)
– Causes program to abort (segfault)? – Communicate with another program –...
Static Data
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Process Address Space: typical structure
Code Segment
Static Data
Stack Segment
Processor registers
sbrk syscall
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Single and Multithreaded Processes
• Threads encapsulate concurrency – “Active” component
• Address space encapsulate protection:
– “Passive” component
– Keeps bugs from crashing the entire system
• Why have multiple threads per address space?
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.25
Important Aspects of Memory Multiplexing
• Protection:
– Prevent access to private memory of other processes
» Different pages of memory can be given special behavior (Read Only, Invisible to user programs, etc).
» Kernel data protected from User programs
» Programs protected from themselves
• Translation:
– Ability to translate accesses from one address space (virtual) to a different one (physical)
– When translation exists, processor uses virtual addresses, physical memory uses physical addresses
– Side effects:
» Can be used to avoid overlap
» Can be used to give uniform view of memory to programs
• Controlled overlap:
– Separate state of threads should not collide in physical memory. Obviously, unexpected overlap causes chaos!
– Conversely, would like the ability to overlap when desired (for communication)
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Alternative View: Interposing on Process Behavior
• OS interposes on process’ I/O operations – How? All I/O happens via syscalls.
• OS interposes on process’ CPU usage
– How? Interrupt lets OS preempt current thread
• Question: How can the OS interpose on process’ memory accesses?
– Too slow for the OS to interpose every memory access
– Translation: hardware support to accelerate the common case – Page fault: uncommon cases trap to the OS to handle
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Loading
Address Spaces
OS Hardware Virtualization
Hardware ISA Processor
Protection Boundary
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 13.28
Binding of Instructions and Data to Memory
Process view of memory
data1:dw 32
start:lw r1,0(data1) jal checkit
loop: addi r1, r1, -1 bnz r1, loop
checkit: ...
Assume 4byte words
0x300 = 4 * 0x0C0 Physica0l xad0dC0res=se0s000 1100 0000 0x300 = 0011 0000 0000
0x0300 00000020 ...... 0x0900 8C2000C0 0x0904 0C000280 0x0908 2021FFFF 0x090C 14200242
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Binding of Instructions and Data to Memory
Process view of memory
data1:dw 32
start:lw r1,0(data1) jal checkit
loop: addi r1, r1, -1 bnz r1, loop
checkit: ...
Physical addresses
0x0300 00000020 ...... 0x0900 8C2000C0 0x0904 0C000280 0x0908 2021FFFF 0x090C 14200242
Physical Memory
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Second copy of program from previous example
Physical Memory
Process view of memory
Physical addresses
0x0900 data1:dw 32 0x030000000020 ?
start:lw r1,0(data1) jal checkit
loop: addi r1, r1, -1
bnz r1, loop ...
0x0900 8C2000C0 0x0904 0C000280 0x0908 2021FFFF 0x090C 14200242
checkit: ...
Need address translation!
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Second copy of program from previous example
Process view of memory
data1:dw 32
start:lw r1,0(data1) jal checkit
loop: addi r1, r1, -1 bnz r1, loop
checkit: ...
Physical addresses
0x1300 00000020 ...... 0x1900 8C2004C0 0x1904 0C000680 0x1908 2021FFFF 0x190C 14200642
Physical Memory
0x1A00 One of many possible translations!
Where does translation take place?
Compile time, Link/Load time, or Execution time?
Joseph & Kubiatowicz CS162 © UCB Spring 2022
From Program to Process
• Preparation of a program for execution involves components at:
– Compile time (i.e.,“gcc”)
– Link/Load time (UNIX “ld” does link) – Execution time (e.g., dynamic libs)
• Addresses can be bound to final values anywhere in this path
– Depends on hardware support
– Also depends on operating system
• Dynamic Libraries
– Linking postponed until execution
– Small piece of code (i.e. the stub), locates appropriate memory-resident library routine
– Stub replaces itself with the address of the routine, and executes routine
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Uniprogramming
• Uniprogramming (no Translation or Protection)
– Application always runs at same place in physical memory since only one application at a time
– Application can access any physical address 0xFFFFFFFF
Operating System
Application
0x00000000
– Application given illusion of dedicated machine by giving it reality of a dedicated machine
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Valid 32-bit Addresses
Primitive Multiprogramming
• Multiprogramming without Translation or Protection
– Must somehow prevent address overlap between threads
0xFFFFFFFF
Operating System
Application2 Application1
0x00020000
0x00000000
– Use Loader/Linker:Adjust addresses while program loaded into
memory (loads, stores, jumps)
» Everything adjusted to memory location of program » Translation done by a linker-loader (relocation)
» Common in early days (... till Windows 3.x, 95?)
• With this solution, no protection: bugs in any program can cause other programs to crash or even the OS
Joseph & Kubiatowicz CS162 © UCB Spring 2022
Multiprogramming w
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com