I/O System Management

1. I/O System Management

  • The operating system will hide the peculiarities of specific hardware from the user
  • In Unix, the I/O subsystem consist of 
    • a buffering, caching and spooling system
    • a general device-driver interface
    • drivers for specific hardware devices
  • Interrupt handlers and device drivers are crucial in the design and efficient I/O subsystems

File Management

1. File Management

  • A file is a collection of related information designed by its creator
  • Commonly, files represent programs (both source and object forms) and data
  • The operating system responsibilities
    • file creation and deletion
    • directory creation and deletion
    • support of primitives for manipulating files and directories
    • mapping files onto secondary storage
    • file backup on stable (non-volatile) storage and data

Memory Management

1. Memory Management

  • all data in memory before and after processing
  • all instructions in memory in order to execute
  • memory management determines what is memory when 
    • optimizing CPU utilization and compute response to users
  • memory management activities
    • keep track of which parts of memory are currently being used and by whom
    • deciding which processes (or parts thereof) and data to move into and out of memory
    • allocating and deallocating memory space as needed
  • virtual memory management is an essential part of most operating system

    Storage Management

    1. Storage Management
    • OS provides uniform, logical view of information storage
      • abstracts physical properties to logical storage unit (file)
      • each medium is controlled by device (i.e., disk drive, tape drive)
        • varying properties include access speed, capacity, data-transfer rate, access method (sequential or random)
    • File system management
      • files usually organized into directories
      • access control on most file systems to determine who can access what
      • OS activities include
        • creating and deleting files and directories
        • primitives to manipulate files and dirs
        • mapping files onto secondary storage
        • backup files onto stable (non-volatile) storage media
    2. Storage-Device Hierarchy
    3. Caching
    • Important principle, performed at many levels in a computer (in hardware, operating system, software)
    • Information in use copied from slower to faster storage temporarily
    • Faster storage (cache) checked first to determine if information is there
      • if it is, information used directly from the cache (first)
      • if not, data copied to cache and used there
    • Cache smaller than storage being cached
      • cache management important design problem
      • cache size and replacement policy


    1. Definition
    • Process: a program in execution
      • process execution must progress in sequential fashion
    • A program is a passive entity, whereas a process is an active entity with a program counter and a set of associated resources.
    • Each process has its own address space
      • Text section (text segment) contains the executable code
        • the program counter and CPU registers are part of the process context.
      • Data section (date segment) contains the global variables
      • Stack contains temporary data (local variables, return addresses…)
      • A process may contain a heap, which contains memory that is dynamically allocated at run-time

    2. OS requirements for processes

    • OS must interleave the execution of several processes to maximize CPU usage while providing reasonable response time
    • OS must allocate resources to processes while avoiding deadlock
    • OS must support inter process communication and user creation of process.

      3. A simple implementation of processes
      • The process index register contains the index into the process list of the currently executing process (B)
      • A process switch from B to A consist of storing (in memory) B’s context and loading (in CPU registers) A’s context
      • A data structure that provides flexibility (to add new features)
      4. Process Creation
      • Principal events that cause process creation
        • system initialization
        • execution of a process creation system call by a running process
        • user request to create new process
      • Parent process creates child processes, which, in turn create other processes, forming a tree (hierarchy) of processes.
      • Issues
        • will the parent and child execute concurrently
        • how will the address space of the child be related to the parent?
        • will the parent and child share some resources?
      5. An example Process

      6. Process Creation in Unix
      • Each process has a process identifier (pid)
      • The parent executes fork() system call to spawn a child
      • The child process has a separate copy of the parent’s address space
      • Both the parent and the child continue execution at the instruction following the fork() system call
      • Typically, the child executes a system call like execlp() to load a binary file into memory

      7. Example program with “fork”

      8. Process Termination

      • process executes lat statement and asks the operating system to delete it (exit)
        • output data from child to parent (via wait or waitpid)
        • process’ resources are deallocated by operating system
      • parent may terminate execution of children processes
        • e.g., TerminationProcess() in  Win32()
      • process may also terminate due to errors
      • cascading termination: when a system does not allow a child process to continue after the parent has terminated
      9. Process States
      • Running states
      • Ready states
      • Blocked states
      • New state
        • os has performed the necessary actions to create process but has not yet admitted the process
      • Exit state
        • termination moves the process to this state
        • tables and other info are temporarily preserved for auxiliary program
      10. Swapping/Suspending
      • Processes may need to be swapped out to disk
        • this is true even with virtual memory
      • 2 new states
        • blocked suspend: blocked processes which have been swapped out to disk
        • ready suspend: ready processes which have been swapped out to disk

      11. Process Scheduling
      • The operating system is responsible for managing the scheduling activities
        • a uniprocessor system can have only one running process at a time
        • the main memory cannot always accommodate all processes at run-time
        • The operating system will need to decide on which process to execute next (CPU scheduling), and which processes will be brought to the main memory (job scheduling)
      12. Process Scheduling Queues
      • Job queue: set of all processes in the system
      • Ready queue: set of processes residing in the main memory, ready and waiting for CPU
      • Device queue: set of processes waiting for an I/O device
      • Process migration is possible among these queues
      13. Schedulers
      • The processes may be first spooled to a mass-storage system, where they are kept for later execution
      • The long-term scheduler (or job scheduler)
        • selects processes from this pool and loads them into memory for execution
        • the long term scheduler, if it exists, will control the degree of multiplexing
      • The short-term scheduler (or CPU scheduler)
        • selects from among ready processes, and allocates the CPU to one of them
        • unlike the long-term scheduler, the short-term scheduler is invoked very frequently
      14. CPU and I/O burts
      • CPU-I/O burst cycle
        • process execution consist of a cycle of CPU execution and I/O wait
      • I/O bound process
        • sends more time doing I/O than computations, many short CPU bursts
      • CPU-bound process
        • sends more time doing computation, few very long CPU bursts

      Instruction Execution

      1. Instruction Execution
      • While executing a program, the CPU
        • fetches the next instruction from memory (loading into IR)
        • decodes it to determine its type and operands
        • executes it
      • May take multiple clock cycles to execute an instruction
      • Example:
        • LOAD R1, #3
        • LOAD R2, M2
        • STORE M3, R4
        • ADD R1, R2, R3
      • Each CPU has a specific set of instructions that it can execute (instruction-set architecture)
      2. Registers
      • General registers (data/address)
      • Program Counter (PC): contains the memory address of the next instruction to be fetched
      • Stack Pointer (PC): points to the top of current stack in memory. T
        • the stack contains one frame for each procedure that has been entered but not yet exited
      • Program Status Word (PSW): contains the condition code bits and various other control bits.
      • Note: when time multiplexing the CPU, the operating system will often stop the running program to (re)start another one. In these cases, it must save the “state information” (e.g., value of the registers)
      3. Computer-System Operation

      • I/O devices and CPU can execute concurrency
      • Each device controller has local buffer(s).
      • CPU moves data from/to main memory to/from  local buffers.
      • I/O is from/to device to/from local buffer of controller
      • The device driver is special operating software that interacts with the device controller
      • Typically, the device controller informs CPU that it has finished its operation by causing an interrupt.
      4. Instruction Cycle with Interrupts
      5. Classes of Interrupts
      • I/O interrupts: generated by an I/O controller, to signal normal completion of an operation or to signal a variety of error conditions
      • Timer Interrupts: generated by a timer within the processor. This allows the operating system to perform certain functions on a regular basis.
      • Hardware Failure Interrupts: generated by a failure (e.g., power failure or memory parity error).
      • Traps (Software Interrupts): generated by some condition that occurs as a result of an instruction execution
        • error
        • user request for an operating system service
      6. Interruption Mechanism
      • Interrupt transfers control to the interrupt service routine generally through the interrupt vector (e.g., Interl) which contains the addresses of all the service routines. (Alternatively, the machine has a status register or cause register that holds the reason for the interrupt – MIPS architecture)
      • Interrupt Service Routines (ISRs): separate segments of code determine what action should be taken for each type of interrupt
      • Once the interrupt has been serviced by the ISR, the control is returned to the interrupted program. Need to save the “process state” (register, PC, …) before ISR takes over.
      7. Basic Interrupt Processing
      • the interrupt is issued
      • processor finishes execution of current instruction
      • processor signals acknowledgement of interrupt
      • processor pushes PSW and PC onto control stack
      • processor loads new PC value through the interrupt vector
      • ISR saves remainder of the process state information
      • ISR executes
      • ISR restores process state information
      • Old PSW and PC values are restored from the control stack
      8. I/O Structure

      • After I/O starts, control returns to user program only upon I/O completion
        • wait instruction idles the CPU until the next interrupt
        • wait loop (contention for memory access)
        • at most one I/O request is outstanding at a time, no simultaneous  I/O processing
      • After I/O starts, control returns to user program without waiting for I/O completion
        • system call: request to the operating system to allow user to wait for I/O completion
        • device-status table contains entry for each I/O device indicating its type address, and state
        • operating system indexes into I/O devices table to determine device status and to modify table entry to include interrupt
      9. Dual-Mode Operation
      • Operating system must protect itself and all other programs (and their data) from any malfunctioning program
      • Provide hardware support to differentiate between at least two modes of operations
        • user mode: execution done on behalf of a user
        • kernel mode: (also monitor mode or system mode): execution done on behalf of operating system.
      • Mode bit added to computer hardware to indicate the current mode
        • kernel: 0
        • user: 1
      • When an interrupt occurs hardware switches to kernel mode
      • Privileged instructions can be issued only in kernel mode
      10. Transition form user to kernel mode

      Introduction to Operating Systems

      1. What is an Operating System

      • A program that acts as an intermediary between the user of a computer and the computer hardware
      • Operating system goals
        • Convenience: make the computer system convenient to use
        • Efficiency: Manage the computer system resources in an efficient manner
      • “The one program running at all times on the computer” is the kernel. Everything else is either a system program or an application program.
      2. OS Features needed for multiprogramming
      • Job Scheduling: must choose the processes that will be brought to memory
      • Memory Management: must allocate the memory to several jobs
      • CPU Scheduling: must choose among several jobs ready to run
      3. Parallel System
      • Multiprocessor systems with more than one CPU in close communication
      • Tightly coupled system
        • processors share memory and a clock;
        • communication usually takes place through the shared memory
      • Advantage of parallel system
        • increased throughput
        • economy of scale
        • increased reliability
      4. Distributed Systems
      • Distributed the computation among several physical processors
      • Loosely coupled system
        • each processor has its own local memory
        • processors communicate with one another through various communication lines
      • Advantage of distributed systems
        • resource and load sharing
        • reliability
        • communications

      Average Age of Renewal Process

      1. Definition

      • Let S_n be the n-th renewal
      • Then S_{N(t)} = time of the last renewal (prior to time t)
      • Let A(t) = t - S_{N(t)}
        • A(t) is called the age of the renewal process
        • Interpretation: A(t) is the time since last renewal 

      2. Average Age of Renewal Process

      • What is R_n? R_n = int^{S_n}_{S_{n-1}} A(t) dt
      • R_n is the area under the curve for one cycle
      • so E(R_n)) = E[(X_n)^2/2] = E[X^2_n]/2
      • Thus the long-run average of the process is 
        • frac{E[R_n]}{E[X_n]} = frac{E[X^2_n]}{2E[X_n]}

      Renewal-Reward Process

      1. Definition

      • let N(t) be a renewal process
      • Let R_n = reward earned at n-th renewal
      • Assume R_n are i.i.d, but can depend on X_n (length of the n-th cycle)
      Then R(t) = sum^{N(t)}_{n=1} R_n is a renewal reward process.
      Intuitive explanation: R(t) = cumulative reward earned up to time t

      2. Renewal Reward Theorem 

      Proposition 7.3 
      • lim_{t to infty} frac{R(t)}{t} = frac{E[R_n]}{E[X_n]}
      • lim_{t to infty} frac{E[R(t)]}{t} = frac{E[R_n]}{E[X_n]}
      Provided E[R_n] < infty, E[X_n] < infty

      3. Example: Inventory Problem



      Reversible Markov Chain

      1. Definition

      Let X_1, X_2, cdots be a Markov chain with transition probabilities P_{ij}.

      P_{ij} = Pr{X_{n+1} = j| X_n = i}

      E.g. A sample realization is 1, 2, 3, 4, 5

      Let X_n, x_{n-1}, cdots be the same sequence in reverse, i.e. cdots, 5, 4, 3, 2, 1, cdots

      Let Q_{ij} be the transition probabilities of the reversed process. That is
      Q_{ij} = Pr{X_{n-1} = j |X_n = i}
                    = frac{Pr{X_{n-1} =j, X_n = i}}{Pr{X_n = i}}
                    = frac{Pr{X_{n-1} = j} Pr{X_n =i | X_{n-1} = j}}{Pr{X_n = i}}
                    = frac{Pr{X_{n-1} = j} P_{ji}}{Pr{X_n = i}}

      2. Conclusion

      In the steady state, assuming the limiting probabilities exist, we have
      Q_{ij} = frac{pi_j P_{ji}}{pi_i}  or pi_i Q_{ij} = pi_j Q_{ji}

      The above equation is saying that the rate of transmissions from i to j in the reversed chain is equal to the rate of transitions from j to i in the forward chain.

      A DTMC is time reversible if Q_{ij} = P_{ij}