Midterm

Question 1

What is an OS?

Answer 1

A program that acts as an intermediary between a user and the computer hardware. It can be software, hardware, software and hardware mixed.

Question 2

What happens when an interrupt occurs?

Answer 2

The cpu transitions from user mode(mode bit = 1) to kernel mode(mode bit = 0)

Question 3

What happens on a hardware interrupt?

Answer 3

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

Question 4

How does XV6 pass parameters for a syscall?

Answer 4

By pushing them onto the stack of the calling process. Then they are popped off the stack by the OS

Question 5

What is a syscall?

Answer 5

A programming interface to OS services. Each syscall has a corresponding function in the OS kernel

Question 6

What is a race condition and how can we solve it?

Answer 6

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

Question 7

Each process has a PCB which includes what?

Answer 7

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

Question 8

What is a context switch?

Answer 8

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

Question 9

Process creation: fork(). What is fork’s ret value for the parent and child? What happens?

Answer 9

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.

Question 10

Process Termination:

1) What happens if no parent invoked wait() and the child terminates?
2) What happens if the parent terminates with invoking wait()?

Answer 10

1) child becomes a zombie
2) child becomes an orphan. Then is adopted by init process (pid = 1)

Question 11

What is copy-on-write?

Answer 11

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.

Question 12

Context Switching steps

Answer 12

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

Question 13

What are critical sections and what are the different ways to implement them?

Answer 13

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

Question 14

For busy waiting, mutual exclusion, semaphores, mutexes, monitors, condition variables, and barriers, read …

Answer 14

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

Question 15

Issues with Busy waiting
What is the solution?

Answer 15

1) wastes CPU cycles
2) Priority Inversion - higher priority process waits on a lower priority process

Solution = semaphores

Question 16

Issues with Semaphores and their solutions

Answer 16

1) Any process can up the semaphore
solution: mutex
2) Deadlock and Starvation

3) Priority Inversion
solution: priority inheritance

Question 17

When are spinlocks better than semaphores?

Answer 17

Very short waiting time to enter critical section - less than 2 context switches

Multi-core systems

Few contending processes

Short critical section code

Question 18

First Come First Served

Selection function? Decision Mode?

Favors CPU or IO bound processes?

Starvation?

Answer 18

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

Question 19

Shortest Job First

Selection function? Decision Mode?

Favors CPU or IO bound processes?

Starvation?

Other criticisms?

Answer 19

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

Question 20

Priority Scheduling

Selection function? Decision Mode?

Potential problem? Solution?

Answer 20

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.

Question 21

Round Robin Scheduling

Selection function? Decision Mode?

Favors CPU or IO bound processes?

Starvation?

Potential problems?

Answer 21

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

Question 22

Multilevel Feedback Scheduling

Selection function? Decision Mode?

How does it work?

Favors CPU or IO bound processes? Why?

Starvation?

Answer 22

Selection function: Dispatcher selects a process for execution from RQ_i only if RQ_i-1 to RQ₀ 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 RQ₀

After the first quantum, they are moved to RQ₁ then after the second quantum, to RQ₂ 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

Question 23

CPU Burst Estimation

What is the overall concept?

Simple averaging equation for SJF estimation?

Exponential averaging equation? Which alpha value to use?

Answer 23

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

Question 24

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?

Answer 24

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.