Operating Systems: Revision Notes (COMP2432, PolyU, 2018)

date

Apr 30, 2018

slug

os-notes

status

Published

tags

Course Notes

summary

The revision notes for final exam of the university course of Operating Systems.

type

Post

Operating System: a program

I/O processing:

synchronous I/O

wait & notified
At most one I/O request is outstanding at a time

asynchronous I/O

I/O and program running at the same time
There could be several I/O request at a time
device-status table: for each I/O device

Interrupt:

Definition: A signal to CPU to tell it about the occurrence of a major event.
Types:

According to priority:

Maskable interrupt: may be ignored or handled later (wait)
Non-maskable interrupt: must be handled immediately

coule be over-interrupted by others (caused "nested interrupts")

According to causes:

Program interrupt (trap)

caused by CPU error (e.g. illegal instruction, overflow, devision by zero, memory access violation) or special instruction

I/O interrupt

caused by I/O related events (e.g. I/O completion, device errors)

Timer (watchdog timer) interrupt

caused by hardware timer
to handle time-related events
to prevent infinite loop and resources hogging by processes for OS by setting up an "alarm"
plays a central role in process scheduling and resource management in Unix.

ISR: interrupt service routine (or interrupt handler)

a program to handle interrupt
stored in "interrupt table" with an index to identify
When interrupt, corresponding ISR will be run

Program interrupts implementation by OS

(almost all) OS: interrupt-driven

allow OS to gain control of the system when necessary

Privileged commands: special interrupt-related commands (execution should be prevented from users)
Dual-mode operation:

User mode (1): Only normal instructions available but not privileged instructions
Kernel mode (System mode / Privileged mode / Supervisor mode) (0): all instructions available
Mode bit: To distinguish them on hardware

System call (or monitor call): for a user process to do I/O that needs to execute privileged instructions.

A program interrupt (trap) that

changes from user mode to kernel mode,
executes the privileged I/O command,
returns from system call, and
reverts back to user mode to continue execution

an API to execute system functions by user programs

API: Application Program Interface

System call table / system call routines with indexes (just like interrupt)
Types of SC:

Process control
File management
Device management
Information maintenance
Communications

Parameter passing:

Three general method:

Register (on CPU)
Table (as a block on memory)

pass the address of block as a parameter in a register

Stack (on stack of the program)

Types of System Programs:

File management
File modification
Status information
Programming language support
Program loading and execution
Communications
Utilities

Types of OS

Batch processing
Multiprogramming
Time-sharing
Real-time
Distributed

OS paradigms:

Simple OS: MS-DOS
Layered OS: Unix and Linux

Advantages:

Reliability
Security
Speed
Cost
Open source

Structure: 2 layers

Kernel (key Unix core)
System programs

Microkernel System:

Microkernel approach: move as many as possible of system programs from the kernel into user space to become user programs.
Advantages:

Easier to extend
Easier to port OS to new architecture / hardware
More reliable
More secure

Modular OS: Solaris

Virtual machine (NOT COVERED)

Process

Definition: a program in execution.
Components in memory: (NOT COVERED)

Value of program counter
Value of registers and processor status word
Stack for temporary variables
Text for program code
Data section for global variables
Heap for dynamic storage of variables (those created using malloc)

Types: (NOT COVERED)

I/O-bound

time: I/O > computation
device contention: competition to access I/O devices

Lower is better

CPU-bound

time: computation > I/O
CPU utilization: % of time that CPU is used

Higher is better

transferrable, not binary

States: condition of a process

new
ready: waiting to be assigned to CPU for execution (in ready queue)
running
waiting: waiting for:

I/O event
child process execution
a certain interrupt

terminated

Process control block (PCB): a data structure

To keep track of the state of a process and the information that should be maintained when the process switches between CPUs
includes:

Process state
Program counter
CPU registers

registers
stack pointer
PSW

CPU scheduling info

process priority
pointer to scheduling queue

Memory-management info

