Operating System

This the note for Operating System, covered chapter 1 to 9

Outline

1. Introduction
2. System Structures
3. Process Concepts
4. Multithreaded Programming
5. Process Scheduling
6. Synchronization
7. Deadlocks
8. Memory-management Strategies
9. Virtural-memory Management

Introduction

Operating System goals/definitions

• A software that manages computer hardware
• An interface for users to communicate with hardware
• A platform for programs to run

1. Resourse Allocator
2. Control Program

Couputer System Structure

• Hardware
• Operating System
• Application Programs

Definitions

• kernel: the on program running at all times
• bootstrap program: loaded at power-up or reboot
• interrupt: devices inform CPU that it has finished its operation
• trap/exception: a software-generated interrupt caused by an error or a user request

I/O Structure

• Synchronous: control returns to user program only upon I/O completion
• Asynchronous: control returns to user program without waiting for I/O completion
  • System call: request to the OS to allow user to wait
  • Device-status table: contains entry for each I/O device

Storage Definition

• The basic unit is the bit
• 8 bits is a byte
• The native unit of data: word(8 bytes)
• caching: copying information into faster storage system(main memory as a chche for secondary storage)
• device driver: interface between controller and kernel

Storage-Device Hieracrchy

• register
• cache
• main memory
• solid-state disk
• magnetic disk
• optical disk
• magnetic tapes

Strorage Structure

• Main Memory: CPU can access directly
  • Random access
  • Volatile
• Secondary Storage: provide nonvolatile storage capacity
• Magnetic Disks:
  • Tracks, and sectors
  • Disk controller, determine the logical interaction between the device and the computer
• Solid-state Disks: faster than magnetic disks, nonvolatile

Multiprocessor

• Also known as parallel systems, tightly-coupled systems
• Advantages:
  • Increased Throughput
  • Economy of scale
  • Increased reliability
• Two types:
  • Asymmetric Multiprocessing
  • Symmetric Multiprocessing

Clustered Systems

• Storage-area netword(SAN): share strorage
• Asymmetric clustering: one machine in hot-standby mode
• Symmetric clustering: multiple nudes running, monitoring each other

Multiprogramming

• organize jobs so CPU always has one to execute
• Timesharing(multimasking): CPU swiches jobs so frequently that user can interact with each job

Dual-mode

• User mode and kernel mode
• Allow OS to protect iteself and other system components
• multimode, ex: virtual machine manager mode

Timer

• Set interrupt after specific period
• Set up before scheduling process to regain control or terminate program that exceeds allotted time

Process Management

• program counter: specify the location of next instructionto execute
• activities:
  • create/delete user/system processes
  • suspend/resume processes
  • provide mechanisms for process synchronization
  • provide mechanisms for process communication
  • provide mechanisms for deadlock handling

Memory managment

• keep track of which parts of memory are currently being used and by whom
• decide which processes and data to move into and out of memory
• allocate/deallocate memory space

Storage management

• create/delete files and directories
• primitive to manipulate files and directories
• mapping files onto secondary storage
• backup files onto stable storage media

Mass-storage management

• free-space management
• storage allocation
• disk scheduling

protection & security

• protection: any mechanism for controlling access of processes or users to resources
• security: defense of the system against external attacks

System Structures

OS services

• User interface
• Program execution
• I/O operations
• File-system manipulation
• Communications
• Error detection
• Memory management
  • Resouce allocation
  • Accounting: keep track of which users use how much and what kind of resources
  • Protection and Security

System calls

• programming interface to the services provided by the OS
• mostly via API
• system call interface: a table indexed according to the numbers associated with each system call
• pass parameters to the OS
  • simplest: pass in registers
  • block: parameters stored in a block, and address of block passed in a register
  • stack: parameters pushed onto the stack and popped off

Design and implement

• policy: what will be done
• mechanism: how to do it
• allow flexibility if policy decisions are to be changed later

Microkernel System Structure

