59.305 - Operating Systems


INTRODUCTION 

What is an Operating system 

Operating system goals: 

Computer System Components 

  1. Hardware - provides basic computing resources (CPU, memory, I/O devices). 
  2. Operating system - controls and coordinates the use of the hardware among the various application programs for the various users. 
  3. Applications programs - define the ways in which the system resources are used to solve the computing problems of the users (compilers, database systems, video games, business pro grams). 
  4. Users (people, machines, other computers). 


  5. Graphic1 

Operating System Functions 

Early Systems - bare machine (early 1950s) - First Generation.

Simple Batch Systems - Second Generation.

Problems: 

  1. How does the monitor know about the nature of the job (e.g., Fortran versus Assembly) or which program to execute? 
  2. How does the monitor distinguish 
    a) job from job? 
    b) data from program? 

Solution: introduce control cards 

Control Cards 

Spooling - overlap the I/O of one job with the computation of another job. 

Graphic3
(Simultaneous Peripheral Operation On Line) Simple Multiprogramming.

Multiprogramming and Time Sharing- Third Generation 

Multiprogramming

OS Features Needed for Multiprogramming 

Time-Sharing Systems- Interactive Computing 

Personal-Computer Systems - Fourth Generation

Parallel Systems - multiprocessor systems with more than one CPU in close communication. 

Distributed Systems - distribute the computation among several physical processors. 

Real-Time Systems 

59.305 Course Notes

COMPUTER-SYSTEM STRUCTURES

Computer-System Operation

Interrupts

Types

  1. Hardware - Asynchronous
    Device informs CPU that something has happened e.g. a key has been pressed on the keyboard.
  2. Hardware - Synchronous
    CPU has tried to do something that has caused the interrupt. e.g. tried to read from an invalid memory location. (not always a problem, it may mean that that page is on disk needs to be fetched). Often called an Exception or Trap.
  3. Software
    CPU asked for the interrupt to happen. e.g. to perform an OS Call. Often called a Trap.

Hardware Interrupts

Interrupt Handling

I/O Calls

Blocking I/O

Non-Blocking I/O

Direct Memory Access (DMA) Structure

Storage Structure

Storage Hierarchy

Hardware Protection

Dual-Mode Operation

I/O Protection

Memory Protection

CPU Protection - how does the OS stay in control.

General-System Architecture

59.305 Course Notes

OPERATING-SYSTEM STRUCTURES

Most operating systems support the following types of system components:

Process Management

Main-Memory Management

I/O System Management

File Management

Protection System

Networking (Distributed Systems)

Command-Interpreter System

Operating-System Services

Additional operating-system functions exist not for helping the user, but rather for ensuring efficient system operation.

System Calls

System Programs

System Structure - Simple Approach

System Structure - Layered Approach

Virtual Machines

Advantages and Disadvantages of Virtual Machines

System Design Goals

Mechanisms and Policies

System Implementation

Booting

59.305 Course Notes

PROCESSES

Process Concepts

Process Scheduling

Context Switch

Process Creation

Example Process Tree

Process Termination

Cooperating Processes

Producer-Consumer Problem

Shared-memory solution:

Threads

Types of threads

Interprocess Communication (IPC)

Provides a mechanism to allow processes to communicate and to synchronize their actions.

Implementation questions:

Direct Communication

Indirect Communication

Buffering - queue of messages attached to the link; implemented in one of three ways.

Exception Conditions - error recovery

Pipes

A pipe is a simple method for communicating between two processes.

59.305 Course Notes

CPU SCHEDULING

Basic Concepts

    1. switches from running to waiting state.
    2. switches from running to ready state.
    3. switches from waiting to ready.
    4. terminates.

Dispatcher

Scheduling Criteria

First-Come, First-Served (FCFS) Scheduling

Shortest-Job-First (SJF) Scheduling

Example of SJF

How do we know the length of the next CPU burst?

    1. Tn = actual length of n'th CPU burst
    2. Pn = predicted value of n'th CPU burst
    3. 0 <= W <= 1
    4. Define:
      Pn+1 = W * Tn + (1-W) Pn

Examples:

Priority Scheduling

Round Robin (RR)

Example of RR with time quantum = 20

Multilevel Queue

Multilevel Feedback Queue

Example of multilevel feedback queue

Multiple-Processor Scheduling

Real-Time Scheduling

Algorithm Evaluation

Summary

59.305 Course Notes

PROCESS SYNCHRONIZATION

Background

The new scheme is illustrated by the following:

The Critical-Section Problem

A solution to the critical-section problem must satisfy the following three requirements:

  1. Mutual Exclusion. If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
  2. Progress. If no process is executing in its critical section and there are some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely.
  3. Bounded Waiting. A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

