#os
All Messages
bakery
Images
File Control Block
TestAndSet using TSET
Approach taken by the kernel for handling deadlocks - deadlock detection, deadlock prevention and deadlock avoidance
Resource ranking algorithm for deadlock prevention
2) Wait-for-graph
2)
The "working set" is short hand for "parts of memory that the current algorithm is using" and is determined by which parts of memory the CPU just happens to access.
Locality of reference - <>
Example of temporal locality:
for(i = 0; i < 20; i++)
for(j = 0; j < 10; j++)
a[i] = a[i]*j;
For example, in the code given, a[i] is referenced frequently, with instructions like a[i] = a[i] * 2 and a[i] = a[i] * 3 being executed very close together. If we are looking at this scope, we could say that references to j and a[i] are temporally local. References to i are also temporally local, because i is referenced every time a[i] is.
References to a[i] are a good example of spatial locality, as one can assume (most of the time) that a[0] and a[1] will be next to each other in memory.
1)
• A more practical approach is to predict the length of the next burst, based on some historical measurement of recent burst times for this process. One simple, fast, and relatively accurate method is the exponential average, which can be defined as follows. ( The book uses tau and t for their variables, but those are hard to distinguish from one another and don't work well in HTML. )
> estimate[ i + 1 ] = alpha * burst[ i ] + ( 1.0 - alpha ) * estimate[ i ]
• In this scheme the previous estimate contains the history of all previous times, and alpha serves as a weighting factor for the relative importance of recent data versus past history. If alpha is 1.0, then past history is ignored, and we assume the next burst will be the same length as the last burst. If alpha is 0.0, then all measured burst times are ignored, and we just assume a constant burst time.
1.c)
System calls - The interface between a process and an operating system is provided by system calls. In general, system calls are available as assembly language instructions. They are also included in the manuals used by the assembly level programmers. System calls are usually made when a process in user mode requires access to a resource. Then it requests the kernel to provide the resource via a system calls.
The system program serves as a part of the operating system. It traditionally lies between the user interface and the system calls. The user view of the system is actually defined by system programs and not system calls because that is what they interact with and system programs are closer to the user interface.
1.b)
• Context Switching & Scheduling, which allocate a process CPU time to execute its instructions.
• Memory Management, which deals with allocating memory to processes.
• Interprocess Communication, which deals with facilities to allow concurrently running processes to communicate with each other.
• File Systems, which provide higher level files out of low level unstructured data on a disk.
1.a>
A trap is an exception in a user process. It's caused by division by zero or invalid memory access. It's also the usual way to invoke a kernel routine (a system call) because those run with a higher priority than user code. Handling is synchronous (so the user code is suspended and continues afterwards). In a sense they are "active" - most of the time, the code expects the trap to happen and relies on this fact.
An interrupt is something generated by the hardware (devices like the hard disk, graphics card, I/O ports, etc). These are asynchronous (i.e. they don't happen at predictable places in the user code) or "passive" since the interrupt handler has to wait for them to happen eventually.
You can also see a trap as a kind of CPU-internal interrupt since the handler for trap handler looks like an interrupt handler (registers and stack pointers are saved, there is a context switch, execution can resume in some cases where it left off).
Uses:
An interrupt can be used to signal the completion of an I/O to obviate the need for device polling. A trap can be used to call operating system routines or to catch arithmetic errors.
3.b.iv)
Busy waiting means that a process is waiting for a condition to be satisfied in a tight loop without relinquishing the processor. Alternatively, a process could wait by relinquishing the processor, and block on a condition and wait to be awakened at some appropriate time in the future. Busy waiting can be avoided but incurs the overhead associated with putting a process to sleep and having to wake it up when the appropriate program state is reached.
4.b.ii) FIFO and Belady's anomaly from here
4.b.i) Optimal page replacement algorithm
It cannot be implemented practically because because the pages that will not be used in future for the longest time can not be predicted.
4.a.iv)
[PART 1] Since segmentation is based on a logical division of memory rather than a physical one, segments of any size can be shared with only one entry in the segment tables of
each user. With paging there must be a common entry in the page tables for each page that is shared.
[PART 2] 16 bits
4.a.iii)
When the process issues an access to a page that is on disk, a page fault occurs. The operating system must retrieve the page from disk and bring it into memory.
At the time of a fault, the hardware generates a TLB (Translation Lookaside Buffer) exception, trapping to the operating system.
The operating system then checks its own page table to locate the virtual page requested. If that page is currently in memory but wasn't mapped by the TLB, then all we need to do is update the TLB. However, the page might be on disk. If this is the case, the operating system must:
1. Allocate a place in physical memory to store the page;
2. Read the page from disk,
3. Update the page table entry with the new virtual-to-physical address translation;
4. Update the TLB to contain the new translation; and
5. Resume execution of the user program.
4.a.i
In operating systems that implement a virtual memory space the programs allocate memory from an address space that may be much larger than the actual amount of RAM the system possesses. The OS is responsible for deciding which programs "memory" is in actual RAM. It needs a place to keep things while they are "out". This is what is called "swap space", as the OS is swapping things in and out as needed. When this swapping activity is occurring such that it is the major consumer of the CPU time, then you are effectively thrashing. Thrashing It is a state in which our CPU perform 'productive' work less and 'swapping' more. CPU is busy in swapping pages, so much that it can not respond to user program as much as required.
Eliminating thrasing - drop degree of multiprogramming, running fewer programs, writing programs that use memory more efficiently, adding RAM to the system, or maybe even by increasing the swap size.
4.b.iv)
The system can detect thrashing by evaluating the level of CPU utilization as compared to the level of multiprogramming
3a iii.
(if instead of while, use queue, wakeup and sleep)