• easier to extend
• easier to port the OS to new architectures
• more reliable
• more secure
• but performance overhead

Virtual Machines

• the OS host creates the illusion that a process has its own processor and virtual memory

System Boot

• when power initialized on system, execution starts at a fixed memory location
• bootstrap loader loads into memory and start it
• kernel loads then system is running

Process Concepts

• process: a program in execution
• parts
  • text section
  • program counter
  • stack: data
  • data section: global variables
  • heap: memory dynamically allocated
• types:
  • I/O-bound process
  • CPU-bound process

process state

• new
• running
• waiting
• ready
• terminated

process control block(PCB)

• process state
• preogram counter: location of instruction to next execute
• CPI registers
• CPU scheduling information
• memory management information
• accounting information
• I/O status information

process scheduling

• job queue
• ready queue
• device queues

schedulers

• long-term scheduler(job scheduler): which process should be brought to the ready queue
• short-term scheduler(CPU scheduler): which process should be executed next and allocates CPU

context switch

• CPU switch to another process, the system must save the state and load the saved state
• context of a process represented in the PCB

process operations

• creation
  • parent create children
  • identified via a process identifier(pid)
  • fork(): system call creates new process
  • exec(): system call to replace the process memory space with a new program
• termination

chrome browser

• multiprocess
  • browser
  • renderer
  • plug-in

interprocess communication(IPC)

• shared memory
• message passing
  • send()
  • reveive()
  • establish a communication link
• Synchronization
  • Blocking(synchronous)
    • blocking send
    • blocking receive
  • Non-blocking(asynchronous)
    • non-blocking send
    • non-blocking receive

communication in client-server

• socket: endpoint for communication
  • TCP: connection-oriented
  • UDP: connectionless
  • MulticastSocket
• remote procedure calls(RPC)
  • stub: client side proxy
• remote method invocation(RMI)
• pipes
  • write-end
  • read-end

Multithreaded Programming

Multithreaded Server Architecture

Client request server, server create new thread to service the request, the server resume listening

Benefits

• Responsiveness
• Resource sharing
• Economy: light weight process(LWP)
• Scalability

Multicore Programming

• parallelism: a system can perform more than one task simultaneously
  • data parallelism
  • task parallelism
• concurrency: support more than one task making progress

multithreading models

• Many-to-one
  • many user threads mapped to single kernel thread
• One-to-one
  • each user thread mapped to kernel thread
• Many-to-many
  • many user threads mapped to many kernel threads

thread library

provides programmer with API for creating and managing threads

• Pthreads: may be provided as user-level or kernel-level
• Java Threads: managed by JVM

Implicit threading

creation and mangagement of threads done by compilers and run-time libraries rather than programmers

• Thread pools: create a number of threads in a pool where they await work
• OpenMP: provide support for parallel programming in shared-memory environments
• Grand Central Dispatch: allow identification of parallel sections
  • serial
  • concurrent

Threading Issues

• sementics of fork() and exec()
• signal handling
  • default handler
  • user-defined handler
• thread cancellation
  • Asynchronous cancellation
  • Deferred cancellation: allow the target thread to periodically check if it should be cancelled
• thread local storage(TLS): allow each thread to have its own copy of data
• scheduler activations: LWP between user and kernel threads

Process Scheduling

• CPU burst
• I/O burst

CPU scheduler

• short-term scheduler: select from the processes in ready queue, and allocate the CPU to one of them
  • nonpreemptive:
    • switch from running to waiting
    • switch from running to ready
    • switch from waiting to ready
    • terminate
  • preemptive
  • dispatcher: give control of the CPU to the process selected

scheduling criteria

• CPU utilization
• Throughput: # of processes
• Turnaround time: amount of time to execute the process
• Waiting time: amount of time to wait in the ready queue
• Response time: amount of time from a request submitted until the first response

Scheduling Methods

First come, First-service(FCFS)

• convoy effect: short process behind long process

Shortest Job First(SJF)

It is optimal, the difficulty is knowing the length of the next CPU