Initial attempts to solve the problem.

Algorithm 1

Algorithm 2

Algorithm 3

Bakery Algorithm - Critical section for n processes

Bakery Algorithm

Synchronization Hardware

Semaphore - synchronization tool that does not require busy waiting.

Semaphore S

Example: critical section for n processes

Implementation of the wait and signal operations so that they must execute atomically.

Implementation of wait(S) operation with the TestandSet instruction:

Race condition exists!

Semaphore can be used as general synchronization tool:

Two types of semaphores:

Classical Problems of Synchronization

Bounded-Buffer Problem

Readers-Writers Problem

A number of processes, some reading data, some writing. Any number of processes can read at the same time, but if a writer is writing then no other process must be able to access the data.

Dining-Philosophers Problem

A Problem posed by Dijkstra in 1965

Possible solution to the problem:

"take_fork" waits until the specified fork is available and then grabs it.

Unfortunately this solution will not work... what happens if all the philosophers grab their left fork at the same time.

Better solution.

High-level synchronization constructs

Monitors

High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes. (Hoare and Brinch Hansen 1974)
A collection of procedures, variables and data structures. Only one process can be active in a monitor at any instant.

The producer consumer problem can be solved as follows using monitors:

The dining philosophers problem can also be solved easily.

There are very few languages that support constructs such as monitors... expect this to change. One language that does is Java. Here is a Java class that can be used to solve the producer consumer problem.

Monitor implementation using semaphores.

What happens when a monitor signals a condition variable?
A process waiting on the variable can't be active at the same time as the signaling process, therefore: 2 choices.

  1. Signaling process waits until the waiting process either leaves the monitor or waits for another condition.
  2. Waiting process waits until the signaling process either leaves the monitor or waits for another condition.

Atomic Transactions

Log-Based Recovery

Checkpoints - reduce recovery overhead

  1. Output all log records currently residing in volatile storage onto stable storage.
  2. Output all modified data residing in volatile storage to stable storage.
  3. Output log record <checkpoint> onto stable storage.

Concurrent Atomic Transactions

59.305 Course Notes

DEADLOCKS

The Deadlock Problem

System Model

Deadlock Characterization - deadlock can arise if four conditions hold simultaneously.

Resource-Allocation Graph - a diagram showing allocations

A set of vertices V and a set of edges E.

Example

Methods for Handling Deadlocks

Deadlock Prevention - restrain the ways resource requests can be made.

Deadlock Avoidance - requires that the system has some additional a priori information available.

Safe State - when a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.

e.g.  12 instances of a resource. systems is safe because <p1, p0, p2> satisfies safety condition.
The following diagram shows how deadlock can occur.
At point t, any move upwards would enter an unsafe state.
 

Resource-Allocation Graph Algorithm

Example

Banker's Algorithm (Dijkstra 1965)

Example: consider the following:

A banker 10 thousand dollars and four customers Florence,  Dougal, Dylan and Zebedee. each customer has a maximum need and and starts owing nothing.
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 10
Safe
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 2
Safe, because any requests for loans, except to Dylan, can wait until Dylan repays his loan.
Name  Used  Max 
Florence 
Dougal 
Dylan 
Zebedee 
Available = 1
Unsafe, since if all customers ask for their maximum, none will get it, causing deadlock.

Safety Algorithm

  1. Let Work and Finish be vectors of length m and n, respectively.


  2. Initialize:
    Work := Available 
    Finish[i] := false for i = 1, 2, ..., n. 
  3. Find an i such that both:
    1. Finish[i] = false
    2. Need i <= Work  (every element in Needi < every element in Work)
    If no such i exists, go to step 4.
  4. Work := Work + Allocation i


  5. Finish[i] := true
    go to step 2.
  6. If Finish[i] = true for all i, then the system is in a safe state.
May require an order of m x n 2 operations to decide whether a state is safe.

Resource-Request Algorithm for process Pi 

Request i = request vector for process Pi .

If Request i [ j ] = k , then process Pi wants k instances of resource type R j .
  1. If Request i <= Need i , go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
  2. If Request i <= Available, go to step 3. Otherwise, Pi must wait, since resources are not available.
  3. Pretend to allocate requested resources to Pi by modifying the state as follows:

Example of Banker's algorithm

Deadlock Detection

Single Instance of Each Resource Type

Several Instances of a Resource Type