limit of memory boundary

Accounting info

Process ID
CPU time used

I/O status info

list of opened files

Queues in OS:

Job queue
Ready queue
Device queues

Scheduler: to select the process to be served when it is waiting for different services

Long-term scheduler (job scheduler)

admission to ready queue? Y/N
makes decision to maintain a good mix of CPU-bound and I/O bound processes
It controls the degree of multi-programming (number of processes protentially competing for CPU) before process admission

Medium-term scheduler

to swap process in/out of ready queue
It controls the degree of multi-programming after process admission

Short-term scheduler (CPU scheduler)

allocation of CPU
CPU scheduling
Context switching

Sequence of events to bring CPU from an executing process to another

save state & load state

driven by "time-up" interrupt

"overhead": time-consuming and useless

Process creation (by another process)

Procedure:

create a new process
load the code into the process
run

Parent-child relationship:

Resource sharing:

Parent and children share all resources
Children share subset of parent's resources
Parent and children share no resources

Execution:

(asynchronously) concurrently
(synchronously) Parent waits until all children terminate

Address space

Each child duplicates that of parent.
Each child has an independent program loaded into it.

In Unix/Linux:

Resource sharing: none
Execution: concurrently
Address space:

fork(): Child duplicates that of parent.
exec() (after forking): Child has an independent program loaded into it.

Parent should wait() for a child to collect it.

Process hierarchy:

A child process could be the parent of another process, and a tree or hierarchy of processes could be formed.

Process termination

Zombie process: a process that has terminated, but whose parent has not yet called wait()
Orphan process: a process without a parent
Some OS allow a child process to continue after parent terminates, others don't.
Non-zero return value: an error

Process cooperation

Types of process:

Independent process: cannot affect or be affected by execution of other processes
cooperating process

Common app: web server & web browser

Reasons:

Infomation sharing
Computation speed-up
Modularity
Convenience: model a user in concurrent working mode

Interprocess communication (IPC)

Shared memory system:

by reading / writing to shared variables

may make data inconsistent

Message passing system:

(Preferred) by passing information without using shared variables
Operations:

establish a physical / logical communication link
send / receive message

Synchronization

ensures the orderly execution of cooperating processes that share a logical address space to guarantee data consistency
requests processes to wait for the signal to go ahead, to avoid the race condition

Thread

Interprocess Communication

allow processes to communicate and to synchronize
Application:

Data transfer and sharing
Event notification
Resource sharing
Process control
Synchronization

Mechanisms:

Message passing

Issues:

How are links established?
Direct / Indirect link?
A link for more than 2 processes?
How many links between every pair of processes?
capacity of link?
message size: fixed or variable?
uni-directional / bi-directional?

Mechanisms:

Direct communication:

Processes must name each other explicitly
Exactly one link for one pair of processes, usually bi-directional
Established automatically

Indirect communication:

Mailbox (port): for messages to be directed and received

Unique identifiers for each

Processes share a common mailbox → Link established
One link → many processes
one pair of processes → several links
unidirectional or bi-directional
Operations:

Create a new mailbox
send / receive messages
Destroy a mailbox

Synchronization between sender and receiver:

Key issue (?) : Message passing may be either blocking or non-blocking
Blocking (synchronous):

Blocking send:

Sender is blocked until the previous message is received

Blocking receive:

Receiver is blocked until sender sends a new message

Non-blocking (asynchronous):

Non-blocking send:

allows sender to send without blocking

Non-blocking receive:

allows receiver to receive:

a valid message;
null if message is not available

Buffering: a queue on the link to store outstanding messages

Key issue (?) : Sender may have sent several messages but receiver has not read them
Capacity implementation:

Zero capacity:

No buffer
Sender must wait for receiver

Bounded capacity

Limited buffer
Sender must wait if queue is full

Unbounded capacity

Unlimited buffer
No waiting

Shared memory

difficult when over the network or individual memory modules with CPU (meaning?)

Implementation:

IPC package: sets up a data structure* in kernel space

persistent: continue to exist until being removed

System calls for IPC:

Creation / Deletion
Writing / Reading

Shared memory mechanism:

Not practical: With protection, a process can only access its own memory space → cannot share between processes
In UNIX/Linux:

able to create shared memory segments within kernel memory space via special system calls
Pthread: share memory naturally within the same process

Message passing machanism

Pipe: a unidirectional, FIFO, unstructured data stream

Characteristics:

a buffer allocated within kernel
(?) Some plumbing is required to use a pipe
Fixed max size
No data type being transferred
Very simple flow control
Broadcast unsupported

Types:

Unnamed pipe

created via pipe()
Two file descriptors:

fd[0]: read-end of pipe
read()
fd[1]: write-end of pipe
write()
Each end could be closed by close()

Pipe between parent and child:

pipe(fd)
fork()
close(fd[1]) close(fd[0])
two pipes for bi-directional communication

Named pipe

Socket: conceptually looks like a named pipe.

CPU Scheduling

Ready queue: the set of processes in memory that are ready to execute
CPU scheduler (Short-term scheduler):

Aim: maximize CPU utilization in presence of multi-programming
Components:

Scheduler: selects one from the ready queue
Dispatcher: allocates the CPU to the selected one

Procedure:

Perform context switching
Switch to user mode
Resume the program

Dispatch latency: overhead

Decisions may take place when a process

running → waiting (for I/O)
running → terminated

non-preemptive scheduling

running → ready
waiting → ready

preemptive scheduling (forced taken of CPU)

Consideration:

CPU utilization
Throughput

Number of process completing execution per time unit.

Turnaround time
Waiting time
Response time

Algorithms:

First Come First Serve

equivalent to:

RR scheduling when q → ∞
Priority scheduling when priority is process arrival time

Shortest Job First

optimal for non-preemptive scheduling:

Shortest avg. waiting time
Shortest avg. turnaround time

equivalent to:

Priority scheduling when priority is CPU burst time

Shortest Remaining Time

preemptive version of SJF
optimal for preemptive scheduling

Priority

Windows convention:

Largest value → first

Linux convention:

Smallest value → first

Problem: starvation for low-priority process

Round Robin

Advantage:

avoid starvation
better response time

Disadvantage:

higher turnaround time
q small: excessive context switching

Multi-Level Queue

Aim: handle a job mix with different needs
Common queues:

System queue (Priority)
Interactive queue (RR)
Batch queue (FCFS/SRT)

Multi-Level Feedback Queue

allow process to move between queues if necessary
Parameters:

Number of queues
Scheduling algorithms for each queue
Method used to determine when to upgrade a process to a higher priority queue
Method used to determine when to downgrade a process to a lower priority queue
Method used to determine which queue a process should enter when that process needs CPU

Convoy effect:

several small processes have to wait for one big process

Real-time Scheduling (NOT COVERED)

Memory Management: manage & protect

3 stages of address binding:

Compile time

If memory location is known ahead
Logical address === Physical address

Load time

Address are defined after loaded
Logical address === Physical address

Run time (required to be supported)

If a process can be moved during execution
Hardware support for dynamic address mapping is required: base (or relocation) and limit (or length) registers
Logical address (or virtual address) !== Physical address

Memory Management Unit (MMU):

hardware device that maps virtual to physical address dynamically
base + offset (0 <= offset < limit)

Memory Allocation:

Partitions of main memory:

Low memory: resident OS, interrupt vector and interrupt handlers
High memory: user processes (concerned)

Methods:

Contiguous allocation:

allocate a single block of memory to hold a process

Non-contiguous allocation:

allocate multiple blocks of memory to hold a process
Major memory management schemes:

Paging
Segmentation

Contiguous allocation:

MFT: Multiprogramming with a Fixed number of Tasks

MAX(COUNT(running jobs)) === COUNT(partitions) --which is fixed

MVT: Multiprogramming with a Variable number of Tasks

