CS计算机代考程序代写 data structure PowerPoint Presentation

PowerPoint Presentation

Memory Virtualization:
Questions answered in this lecture:
What is in the address space of a process (review)?
What are the different ways that that OS can virtualize memory?
Time sharing, static relocation, dynamic relocation
(base, base + bounds, segmentation)
What hardware support is needed for dynamic relocation?

CSE 2431
Introduction to Operating Systems
Based on slides by Andrea C. Arpaci-Dusseau
Remzi H. Arpaci-Dusseau

JOB arrival run
A 0 40
B 0 20
C 5 10

A
B

A
B
C

60
80

A
B

A
Workload
Schedulers:
FIFO
SJF
STCF
RR
Timelines
RR
SJF
STCF
FIFO
Scheduling Policy:
Review

Motivation for
Virtualization
Uniprogramming: One process runs at a time

User
Process
OS
Physical Memory
0
2n-1

Stack
Code
Heap

Address
Space
Disadvantages:
Only one process runs at a time
Process can destroy OS

Modern Systems
We want multiprogramming (or multitasking)
This means more than one program can be run as a process at any given time.
Thus, in modern systems, we have many processes running at any given time typically (virtually always).
Major Complication: This means that all these processes have to share:
A single CPU (prior slides – CPU virtualization)
A single physical memory (This, and following slide sets, Memory virtualization)

Multiprogramming
Goals
Transparency
Processes are not aware that memory is shared
Works regardless of number and/or location of processes
Protection
Cannot corrupt OS or other processes
Privacy: Cannot read data of other processes
Efficiency
Do not waste memory resources (minimize fragmentation)
Sharing
Cooperating processes can share portions of address space

Abstraction: Address SPace
Address space: Each process has set of addresses that map to bytes
Problem:
How can OS provide illusion of private address space to each process?
Review: What is in an address space?
Address space has static and dynamic components
Static: Code and some global variables
Dynamic: Stack and Heap

Stack
Code
Heap

0
2n-1

Motivation for
Dynamic Memory
Why do processes need dynamic allocation of memory?
Do not know amount of memory needed at compile time
Must be pessimistic when allocate memory statically
Allocate enough for worst possible case; Storage is used inefficiently
Recursive procedures
Do not know how many times procedure will be nested
Complex data structures: lists and trees
struct my_t *p = (struct my_t *)malloc(sizeof(struct my_t));
Two types of dynamic allocation
Stack
Heap

Stack Organization
Definition: Memory is freed in opposite order from allocation
alloc(A);
alloc(B);
alloc(C);
free(C);
alloc(D);
free(D);
free(B);
free(A);
Simple and efficient implementation:
Pointer separates allocated and freed space
Allocate: Increment pointer
Free: Decrement pointer
No fragmentation

Where Are stacks Used?
OS uses stack for procedure call frames (local variables and parameters)
main () {
int A = 0;
foo (A);
printf(“A: %d\n”, A);
}
void foo (int Z) {
int A = 2;
Z = 5;
printf(“A: %d Z: %d\n”, A, Z);
}

Heap Organization
Advantage
Works for all data structures
Disadvantages
Allocation can be slow
End up with small chunks of free space – fragmentation
Where to allocate 12 bytes? 16 bytes? 24 bytes??
What is OS’s role in managing heap?
OS gives big chunk of free memory to process; library manages individual allocations
Definition: Allocate from any random location: malloc(), new()
Heap memory consists of allocated areas and free areas (holes)
Order of allocation and free is unpredictable
Free
Free
Alloc
Alloc
16 bytes
24 bytes
12bytes
16 bytes
A
B

Quiz: Match that Address Location
int x;
int main(int argc, char *argv[]) {
int y;
int *z = malloc(sizeof(int)););
}
Address Location
x
main
y
z
*z

Possible segments: static data, code, stack, heap
Static data
Code
Stack
Stack
Heap
What if no static data segment?
 Code

Memory Accesses
#include
#include

int main(int argc, char *argv[]) {
int x;
x = x + 3;
}

otool -tv demo1.o
(or objdump on Linux)
0x10: movl 0x8(%rbp), %edi
0x13: addl $0x3, %edi
0x19: movl %edi, 0x8(%rbp)
%rbp is the base pointer:
points to base of current stack frame

Quiz: Memory Accesses?
0x10: movl 0x8(%rbp), %edi
0x13: addl $0x3, %edi
0x19: movl %edi, 0x8(%rbp)
Fetch instruction at addr 0x10
Exec:
load from addr 0x208

Fetch instruction at addr 0x13
Exec:
no memory access