Priority scheduling

• Starvation: low priority processes may never execute
• Aging: as time progress increase the priority

Round Robin(RR)

• time quantum: after this time, the process is preempted

Multilevel Queue

• foreground(interactive): RR
• background(batch): FCFS

Thread scheduling

• process contention scope(PCS): competition within the process
• system contention scope(SCS): competition among all processes

Multiple-processor scheduling

• Homogeneous processor within a multiprocessor
• Asymmetric multiprocessing: only one processor access the system data
• Symmetric multiprocesssing: each processor is self-scheduling
• processor affinity

Real-time CPU scheduling

• soft real-time system
• hard real-time system
• latencies:
  • interrupt latency
  • dispatch latency

priority-based scheduling

rate montonic scheduling

• a priority is affigned based on the inverse of its period

earliest deadline first scheduling(EDF)

• priority is assigned according to deadline

proportional share scheduling

• each application receives N/T

Little’s Formula

• n: average queue length
• W: average waiting time in queue
• $\lambda$ : average arrival rate into queue

Synchronization

background

Processes can be execute concurrently, and might lead to data inconsistency.

• race condition: the problem of synchronization
• critical section problem: process may be changing common variables

Solutions

Requirements

• Mutual Exclusion(MUTEX): If a process is executing in its cirtical section, then no other processes can be executing in its critical section
• Progress: No process in critial section and there are some wish to enter, the selection of the processess can’t be postponed indefinitely
• Bound Waiting: A bound for the number of times the other processes enter the critical section.

Peterson’s Solution

• atomic: can’t be interrupted
• 2 processes share:
  • turn: whose turn to enter the critical section
  • flag[2]: indicate if the process is ready

Bakery Algorithm

• Originally designed for distributed systems
• 2 arrays
  • number[i]: Pi’s token number
  • choosing[i]: Pi is taking a number

Synchronization Hardware

• protecting critical sections via locks
• use 2 methods to set lock:
  • test_and_set()
  • compare_and_swap()

Mutex Locks

• also called “spinlock”
• busy waiting
• acquire(): get the lock
• release(): release the lock

Semaphore

• no need of busy waiting
• 2 operations
  • wait()
  • signal()

problems

deadlock

2 or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

starvation

A process may never be removed from the semaphore queue

Monitors

• signal and wait
• signal and continue

Deadlocks

Definition

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

Charaterization

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

System Model

• Each process utilizes a resource:
  • request
  • use
  • release

Avoidance

• Each process declare the maximum number
• safe state
  • if pi resource needs aren’t available, it can wait until all pj finished
  • when pj is finished, pi can obtain needed resources
  • when pi terminates pi+1 can obtain its needed resources

Resource-allocation Graph

The request can be granted only if converting the request edge to an assignment edge doesn’t result in the formation of a cycle.

Banker’s Algorithm

• multiple instances
• data structure:
  • Available
  • Max
  • Allocation
  • Need: Max-Allocation
• safety algorithm
  1. Initialize
     • Work = Available
     • Finish[i] = false
  2. find an i that:
     • Finish[i] = false
     • Needi <= Work
     • if no, go to 4
  3. After these, go back to 2
     • Work += Allocation
     • Finish[i] = true
  4. If Finish[i] == true for all i, it’s safe
• algorithm
  • Available -= Request
  • Allocation += Request
  • Need -= Request
  • If safe, do allocation; if unsage, wait.

Detection Algorithm

It’s O(mn^2)

1. Work: m, Finish: n
   • Work = Available
   • Finish[i] = false if Allocation[i] != 0, else, true
2. Find an i that:
   • Finish[i] = false
   • Request[i] < Work
   • if no, go to 4
3. After these, go back to 2
   • Work += Allocation
   • Finish[i] = true
4. If Finish[i] == false for some i, it’s in deadlock

Recovery

Process Termination

• abort all deadlocked processes
• abort one by one untile the cycle is eliminated

Resource Preemption

• Select a victim
• Rollback
• Starvation

