The system will never enter a deadlock state: Deadlock prevention and Deadlock avoidance
Deadlock Prevention Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources.
Hold and wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. Require process to request and be allocated all its resources before it begins execution, or
allow process to request resources only when the process has none allocated to it. Low resource utilization; starvation possible.
No preemption - Resources can only be released if the process holding it releases it, or after the process has completed its task of using that resource.
Circular Wait - A set of processes {P0, P1, ..., Pn-1, Pn} must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn-1 is waiting for resource held by Pn and Pn is waiting for a resource
held by P0.
Deadlock Avoidance - This requires that the operating system be given additional information in advance concerning which resources a process will request and use during its life time.
Deadlock Detection: Allow system to enter deadlock state. Need:Detection algorithm, Recovery scheme
Safe State- A state is this if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock.
If a system is in safe state = no deadlocks. If a system is in unsafe state = possibility of deadlock
Avoidance = ensures that a system will never enter an unsafe state
Banker's Algorithm: Multiple instances per resource. Each process must a priority claim maximum use. When a process requests resource it may have to wait. When a process gets all its resources it must return
them in a finite amount of time.
If safe = the resources are allocated to Pi .If unsafe = Pi must wait, and the old resource-allocation state is restored
Recovery from Deadlock: Resource Preemption
Selecting a victim – minimize cost Rollback – return to some safe state, restart process for that state. Starvation – same process may always be picked as victim, include number of rollback in cost factor
CPU Scheduler (Short-Term) - The short term CPU scheduler selects a process from the processes in memory that are ready to execute and allocates the CPU to that process
CPU Scheduling Decisions 1. When a process switches from the running state to the waiting state. When a process switches from the running state to the ready state. When a process switches from the waiting state to the ready
state. When a process terminates.
First Come First Serve Scheduling: • The process that requests the CPU is allocated the CPU first. FIFO Queue: Processes selected from head of queue. Processes added to the tail of the queue.
Nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it either terminates or goes to the waiting state.
Shortest-Job-First Scheduling: When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used
(choose the process that requested the CPU first) Special case of priority-scheduling - the larger the CPU burst, the lower priority.
Priority Scheduling: A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. Can be preemptive or nonpreemptive. Problem
= Starvation – low priority processes may never execute Solution = Aging – as time progresses increase the priority of the process.
Round Robin (RR): The CPU scheduler goes around the FIFO ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.
1. CPU picks process at head of queue
2. CPU allocates 1 time quantum (AT MAXIMUM) to the process. Uses a timer.
3. Scheduler picks the next process and puts the old process into the tail of the ready queue
• Preemptive
q large => FIFO. q small => q must be large with respect to context switch,otherwise overhead is too high.
Multilevel Queue: Each queue has its own scheduling algorithm: foreground – RR background – FCFS
Scheduling must be done between the queues: Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation. Time slice – each queue gets a certain amount of CPU
time which it can schedule amongst its processes; i.e., 80% to foreground in RR. 20% to background in FCFS
Multilevel Feedback Queue
A process can move between the various queues; aging can be
implemented this way Multilevel-feedback-queue scheduler defined by the following
parameters: number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine
which queue a process will enter when that process needs service
example of Multilevel Feedback Queue
Three queues:
Q0 – RR with time quantum 8 milliseconds Q1 – RR time quantum 16 milliseconds Q2 – FCFS
Scheduling
A new job enters queue Q0 which is served FCFS When it gains CPU, job receives 8 milliseconds If it does not finish in 8
milliseconds, job is moved to queue Q1 At Q1 job is again served FCFS and receives 16 additional milliseconds If it still does not complete, it is preempted and moved to queue Q2.
Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are
available
Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing.
Symmetric multiprocessing (SMP) – each processor is self- scheduling, all processes in common ready queue, or each has its own private queue of ready processes. Currently, most common. Need to keep all
CPUs loaded for efficiency. Load balancing attempts to keep workload evenly
distributed.
Multicore Processors: Recent trend to place multiple processor cores on same
physical chip. Faster and consumes less power. Multiple threads per core also growing. Takes advantage of memory stall to make progress on another thread while memory retrieve happens.
Slide 3 : virtual memory
Virtual memory – separation of user logical memory from physical memory. Only part of the program needs to be in memory for execution Logical address space can therefore be much larger than physical
address space. Allows address spaces to be shared by several processes. Allows for more efficient process creation. More programs running concurrently. Less I/O needed to load or swap processes.
Virtual address space – logical view of how process is stored in memory .Usually start at address 0, contiguous addresses until end of space. Meanwhile, physical memory organized in page frames. MMU must
map logical to physical.
Demand Paging
Bring a page into memory only when it
is needed
! Less I/O needed, no unnecessary
I/O
! Less memory needed
! Faster response
! More users
" Page is needed Þ reference to it
! invalid reference Þ abort
! not-in-memory Þ bring to memory.
Page Fault
! If there is a reference to a page, first reference to that page will
trap to operating system:
page fault
1. Operating system looks at another table to decide:
! Invalid reference Þ abort
! Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Restart the instruction that caused the page fault.
Performance of Demand Paging
Three major activities
! Service the interrupt – careful coding means just several
hundred instructions needed
! Read the page – lots of time
! Restart the process – again just a small amount of time
! Page Fault Rate 0 £ p £ 1
! if p = 0 no page faults
! if p = 1, every reference is a fault
Basic Page Replacement
1. Find the location of the desired page on disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to
select a victim frame
- Write victim frame to disk if dirty
3. Bring the desired page into the (newly) free frame; update the page
and frame tables
4. Continue the process by restarting the instruction that caused the trap
Note now potentially 2 page transfers for page fault – increasing EAT
Frame-allocation algorithm determines
How many frames to give each process
Which frames to replace
Page-replacement algorithm
Want lowest page-fault rate on both first access and re-access
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string
String is just page numbers, not full addresses
Repeated access to the same page does not cause a page fault
Results depend on number of frames available
Least Recently Used (LRU) Algorithm
Use past knowledge rather than future
Replace page that has not been used in the most amount of time
Associate time of last use with each page
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames (3 pages can be in memory at a time per process)
12 faults – better than FIFO but worse than OPT
Generally good algorithm and frequently used.
Lease Frequently Used (LFU) Algorithm replaces page with smallest count. Most Frequently Used (MFU) Algorithm: based on the argument that the page with the smallest count was probably just brought in
and has yet to be used.
Thrashing If a process does not have “enough” pages, the page-fault rate is very high. Page fault to get page. Replace existing frame. But quickly need replaced frame back This leads to: Low CPU utilization.
Operating system thinking that it needs to increase the degree of multiprogramming. Another process added to the system. Thrashing = a process is busy swapping pages in and out
Why does demand paging work? Locality model. Process migrates from one locality to another. Localities may overlap.
Why does thrashing occur? S size of locality > total memory size. Limit effects by using local or priority page replacement.
Slide 4 : Main memory
6
Base and Limit Registers
! A pair of base and limit registers define the logical address space
! CPU must check every memory access generated in user mode to
be sure it is between base and limit for that user.
Address binding of instructions and data to memory addresses
can happen at three different stages
! Compile time: If memory location known a priori, absolute
code can be generated; must recompile code if starting
location changes
! Load time: Must generate relocatable code if memory
location is not known at compile time
! Execution time: Binding delayed until run time if the
process can be moved during its execution from one memory
segment to another.
Logical address – generated by the CPU; also referred to as
virtual address
! Physical address – address seen by the memory unit
! Logical and physical addresses are the same in compile-time
and load-time address-binding schemes; logical (virtual) and
physical addresses differ in execution-time address-binding
scheme
! Logical address space is the set of all logical addresses
generated by a program
! Physical address space is the set of all physical addresses
generated by a program.
static linking – system libraries and program code combined by
the loader into the binary program image
! Dynamic linking –linking postponed until execution time, used
with system libraries, such as the standard C language library
! Without this facility, each program on a system must include a
copy of its language library (or at least the routines referenced by
the program)
! Dynamic linking is particularly useful for libraries
! System also known as shared libraries.
Memory Allocation
Main memory must support both OS and user processes. Limited resource must allocate efficiently
Contiguous allocation is one early method. Main memory usually into two partitions: One for the operating system and one for the user processes. Many operating systems (including Linux and Windows) place
the operating system in high memory. Each process contained in single contiguous section of
memory.
Multiple-partition allocation
Degree of multiprogramming limited by number of partitions. Variable-partition sizes for efficiency (sized to a given process’ needs). Hole – block of available memory; holes of various size are scattered
throughout memory When a process arrives, it is allocated memory from a hole large enough to accommodate it Process exiting frees its partition, adjacent free partitions [Link] system maintains
information about: a) allocated partitions b) free partitions (hole).
Dynamic Storage-Allocation Problem
First fit: Allocate the first hole that is big enough, fast
Best fit: Allocate the smallest hole that is big enough; must
search entire list, unless ordered by size
! Produces the smallest leftover hole
! Worst fit: Allocate the largest hole; must also search entire list
! Produces the largest leftover hole
How to satisfy a request of size n from a list of free holes?
First-fit and best-fit better than worst-fit in terms of speed and storage
utilization.
Fragmentation External Fragmentation – total memory space exists to
satisfy a request, but it is not contiguous
! Internal Fragmentation – allocated memory may be slightly
larger than requested memory; this size difference is memory
internal to a partition, but not being used.
Paging: Physical address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available
Avoids external fragmentation
Avoids problem of varying sized memory chunks
Divide physical memory into fixed-sized blocks called frames
Size is power of 2, between 512 bytes and 16 Mbytes
Divide logical memory into blocks of same size called pages
Keep track of all free frames
To run a program of size N pages, need to find N free frames and
load programSet up a page table to translate logical to physical addresses
Backing store likewise split into pages
Still have Internal fragmentation.
Swapping A process can be swapped temporarily out of memory to a
backing store, and then brought back into memory for continued
execution
Total physical memory space of processes can exceed
physical memory
Backing store – fast disk large enough to accommodate copies
of all memory images for all users; must provide direct access to
these memory images
Roll out, roll in – swapping variant used for priority-based
scheduling algorithms; lower-priority process is swapped out so
higher-priority process can be loaded and executed
Major part of swap time is transferring time; total transfer time is
directly proportional to the amount of memory swapped
System maintains a ready queue of ready-to-run processes
which have memory images on disk.