CSC369 Midterm Review Notes

Based on CSC369 slides

OS is a

- virtual machine: extends and simplifies physical system and provide API ..

- resource allocator: allows proper use of resources, provides an environment for programs

- control program: control execution of user programs, prevent errors and improper use

Storage

Main Memory(DRAM):

- small & volatile

- directly accessible by CPU

- a large array of bytes, each has its own address

- byte-addressable

CPU + L1 Cache →  L2/L3 Cache →  Main Memory →  Disk → Tape

Hardware Support for OS

• Protection domains -> mode bit
• privileged instructions
• user mode -> privileged instructions -> protection fault -> trap to OS
• Interrupts
• hardware signal causes CPU to jump to pre-defined interrupt handler
• caused by software/hardware - (division by zero/timer interrupt)
• is a mechanism to support OS’s efficient virtualization:
• any illegal instruction executed by a process causes interrupt → make sure OS gain control when sth is wrong
• Periodic hardware-generated timer interrupt ensures OS get control at regular intervals
• Hardware Interrupt: device controllers → sigal CPU some event has occurred
• Software Interrupt: used to signal errors or system calls

→ traps  or exceptions

• Timers
• memory Management Unit
• Other Hardware

Bootstrapping

• HW stores small program in non-volatile memory
• BIOS
• Power on:

1. system mode
2. OS initialization
1. initialize internal data structures
2. create first process (init)
3. switch mode for user and start running first process
4. wait for something to happen
1. something always starts with an interrupt
2. OS is event-driven
   
   
   

Process

• Def: a program in execution
• active entity
• (programs are not active, they are static entities with the potential for execution)

Process State

Components

• All state for program
• Address Space (memory)
• code and data
• execution stack → state of procedure calls
• PC for next instruction
• set of registers with values
• set of os resources
• open files, network connections, etc.
• Name: Process ID (PID)
• OS data about the process is stored in a process control block (PCB)

Process Control Block

Generally includes:

• process state (ready, running, blocked …)
• program counter: address of the next instruction
• CPU registers: must be saved at an interrupt
• CPU scheduling information: process priority
• memory management info: page tables
• accounting information: resource use info
• I/O status information: list of open files

Queues (generally one queue per state)

Process creation: create by other process

Unix example:

• fork() → make a copy of parent, returns twice
• exec(prog, argv) → stop current thread and load program “prog” into the thread’s address space, initialize hardware context and args for new program, places PCB into ready queue..
• exec return: failed

Process destruction: zombies need to be cleaned up by parents

Inter-Process Communication (IPC)

OS provide various mechanisms for IPC:

• passing arguments to a newly exec’d program
• return exit status
• sending signals → software interrupt: kill()
• shared file system
• message passing, shared memory, synchronization primitives..

System Calls

• System Call Interface
• user program call C library w/ arguments
• C library passing arguments and system call identifier to OS
• executes special instruction to trap to system mode
• interrupt/trap vector transfers control to a system call handling routine

(HW support needed here)

• syscall handler figures out which sys call is needed and call that operation

A thread is a single control flow through a program

kernel-level threads

- managed by kernel

- called kernel-level threads or lightweight processes

- all thread operations implemented in kernel

- limitation: still slow, every thread operations need a system call

user-level threads

- managed by run-time system (user level library)

- limitation: OS does not see, will have scheduling problem

- to solve the limitation, need OS to communicate with thread manager

synchronization is a mechanism

uses of synchronization:

1. Enforce single use of a shared resource

→ critical section problem

2. Control order of thread execution

e.g. parent waits for child to finish

race condition

What program data is shared by threads in the same address space?

• Local variables are NOT shared (private)
• located on the thread’s private own stack
• Global variables and static objects are shared
• stored in the static data segment
• Dynamic objects and other heap objects are shared

Critical Section Requirements

1. Mutual Exclusion
2. Progress
3. Bounded waiting (no starvation)

2-thread solutions:

1. shared variable turn for permission for which thread to run
1. → not satisfy progressing requirement
2. shared array of status, only enter CS if the other one is not interested:

while (flag[1-id]) ; /* entry section */

flag[id] = true; /* indicate entering CS */

/* critical section, access protected resource */

flag[id] = false; /* exit section */

... /* remainder section */

→ mutual exclusion not guaranteed

→ cannot fix by switching checking and setting → lead to deadlock

