1-5 Flashcards
Virtualization:
(4)…
• The OS takes a physical resource and transforms it into a virtual form of itself
- Physical resource: Processor, Memory, Disk …
- The virtual form is more general, powerful and easy-to-use
- Sometimes, we refer to the OS as a virtual machine
System call allows user to __.
tell the OS what to do
The OS provides some __.
interface (APIs, standard library)
A typical OS exports a few hundred system calls:
(3)…
- Run programs
- Access memory
- Access devices
The OS manage resources such as (3)…
CPU, memory, and disk
The OS allows:
(3)…
- Many programs to run → Sharing the CPU
- Many programs to concurrently access their own instructions and data → Sharing memory
- Many programs to access devices → Sharing disks
Virtualizing the CPU:
• The system has a very large number of virtual CPUs
- Turning a single CPU into __.
- Allowing many programs to seemingly run at once → __.
a seemingly infinite number of CPUs;
Virtualizing the CPU
Virtualizing Memory:
The physical memory is an __.
array of bytes
Virtualizing Memory: 1. Read memory (load): ... 2. Write memory (store): ...
- Read memory (load):
Specify an address to be able to access the data - Write memory (store):
Specify the data to be written to the given address
Virtualizing Memory:
Each process accesses its own private __.
virtual address space
Virtualizing Memory:
Each process accesses its own private virtual address space.
- The OS maps __
- A memory reference within one running program does not affect __
- Physical memory is a __ resource, managed by the OS
address space onto the physical memory;
the address space of other processes;
shared
How to Provide the Illusion of Many CPUs?
(4)…
- Goal: run N processes at once even though there are M CPUs
• N»_space; M - CPU virtualizing
• The OS can promote the illusion that many virtual CPUs exist
• One isolated machine for each program - Time sharing
• Running one program, then stopping it and running another
• The potential cost is performance - What are the benefits?
• Ease of use for the programmer
• Protection – program runs on a restricted machine
A process is an __.
OS’s abstraction of a running program
What constitutes a process?
(3)…
1. Memory (address space) • Instructions • Data 2. Registers (state of the processor) • General purpose registers • Program counter (PC) • Stack pointer (SP) 3. I/O Information • List of files process currently has open
Process API:
These APIs are available on any modern OS:
(5)…
1. Create • Create a new process to run a program 2. Destroy • Halt a runaway process 3. Wait • Wait for a process to stop running 4. Miscellaneous Control • Suspend • Resume 5. Status • Get some status information about a process • How long it has been running • What state is it in
Process Creation:
(5)…
- Load a program code into memory, the address space of the process
• Programs reside on a disk in an executable format
• OS performs the loading process lazily
- Loads pieces of code or data only as they are needed during program execution (demand paging) - The program’s run -time stack is allocated
• Stack is used for local variables, function parameters, return address
• Initialize the stack with arguments
- argc and argv array of main() function - The program’s heap is created
• Used for explicitly requested dynamically allocated data
• malloc(); free() - The OS does some other initialization
• I/O setup (stdin, stdout, stderr) - Start the program running at the entry point main()
• The OS transfers control of the CPU to the newly-created process
A process can be in one of three states:
(3)…
- Running
• A process is running on the CPU - Ready
• A process is ready to run but for some reason the OS has chosen not to run it at this given moment - Blocked
• A process has performed some kind of operation that it is waiting on
• E.g., an disk request
Process Data Structures:
• The OS has some key data structures that track various pieces of information:
(2)…
1. Process list • Ready processes • Blocked processes • Current running process 2. Register context • A copy of all the registers for a process
The Process Control Block (PCB):
• A C-structure that __.
contains information about each process
The xv6 Kernel Process Structures:
// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
int eip;
int esp;
int ebx;
int ecx;
int edx;
int esi;
int edi;
int ebp;
};
// the different states a process can be in
enum procstate { (6)... };// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
int eip; // Index pointer register
int esp; // Stack pointer register
int ebx; // Called the base register
int ecx; // Called the counter register
int edx; // Called the data register
int esi; // Source index register
int edi; // Destination index register
int ebp; // Stack base pointer register
};
// the different states a process can be in
enum procstate { UNUSED, EMBRYO, SLEEPING,
RUNNABLE, RUNNING, ZOMBIE };The xv6 Kernel Process Structures:
// Per-process state
struct proc {
uint sz;
pde_t* pgdir;
char *kstack;
enum procstate state;
int pid;
struct proc *parent;
struct trapframe *tf;
struct context *context;
void *chan;
int killed;
struct file *ofile[NOFILE];
struct inode *cwd;
char name[16];
};// Per-process state
struct proc {
uint sz; // Size of process memory (bytes)
pde_t* pgdir; // Page table
char *kstack; // Bottom of kernel stack for this process
enum procstate state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
struct trapframe *tf; // Trap frame for current syscall
struct context *context; // swtch() here to run process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
char name[16]; // Process name (debugging)
};fork()
Makes a copy of the currently running process
• The newly-created process has its own copy of the address space, registers, and PC.
p1.c:
#include [LTS]stdio.h>
#include [LTS]stdlib.h>
#include [LTS]unistd.h>
int main(int argc, char *argv[]){
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if (rc [LTS] 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else { // parent goes down this path (main)
printf("hello, I am parent of %d (pid:%d)\n",
rc, (int) getpid());
}
return 0;
}
exec()
Replaces a process with a different program
• Run a program that is different from the calling program
p3.c:
int main(int argc, char *argv[]){
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if (rc [LTS] 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
char *myargs[3];
myargs[0] = strdup("wc"); // program: "wc" (word count)
myargs[1] = strdup("p3.c"); // argument: file to count
myargs[2] = NULL; // marks end of array
execvp(myargs[0], myargs); // runs word count
printf("this shouldn’t print out");
} else { // parent goes down this path (main)
int wc = wait(NULL);
printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
rc, wc, (int) getpid());
}
return 0;
}
wait()
Wait for a child process to finish
• This system call won’t return until the child has run and exited
Why are fork() and exec() separate functions?
(3)…
Necessary for building a UNIX shell
• Lets the shell run code after the call to fork() but before the call to exec()
• Can alter the environment of the about-to-be-run program
• Can easily support things like redirection and pipes
How to Efficiently Virtualize the CPU with Control?
• The OS needs to share the physical CPU by __.
time sharing
How to Efficiently Virtualize the CPU with Control?:
Issues:
(2)…
- Performance: How can we implement virtualization without adding excessive overhead to the system?
- Control: How can we run processes efficiently while retaining control over the CPU?
Direct Execution:
(10)…
OS:
- Create entry for process list
- Allocate memory for program
- Load program into memory
- Set up stack with argc / argv
- Clear registers
- Execute call main()
Program:
- Run main()
- Execute return from main()
OS:
- Free memory of process
- Remove from process list
Without limits on running programs, the OS wouldn’t be in control of anything and thus would be “__.”
just a library
What if a process wishes to perform some kind of restricted operation such as …
• Issuing an I/O request to a disk
• Gaining access to more system resources such as CPU or memory
Solution:
…
- Solution: Using protected control transfer
- User mode: Applications do not have full access to hardware resources
- Kernel mode: The OS has access to the full resources of the machine
System Call:
• Allow the kernel to carefully expose certain key pieces of functionality to user program, such as (4)…
- Accessing the file system
- Creating and destroying processes
- Communicating with other processes
- Allocating more memory
Trap instruction:
(2)…
- Jump into the kernel
* Raise the privilege level to kernel mode
Return-from-trap instruction:
(2)…
- Return into the calling user program
* Reduce the privilege level back to user mode
Limited Direction Execution Protocol @Boot
(2)…
- OS @ boot (kernel mode):
initialize trap table - Hardware:
remember address of … syscall handler
Limited Direction Execution Protocol @Run
(8)…
1. OS @ run (kernel mode): Create entry for process list Allocate memory for program Load program into memory Setup user stack with argv Fill kernel stack with reg/PC return-from -trap
- Hardware:
restore regs from kernel stack
move to user mode
jump to main
3. Program (user mode): Run main() … Call system call trap into OS
- Hardware:
save regs to kernel stack
move to kernel mode
jump to trap handler - OS @ run (kernel mode):
Handle trap
Do work of syscall
return-from-trap - Hardware:
restore regs from kernel stack
move to user mode
jump to PC after trap - Program (user mode):
…
return from main
trap (via exit()) - OS @ run (kernel mode):
Free memory of process
Remove from process list
How can the OS regain control of the CPU so that it can switch between processes?
(2)…
- A Cooperative Approach: Wait for system calls
* A Non-Cooperative Approach: The OS takes control
Processes periodically give up the CPU by making __ such as yield.
system calls
Processes periodically give up the CPU by making system calls such as yield:
(2)…
• The OS decides to run some other task
• Application also transfers control to the OS when they do something illegal
- Divide by zero
- Try to access memory that it shouldn’t be able to access
A process gets stuck in an infinite loop → __
Examples: early versions of the Macintosh OS, the old Xerox Alto system
A Non-Cooperative Approach: OS Takes Control:
A timer interrupt:
(3)…
- During the boot sequence, the OS starts the timer
- The timer raises an interrupt every so many milliseconds
- When the interrupt is raised:
• The currently running process is halted
• Save enough of the state of the program
• A pre-configured interrupt handler in the OS runs
A __ gives OS the ability to run again on a CPU.
timer interrupt
Saving and Restoring Context:
Scheduler makes a decision:
(2)…
- Whether to continue running the current process, or switch to a different one
- If the decision is made to switch, the OS executes context switch
Context Switch:
(3)…
A low-level piece of assembly code
1. Save a few register values for the current process onto its kernel stack
• General purpose registers
• PC
• Kernel stack pointer
2. Restore a few register values for the soon-to-be-executing process from its kernel
stack
3. Switch to the kernel stack for the soon-to-be-executing process
Limited Direction Execution Protocol (Timer interrupt) @Boot
(4)…
- OS @ boot
(kernel mode)
initialize trap table - Hardware
remember address of …
syscall handler
timer handler - OS @ boot
(kernel mode)
start interrupt timer - Hardware
start timer
interrupt CPU in X ms
Limited Direction Execution Protocol (Timer interrupt) @Run:
(5)…
- Program (user mode):
Process A
…
2. Hardware: timer interrupt save regs(A) to k-stack(A) move to kernel mode jump to trap handler for timer
3. OS @ run (kernel mode): Handle the trap Call switch() routine save regs(A) to proc-struct(A) restore regs(B) from proc-struct(B) switch to k-stack(B) return-from-trap (into B)
- Hardware:
restore regs(B) from k-stack(B)
move to user mode
jump to B’s PC - Program (user mode):
Process B
…
What happens if, during interrupt or trap handling, another interrupt occurs?
OS handles these situations:
(2)…
- Disable interrupts during interrupt processing
* Use a number of sophisticated locking schemes to protect concurrent access to internal data structures
Separating Policy and Mechanism:
- Design paradigm
(1) … - Mechanism
(2) … - Policy
(2) …
- Design paradigm
• Separate high-level policies from their low-level mechanisms - Mechanism
• Answers the “how” question about a system
• How does the OS perform a context switch? - Policy
• Answers the “which” question about a system
• Which process should the OS run right now?
Initial workload assumptions (we’ll relax these assumptions later):
(5)…
- Each job runs for the same amount of time
- All jobs arrive at the same time
- Once started, each job runs to completion
- All jobs only use the CPU (i.e., they don’t perform any I/O)
- The run-time of each job is known