Fetch instruction at addr 0x19
Exec:
store to addr 0x208
Initial %rip = 0x10
%rbp = 0x200

%rbp is the base pointer:
points to base of current stack frame

%rip is instruction pointer (or program counter)
Memory Accesses to what addresses?

Question
The problem we have to solve (actually, that the OS has to solve) is raised by this question: What if we run the same program shown on the prior slide as two different processes at the same time?
Of course, you may want to do this kind of thing (open two process instances of a browser, for example).
Even if we run two different programs at the same time as distinct processes, the problem still comes up, because all programs start the addresses in their address spaces at 0x0.

How to Virtualize Memory?
Problem: How to run multiple processes simultaneously?
Addresses are “hardcoded” into process binaries
How to avoid collisions?
Possible Solutions for Mechanisms (covered today):
Time Sharing
Static Relocation
Base
Base+Bounds
Segmentation

1) Time Sharing of Memory
Try similar approach to how OS virtualizes CPU
Observation:
OS gives illusion of many virtual CPUs by saving CPU registers to memory when a process isn’t running

Could give illusion of many virtual memories by saving memory to disk when process isn’t running (and when it’s time for process to run again, bring address space back into memory from disk).

code
data
Program

Memory
Time Share Memory: Example

code
data
Program

Memory
code
data
heap

stack
Process 1

create

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

create

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

code
data
Program

Memory
code
data
heap

stack
Process 1

code
data2
heap2

stack2
Process 2

Problems with
Time Sharing Memory
Problem: Ridiculously poor performance
Better Alternative: space sharing
At any time, space of memory is divided across processes
Remainder of solutions all use space sharing

2) Static Relocation
Idea: OS rewrites each program before loading it as a process in memory (by adding address where it will be loaded to address in program)
Each rewrite for different process uses different addresses and pointers
Change jumps, loads of static data
0x10: movl 0x8(%rbp), %edi
0x13: addl $0x3, %edi
0x19: movl %edi, 0x8(%rbp)
0x1010: movl 0x8(%rbp), %edi
0x1013: addl $0x3, %edi
0x1019: movl %edi, 0x8(%rbp)
0x3010: movl 0x8(%rbp), %edi
0x3013: addl $0x3, %edi
0x3019: movl %edi, 0x8(%rbp)

rewrite
rewrite

(free)
Program Code
stack
Heap
(free)
Program Code
stack
Heap
(free)
(free)
(free)

4 KB
8 KB
12 KB
16 KB

process 1
process 2

0x1010: movl 0x8(%rbp), %edi
0x1013: addl $0x3, %edi
0x1019: movl %edi, 0x8(%rbp)
0x3010: movl 0x8(%rbp), %edi
0x3013: addl $0x3, %edi
0x3019: movl %edi, 0x8(%rbp)
Static: Layout in Memory

Static Relocation: Disadvantages
No protection
Process can destroy OS or other processes
No privacy

Cannot move address space after it has been placed (relocation is STATIC, that is, before process starts executing instructions )
May not be able to allocate new process, if do not have a free space (hole) in memory which is large enough, with all the processes currently running.

3) Dynamic Relocation
Goal: Protect processes from one another; enable movement of process address space after it starts running
Requires hardware support
Memory Management Unit (MMU)
MMU dynamically changes process address at every memory reference
Process generates logical or virtual addresses (in their address space)
Memory hardware uses physical or real addresses

CPU
MMU
Memory

Process runs here
OS can control MMU
Logical address
Physical address

Hardware Support for
Dynamic Relocation
Two operating modes
Privileged (protected, kernel) mode: OS runs
When enter OS (trap, system calls, interrupts, exceptions)
Allows certain instructions to be executed
Can manipulate contents of MMU
Allows OS to access all of physical memory
User mode: User processes run
Perform translation of each logical address to physical address
Minimal MMU contains base register for translation
base: start location for physical address space

Implementation of
Dynamic Relocation: BASE REG
Translation on every memory access by user process
MMU adds base register (memory offset) to logical address to form physical address

base
mode
registers
32 bits
1 bit
mode
=
user?
no
yes

+
base

logical
address
physical
address
MMU

Dynamic Relocation with Base Register
Idea: translate virtual addresses to physical by adding a fixed offset each time.
OS stores offset in base register whenever process is going to run
Each process has different value in base register

4 KB
5 KB
6 KB
2 KB
3 KB
1 KB
0 KB
same code

VISUAL Example of DYNAMIC RELOCATION:
BASE REGISTER

4 KB
5 KB
6 KB
2 KB
3 KB
1 KB
0 KB

base register
P1 is running

4 KB
5 KB
6 KB
2 KB
3 KB
1 KB
0 KB

base register
P2 is running