Operating Systems Flashcards
1
Q
Why do we need operating systems?
A
The OS works as an interface between users, applications and hardware. It hides the technical complexities (abstracts them away) and provides the user with interfaces to actually utilise the hardware
Provides a file system which allows data to be organised into files and folders (also permission management, metadata, searching)
It’s a resource manager: responsible for allocating resources to users and processes while ensuring there is no starvation (all users everyone should be able to access resources without a single user hogging them all), allocates resources according to policy (e.g. CPU timeslices can be allocated according to first-come-first-served etc.)
2
Q
What is the definition of an operation system?
A
Software that acts as an intermediary between a user and hardware, executes programs which serve users’ needs, makes solving user problems easier, makes the computer convenient to use (e.g. by providing a file system) and uses the resources of the system fairly according to policies
3
Q
Structure of an operating system
A
Users
Application programs - define the way in which the system resources are used to solve the computing problems of the users
OS - controls and coordinates the use of hardware by applications
Hardware
4
Q
What is a kernel?
A
The core of the operating system, a program that is constantly running (in privileged/kernel mode)
5
Q
Privileged mode/user mode
A
Programs in privileged/kernel mode can decide other programs’ access to hardware. The OS also prevents applications from interfering with each other.
6
Q
What is the mode bit?
A
The bit provided by hardware that determines whether code is coming from user mode programs or kernel mode programs. Some instructions can only be executed in privileged mode, including managing interrupts, I/O, and halting processes
6
Q
What is the mode bit?
A
The bit provided by hardware that determines whether code is coming from user mode programs (1) or kernel mode programs (0). Some instructions can only be executed in privileged mode, including managing interrupts, I/O, and terminating processes
7
Q
When does a transition from user mode to kernel mode occur?
A
When a user mode process asks the operating system to execute a function which requires a privileged instruction (system call)
When an interrupt occurs
When an error condition occurs
When an attempt is made to execute a privileged instruction while in user mode
8
Q
How does the OS allow programs to communicate (on the same PC or over a network)?
A
Processes can communicate via shared memory or through message passing (packages moved by the OS across a network)
9
Q
Error detection
A
The OS needs to be constantly aware of possible errors (which may occur in the CPU and RAM, I/O devices, user programs)
It needs to take the appropriate action to ensure correct and consistent computing
It also provides debugging facilities
9
Q
Error detection
A
The OS needs to be constantly aware of possible errors (which may occur in the CPU and RAM, I/O devices, user programs)
It needs to take the appropriate action to ensure correct and consistent computing
It also provides debugging facilities
10
Q
Protection and security
A
In a multiuser system, the OS should ensure that all access to system resources is controlled, programs do not interfere with each other, users cannot access each other’s personal data
11
Q
CLI vs GUI
A
CLI = command line (implemented by kernel, sometimes by system programs such as cmd.exe). Commands are either built in or names of programs
12
Q
User goals and system goals
A
User goals: OS should be convenient to use, easy to learn, reliable, safe, fast
System goals: Easy to design, implement and maintain, flexible, error-free, reliable, efficient
13
Q
How are operating systems implemented?
A
Lowest levels in assembly, main body in C, system programs in C, C++, Python, shell scripts
Higher level languages are easier to port to other hardware, emulation can allow an OS to run on non-native hardware
14
Q
What is monolithic kernel architecture and how does UNIX use this?
A
An operating system architecture where the entire OS runs in kernel mode
The UNIX OS consisted of two parts: system programs and the kernel, which is anything below the system call interface and above the hardware
15
Q
What is microkernel system architecture and how does Mac OS use this?
A
The kernel is small and only contains the bare minimum amount of software
Communication between modules such as device drivers, application programs and the file system takes place via message passing
16
Q
What does a process contain?
A
Code
Current activity (program counter and content of CPU registers)
Stack (temporary data such as local variables)
Data section (global variables)
Heap (memory allocated while process is running)
17
Q
What is a process control block and what does it contain?
A
Data structure which stores information about a process
Process ID, status, CPU registers, priority, memory usage, I/O status
18
Q
Process states
A
New - the process is being created
Running - instructions are being executed
Waiting - the process is waiting for some event to occur
Ready - the process is ready to be dispatched to the CPU
Terminated - the process has completed its execution, or some other event causing termination
19
Q
Transitions between process states
A
admitted: new=>ready
scheduler dispatch: ready=>running
interrupt: running=>ready
exit: running=>terminated
I/O or event wait: running=>waiting
I/O or event completion: waiting=>ready
20
Q
How are processes stored in memory?
A
Each process has a separate memory space, delimited by a base register and a limit register. The CPU has to check every memory access generated in user mode to make sure it’s within these bounds
21
Q
What does memory consist of?
A
Memory cells: electronic circuits which store one bit of information.
22
Q
Logical vs physical addresses
A
Logical addresses are generated by the CPU, and are also known as virtual addresses
Physical addresses are the ones used in the RAM itself, never known by user programs
23
What is the memory management unit?
The hardware device that maps virtual to physical addresses. A simple MMU adds the value in the relocation register to the logical address, to make a physical address
24
How is main memory partitioned?
One partition for kernel processes and another for user processes
25
How are new processes allocated memory?
When a process arrives, it is allocated memory from a "memory hole" large enough to accommodate it. The OS needs to maintain information about each partition and its allocated memory and free holes.
26
What is the first-fit strategy for allocating a hole to a new process?
Allocate the first hole which is large enough
27
What is the best-fit strategy for allocating a hole to a new process?
Allocate the smallest hole which is large enough
Requires you to search the whole list
Produces the smallest leftover hole
28
What is the worst-fit strategy for allocating a hole to a new process?
Allocate the largest hole
Requires you to search the whole list
Produces the largest leftover hole
29
Resource sharing: three possible cases
The parent and child processes share all resources
The child process shares a subset of the parent's resources
The parent and child processes share no resources
30
Execution: two possible cases
The parent and child execute concurrently
The parent waits until the child terminates
31
Process termination
The process asks the OS to delete it using the exit() system call
Outputs data from child's process to parent (via wait())
The child process's resources are de-allocated by the operating system
32
When do parent processes terminate execution of child processes
The child process has exceeded its allocated resources
The task assigned to child is no longer required
The parent is itself terminating
33
Zombie and orphan processes
Zombie proccess: no parent waiting for it (did not invoke wait())
Orphan process: Parent terminated without invoking wait()
34
Process scheduling
Purpose is to maximise CPU use, and quickly switch processes onto CPU for time sharing
Process scheduler selects process for next execution on CPU
35
Different types of scheduling queue
Job queue: Set of all processes
Ready queue: Set of all processes residing in main memory, ready and waiting to execute
Device queue: Set of all processes waiting for an I/O device
36
Process creation
Child duplicates parent's address space for easier communication with the parent
fork() system call creates new process which starts executing from the line below the parent's fork() call
37
Four components of the kernel
Privileged instruction set
Interrupt mechanism
Memory protection
Real-time clock
FLIH manages interrupts
Dispatcher/scheduler switches CPU between processes
Intra-OS communications (e.g. via system bus)
38
First-level interrupt handler (FLIH)
Determines the source of an interrupt, what happened and to prioritise the processes
Initiates servicing of the interrupt (selects which process should be sent to the dispatcher/scheduler)
39
The dispatcher
Assigns processing resource (CPU time) to processes
Is initiated when:
- A current process cannot continue
- An interrupt changes a process state
- A system call results in the current process not being able to continue (e.g. waiting for an input or output)
40
What are threads
Unit of execution
Lists a sequence of instructions that execute
Belongs to a process and executes within it
Kernel threads are initiated by the operating system
41
Multithreading
When an OS supports multiple threads within a single process
Single threading is where the OS does not recognise the separate concept of threads (e.g. MS-DOS)
One thread per process
Local variables are per thread, allocated on the stack (each thread has its own stack)
Global variables are shared between all threads, allocated in the data section. Need to take into account concurrent access
Dynamically allocated memory can be global or local (programmer chooses)
42
Benefits of multithreading
Creating, terminating and switching threads is quicker than doing the same thing but with processes
Responsiveness: May allow continued execution if part of process is blocked (if a tab crashes then the whole browser doesn't crash)
Resource sharing: Threads share resources of process, easier than shared memory or message passing
Thread switching has lower communication overhead than context switching
Processes can take advantage of multiple cores
43
Amdahl's law
Identifies performance gains from adding additional cores, to an application that has both serial and parallel components.
S = serial portion
N = processing cores
speedup <= 1/(S + (1-S)/N)
44
Long-term scheduler (job scheduler)
Selects which processes should be brought into the ready queue
45
Medium-term scheduler
In charge of handling the swapped out-processes
46
Short-term scheduler
Selects the processes to be executed next and allocated to the CPU
47
Dispatch latency
The time it takes for the dispatcher to stop one process and start another. The dispatcher saves the current process's state into PCB, and restores the next process's state.
48
Optimisation criteria for schedulers
Maximum CPU utilisation
Maximum throughput (number of processes that complete their execution per unit time)
Minimum turnaround (time taken to execute a particular process)
Minimum waiting time (total amount of time a process has been waiting in the ready queue)
Response time (amount of time it takes for a request to receive a response (access to the CPU))
49
First Come, First Served scheduling algorithm
The first process to request the CPU is allocated the CPU until it is completed. Simple algorithm, may result in a convoy effect where short processes have to wait for a long process to finish
50
Shortest Job First
Associate with each process the length of its next CPU burst, and use these lengths to schedule the process with the shortest time (FCFS if they have the same length)
Gives minimum average waiting time
51
Calculating waiting time and turnaround time
Waiting time: (start time - arrival time)
Turnaround time: (end time - arrival time)
52
Shortest Remaining Time First
If a new process arrives in the ready queue with a CPU burst length less than the remaining time of the executing process, then switch to the new process and then back to the old process when it's done
Pre-emptive version of SJF
53
Round Robin
Each process gets a small unit of CPU time: a time slice usually 10-100 milliseconds
After the time slice has elapsed, the process is pre-empted and added to the end of the ready queue
54
Round Robin performance
Performance depends on the size of the time slice
If the time slice is extremely large, the RR policy is the same as the FCFS policy
If the time slice is extremely small, a lot of time will be wasted on context switching
The rule of thumb is that 80% of CPU bursts should be shorter than the time quantum
55
Priority scheduling
An algorithm associates a priority number with each process, and CPU time is allocated to the process with the highest priority (smallest number)
56
What is starvation and when can it occur
When processes are given CPU time in order of priority, low priority processes may never execute (starvation). The solution is either aging (increasing priority as time goes on) or combining it with Round Robin: executing the highest-priority process without RR and the lower-priority ones with RR
57
Multilevel queue
The ready queue is partitioned into separate queues, each with its own scheduling algorithm. Scheduling must be undertaken between queues: e.g. serving all from the foreground then from the background, or allowing each queue a certain percentage of CPU time
58
Multilevel queue scheduling
Separate queue for each priority level
The problem with this is that it's not flexible as processes cannot change queue
59
Multilevel feedback queue
An adaption of multilevel queue scheduling where processes can move between various queues, allowing aging to be implemented. Multilevel feedback queue schedulers vary in the number of queues used, scheduling algorithms used for each queue, method used for promoting/demoting, and method for queue allocation
60
Multilevel feedback queue evaluation
Deterministic modelling: taking a predetermined case and analysing the performance of each algorithm in this case
Little's formula: n = LW
n = avg. long-term queue length
L = avg. arrival rate for new processes
W = avg. waiting time in queue
Simulation: using a complex model to determine average performance
Post-implementation: Examining the running operating system
61
How does Windows scheduling work
The dispatcher uses a queue for each scheduling priority, and traverses the set of queues looking for the highest priority thread to run. When no thread is found in any queue, the dispatcher will select the idle thread for execution.
When a thread's time slice runs out, it's interrupted and dispatched to the ready queue + priority lowered
When a thread is released from a wait operation it is dispatched to the ready queue and its priority is raised
62
Types of memory
Cache memory (invisible to operating system)
Main memory (RAM)
Storage memory
Virtual memory
63
Structure of a process's memory space
Base and limit registers define the logical address space. The CPU must check every memory access generated in user mode to be sure it's between (base) and (base+limit)
64
Logical vs physical address
Logical/virtual address: Generated by the CPU
Physical address: Address seen by the memory controller, never seen by programs
65
Memory Management Unit
Hardware device which maps virtual to physical addresses. A simple method would be adding the value in the relocation register to every address generated by a user process, to get the physical address.
66
How is main memory partitioned
Area for kernel processes and area for user processes
67
How does the MMU convert logical to physical addresses
1. Extract the page number p from the logical address
2. From the page table, extract the frame number f which is stored at index p
3. Replace the page number p in the logical address which the frame number f
68
Contiguous allocation
It's quicker to read memory contiguously without skipping. Memory allocation strategies must take into account holes (blocks of available memory) and how to allocate memory to newly-arrived processes.
69
First-fit algorithm for memory hole allocation
Allocate the first hole which is big enough
70
Best-fit algorithm for memory hole allocation
Allocate the smallest hole which is big enough
Produces the smallest leftover hole
Must search the entire list of holes
71
Worst-fit algorithm for memory hole allocation
Allocates the largest hole
Produces the largest leftover hole
Must search entire list of holes
72
External fragmentation
Memory space which is able to satisfy a request but is not contiguous
73
Internal fragmentation
Where memory is allocated successfully but is slightly larger than the requested amount of memory (e.g. request for 27 bytes of memory => allocated to 32-byte block leaving 5 bytes unused)
74
Fragmentation
With First Fit, if N blocks are allocated, 0.5N are lost to fragmentation, making 1/3 of memory unavailable. We reduce external fragmentation by compaction (shuffling memory contents so all free memory is together in one large block)
75
Frames and pages
Physical memory is divided into fixed-size blocks called frames (size is typically between 512 and 8192 bytes)
Logical memory is divided into blocks of the same size called pages
76
Paging
To run a program whose size is n pages, we need to find n free frames and load the program. A page table is set up to help manage the mapping of logical to physical addresses.
Logical addresses are divided into two parts:
page number (p): index into a page table (contains physical base address of all pages)
page offset (d): the difference between the base address and the current address
77
Implementing the page table
The page table is kept in memory, and a page-table base register points to it
With this method every data/instruction access requires two memory accesses, one for the page table and one for the data/instruction
78
Translation look-aside buffer (TLB)
When a logical address is generated by the CPU, the MMU first checks if its page number is present in the TLB. If it is, its frame number is immediately available. If not (TLB miss), the frame number must be obtained from the page table and the pair added to the TLB, overwriting a pre-existing entry if necessary.
79
Effective Access Time
a = Hit ratio (percentage of times a page number is found in the TLB)
m = memory access time
Effective Access Time = m(2-a)
80
Implementing memory protection with page tables
A valid-invalid bit is attached to each entry in the page table indicating whether or not the associated page is in the process's logical address space
81
What is virtual memory?
The OS lets programs address more memory locations than are actually provided in main memory
The logical address space is larger than the physical address space
Pages are swapped (paged) in and out of main memory
The physical address space is shared by several processes
Only part of the process needs to be in the physical address space for execution
A free frame list of the physical address space is maintained by the operating system.
82
Virtual Address Space
Logical view of how a process is stored in memory
Each process the address space as a contiguous block of memory
Consists of:
Code (read-only)
Data (read and write)
Heap: address space in memory that holds data produced during execution of a process (expands and contracts)
Stack: address space which holds instructions and data known at the time of the procedure call. The contents of the stack grow as the process issues nested procedure calls and shrinks as the called procedures return.
83
Demand paging
Bringing a page into memory only when it's required by the process during its execution
Reduces: number of pages to be transferred, number of frames allocated to a process
Increases: number of processes executing, overall response time for a collection of processes
84
How does demand paging work
When a reference is made to a page's address, if valid/invalid bit is zero then it's loaded into memory.
During address translation, when the valid/invalid bit in the page table entry is 0, this causes a page fault trap
85
How is memory address handled
A process requests access to an address within a page
OS checks the validity of the process's access to that address
If it's invalid, the process is terminated and its memory is cleared
If it's valid and the page has been allocated a frame in main memory, break
If it's valid and a page fault trap has occurred, the OS will:
- Identify a free frame from the list
- Read the page from the backing store into the identified frame
- Update the process's page table
- Restart the instruction interrupted by the page fault trap
86
Performance of demand paging
p = page fault rate (0 <= p <= 1)
E = effective access time
E = (1-p)*(memory access) + p*(page fault overhead + swap page out + swap page in)
Page fault overhead = Context switching when relinquishing CPU, time waiting in the paging device queue, time waiting in ready queue, context switching when regaining the ready queue
87
What happens when all main memory frames available to a process are already allocated?
Page replacement: Find a page in memory which isn't really in use, and swap it out
The page which is swapped is determined by an algorithm
88
Basic page replacement
Find the location of the desired page on the disk
If there is a free frame, use it
Otherwise, use a page-replacement algorithm to select a victim page
Write the victim's page to the disk, update the process's page table and the free frame list accordingly
Read the desired page into the newly-freed frame, update the process's page table and restart the user process
89
First in first out (FIFO) algorithm
Associate each page with the time it was brought into memory, and let the oldest page be the victim page.
Example:
Max frames in memory: 3, Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Page frames: [7], [7, 0], [7, 0, 1], [2, 0, 1], [2, 0, 1], [2, 3, 1], etc.
90
Belady's anomaly
"For some page fault algorithms, the page fault rate may increase as the number of allocated frames increases"
FIFO suffers from this problem
91
Optimal algorithm for page replacement
Replace the page which will not be needed for the longest period of time. This algorithm always results in the fewest page faults but is also impossible to implement as it requires seeing into the future
92
Least Recently Used algorithm for page replacement
Associate with each page the time it was last used
The victim page will be the one that has not been used for the longest period of time
LRU belongs to a class of page replacement algorithms known as stack algorithms.
These algorithms can never exhibit Belady's anomaly as a set of pages in memory for n frames is always a subset of the set of pages that would be in memory with n+1 frames.
93
How is the LRU algorithm implemented?
Counter implementation: every page entry has a counter, and every time that page is referenced the time is recorded
Stack implementation: Keep a stack of page numbers in a double link form. When a page is referenced, move it to the top. The tail pointer points to the bottom of the stack (LRU page)
94
Counting-based page replacement algorithms
Keep a counter of the number of references that have been made to each page
Least Frequently Used: Replaces page with smallest count
Most Frequently Used: Replaces page with the greatest count
95
What is thrashing?
Thrashing is when a process is spending more time paging than doing useful work, usually because it doesn't have enough pages. This leads to low CPU utilisation and the OS thinking that it needs to increase the degree of multiprogramming.
96
What is prepaging?
Paging all the necessary pages at once
Each process stores a list of pages within its working set model. If a process is suspended we remember the working set for that process. When it resumes we automatically bring back into memory its entire working set before restarting the process.
97
Ways of allocating frames
Global replacement: Selecting a replacement frame from the set of all frames (one process can take a frame from another)
Local replacement: Selecting from only the process's own set of allocated frames
Fixed allocation: Allocate according to size of process
Priority allocation: Select a victim frame from a process with a lower priority number
98
Page-Fault Frequency Scheme
An alternative approach to prevent thrashing. It establishes an acceptable page-fault rate, and then gives or takes frames from processes depending on their actual page fault rate.
99
Disk performance parameters
Seek time: The time it takes to move the head to the target track
Rotational delay/latency: The time taken for the target sector to move under the head
Access time = Seek time + latency
100
Disk scheduling
The OS maintains a queue of requests. An idle disk can work immediately on request, a busy disk means work must queue. Optimisation algorithms only make sense when a queue exists. Several algorithms exist to schedule the servicing of disk I/O requests. We illustrate scheduling algorithms with a request queue (e.g. 98, 183, 37, 122, 14, 124, 65, 67, head pointer 53)
101
FCFS disk scheduling algorithm
The requests in the queue are fulfilled from oldest to newest
102
SSTF disk scheduling algorithm
Shortest Seek Time First
This algorithm selects the request with the minimum seek time from the current head position. This algorithm may cause starvation of some requests.
103
SCAN/Elevator disk scheduling algorithm
The disk arm moves towards one end of the disk, servicing requests along the way, before "bouncing back" towards the other end and servicing more requests along the way.
104
C-SCAN disk scheduling algorithm
The head moves from the starting point to one end of the disk (while servicing requests) before hitting that end and jumping all the way back to the beginning. It then travels back towards where it started, servicing requests.
This treats the cylinders as a circular list.
105
(C-)LOOK disk scheduling algorithm
A variant of (C-)SCAN where the arm only goes as far as the last request in each direction before bouncing back.
106
Choosing a disk scheduling algorithm
SSTF is common
(C-)SCAN performs better for systems that place a heavy load on the disk
The disk-scheduling algorithm should be written as a separate module of the operating system, allowing it to be replaced with a different algorithm if necessary
Either SSTF or LOOK is a reasonable choice for the default algorithm
107
Storage array
A collection of disks
Ports connect hosts to array
Memory and controlling software
RAID, hot spares, hot swap
Shared storage => More efficiency
108
Storage Area Network
Common in large storage environments Multiple hosts attached to multiple storage arrays - flexible
109
Network-Attached Storage (NAS)
Network-attached storage (NAS) is storage made available over a network rather than over a local connection (such as a bus)
Implemented via remote procedure calls (RPCs) between host and storage over typically TCP or UDP on IP network
110
Redundant Array of Inexpensive Disk (RAID)
Multiple Disk drives provide reliability via redundancy
RAID schemes improve performance and improve the reliability of the storage system by storing redundant data
Mirroring or shadowing keeps duplicate of each disk
Block interleaved parity uses much less redundancy
111
What is deadlock?
A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause
112
System model for deadlock characterisation
System contains resources of types R_1, R_2, ..., R_m (e.g. CPU cycles, memory space, I/O devices)
Each resource type R_i has W_i instances
Each process utilises a resource as follows: request, use, release
113
Deadlock characterisation
Mutual exclusion: only one process at a time can use a resource
Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
No preemption: A resource can be released only voluntarily by the process holding it, after that process has completed its task
Circular wait: There exists a set {P0, P1, ..., Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, ..., and P_n is waiting for a resource held by P0
114
Resource allocation graph
A set of vertices V and a set of edges E
V is partitioned into two types: P = {P1, P2, ..., P_n} consisting of all processes, and R = {R1, R2, ..., R_m} consisting of all resource types in the system
Request edge = directed edge P_i => R_j
Assignment edge = directed edge R_j => P_i
115
How to determine if a deadlock can/will occur?
If the graph contains no cycles => no deadlock
If the graph contains a cycle and there's only one instance per resource type => deadlock
Otherwise => Possibility of deadlock
116
Dealing with deadlocks
1. Pretend there is no problem (reasonable if deadlocks are rare and cost of prevention is high)
2. Deadlock prevention (mutual exclusion, hold and wait: must guarantee that whenever a process requests a resource, it does not hold any other resources, no preemption, circular wait)
3. Deadlock avoidance (each process must declare maximum number of resources of each type that it may need)
117
Safe state
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
This is when there exists a sequence of all the processes such that for each P_i, the resources that P_i can still request can be satisfied by currently available resources + resources held by all P_j, j < i
118
RAG scheme
Claim edge P_i => R_j (dashed line) indicates P_j may request R_j. This changes to a request edge when a process requests a resource. Request edge converted to an assignment edge when the resource is allocated to the process. Turns back into a claim edge when the resource is released.
119
RAG algorithm
If P_i requests R_j, the request can only be granted if converting the request edge to an assignment edge does not form a cycle
120
Banker's algorithm
Let n = number of processes, m = number of resource types
Available: vector of length m, represents number of available resources of type R_j
Max: n x m matrix where the cell (i,j) represents the max number of resources of type R_j that could be accessed by P_i
Allocation: n x m matrix where the cell (i,j) represents the number of resources of type R_j currently allocated to P_i
Need: Max - Allocation
121
Banker's safety algorithm
1. Let Work and Finish be vectors of length m and n respectively
Work = Available
Finish[i] = false for i from 0 to n-1
2. Find an i such that both Finish [i] = false and Need_i <= Work
If none exists, go to step 4
3.
Work = Work + Allocation_i
Finish[i] = true
4. If Finish[i] == true for all i, then the system is in a safe state
P_i's request is valid if Request <= Available_i
122
Banker’s Resource-Request Algorithm
Request_i = request vector for process P_i. Request_i[j] means process P_i wants k instances of resource type R_j
1. If Request_i <= Need_i go to step 2, otherwise raise error condition
2. If Request_i <= Available, go to step 3, otherwise P_i must wait since resources are not available
3. Pretend to allocate resources to P_i by modifying the state as follows:
Available = Available - Request_i
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i
4. If this is safe, allocate the resources, otherwise P_i must wait (undo the changes from step 3)