3. Peterson’s Algorithm

set own flag & set turn to self

spin wait while turn is self AND other has flag set

4. Lamport’s Bakery Algorithm

upon entering each thread gets a number;

thered gets the lowest number served first

in case of tie, thread with the lowest id goes first

Synchronization Hardware

• TAS: Test and Set

→ spinlock: busy waiting

• Swap/ Exchange

Problems with Machine Instructions:

1. Busy waiting
2. Starvation is possible
3. Deadlock possible through priority inversion

Sleep Lock

→ put thread into “blocked” state while waiting

→ requires a queue for waiting threads

Semaphores

• a counter
• a queue

→ wait/P: block if counter = 0, decrement counter

→ signal/V: increment counter, unblock waiting thread

Types of Semaphores

• Mutex

single access, mutual exclusion

• Counting Semaphore

max value is determined by initial value count

Conditional Variables

Abstract data type that encapsulates pattern of “release mutex, sleep, re-acquire mutex”

…

Monitors

…

Scheduling

Mechanisms:

• thread states, thread queues

• Policies:

• Given more than one runnable thread, how do we choose which to run next?

• When do we make this decision?

Scheduling

• Goals
• Fairness
• Avoid Starvation
• Policy enforcement
• Balance
• Time
• Enters Ready State: I/O interrupts, signals, thread creation
• When the running thread blocks or exits: syscalls, signals
• Fixed intervals: clock interrupts
• Types
• Non-preemptive: once a thread has cpu, let it runs til it terminats or blocks
• Preemptive: CPU can be taken

Scheduling Algorithms:

• FCFS: First come, first served
• Non-preemptive
• Choose from top of queue, queue is in FIFO order
• Average wait time usually long (convoy effect)
• SJF (Shortest Job First) aka SJF(Shortest Process Next)
• pre-emptive version of “shortest remaining time”
• provably optimal w.r.t. average wait time
• RR (Round Robin)
• preemptive
• ready queue circular
• quantum time is critical: want q to be large w.r.t context switch time
• Priority Scheduling
• pre-emptive or non-preemptive
• priority inversion can occur
• starvation is possible
• Multi-Level Queue Scheduling
• multiple ready queue, threads permanently assigned to a queue, each queue has own scheduling algorithm
• another level of scheduling decides which queue goes next (usually priority based)
• Feedback Scheduling
• adjust criteria for choosing a particular thead based on past history
• Combie with MLQ to move threads between queues → multi-level feedback queue (MLFQ)
• Fair Share Scheduling
• group threads
• ensure each group has proportional share
• priority of a thread depends on its own priority and past history of whole group
• Lottery scheduling variant - each group is assigned “tickets” according to its share
• Unix CPU Scheduling
• interactive threads favoured
• small CPU time slices are given to threads by a priority algorithm that reduces to RR for CPU-bound jobs
• the more CPU time a thread accumulates, the lower its priority becomes (negative feedback)
• aging prevents starvation
• RR scheduling results from a timeout mechanism
• MLFQ with RR within each priority queue

Memory Management

• Requirements
• Relocation
• Implies address translation
• Protection
• need hardware support
• Sharing
• ability, ways to specify and control
• Logical Organization
• Physical Organizaiton
• Solutions
• virtual memory
• based on segmentation and/or paging
• simpler schemes:
• Fixed partitioning
• Dynamic partitioning
• Paging
• Segmentation

Address Binding

• address translation: processing of linking variable names to physical locations
• Timing:
• compile time → absolute code
• Load time (static relocation)
• Execution time (dynamic relocation)

Logical vs. Physical Memory

Fixed Partitioning of Physical Memory

• Concept
• Fixed partiioning
• OS one partitioning
• one partition per process
• internal fragmentation - memory wasted when process smaller than partitioning
• overlays - programmers must deal when process bigger than partitioning
• Placement
• # partition = # process
• if full, needs to swap some out
• loading
• equal sized: anyone
• unequal-sized:
• queue-per-partition
• single queue, assign process to smallest available

Dynamic Partitioning

• exact sized partition
• “holes” when process goes
• external fragmentation: holes too small for any process
• compaction: OS may move process around to create larger free space
• require process to be relocatable
• need to know max size of process at load time
• Placement algorithms
• First-fit
• Best-fit
• Worst-fit
• Quick-fit

Paging