Section 1
Preview this deck
Types of Memory
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 (208)
Section 1
(50 cards)
Types of Memory
registers cache main memory SSDs Magnetic Disks
virtualization
running a computer on a computer - all modern computers have specialized software support for this
kernel
loads and starts other programs programs become processes and execute from main memory
ready queue
contains the processes that are in main memory and aren't waiting
Register Set
what the process thinks the state of all other registers currently is
mobile computing
laptops and tablets have a lot of characteristics of desktop operating systems tend to be optimized for information consumption
interrupt handler
executes then returns control to the program that was running
real-time computers/OS
when things have to be done now popular for control systems (Xrays) can show up as subsets of other systems
multiprogramming
scheduling more than one program at once
State
generally new, ready, waiting, running, or terminated
Job/Process
program in execution program becomes this when it's loaded into memory and started
Privileged Instructions
can only be executed in kernel mode include all hardware access, so OS must provide system function calls
multitasking (interactive time sharing)
multiprogramming with switches frequent enough that users can interact with running programs often requires a time-shared OS
Long-Term Scheduler
loads entire batch-scheduled processes from disk gets a mix of CPU bound and I/O bound processes going useless for fully-interactive OS
Scheduling Information
the process's priority, and anything else the OS uses to decide how to schedule it
I/O
everything except CPU and main memory is this performed by CPU via controllers connected to a bus disks are also this
cloud computing
client-server systems running over commodity internet or large private networks can include file servers, computation servers, virtual machines, etc not a new tech so much as radically scaled existing tech
User Mode
only allowed specific instructions and regions of memory make requests of the OS by raising interrupts OS in kernel mode fulfills and then returns control to the programs
device queue
each I/O device has one contains the processes that are waiting on that device
I/O Status information
what files and devices this process has open, what it's waiting on, etc
Iron Law of the Memory Hierarchy
fast memory is expensive cheap memory is slow
Context Switching
interrupt to return control to OS copy frozen process's current state change frozen process's state from running to ready select new process copy new process's state from its PCB into the registers change the new process's state from ready to running return control to the new process at its current program counter the running process has control of the program counter and registers, but others have their own copy ready to be loaded back in
Kernel Mode
aka privileged mode, system mode, monitor mode allowed to do anything only OS is allowed this
Multiprocessor Systems
include smartphones higher throughput, better economy symmestric multiprocessing
child process
created by parent process needs resources (constrained by parent process or requests from OS) can receive parameters from the parent process may execute concurrently with parent, or parent can wait may be duplicate of parent, or have new program
emulation
running code on another kind of computer
Starting a Process The OS must:
create and initialize a PCB for the process (new) load the program into main memory set the PCB program counter to the entry point of the program Set the PCB state to ready
desktop/laptop computers
interrupt driven and multitaskers supports multiple users, may or may not support multiple at once
Von Neumann Machine
Stored Programs CPU with: - Control Unit - Arithmetic/Logic Unit Memory Input and Output
large systems
initially require to centralize very scarce computing resources built around time-sharing; typically noninteractive uncommon
Accounting information
who's responsible for this process, how much time it's taken, etc
interrupts
stop execution of the running program and transfer control to an interrupt handle can be generated from - hardware events - timer events - requests for system services
job queue
contains all processes in a system
CPU Scheduler
selects ready processes and decides which one to run
clustered systems
multiprocessor systems over a network synchronization issues
client-server systems
networked systems that allow a client to ask a server to do something web servers, database servers, game servers
Starting the Computer
- boot program is run when computer turns on - loads and start kernel
Scheduling
deciding which processes to run from the processes that can be run all about queues
I/O Methods
polled interrupt-driven direct memory access
Main Memory
largest storage device the CPU can directly access programs have to be here to run
Process Management
Processes need memory, I/O, and CPU (and other resources)
peer-to-peer systems
any computer can be a client, a server, or both have to be able to discover each other famous for piracy but have other applications
Medium-Term Scheduler
kicks processes right back out to disk
Program Counter
register in CPU points at where the next instruction that's going to be executed is does not point at current instruction
interpretation
running code for a theoretical computer
Single-Processor Systems
systems with one general-purpose CPU
Modern Operating Systems Need:
process management memory management I/O management security
Dual-Mode Operation
normal processes shouldn't be able to access the hardware or mess with other processes, but they have have to be allowed to run and do normal thing User Mode and Kernel Mode
Process Control Block
where the OS stores all information about a process - centrally located, easily accessible
files
named sequential arrays of bytes make up almost all data on disks
Section 2
(50 cards)
I/O Management
the OS: communicates with device controllers provides output to devices receives input from devices
Cooperating Process
Affects or is affected by other processes Any process that needs to share data with other processes Require IPC mechanism
Identifying Tasks (Threads)
Issue Dividing up the work in terms of operations
CPU Processes
Have relatively long CPU bursts and less I/O waiting
Thread Scalability
Benefit Exploitation of multiple processors
Response Time
The time between the submission of a request by a user and the first output to that user Irrelevant to overall scheduler performance Most import measure in terms of user satisfaction
Data Parallelism
Divides up data, using multiple processors to run the same code on different data slices (image processing)
Multiprogramming
Processes run until they: Have to wait Are terminated Yield Are preempted Other processes can then take a turn
Java Thread Implementation
Any class can be made a thread by implementing Runnable interface
Creating Processes on Windows
CreateProcess is similar to UNIX, but accepts ten different parameters to account for every possible permutation on one function call when a process is terminated, its children may be too
Linux Thread Implementation
Doesn't have threads Has different levels of sharing Clone() helps to decide what to clone and not clone
Thread Dependency
issue Managing dependent work (think about producer/consumer problem)
CPU Scheduler
Selects a process from the ready queue to run
Authorization
process of determining, given who you are, what you may do
Security Management
The OS: deflects passive and active attempts to defeat its management mechanisms uses authentication authorization access control cryptography
Creating Processes on UNIX
fork creates a new copy of the current process as a child if you're the child, get back 0 otherwise, get back child's process ID exec can then be used to run a different process as the parent, either wait for a child, or keep going
Task Parallelism
Divides up code, using multiple processors to run different parts of the program (sockets)
Access Control
process of enforcing authorization
Parallelism
Doing different parts of the same job on different processors
Symmetric Multiprocessor
Allow each processor to be an equal participant
Turnaround Time
Process-individualistic version of throughput How long it takes to execute a given process, from start to termination Minimizing results in best experience for users waiting on (whole) processes
Cooperative Multitasking Process Stop
Have to wait (on I/O) Are terminated (by themselves or by OS) Yield (give another process a turn)
Dispatcher
Part of the CPU scheduler that actually does the business of context switching once the new process is selected Performance is just as important as performance of the scheduling algorithm
Files I/O Management
The OS: creates, writes, and deletes files and directories provides functions for processes to work with files maps files onto disks (partitions)
cryptography
process of making it difficult to effectively interpret private communications or impersonate users
Preemptive Scheduling
Processes are not allowed to run as long as they feel like Processes stop if preempted by timer interrupt
Independent Process
Apart from being managed by the OS, it doesn't affect and isn't affected by any other processes
Waiting Time
Amount of time a process is ready without running Only component of a process's total runtime that the CPU scheduler directly affects Considered a good overall measure of the efficiency of the CPU scheduler in specific
Thread Data Splitting
Issue Dividing up work in terms of data
Scheduling Fundamentals
A system can only run as many processes at once as it has processors CPU time is wasted if a process is just idle while waiting We only want processes to hold the CPU until they have to wait
Thread Resource Sharing
Benefit Can implement parallelism without the need for message passing or shared memory
OS and Memory Management
The OS: keeps track of what memory is being used, and by which processes decide what to move in and out of memory allocate and de-allocate memory as necessary make sure process stay within their bounds of memory
OS and Processes Management
loads programs into memory to turn them into processes create, delete, suspend, and resume processes schedule processes and threads to CPU assign resources provide synch and communication to processes
Thread Debugging
Issue Fixing multithreaded processes is very hard
Under-loaded processors
Pull processors from other processors
Windows Thread Implementation
Implements threads directly CreateThread() analogous to CreateProcess()
Dispatch Latency
Time dispatcher takes to stop one process and start another Total time taken every time the CPU scheduler runs + the time taken by the actual scheduling algorithm
CPU Utilization
Want to keep CPU as busy as possible 0-100% For an optimally loaded system not considering direct user responsiveness, 40-90% Avoids wasting hardware time via lack of use or via overload and its corresponding overhead
Authentication
process of determining that you are who you say you are
Burst Cycle
Processes alternate bursts of CPU activity and I/O waits Types of processes differ in their burst patterns What we are scheduling is not a process, but the next CPU burst for that process Kinds of processes you have affect the best scheduling algorithm to use
Multiple-Processor Scheduling
Symmetric Multiprocessor The CPU scheduler is run by, and for, each processor Each processor selects its own process from the ready queue to execute Avoid multiple processors choosing the same process to run Avoid moving processes between processors Ready queue per processor
Throughput
Number of processes completed per time unit Originally a figure used for batch-processing systems Maximizing results in the highest number of complete processes getting done in a given time period
Overloaded processors
push processors to other processors
Ready Queue
Conceptually a queue Not a FIFO queue
CPU Scheduler Runs when
Running process waits (I/O call) Running process becomes ready (yield or preemption) Waiting process becomes ready (I/O completion) Process terminates
Thread Balancing
Issue Make sure every thread gets enough work
Thread Responsiveness
Benefit Can allow for an application to be more responsive without having to logically interrupt its own work
I/O Bound Processes
have relatively short CPU bursts interspersed with I/O waits
Disks I/O Management
the OS: organizes files manages free space allocates space to files schedules for processes
Threads
Processes are allowed to have any number of program counters Each thread needs its own Program counter Register set Call stack (in kernel or user space) are a simple form of parallelism
Section 3
(50 cards)
Shortest Job First Weakness
Not actually possible Longer processes may never get run
Interactive User Processes (Multilevel)
Queue 2 Traditional applications
EDF Advantages vs Rate-Monotonic
Processes do not need to be periodic Can take different amounts of time each period Can achieve higher processor utilization
First-Come First-Served (FCFS)
Simplest of all reasonable schedulers Processes allocated the CPU in the order which they arrive Run until completion and termination Cannot be sensibly made preemptive
System Process (Multilevel)
Queue 0 OS Processes, device drivers
FCFS Weakness
Unpredictable wait times Non-preemptive nature makes it unusable to modern OSs
Relative Priority Disadvantage
Higher-priority processes more likely to be disrupted by lower-priority processes
Processing time
How long it takes to run each period
FCFS Strengths
Simple Easy to write and understand
Relative Priority Advantages
Avoids starvation
Deadline
How quickly the burst must be completed when it becomes ready
Round-Robin
Algorithm explicitly designed for time-sharing systems Redesigned from FCFS to have preemption Set timer to interrupt to stop the running process if its burst goes longer than the time quantum (10ms-100m) When a process becomes ready for whatever reason, put in on the back of queue each process is guaranteed to have to wait at most (n-1)q time units until it gets processor back
Earliest Deadline First
Priority based, strictly preemptive Process declarers deadline every time it becomes ready Each process assigned a priority based on deadline - Priority to process that needs to finish soonest Earliest deadline is immediately assigned to processor
Multi-Multi-Level Queue scheduling
Use combination of absolute and relative approaches Schedule so that the system queue and quasi-real-time queue
Relative Priority
Give each queue its own set of time slices to slice
Multilevel Queue Disadvantages
Starvation, as with anything with absolute priority
True Background Process (Multilevel)
Queue 4 Virus scanners, search indexers
Period/rate
How often it needs to run
Windows Scheduling
Explicit multilevel queue with internal priorities mapped to linear numeric values that in turn provide an implicit multilevel queue Higher-priority threads immediately preempt lower-priority threads - Soft real-time threads always preempt other threads
Thread Scheduling
Like scheduling processes Difference is contention scope
Priority Weakness
Dependent on priority being set reasonably Starvation
EDF Disadvantages vs Rate-Monotonic
Each process must declare its deadline each period Less predictable - may not know we will fail until a process becomes ready
Real Time Scheduling
Used for processes that need to respond to events as quickly as possible Non-preemptive multitasking non-starter
Rate Monotonic
The process with the faster rate always goes first Priority based Strictly preemptive Each process must declare its period and its decline Priority based on period Deadline is assumed to be beginning of the next period Throws away about 30% of CPU cycles
Process Contention Scope
Schedule processes and then schedule threads within them
System contention scope
Schedule threads just as we would schedule processes
Shortest Job First
Scheduled to the CPU giving priority to the process that will have the next-shortest burst Can be cooperative or preemptive
Multilevel Feedback Queue
- processes can move between queues - defined by: - number of queues - scheduling algorithm for each queue - algorithm used to decide when to move processes between queues - algorithm used to decide which queue a process starts in
Admission control algorithms
Determine whether it is possible to accept a given process given the three characteristics of hard real-time scheduler processes
Active Array
When this runs out of processes, the scheduler switches it
Change in Priority for Windows Scheduling
When a thread returns from an I/O wait, its priority is raised - Higher amount for user interaction - Lower for disk I/O When a thread uses its entire quantum, its priority is lowered - Never lowered below base priority The process owning the foreground window gets a priority bump - Usually about 3
Priority Strength
Flexible
Hard real-time
Need to ensure that we will either service a process's latency requirements or refuse it
Quasi-Real-Time User Processes (Multilevel)
Queue 1 Media players, games
Processor-Level Threading
Multicore processors present one physical processor as multiple logical processors, allowing multiple threads to be "running" on it The processor then decides internally how to schedule those threads, running a second-level, simpler CPU scheduling algorithm of its own
Multilevel Queue
Partition the ready queue into multiple separate queues Permanently assign each process to a given queue based on input or an inherent property of the process Queues given priority order
Multilevel Queue Advantages
Higher importance processes less likely to be stalled by lower-importance processes
Linux Scheduling Advantages
An O(1) scheduler This scheduler implements priority with a guaranteed constant upper bond of execution time a constant number of priority levels, and a queue for each of them
Priority
General version of Shortest Job First Each process has a priority that determines how soon it is scheduled compared to other processes (determined by number or function) Cooperative or preemptive
Three Characteristics of a Hard Real-Time Scheduler Process
- Period/rate - Deadline - Processing Time
Absolute Priority
Causes starvation In general, a bad idea
Linux Scheduling Disadvantages
Heuristics were pretty bad at figuring out which processes were interactive
Linux Scheduling
Has a constant number of priority levels, and a queue for each of them -> O(1) Scheduling 140 priority levels Each processer is given two arrays of doubly linked lists - Expired Array - Active Array When a process needs to be chosen, an active process with best priority is chosen Guaranteed to be doable in 140 compares or less
Hard Real-Time Scheduling
Attempts to guarantee that a task will be serviced by its deadline Failure to do so is considered complete failure Run the gamut from radios to life-safety-critical systems
Expired Array
A process is put here when its quantum expires, re-inserted into the corresponding queue Priority can change at this point
Round Robin: q
needs to be large with respect to the context switch time needs to be small enough for the system to be continually responsive
Soft real-time
Enough to ensure that real-time processes run with absolute priority over other processes
Soft Real-Time Scheduling
Guarantees only that real-time processes get priority over non-real-time processes
Non-Interactive User Processes (Multilevel)
Queue 3 Compilers, media encoders
Shortest Job First Strength
Guaranteed to produce an optimal schedule in terms of waiting time
Section 4
(50 cards)
Completely Fair Scheduler (CFS)
implements weighted fair queuing concept each process is given a virtual runtime scheduler selects whichever process currently has lowest virtual runtime for normal priority processes, virtual runtime = physical runtime processes and runtimes held in red-black tree takes O(log n) to insert a process
Disabling Interrupts Issues
Performance - If timer is controlled by interrupts, its going to mess them up Potential unpredictable consequences - Disables fundamental bits of the operating system Absolute non-starter on multiprocessor systems
Hold and Wait
At least one process is waiting on a resource while holding a different one
Mutual Exclusion
Resources are held by processes and cannot be shared
Circular Wait
A set of processes P = {P0, P1....Pn} must exist so that: - For each i so that 0<i<n, P is waiting on a resource that Pi+1 holds - Pn is waiting on a resource that P0 holds
Deal With Deadlocks
Prevent by eliminating one of the condition that allow them to occur Avoid by monitoring resource allocation with an algorithm Recover by detecting them when they occur and taking action Ignore and hope they don't happen very often
Solaris Priority
real-time threads always have priority system threads are second threads that return from I/O have priority increased threads that use up time quanta have priority decreased lower priority = longer time quanta
priority inheritance
once a process waits for a lock, the process that holds that lock receives the waiting process's priority prevents medium priority processes from preempting a lower priority one
Deadlock Recovery Plan A
Terminate every process involved in the deadlock Immediately takes care of the deadlock without further computation However, every process involved with the deadlock is terminated. All processes need to be restarted from the beginning
Deadlocked
If every process in a set is waiting on an event that can only be caused by another process in the same set If every process P is requesting some resource from R, and all resources in R are already held by processes in P, every process in P will wait indefinitely
Solaris Scheduling
each of the Solaris treads use different scheduling methods the scheduler maps each class-specific output to global priority uses dynamic priority
Counting Semaphores
like mutex locks but integer instead of boolean signaling increments, waiting decrements; processes are blocked when they wait on zero
No Resource Preemption
A resource cannot be forcibly removed from the process holding it
Avoid Spin Waits
turn mutex into queue when a process waits on a mutex that isn't available, it's inserted into a queue for that mutex queuing is a critical section
Monitors
an object with extra properties only one function can execute at the same time
Mutual Exclusion Fix
Dead end: resources that are inherently sharable are already marked as sharable for performance purposes, so they won't deadlock Resources that are inherently un-sharable will cause undefined behavior if they're shared EX: Mutex locks
Solaris Classes of Tread
Real-Time System Time-Sharing Interactive Fair Share Fixed Priority
Hold and Wait Fix
Set up a resource request method so you cannot request resources when you already have resources Has performance and starvation issues
Mutex
Primitive function provided by the operating system Implemented in such a way that wait cannot be interrupted between testing that m is true and setting it to false
Mutex Locks and test-and-Set
muex is free if m is false, releasing it sets it as false, and acquiring lock sets true returns false if m was false and true if m was true m is true after either way does not disable interrupts
Multipliers affecting Virtual Runtime
- Priority (direct multiplier) - Long-running processes get deprioritized - CPU-bound processes get deprioritized - I/O bound processes get prioritized all done preemptively
Issues with Semaphores
use, but low-level constructs like malloc and free - can cause resource leaks
Signal and Wait
signaling process is locked until the resumed process leaves the monitor
How Processes Use Resources
A process requests a resource, waiting until the resource is available, and once it is, obtaining exclusive access to it The process then uses the resource The process then releases the resources, freeing it for the use of other processes
Examples of Deadlock Handling
Only databases actually acknowledge Proper handling is hard Don't happen very often User-level programmers have incentive to avid them
Producer
Creates chunks of data must be delayed as appropriate to not overrun buffer
Livelock: Priority Inversion
Less severe than a deadlock, but still a problem if a lower priority process holds a lock needed by a higher-priority process, that higher priority process's priority is effectively lowered to that of the lower priority one
methods
functions and procedures that operate on upon the object
Signal and Continue
the signaling process continues, and the resumed process waits until it can enter the monitor normally
Concurrent Pascal Method
signaling leaves the monitor don't signal until critical section is done
No Resource Preemption Fix
take away all the resources it currently has and make it wait on all of them at once Can also allow a process to steal a resource from another process if that other process is waiting Not useful for mutex locks or semaphores
Victim Selection Algorithm
A cost function to determine the process out of the set that it will cause the least mischief to terminate Some Factors - Process priority - How close the process is to completion - How many resources the process has - How many more resources the process needs - How likely terminating the process is to help solve the problem - Whether or not the process is interactive
Deadlock Recovery Plan C
Preempt specific resources from a process Victim selection Terminate the process we're going to preempt them from Requires the victim process to be able to roll back the state before it got the resources it's having taken away
Deadlock Recovery Plan B
Terminate process involved in the deadlock until the deadlock goes away Define a victim selection algorithm Requires re-running the deadlock detection algorithm after every process is killed
Shared Memory
convenient for large amounts of data
Circular Wait Fix
Impose a total order on resources. Each resource has a number A process cannot request a resource if it has any resource with a number higher than that resource Mostly prevents circular waits bc circle can't be completed Still limits resource allocation
object
abstract data type that contains: public and private data public and private methods
condition variables
like a queued mutex a condition cannot be free waiting on this always waits signaling this can only free a process already waiting on it a thread that is waiting on this does not occupy the monitor provided by monitors internally
Message Passing
avoids conflict and works better across networks
Test and Set Instruction
defines minimum possible critical section in hardware if called on true, stays true and returns true if called on false, becomes true and returns false
Critical Section
Segment of code In a cooperating process Modifies shared information in a way that either: - Can destructively interfere with other critical sections - Can be destructively interfered with by other critical sections
Mutex Locks with Disabling Interrupts
Wait is never interrupted between determining that m is true and setting it to false In one version, wait yields, in another version, wait just keeps checking whenever it can get the CPU
Dining Philosophers Problem
A bunch of philosophers sit around a table with one fork between each philosopher Each philosopher: - Thinks until they get hungry - Tries to pock up both forks and eat - Eats until they're full - Puts down their forks - Repeats To eat, each philosopher needs both forks on left and right To prevent starvation, pick up left fork first until last philosopher Number the forks
Deadlock Avoidance
Look at the set of waiting processes If there's a circular wait, there's a deadlock O(n2) problem - detecting a cycle in a graph
Windows Synchronization
uses simple spinlocks and mutex locks i the kernel adapts spinlocks to interrupt-disabling for single-processor systems provides thread synch with dispatcher objects: - mutex locks - semaphores - timers - conditions (events) lock-guarded shared memory
Inter-Process Communication
Uses Shared Memory and Message Passing
Conditions for Deadlock
occur when all conditions are met: Mutual Exclusion Hold and Wait No Resource Preemption Circular Wait
The Producer-Consumer Problem
example of inter-process sharing producer places chunks of data in shared memory location where consumer can read them
Monitors in Practical Use
puts all synchronized behavior in one place no longer synch main code threads' code logic particular to each thread monitor's code contains all logic that lets the threads onteract
Consumer
operates on chunks of data needs to be delayed as appropriate to wait for more generated data
Section 5
(8 cards)