"Hole": a block of available memory
Mechanism:

First-fit: allocate the first hole which is big enough
Best-fit: allocate the smallest hole which is big enough

Produce the smallest leftover hole

Worst-fit: allocate the largest hole

Produce the largest leftover hole
normally performs worst

Major problem: Fragmentation

External fragmentation: When

Total memory space is enough, but
Holes are not contiguous → not usable
Solution: compaction

To move holes together
Possible only if relocation is dynamic

Applicable for Segmentation

Internal fragmentation: When

Memory inside partitions are not used
Applicable for Paging

Non-contiguous allocation

PAGING:

Frame: fixed-sized blocks in physical memory

Frame table: to keep track of all free frames

Page: blocks of same size as frames in logical memory

Page table: to translate logical address (page number) to physical address (frame number)

One for each process
Page-table base register (PTBR): points to the page table for a process
Page-table length register (PTLR): indicates the size of a page table

Used to check for validity of a logical address

Solutions to avoid large page table:

Hierarchical paging
Hashed page table (NOT COVERED)
Inverted page table (NOT COVERED)

Cache between tranlation path: Tranlation Look-aside Buffer (TLB)

p = TLB hit ratio (0 <= p <= 1)
cache access time << memory access time
Performance measurement: Effective Access Time

= tranlation time + memory access time

= cache access time + (1 - p) * memory access time + memory access time

= cache access time + (2 - p) * memory access time

Valid-invalid bit with each page:

Valid: the page is in process' logical address space and is a legal page
Invalid: the page is not in logical address space.

trap generated

MAX(page number) >= MAX(frame number)
Logical address = (page number, offset)

Unit of page offset: Byte

n = log(frame size)

f = log(physical memory size / frame size)

1 byte = 8 bits

Shared pages: same frames in different page tables

SEGMENTATION: variable-length paging

supports user view of memory with segments
Logical address = (segment number, offset)
Segment table entry:

Base
Limit (length)
Valid bit
Access privilege bits

Memory allocation: FF, BF, WF
Segment-table base register (STBR): points to the segment table for a process
Segment-table length register (STLR): indicates the number of segments used by a process
Segmentation with Paging (NOT COVERED)

Virtual Memory

Solution when needed memory is more than physical memory:

Overlay: break a program into stages… (NOT COVERED)
Virtual Memory

Physical memory: only currently executing part
Logical address space to be stored on the disk: an extension of real physical memory
Allow sharing of memory
Possible implementations:

Paging
Segmentation

Memory map: translate virtual address to physical address
When to bring a page from disk into memory:

Demand paging: [in-time] do when the page is needed

Effective use of I/O resource
Process must wait when loading pages
Most implemented
Advantages:

Less I/O needed
Less physical memory needed
Relatively good response
Can support more users

Anticipatory paging: [ahead-of-time] do when the page will be needed in near future

I/O would be wasted when prediction is wrong
No need to wait for page loading

Reference: an access to the address within a page.

Invalid reference: when accessing outside the address space

Pager: swapper that swap pages
Valid-invalid bit of pages: page is in physical memory?

Valid: Yes
Invalid: generate a page fault

Page fault handler:

If reference is beyond logical address space: segmentation fault error
Else: ask pager to swap

Find the location of the needed page on disk
Get an empty frame from frame table

If frame table is empty: use a page replacement algorithm to select a victim frame
Write victim frame to disk if modified

Load the needed page on disk into the free frame
Update the page table and frame information for both the new and the victim page (if any).

Update the new page table entry to point to the loaded frame
Set the valid-invalid bit of the new page table entry to be valid
Set the valid-invalid bit of the victim page table entry to be invalid

Return from page fault handler and resume the user process generating the page fault

Initially all invalid

p = page fault rate (0 <= p <= 1)
Performance measurement: Effective Access Time

EAT = (1 - p) * memory access time + p * page fault service time

Page fault service time = page fault overhead + time to swap the page in + restart overhead

