CrabAss/!OS_Revision_Notes.md

## !OS_Revision_Notes.md

      
    Raw
  

              !OS_Revision_Notes.md
            
          
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: bwb
ready: waiting to be assigned to CPU for execution (in ready queue)
running: bvb
waiting: waiting for:

I/O event
child process execution
a certain interrupt


terminated: bxb


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


## LICENSE.md

      
    Raw
  

              LICENSE.md
            
          
    COMP2432 Revision Notes (PolyU, 2018) by CrabAss is licensed under CC BY-NC-SA 4.0. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/4.0