Memory-management Strategies

Background

• Main memory can take many cycles, causing a stall(too slow to access memory)

Base and Limit registers

• a pair of base and limit define the logical address space

Binding

• compile time
• load time
• execution time

address space

• logical: generated by CPU, virtual address
• physical: address seen by the memory unit

Memory Management Unit(MMU)

• map virtual to physical address

Swapping

• a process can be swqpped temporarily out of memory to a backing store, and then brought back
  • backing store: fast disk to accomodate copies
  • roll out, roll in: lower priority out, higher priority be loaded

Contiguous Allocation

• fixed partitions
• pros:
  • bound registers
  • each partition may have a protection key
• cons:
  • fragmentation gives poor memory utilization

Dynamic Storage-Allocation Problem

• First-fit: allocate the first hole
• Best-fit: allocate the smallest hole
• Worst-fit: allocate the largest hole

Fragmentation

• External Fragmentation: total memory space exists, but not contiguous
• Internal Fragmentation: allocated memory space be larger than requested memory
• Reduce External Fragmentation
  • compaction: put free spce together
• Dynamic Partition
  • pros:
    • eliminate fragmentation to some degree
    • have more partitions and a higher degree of multiprogramming
  • cons:
    • relocation cost

Segmentation

• Memory-management scheme that supports user view of memory
• Segment table
  • base: contains the physical address (segment-table base register)
  • limit: specify the length of the segment (segment-table length register)

paging

• frames: divide physical memory into fixed-sized blocks
• pages: divide logical memory into blocks of same size
• page number: in a page table which contains base address of each page
• page offset: base address
• Increase context-switch time

Associative memory/Translation look-aside buffers(TLBs)

• Fast-lookup hardware cache.
• Store address-space identtifiers

Memory protection

• valid-incalid bit
• Page Table Length Register

Shared Pages

• shared code: one copy of read-only code shared among processes
• private code and data: each process keeps a separate copy

Multilevel paging

• The logical address space of a process is very large
• Hierarchical Page table: break up intot multiple page tables

Hashed page tables

Inverted page table

• pros:
  • decrease the amount of memory needed to store each page table
• cons:
  • sorted by virtual address
  • difficult to implement with shared memory

Virtual-memory Management

Virtual memory

• Entire program code not needed at the same time, the ability to execute partially-loaded program
• virtual memory: separation of user logical memory from physical memory
• can be implemented:
  • Demand paging
  • Demand segmentation

Demand Paging

• could bring entire process into memory
• lazy swapper: never swaps a page into memory unless page will be needed
• valid-invalid bit:
  • v: in memory
  • i: not in memory (page fault)

page fault

1. OS look at another table
2. Get empty frame
3. Seap page into frame
4. Reset table
5. Set validation bit v
6. Restart the instruction

Process Creation

copy-on-write

• allow both parent and child processes to initially share the same pages in memory

page replacement

• prevent over-allocation of memory
• use modify bit to reduce overhead of page transfers

1. Find the location of the desired page
2. Find a free frame
   1. If no free frame, select a victim frame
3. Bring the page into the free frame, update
4. Continue the process

comparison

• frame-allocation algorithm
  • how many frames to give each process
  • which frame to replace
• page-replacement algorithm
  • lowest page-fault rate

algorithms

• FIFO
• Optimal algorithm
  • replace page that will not be used for longest period of time
• Least recently used(LRU)
• Most frequently used(MFU)

global vs local

• global replacement: process selects a replacement frame from all frames
• local replacement: process selects from its own set of allocated frames

Thrashing

• high page-fault rate
• a process is busy swapping
• low CPU utilization

Memory-mapped files

• mapping a disk block to a page in memory

Buddy System

• allocate memory from fixed-size segment consisting of physically-contiguous pages
• using power of 2 allocator
• pros: quickly coalesce unused chunks into larger chunk
• cons: fragmentation

Slab allocator

• slab: one or more physically contiguous pages
• cache: consist of one or more slab