Page replacement: the action of finding a frame in memory to be removed in order to admit a newly needed page

Issues:

Which page to remove?

not been modified (because no need to save back to disk)

Could a process remove pages of another one?

Local page replacement: seek within its own set of frames
Global page replacement: seek within all frames of all processes

Save removed pages back to disk?

Only when modified

Indicator: Dirty bit

Goal: to generate smallest number of page faults
Common algorithms:

First In First Out

Victim: The earliest page admitted
Implementation: circular queue

Optimal: predict

Victim: the page which will not be used for the longest period of time in future
Used as a benchmark

Least Recently Used: mirror of Optimal

Victim: the page which has not been used for the longest period of time in the past
Perform well; most popular
Implementaion:

Counter: one for each page entry

When referenced: Copy the clock value into counter
Victim: the page with smallest value in counter
Problems:

Storage overhead
Search is needed

Stack

When referenced: move the page to the top of stack
Victim: the page at the bottom of stack
Problem: operation overhead

Approximation (NOT COVERED)

Performance measurement: number of page faults
Reference string: only page numbers of references

Allocation of (numbers of free) frames

Fixed allocation:

Equal allocation
Proportional allocation: in proportion of the size of the process
Only local page replacement

Variable allocation:

Allow the allocated number of frames vary over time
More page faults → more frames
Both local page replacement and global page replacement can be used

Deadlock

Livelock: can be resolved if lucky
Resource model of OS:

Resource: an object which is capable of being used
Steps to use a resource:

Request
Wait until granted
Use
Release

Resource type: R

Resource instance of a type: W

Types of deadlock:

Resource deadlock

A set of blocked processes, each holding a resource and waiting to acquire a resource held by another process in the set

Communication deadlock

A set of processes are waiting for a message to be sent from processes within the set, or an event to be triggered by the set

Characterization of deadlock (necessary conditions):

Mutual exclusion
Hold and wait
No preemption
Circular wait

Resource allocation graph:

Cycle is only a necessary condition of a deadlock
Algorithm:

Do not allocate the resource if a cyle is produced

Deadlock prevention: To "ensure" deadlock never happens.

Attack the condition of "Circular wait":

Order all resource types with a number
Each process can only request resources in an increasing order of resource number

Deadlock avoidance: use additional info

Additional info: Maximum number of resources of each type that it may need
Unsafe state: a possibility of deadlock

if NO safe sequence exists

Safe state (to be ensured): no deadlock

if safe sequence exists
Property of safe sequences:

The resources that each process can still request can be satisfied by currently available resources plus resources currently held by all preceding processes.

Banker's Algorithm

Assumption:

Declare the maximum use of resources before hand
When request, it may have to wait
When get all its resources, it must return them in a finite amount of time

Request_i: Need_i → Allocation_i

Available -= Request_i

Deadlock detection: after-hand

Wait-for graph checking when each resource has only one instance:

Wait-for graph: condensed form of a resource allocation graph
Deadlock: iff a cycle in wait-for graph

Banker's algorithm otherwise

Process Synchronization

Synchronization: the mechanism that ensures the orderly execution of cooperating processes.
Race condition: no synchronization
Producer/comsumer problem:

Solutions:

Shared variable
Critical section

Critical section problem

Critial section: shared resource of multiple concurrent processes
Properties of solutions:

Mutual exclusion:

at most one process could be in CS

Progress

at least one process could enter CS

Bounded waiting

no starvation

Solution: Peterson's algorithm (for only two processes)

3 bowls

Semaphore: solution of busy waiting

Types:

Binary semaphore
Counting semaphore

Operations (atomic):

P(S): wait

Implementation: (S as a queue)

S.value--;
if (S.value < 0) block(S.queue);

V(S): signal

Implementation:

S.value++;
if (S.value <= 0) wakeup(S.queue);

Remark:

block(): place the process on the waiting list
wakeup(): move an appropriate process from the waiting list to the ready queue