Detection Algorithm

  1. Let Work and Finish be vectors of length m and n, respectively. Initialize:

  2. Work := Available.
    For i = 1, 2, ..., n, if Allocationi <> 0, then Finish[i] := false; otherwise, Finish[i] := true.
  3. Find an index i such that both:
    1.  Finish[i] = false.
    2.  Request i <= Work.
    If no such i exists, go to step 4.
  4. Work := Work + Allocation i
    Finish[i] := true

  5. go to step 2.
  6. If Finish[i] = false, for some i, 1 <= i <= n, then the system is in a deadlock state. Moreover, if Finish[i] = false, then Pi is deadlocked.
  • Algorithm requires an order of m x n2 operations to detect whether the system is in a deadlocked state.
  • Example of Detection algorithm

    Detection-Algorithm Usage

    Recovery from Deadlock

    Combined Approach to Deadlock Handling

    59.305 Course Notes

    MEMORY MANAGEMENT

    Background

    Address binding of instructions and data to memory addresses can happen at three stages:

    Logical versus Physical Address Space

    Memory-management unit (MMU) - hardware device that maps virtual to physical address.

    Swapping

    Contiguous Allocation

    Paging - logical address space of a process can be noncontiguous; process is allocated physical memory wherever the latter is available.

    Implementation of page table

    Multilevel Paging - partitioning the page table allows the operating system to leave partitions unused until a process needs them.

    Inverted Page Table

    One entry for each real page of memory; entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.

    Shared pages

    Segmentation - memory-management scheme that supports user view of memory.

    Sharing

    Protection

    With each entry in segment table associate:

    Allocation

    Segmentation with Paging

    Considerations in comparing memory-management strategies:

    59.305 Course Notes

    VIRTUAL MEMORY

    Background

    Demand Paging

    Valid-Invalid bit

    Page Fault

    1. If there is ever a reference to a page, first reference will trap to OS -> page fault.
    2. OS looks at another table to decide:


    3. a) Invalid reference => abort.
      b) Just not in memory.
    4. Get empty frame.
    5. Swap page into frame.
    6. Reset tables, validation bit = 1.
    7. Restart instruction:

    What happens if there is no free frame?

    Performance of Demand Paging

    Page Replacement

    Page-Replacement Algorithms

    First-In-First-Out (FIFO) Algorithm

    Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

    FIFO Replacement - Belady's Anomaly

    Optimal Algorithm

    Least Recently Used (LRU) Algorithm

    LRU Approximation Algorithms

    Allocation of Frames

    Global versus local allocation

    Thrashing

    Working-Set Model

    How do you keep track of the working set?

    Page-Fault Frequency Scheme

    Other Consideration

    1. Prepaging
    2. Page size selection


    3. - fragmentation
      - table size
      - I/O overhead
      - locality
    4. Program structure


    5. - Array A[1024,1024] of integer
      - Each row is stored in one page
      - One frame -
      - Program 1
       for j := 1 to 1024 do 
          for i := 1 to 1024 do 
            A[i,j] := 0; 
        1024 * 1024 page faults
      - Program 2
       for i := 1 to 1024 do 
          for j := 1 to 1024 do 
            A[i,j] := 0; 
      1024 page faults
    6. I/O interlock and addressing

    Demand Segmentation - used when insufficient hardware to implement demand paging.

    59.305 Course Notes

    FILE-SYSTEM INTERFACE

    File Concept

    File Structure

    Can simulate last two with first method by inserting appropriate control characters.

    File Operations

    Access Methods

    Directory Structure - a collection of nodes containing information about all files.

    Organize the directory (logically) to obtain:

    Single-Level Directory - a single directory for all users.

    Two-Level Directory - separate directory for each user.

    Tree-Structured Directories

    Acyclic-Graph Directories - have shared subdirectories and files.

    General Graph Directory

    Protection

    Access Lists and Groups

    59.305 Course Notes

    FILE-SYSTEM IMPLEMENTATION

    File-System Structure

    Contiguous Allocation - each file occupies a set of contiguous blocks on the disk.

    Linked Allocation - each file is a linked list of disk blocks; blocks may be scattered anywhere on the disk.

    Indexed Allocation - brings all pointers together into the index block.

    Free-Space Management

    1. Bit vector (n blocks)
    2. Need to protect:

    Directory Implementation

    Efficiency and Performance

    Recovery

    59.305 Course Notes

    SECONDARY-STORAGE STRUCTURE

    Disk Structure

    Disk Scheduling

    Disk Management

    Swap-Space Management

    Disk Reliability

    Stable-Storage Implementation

    59.305 Course Notes

    PROTECTION

    Goals of Protection

    Domain Structure

    Domain Implementation

    Access Matrix

    Use of Access Matrix

    Implementation of Access Matrix

    Revocation of Access Rights

    Language-Based Protection

    59.305 Course Notes

    SECURITY

    The Security Problem

    Authentication

    Program Threats

    System Threats

    Threat Monitoring

    Encryption