Midterm Flashcards
What is an OS?
A program that acts as an intermediary between a user and the computer hardware. It can be software, hardware, software and hardware mixed.
What happens when an interrupt occurs?
The cpu transitions from user mode(mode bit = 1) to kernel mode(mode bit = 0)
What happens on a hardware interrupt?
1) CPU checks for interrupts after executing each instruction. Keyboard interrupt.
2) reads IDT register for IDT memory address.
3) Saves old mode bit on kernel stack then Changes mode bit to 0 kernel mode
4) Accesses entry 1 in IDT table because keyboard is interrupt number 1.
5) Saves PC value onto kernel stack then Copies address in entry 1, which is function number 1, into the Program Counter register
6) Function 1 executes
7) ISR finishes, special instruction iret (return from interrupt) executes
8) CPU switches mode bits back to what they were before, user mode (mode bit = 1)
9) Pops the kernel stack to load the PC instruction that was saved before interrupt
How does XV6 pass parameters for a syscall?
By pushing them onto the stack of the calling process. Then they are popped off the stack by the OS
What is a syscall?
A programming interface to OS services. Each syscall has a corresponding function in the OS kernel
What is a race condition and how can we solve it?
Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
Solve by ensuring process synchronization
Each process has a PCB which includes what?
A Process Control Block contains:
Process state - running, waiting, etc
Program Counter - location of inst to execute next
CPU registers - contents of all process registers
Scheduling info - priorities, scheduling queue pointers
Memory management info - memory allocated to process
Accounting info - CPU used, clock time elapsed, time limits
IO status - IO devices allocated to process, list of open files
What is a context switch?
Switching the CPU to another process requires switching to kernel mode and performing a state save of the current process and a state restore of a different process. Then next process runs
Process creation: fork(). What is fork’s ret value for the parent and child? What happens?
Fork’s ret values are their pids
Parent: pid = > 0
Child: pid = 0
A copy of the parent’s address space is created for the child, duplicating the pages and giving them to the child as well. Therefore they share all the same variables on those pages upon time of creation.
Both parent and child proceed to instruction directly after fork.
Process Termination:
1) What happens if no parent invoked wait() and the child terminates?
2) What happens if the parent terminates with invoking wait()?
1) child becomes a zombie
2) child becomes an orphan. Then is adopted by init process (pid = 1)
What is copy-on-write?
However, considering that many child processes invoke the exec() system
call immediately after creation, the copying of the parent’s address space may
be unnecessary. Instead, we can use a technique known as copy-on-write,
which works by allowing the parent and child processes initially to share the
same pages. These shared pages are marked as copy-on-write pages, meaning
that if either process writes to a shared page, a copy of the shared page is
created.
Context Switching steps
Reminder: Stack grows downwards for XV6
%esp stack pointer points to top of P0 stack. Context field inside the PCB of P1 points to the top of its stack.
1) Interrupt or syscall occurs. Context switch from P0 to scheduler then scheduler to P1; Swtch() function.
-Parameters for this function are the context for both processes and are pushed onto process which invoked swtch(), P0
2) Swtch() function executes.
-First 2 instructions are moving the parameters into %eax and %edx.
-Save the state of P0 onto its own stack. %esp is now pointing to top of this stack.
-Switch stacks by copying the %esp pointer value to whatever %eax is pointing to (context of P0). This means that the
context of P0 is now pointing to the top of the stack of P0
-Copy %edx, which is pointing to top of P1 stack, into %esp. Now %esp is pointing to P1s stack.
3) Load new process registers
- 4 pops
- Now we arrived at the return instruction which is popped into the %eip, instruction pointer.
4) Next instruction in P1 is now executing
What are critical sections and what are the different ways to implement them?
A section of code that only one process can run at a time. Code can be shared and accesses shared data.
- Mutex locks
- spinlocks
- Semaphores
- Monitors
For busy waiting, mutual exclusion, semaphores, mutexes, monitors, condition variables, and barriers, read …
Busy waiting, mutexes, semaphores: Process notes and start on pg 212
Mutual exclusion; pg 209
Condition variables: Producer Consumers Notes
Monitors: start on pg 223
Barriers: Process notes; test&set, spinning
Issues with Busy waiting
What is the solution?
1) wastes CPU cycles
2) Priority Inversion - higher priority process waits on a lower priority process
Solution = semaphores
Issues with Semaphores and their solutions
1) Any process can up the semaphore
solution: mutex
2) Deadlock and Starvation
3) Priority Inversion
solution: priority inheritance
When are spinlocks better than semaphores?
Very short waiting time to enter critical section - less than 2 context switches
Multi-core systems
Few contending processes
Short critical section code
First Come First Served
Selection function? Decision Mode?
Favors CPU or IO bound processes?
Starvation?
Selection function: The process that has been waiting the longest in the ready queue will be selected
Decision Mode: Non-preemptive
- As a result, process run-through is simple, free from race conditions, but less responsive
Favors CPU bound processes
Starvation is NOT possible
Shortest Job First
Selection function? Decision Mode?
Favors CPU or IO bound processes?
Starvation?
Other criticisms?
Selection function: The process with the shortest expected CPU burst time is selected
Decision Mode: Non-preemptive
As a result, process runthrough is simple, free from race conditions, but less responsive
Favors IO bound processes since these have lower burst times
Possibility of starvation for longer processes
Implicitly incorporates priorities (shortest jobs are preferred first), therefore CPU could get monopolized by IO processes or CPU processes that entered first
Priority Scheduling
Selection function? Decision Mode?
Potential problem? Solution?
Selection function: Selects Process with highest priority
Priority is relative - Defined either internally(some measurable quantity like memory requirement) or externally(Set by criteria outside the OS)
Decision Mode: Either Preemptive(priority is compared when preempted) or Non-preemptive(placed at front of ready queue if higher priority)
Potential Problem: Indefinite Blocking - Low priority processes waiting for the CPU, but never or almost never reached
Solution: Aging - Gradually increasing priority of processes that have been waiting for a long time.
Round Robin Scheduling
Selection function? Decision Mode?
Favors CPU or IO bound processes?
Starvation?
Potential problems?
Selection function: The process that has been waiting the longest in the ready queue
Decision mode: Preemptive
As a result, process run-through is more complicated, not free from race conditions, but more responsiveFavors CPU bound processes like FCFS
Starvation free
Potential problems: Must be careful with quantum.
1) Quantum must be larger than the required time to handle the clock interrupt and dispatching
2) Quantum must be larger than the typical interaction
3) Quantum cannot be too much larger to avoid penalizing IO bound processes
Multilevel Feedback Scheduling
Selection function? Decision Mode?
How does it work?
Favors CPU or IO bound processes? Why?
Starvation?
Selection function: Dispatcher selects a process for execution from RQi only if RQi-1 to RQ0 are all empty
Decision Mode: Preemptive with dynamic priorities
As a result, process run-through is complicated, not free from race conditions, but more responsive
How it works: Newest processes = Highest priority, placed into RQ0
After the first quantum, they are moved to RQ1 then after the second quantum, to RQ2 and so on. Each queue has its own scheduling algorithm.
Favors IO bound processes because their turnaround times are less than CPU bound processes. Quantums increase up the Ready queues.
Starvation is possible with long jobs
CPU Burst Estimation
What is the overall concept?
Simple averaging equation for SJF estimation?
Exponential averaging equation? Which alpha value to use?
Recent instances are more likely to better reflect future behavior
n = number of measurements
S[n] = Previous estimate
T[n] = most recent measurement
Simple averaging: S[n+1] = (1/n) * T[n] + (n-1/n) * S[n]
Exponential averaging: S[n+1] = alpha * T[n] + (1 - alpha) * S[n]
where 0 < alpha < 1
Higher alpha = more weight on new measurements
Lower alpha = more weight on old measurements
Alpha value to use: alpha = 0.8 is closest to actual observation. To look at trend, use smaller alpha like 0.5
Memory Management
Fixed memory partitions: How it works and input queue structure
Base and Limit registers
Physical address and logical address. What is OS’s job in this?
Fixed memory partitions: Divide memory into fixed spaces and assign a process to a space when it is free.
Separate input queues for each partition (local), search quickly within queue, but partitions that can take processes cannot take other partitions’ processes that might need help
or
Single input queue for all partitions (global), better ability to optimize CPU usage, but have to search for next process to run in large queue.
Base register stores starting address of that process partition
Limit register stores process partition size
Physical address: location in actual memory. Base + logical address
- On bus in memory
Logical/virtual address: location from the process’s point of view. Cannot be larger than limit.
- From CPU to MMU, intercepts CPU and memory to check logical address and convert to physical address. Then sends it to memory.
OS’s job is to change base and limit registers every time process is switched.
