Section 1
Preview this deck
Response Time
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
1
All-time users
1
Favorites
0
Last updated
1 year ago
Date created
Mar 1, 2020
Cards (137)
Section 1
(50 cards)
Response Time
time between issuing a command and getting a result
Zombie processes
-process has terminated -parent process has not collected status -dead, but not gone
Waiting time
amount of time a process has been waiting in the ready queue
Evaluating Scheduling Policies
-CPU utilization -throughput -turnaround time-how long process takes to run, from init to term, inc wait time -response time -waiting time
Operating System
Software that manages a computer's resources -Easier to write desired applications -Runs applications efficiently
Evaluating an OS
1) Reliability -does exactly what it is designed to do 2) Security - OS cannot be compromised by hackers - strong fault isolation helps but isn't enough 3) Portability -OS doesn't change when hardware does -3 interfaces -can last a long time
Interactive Timesharing (1970-)
-cheap terminals to let multiple users use the system at the same time -requires more sharing, protection and concurrency -New services: shell, file system, rapid process switching ,etc Problem: response time, thrashing
What is a process?
A program during execution (process = executing program = program + execution state) -basic unit of execution in an OS -at minimum, process execution requires: memory to contain program code and data, and set of CPU registers to support execution
Saving the State of an Interrupted Process
Privileged register points to exeception stack -on switch, pushes interrupted process registers on exception stack BEFORE handler -handler pushes the rest -when returned, reverse Don't use user-level stack because of reliability and security One exception state per processor/process/thread
Booting an OS Kernel
CPU loads boot program from ROM Boot program: -examines/checks machine config (# CPU's, how much mem, # and type of hardware devices) -builds a config structure describing the hardware -loads OS kernel and gives it to config structure -initialize kernel data structures and state of all hardware devices -create number of processes to start operation then runs an idle loop if no user programs are avaliable -performs system management and profiling -halts processor and enters low power mode OS wakes up on interrupts from hardware devices
Why study OS?
-show how computers work -learn to manage complexity with abstractions -learn about system design
Dual Mode Execution
User vs Kernel Modes
Transitioning from User to Kernel Mode
Exceptions (synchronous) -user program acts weird (divides by zero) -attempt to perform privileged instructions Interrupts (asynchronous) -something interrupts the currently running process System calls/traps (synchronous) -user requests OS service (ex. function call)
Process Control
OS must include calls to enable special control of a process -priority manipulation: nice(), specifying base process priority -Debugging support: ptrace(), allows process to be put under control of another -Alarms and times: sleep puts a process on a timer queue waiting for some number of seconds
Fork()
fork(): copies processes into an identical process -copies var values and PC from children to parent -returns twice: once to the parent and to child -return values (parent = child PID and child = 0) -both processes begin execution from same point after fork -each process has its own memory and copy of each var
CPU Utilization
percentage of time that the CPU is busy
Switching back to User Mode
-From and interrupt --> just reverse all steps (asynchronous, so not related to executing instruction) -From exception and system call-->increment PC on return (synchronous) --on exception: handler changes PC at the based of the stack --on sys call: increment is done by the hardware
How does the OS enforce restricted rights?
-OS interprets each instruction -Dual Mode Execution
Short-term scheduling
The decision as to which available process will be executed by the processor. Scheduler schedules next process on CPU Scheduler may execute when: -a process switches from running to blocking -a process is create or terminated -an interrupt occurs
Exec
-overlays process w/ new program (PID doesnt change) -code, stack, heap overwritten -new program begins at main
Process States
Process state has at least: -content of the address space (code for running program, static data running, the stack, heap) -registers and contents (heap pointer, program counter for next instruction, stack pointer) -set of OS resources in use (open files) -process identifier (PID) -process execution state (ready, running, etc)
Wait() system call
causes the parent process to wait for the child process to terminate -allows parent process to get return val from child -puts parents to sleep waiting for child's results -when a child calls exit(), the OS unblocks the parent and returns value passed by exit() as a result of the wait call -if no children alive, returns immediately -if zombies are waiting for parents, wait() returns one of the values immediately (and de allocates zombies)
Throughput
The number of processes that are completed per time unit
Overlap IO and Computation Interrupts
-No sharing, only protect OS from apps -add concurrency within the SAME PROCESS -OS requests IO, goes back to computation, gets interrupt when IO device finishes
Terminating a process: kill()
A parent can terminate a child using kill() -kill also used for interprocess communication -sends a signal to a specified process (by PID) -receiving a process can define signal handlers to handle signals in a particular way -if handler for that signal does not exist, default action is taken
Three Interfaces
1) Abstract Machine Interface (AMI) -between OS and apps: API, memory access model, legally executable instructions 2) Application Programming Interface (API) -Function calls provided to apps 3)Hardware Abstraction Layer (HAL) -Abstract hardware internally to OS
Batch Processing (1955-1965)
-load, run, output to tape, print, repeat-users give punch cards to humans who schedules in batches Advantage: next job loaded right after previous finishes Disadvantages: no protection and computer can idle during IO
How does the OS track this data?
OS uses a Process Control Block (PCB) - dynamic kernel data structure kept in mem -represents execution state and location of each process when not executing PCB contains: -processor identification number, PC, stack pointer, general purpose registers, memory management info, etc PCB's initialized when a process is created and deleted when a process terminates
Dual Mode Execution: Protection Pieces
For efficient protection, the hardware must support these 3 features: 1) Privileged Instruction --prevents user processes from halting the machine or something --implementation: mode status bit in process status register 2) Timer Interrupts --prevents process from gaining control of the CPU and never releasing it --implementation: hardware timer can be set to expire after a delay (pass back to kernel) 3) Memory protection --prevents unauthorized access of data
If applications had free rein...
buggy or malicious applications could -crash others -violate other's privacy -hog resources -change or crash OS
Phase 3 - OS History (1)
Personal computing -computers are cheap so everyone has one -simplify OS by elimination of multiprogramming, concurrency and protection
Multiprogramming
-several program run at the same time sharing the machine -one job runs until it performs IO, then another job gets the CPU -OS manages interactions between concurrent programs Requires memory protection and relocation
User Mode to Kernel Mode: Details
OS states state of user prog -hardware identifies why boundary is crossed -hardware gets entry from interrupt vector and appropriate handler is evoked
Orphaned Processes
-when a parent terminates before child -in UNIX, the init process automatically becomes new parent, other instances kill all children when parent dies -child can orphan itself to cont. running in the bg
System Calls: OS Job
-Hardware calls OS at sys-call handler (specified location) -OS identifies service and executes it -sets registers to contain result -execute RTI instruction to return to user prog User prog receives result and continues
User Mode vs Kernel Mode
User processes cant: -address I/O directly -use instructions to manipulate OS memory -set mode bits from user to kernel -disable/enable interrupts -halt machine Kernel mode can do all of these
Parallel and Distributed Computing
-multiple processors in the same machine, sharing memory and I/O devices -multiple processes communicate via network -Advantages: increase performance, increased reliability, sharing of specialized resources
OS 3 Hats
1) Referee -manages shared resources -isolation (protects processes from one another) -communication (all processes work together) 2) Illusionist -illusion of unlimited resources 3) Glue - provides a standard interface to the hardware -ex: file sys, VM, networking, etc
Scheduling Policies: 2 Big Categories
Non-premptive Preemptive
Preemptive
scheduler runs on interrupts, mostly timers, but also system call and other hardware device interrupts -executing process might be pre-empted from the CPU -Most OSes today use this
System Calls
-request by user-level function to call function in kernel -interface between application and OS (API) -Parameters passed according to calling convention
Timesharing
A timer interrupt is used to multiplex CPU among jobs
History of OS
1) $$$ hardware, $ humans 2)$ hardware, $$$ human 3) $ hardware, $$$$ human
Turnaround Time
The CPU scheduling metric that measures the elapsed time between a process's arrival in the ready state and its ultimate completion (initialization to termination)
Terminating a process: exit()
After the program finished execution, it calls exit() -takes the result of process as an argument -closes all open files/connection/etc -deallocates memory and most of the OS structures supporting the process -checks if parent is alive (if so, hold the ret val until parent requests it, if not, it dellocates) -process termination is garbage collection (resources reclamation)
Performance of OS Evaluation
Efficiency/Overhead, Fairness, Response time, throughput, predictability
How to Create a Process
One process can create other processes -create processes are children and creator is parent process In some systems, parents define/donate resources and privileges to its children Parent can either wait for the child to complete or continue in parallel
Process Life Cycle
Processes are either running, ready to run or blocked waiting for an event to occur And know how to draw it
Non-Preemptive
runs until exits kernel mode, blocks, or voluntarily yields CPU; Essentially free of race conditions in kernel mode; an executing process is not ever pre-empted
Phase 1 - OS History (1)
One user & one process at a time (1945-1955) -single user system -Problem: low utilization of expensive components
Section 2
(50 cards)
Interrupts and Context Switches
interrupt state is part of the thread state -when a thread blocks, its interrupt state is saved with the rest of it's context -when a process continues running, its interrupt state is restored with the rest of its context
Locks (more formal)
provide mutual exclusion to shared data with 2 atomic routines Lock acquire: wait until lock is free, then grab it Lock release: unlock and wake up ant thread waiting in acquire locks have 2 states: busy and free (*initially free)
Critical Section
a piece of code that only one thread can execute at a time
Thread Life Cycle
new process > WAITING > RUNNING > BLOCKED - waiting starts and runs or times out - runs unless blocked until unblocked or until complete new, ready, running, blocking, terminated (just like processes)
Round Robin Scheduling
A PREEMPTIVE scheduling designed for Time Sharing Systems The Ready Queue is treated as a circular queue A small execution time interval is defined as the Time Quantum, or TIME SLICE Interrupts in Round Robin When the executing interval of a process reaches the time quantum, a SYSTEM TIMER will cause the OS to interrupt the process The OS carries out a CONTEXT SWITCH to the next selected process from the ready queue. Length of the Time Quantum Time quantum that is too short will generate many context switching and results in lower CPU efficiency. Time quantum too long may result in poor performance time.
Metadata Structures
-Process Control Block (PCB) contains process-specific info (owner, PID, heap pointer, priority, active thread, and pointers to thread info) -Thread Control-Block (TCB) contains thread-specific info (stack pointer, PC, thread state, register vals, a pointer to PCB)
Binary Semaphore
-same as lock -mutually exclusive access to a resource has 2 values: 0 or 1 (busy or free) -initial value is always free
User-Level Threads: Context Switches
Similar to processes and kernel-level threads: -thread is running -thread is interrupted by a signal or voluntarily yields -library code saves thread state (to TCB) -Library code chooses new thread to run -library code loads its state (from TCB) -thread is running
Race Conditions
Instances where the result changes based on scheduling
Multilevel Feedback Queue
-multiple queues with different priorites -OS uses round robin scheduling at each priority level, running jobs in the highest priority queue first -once those finish, OS runs jobs out of the new highest queue -round robin time slice increases exponentially at lower priorities
Liveness (critical section and correctness)
if there is no thread in the critical section, there must be one waiting that a thread must be guaranteed to eventually enter
First-Come-First-Served (FCFS)
A priority-based scheduling method in which the scheduler always dispatches the ready thread that has been waiting the longest. job runs until either complete or block on I/O
Types of Semaphores
Binary semaphores and counted semaphores only difference is the initial value!!
Multi-threaded processes with kernel-level threads
-threads created by OS (so knows about them) -thread management through sys calls -TCBs and PCBs in-kernel ready list -scheduled by OS
Ideal Synchronization
-satisfies correctness properties (safety, liveness and bounded waiting) -no busy waiting (thread should block when waiting and then be awakened when it is their turn) -extendable to many threads (symmetric)
Processes Review
-A process is the abstraction used by the OS to manage resources and provide protection -defines an address space -has a single thread of control that executes instructions sequentially
Kernel-Level Threads
-the OS is aware that they exist -scheduled and managed by the kernel -small context switch req: save thread state, mode switches (when switching between kernel level threads of the same process)
Mutual Exclusion
The requirement that when one process (thread) is in a critical section that accesses shared resources, no other process (or thread) may be in a critical section that accesses any of those shared resources. Two threads adding to linked list can corrupt the list
Locks
allows one thread to prevent another thread from doing something -lock before entering a critical section or before accessing shared data -unlock when leaving critical section or when access to shared data is complete -wait if locked
Test&set
the hardware solution to mutual exclusion that reads the contents of memory into a register then stores a nonzero value in the memory location as an indivisible instruction -reads a value from memory -writes '1' back to the memory location
Independent vs Cooperating Threads
Independent have no shared state with other threads -simple to implement -deterministic -reproducible -scheduling order doesn't matter Cooperating threads share state -non-deterministic -non-reproductive -give concurrency
When to use Mutual Exclusion
Anytime you access shared data -if a thread check a values -if a thread updates a piece of shared data
User-Level Threads
-OS does not know about -OS only schedules the process NOT the threads within the process -Programmer uses a thread library to manage threads (create, delete, synchronize, and schedule) -switching threads does not involve a context switch
Using the past to predict the future
policy is adaptive because it relies on past behavior and changes in behavior result in changes to scheduling decisions
Atomic Read-Modify-Write Instructions
atomically read a value from memory into a register and write a new value -read a mem location into register and write a new val to that location -uniprocessor just needs a new instruction
SJF (Shortest Job First)
Shortest jobs get highest priority in waiting queue. Shortest average wait time I/O bound job get priority over CPU bound jobs -Works with preemptive and non-preemptive
Atomic Operation
an operation that is uninterruptible
Synchronization
using atomic operations to ensure cooperation between threads
Real CPU Scheduler's Policy
-minimize response time -minimize variance of average response time (predictability) -maximize throughput -minimize waiting time
Single Threaded Processes
-what we have been assuming -each has exactly one kernel-level thread -add protection
Threads and Address Space
Threads share an address space -all process data can be accessed by any thread (global data and heap also shared) Each thread has it's own: -stack (but with no protection from other threads) -exclusive use of CPU registers while it is executing (when pre-empted, register vals are saved as part of the state)
Multi-threaded processes with user-level threads
-threads are created in user space -have exactly one kernel-level thread -thread management through procedure calls -scheduled by user-space scheduler -TCB's in user-space ready list
Critical Section and Correctness
For properties are required: 1) safety 2) liveness 3) bounded waiting 4) failure atomicity
ideal CPU scheduler
-maximizes CPU utilization and throughput -minimizes turnaround time, waiting time and response time -requires knowledge of process behavior we typically don't have
One Abstraction, Many Flavors
-Single-threaded processes -Multithreaded processes with user-level threads -Multi-threaded processes with kernel level threads -In-kernel threads Note: kernel level threads and user level threads are unrelated to kernel mode and user mode execution!!!!!!
Semaphores
give mutual exclusion and more general synchronization -basically generalized locks (2 atomic operations: up and down, has a value but is more than just busy/free)
Improving Fairness
Possible solutions: -give each queue a fraction of CPU time. Only fair if there is an even distribution of jobs among queues -Adjust the priority of the jobs as they do not get serviced. (Avoids starvation but average wait time suffers when the system is overloaded because all jobs end up at a high priority)
How MLFQ's work
1) Job starts in the highest priority queue 2)if job's time slice expires, drop priority a level 3)if job's time slice does not expire (context switch comes from I/O instead), increase its priority one level In practice, CPU bounds drop and I/O jobs stay at a high priority
Kernel-Level Threads: Context Switch
Similar to processes: -thread is running thread blocks, is interrupted or voluntarily yields -mode switch to kernel mode -OS code saves thread state (to TCB) -OS code chooses new thread to run -OS code loads its state (from tCB) -mode switch to user mode -thread is running
In-kernel threads
-threads that are part of the OS (init, idle)
Why Use Threads?
-better represent the structure of tasks -improve performance (one thread can perform computation while the other waits for I/O)
Safety (for critical section and correctness)
only one thread in the critical section at a time
Safety and Liveness (more generally)
properties define over the execution of a program Safety: nothing bad happens -holds in every finite execution prefix Liveness: something good eventually happens -no partial execution is irremediable
Threads
-an abstract entity that executes a sequence of instructions -defines a single sequential execution streams within a process -a thread is bound to a single process -each process may have multiple threads of control but MUST have one
Failure atomicity
It's okay for a thread to die in the critical section
Disabling interrupts
Tells the hardware to delay handling any external events until after the thread is finished modifying the critical section in some implementations, done by setting and unsetting the interrupt status bit
Power of Kernel Threads
-I/O: the OS can choose another thread in the same process when a thread does I/O -Kernel-level threads can exploit parallelism
Bounded Waiting
if a thread wishes to enter a critical section, then there exists a bound on the number of other thread that may enter the critical section before the thread does
Threads are Lightweight
Creating a thread is cheaper than creating a process -communication between threads is easier than between processes -context switching between threads is cheaper (because they are in the same address space)
Schedules/Interleavings
-model of concurrent execution -interleave statement from each thread into a single thread -if any interleaving yields incorrect results, some synchronization is needed
Section 3
(37 cards)