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

© Henry Johnson 2021 - 2024

Licensed under CC BY-SA 4.0.

Any and all opinions listed here are my own and not representative of my employers.