7ELmc0CJ

13              1-40
25              1-29
36              1-36
48              1-50
59              1-58
618             1-20
719             11-18 + notes on Rate Monotonic Algorithm + notes on Priority Inversion/inheritance/ceiling
8
9Chapter 3
10
11What is a process?
12Definition: A process is a program in execution, a program becomes a process when it is loaded into memory.
13(So one program can be several processes)
14
15Breaking a process down:
16
17The program code - text section
18Current activity - program counter and registers
19Stack - temporary data (function parameters, return addresses, local variables)
20Data section - global variables
21Heap - memory dynamically allocated during runtime
22
23STACK
24---------
25---------
26 HEAP
27 DATA
28 TEXT
29
30So stack, temporary data grows down and the heap grows up as required.
31
32A process can be in various states:
33new - process is being created
34running - instructions are being executed
35waiting - process is waiting for some event to occur (I/O or another process f.e)
36ready - process is waiting to be granted CPU time
37terminated - process completed
38
39NEW -- admitted --> READY -- scheduler dispatch --> RUNNING -- exit --> TERMINATED
40 			   	^					      |
41				 ----------- interrupt ----------------
42				^					      |
43			          event done - WAITING - event waiting
44
45Process control block: Information associated with each process
46Process state, program counter, cpu registers, cpu scheduling information, memory-management information,
47accounting information, I/O status information.
48
49Switching from process to process: A process is interrupted or is WAITING, the process is saved to a PCB, another process is loaded from a PCB and executes.
50This is called context switching. The 'context' a process is represented in the PCB. During context switching the system does no useful work and the more complex the OS and PCB the longer the context switch.
51
52Process scheduling: Need to maximise CPU usage, quickly switching processes onto the CPU for time sharing. A process scheduler selects which process should be given CPU time next. 
53A process scheduler must maintain various queues:
54Job queue - set of all processes in a system
55Ready queue - set of all processes in main memory waiting to execute
56Device queue - set of processes waiting for an I/O device
57
58The long term scheduler determines which processes should be brought into the ready queue. (invoked infrequently, can be slow)
59A short term scheduler determines which processes in the ready queue should be executed next. (invoked frequently, needs to be fast) (Sometimes the only scheduler in a system)
60
61A process can either be CPU-bound: spends more time doing computations, few very long CPU bursts
62Or I/O bound: spends more time doing I/O, many short CPU bursts
63
64Processes create child processes, which may in turn create children of their own; creating a tree of processes. The processes are managed by a process identifier (pid).
65Child processes can share from all to none of the parents resources depending on the OS or process. Children and parents may or may not execute concurrently.
66A child is a duplicate of the parent.
67
68Process termination: A process may execute its final statement and then ask the OS to delete it. (exit) Process resources are now deallocated by OS.
69A parent may terminate a child process and whether a child can continue to run after a parent is terminated is OS dependent.
70
71Processes may need to share information, this is called interprocess communication (IPC). IPC can be done with shared memory or with message passing.
72With message passing the process communicates with the kernel which passes the message to the correct process.
73With shared memory the receiver reads from the shared memory of the sender in order to get a message.
74IPC can be used for information sharing, computation speed up, modularity or convenience.
75
76Producer-consumer problem
77A producer produces information that that is consumed by a consumer. One solution is to use a bounded buffer of memory for the processes to share. Problem is that a producer can only produce the number of items it can fit in its bounded buffer. 
78
79Message passing: processes need to establish a link between them (shared memory, hardware etc).
80Links can be implemented in many different ways for different utility. 
81Direct communication establishes a link between exactly one pair of processes and is usually bidirectional.
82Indirect communication is made using mailboxes, process can communicate if they share a mailbox. Problem is in determining who a message is meant for.
83Message passing can either be made block or non-blocking.
84
85Chapter 5: CPU Scheduling
86
87Process consists of CPU cycles and I/O waits.
88Scheduler selects from processes in the ready queue and allocates the CPU to one of them.
89Non-preemptive scheduling includes when a process changes to ready or a stops running.
90Preemptive processing considers access to shared data, kernel mode switching and crucial OS activities.
91
92The dispatcher is responsible for switching processes, switching to user mode and jumping to the correct location in a user program.
93Dispatch latency is the time it takes to stop one process and start another.
94
95Scheduling wants to keep the CPU as busy as possible, to maximise the number of processes that complete per unit time (throughput), to minimise the time it takes to execute a process, minimise the amount of time processes spend waiting and minimise the time between a request is submitted and a response is produced.
96
97First-come first-served (FCFS) has long waiting times if a long process is first.
98
99Shortest-job-first (SJF) associates each process with the length of its next CPU burst and uses these times to schedule the shortest first. SJF is the optimal scheduler, but the difficulty is knowing how long a CPU burst is going to be. The length of the next CPU burst can only be estimated. The length of the previous CPU bursts can be used to estimate the length of the next one. 
100An example of an estimation algorithm is: the length of the previous burst * t + estimate for previous burst * (1 - t)
101We  can ignore the recent burst history by setting t to 0 and we can use only the last burst by setting t to 1.
102As t is set to be less than or equal to 1, each successive burst has less weighting on the estimate that its predecessor.
103
104Shortest-time-remaining-first schedules processes with the smallest amount of CPU time required first.
105
106Priority scheduling associates each process with an integer, the smaller the integer the higher the priority.
107(SJF is priority scheduling where the priority is the inverse of the predicted CPU burst length)
108One problem is starvation, need to ensure that low priority jobs do execute eventually.
109A solution to this problem is ageing, the priority of a job is increased as time goes on.
110
111Round robin (RR) scheduling gives each process a small amount of CPU time, after which the process is added to the end of the ready queue. If processes are allowed a long time each on the processor then this is the same as FIFO, if they are interrupted often then there will be a lot of switching and the overhead will be too high. Time between each interrupt should be large compared to context switch time. For optimal RR 80% of the CPU bursts should be shorter than the interrupt time.
112
113Multi-level queues can be implemented. A process is permanently in a given queue, each queue has its own algorithm and CPU time is split between each queue. Queues may be split based on priority, with high priority queues being given more CPU time.
114If a process can move between queues, then an algorithm needs to determine how that takes place. A process may move between queues if it is preempted before it competes its CPU burst.
115
116Chapter 6: Process Synchronisation
117
118Need mechanisms to ensure data consistency when using shared memory.
119
120Each process has a critical section of code, a process may change data in a block of shared memory within its critical section. Only one process can be in its critical section at one time. Each process must ask for permission  to enter a critical section. This can be difficult with preemptive kernels.
121
122A solution to the critical section problem must address the following things:
123Mutual exclusion - Only one process can be accessing its critical section at one time
124Progress - If no processes are currently within their critical section and there exists processes that wish to enter their critical section, then the selection of the next process to access their critical section cannot be postponed indefinitely.
125Bounded waiting - A bound must exist on the number of times that other processes are allowed to enter their critical section after a process has made a request to enter its critical section and before that request is granted.
126
127Peterson's solution is for two processes. They share an int and a boolean[2] which determine whose turn it is to enter the critical section and which process is ready. This assumes that LOAD and STORE  instructions are atomic.
128
129interested[i] = true; // i wants to enter its critical section
130turn = j; // set that it is js turn current
131while(interested[j] && turn == j) { } // busy wait whilst j is within critical section
132- critical section -
133interested[i] = false; // i is done with critical section
134
135Some hardware provides support for critical section code, uniprocessors may disable interrupts whilst code is running within its critical section. This is too inefficient on multiprocessor systems.
136Modern machines provide atomic instructions for testing, setting and swapping some memory.
137
138TestAndSet sets a boolean to true and returns the previous value of the boolean. Busy waiting loop involves waiting until lock is false, lock is only true if it is in use.
139Swap solution very similar, each process has a key, repeatedly swap key and lock. If the lock is false it is not in use, swapped to true and critical section is entered.
140
141Semaphore: wait() decrements value of semaphore and does not continue until S was above 0 and it was decremented.
142signal() increments the value of the semaphore.
143Need to guarantee that wait and signal cannot be executed on the same process at the same time.
144In wait if S <= 0 in wait, add process to waiting queue.
145If there are processes waiting in signal then wakeup that process.
146
147Deadlock is the problem where two or more processes are waiting indefinitely for the other process.
148Starvation is the problem where a process is never removed from waiting.
149Priority inversion is the problem where a low-priority process holds the lock for a high priority process.
150
151The bounded-buffer problem (producer-consumer problem) describes the problem where a producer tries to write to a full buffer and a consumer tries to read from an empty buffer. A solution is to get the process to sleep until the other process informs them they can continue.
152
153The readers-writers problem describes the problem where a reader and a writer want to use the same shared memory at once. Two of the solutions leads to starvation but some systems solve the problem by providing reader-writer locks in the kernel.
154
155Dining-philosopher problem describes the problem where processes are waiting for other processes to complete, how do we guarantee that each process has its turn and avoid deadlock and starvation?
156
157Chapter 8: Main Memory
158
159A program must be brought from the disk into memory for the process to run, as the memory and registers are the only storage the CPU can access directly.
160Registers can be accessed very fast whereas memory is slower.
161Cache sits between main memory and CPU registers.
162
163A process is given a base and limit number, this defines the start address and the size of the memory block it has been allocated.
164Compiled code addresses bind to the allocated addresses, i.e "14 bytes from the start of this module". 
165
166If memory address is decided at compile time then it must recompile until the addresses are usable.
167If they are decided at load time we must generated relocatable code.
168If they are decided at run time then we must be able to move the process during execution, but needs hardware support for address maps.
169
170A logical address is an address seen by the CPU, a 'virtual address'.
171A physical address is an address seen by the memory unit.
172Logical and physical address spaces are only different if an execution address-binding scheme is used.
173
174Memory-Management Unit (MMU) is a hardware device that maps virtual to physical addresses.
175User program only ever sees logical addresses, it never sees physical addresses.
176
177Dynamic loading: Not loading a routine until it is called, ensures that an unused routine is never loaded. All routines are stored on disk in a relocatable format.
178Dynamic linking: Linking libraries at execution time, small piece of code used to locate the library routine. Particularly useful for libraries.
179
180Swapping: A process can be swapped temporarily out of memory into a backing store, and then brought back into memory for execution. Total process memory space can exceed physical memory space.
181A backing store is a fast disk large enough to accommodate copies of memory space for all users and must provide direct access to those memory spaces.
182Major part of memory swapping is transfer time.
183System maintains a ready queue of processes which are ready and have memory images on disk.
184If the next process to be put on the CPU is not in memory one needs to be swapped out and the process swapped in. This time can be very high.
185Can reduce the time taken can be reduced by only swapping the memory that is really used.
186
187Memory is split into low OS memory and high level user memory, each process is in a single continuous portion of memory. When a process arrives it is allocated a free hole in memory. 
188Operating system maintains information about free holes and allocated partitions.
189
190Different ways to choose which hole to use. First-fit: Allocate first available hole. Best-fit: Allocate smallest hole big enough. Worst-fit: Allocate the largest hole. First and best better in terms of speed and storage.
191
192Alternative to contiguous memory is fragmentation.  Fragmentation means that some space is lost. Fragmentation can be reduced by compaction, shuffling contents to place them together. Compaction is only possible if relocation is dynamic and done at execution time.
193
194Paging
195Logical address space of a process can be noncontiguous, process is allocated physical memory whenever it is available. 
196Physical memory is divided into fixed-sized blocks called frames.
197Logical memory is divided into same-sized blocks called pages.
198Setup a page table to translate logical addresses to physical addresses.
199Can still have internal fragmentation.
200Page table maps pages to physical addresses. Key is page, value is physical address.
201
202Page tables ---------- --  Implementations -- - --  --- -  -- - -- - 
203
204Chapter 9: Virtual Memory
205
206Program needs to be in memory to run but entire program is rarely needed. i.e Error codes, unusual routines, large data structures.
207Virtual memory: Separates virtual memory from physical memory. Only part of program needs to be loaded in memory, therefore logical space can be much larger than physical space.
208Demand paging: Bringing pages into memory only when they are needed. Less memory needed, faster response, more users.
209Never swap a page in unless it will be needed.
210Each page in memory is given an invalid/valid bit, valid being that the page is in memory. If page not in memory is needed that is called a page fault.
211Every page causes a page fault the first time it is accessed and a given instruction could access multiple pages causing multiple faults.
212Hardware support is needed for demand paging: page table with valid/invalid bit, secondary memory is needed for swap space and instruction restart is required.
213
214Page fault stages:
215Trap to the operating system
216Save the users processes and register state
217Determine that the interrupt was a page fault
218Check that the page is legal, that it is in the backing store and determine the location on the disk
219Issue a read from disk: Wait for device to be ready, wait for latency time, begin transfer
220Allocate the CPU to something else during this time
221Receive an interrupt from the disk when it is complete
222Save the registers and process state again
223Determine that the interrupt was from the disk
224Correct the page table to show that the page is now in memory and valid
225Wait for the CPU to be allocated this process again
226Restore the registers and process state and then resume interrupted instruction.
227
228If one page fault in 1000 is a page fault then that is a slowdown of factor 40
229
230Copy-On-Write (COW) allows child and parent to initially share the same pages in memory. If either process modifies the page then one only is copied.
231Page replacement problem: Need an algorithm to pick a page to swap out that minimises the number of page faults.
232Use a modify bit in pages to reduce overhead, only modified pages are written to disk.
233
234Page replacement:
235Find location of page on disk
236Find a free frame - If there isn't one use page replacement algorithm to select victim frame; write victim frame to disk if modified (dirty)
237Bring the desired page into free frame and update the page and frame tables
238Continue instruction
239
240Frame-allocation algorithm decides how many frames to give each process and which frames to replace.
241Page-replacement algorithm tries to reduce number of page faults.
242
243Beladys anomaly displays that increasing the number of page frames used in FIFO can increase the number of page faults.
244
245Optimal algorithm replaces page that will not be used for longest time, but this is impossible in practice as we cannot see the future.
246
247Least recently used algorithm replaces the page that hasn't been used in the longest time.
248LRU: Every page is given a counter or a stack is implemented.
249In stack implementation page referenced is moved to the top. LRU and OPT do not have Beladys Anomaly, increasing number of page frames decreases page faults.
250Second-chance algorithm only replaces a page after it has been chosen twice.
251Counting algorithms count how many times a page has been referenced and replaces the page referenced the least.
252
253Each process needs a minimum number of frames. 
254Equal allocation gives each process equal split of the frames and keep some free frames as a buffer pool.
255Proportional allocation gives more frames to larger processes.
256Priority allocation gives more frames to higher priority processes.
257Global replacement replaces pages from set of all frames. This causes varying execution time but greater throughput so more common.
258Local replacement replaces pages with its own pages which causes more per-process performance but can cause under-utilised memory.
259
260So far all memory is accessed equally but many systems use non uniform memory access. Optimal performance comes from allocating memory 'close to' CPU.
261If a process does not have enough pages, the page fault rate is very high. Thrashing is when a process is busy swapping pages in and out.
262
263Demand Paging, Thrashing, Working-Set Model
264
265Chapter 18: Distributed Coordination
266
267Happened-before: A -> B
268If A was executed before B A -> B, if A is sending a message and B is receiving it then A -> B and if A ->B and B -> C then A -> C.
269Implementing A -> B
270Associate timestamp with each event and ensure that for each pair for events the timestamp of A is less than the timestamp of B.
271Within each process a logical clock is associated. 
272The timer is increased with every event that occurs within a process.
273The process advances its logical clock when it receives a message with a timestamp greater than the current value of the clock.
274If the timestamps are the same then the two events are concurrent, we can use the process identity numbers to create a total ordering.
275
276Distributed Mutual Exclusion (DME). Each process is on a different processor, each process has a critical section. Only one process can be executing its critical section at once.
277
278Centralised Approach
279One process in the system is used to coordinate the entry to the critical section.
280A process that wants to enter its critical section must send a request to the message coordinator. The coordinator decides which process can enter its critical section.
281When a process receives a reply message it enters its critical section. After exiting the section it sends a message to the coordinate process to release the lock.
282This requires 3 messages per entry: request, reply, release.
283
284Fully Distributed Approach
285When a process wants to enter its critical section it generates a new timestamp and sends the request to all other processes in the system.
286When a process receives a request it may reply immediately or defer sending a reply back.
287When a process receives a reply from all other processes in the system it can enter its critical section.
288After exiting its critical section it sends a reply message back to all the processes it deferred replying to.
289If a process receives a request to enter a critical section then if the request has a timestamp before he current timestamp of the process it replies immediately, else it performs its critical section if it is waiting.
290Desirable Behaviour: System is free from deadlock. Freedom from starvation is ensured since critical sections are served by their time stamp. But the number of messages per critical request is 2 (n-1).
291Where n is the number of processes in the system.
292However, the processes need to know about all the other processes within the system and if one process fails the entire system collapses and processes who wish to enter their critical section must pause frequently to assure other processes that they intend to enter their critical section. Therefore this system is suitable for small, stable sets of cooperating processes.
293
294Token-Passing Approach
295Token is a special kind of message that entitles holder to critical section access. Processes logically organised into a ring structure. Unidirectional ring guarantee freedom from starvation.
296Failures can occur: token is lost or process fails.
297
298Atomicity
299Either all operations associated with a program are executed or none of them are.
300Ensuring atomicity in a distributed system requires a transaction coordinator which start the execution of the transaction, break the transaction into a number of sub transactions, distribute these transactions to the appropriate sites for execution and coordination the termination of the transaction.
301
3022 phase commit
303
304Chapter 19
305
306Real time systems must provide pre-emptive priority based scheduling, preemptive kernels and low latency.
307
308Event latency is the time between an event occurring and the event being serviced.
309
310Interrupt latency is the time taken between an interrupt arriving at the CPU and the interrupt being serviced. (Interrupt arrives -> determine interrupt type -> context switch)
311
312Dispatch is the amount of time required for a scheduler to stop one process and start another.
313
314Rate monotonic scheduling:  shorter periods have higher priority