Operating Systems: Deadlock, Memory Management, and Virtual Memory
Deadlock
18-Spin-lock:
General (counting) semaphore using busy waiting instead of blocking. Used in multiproc OS to implement short critical sections.
19-Deadlock:
Two or more procs are waiting indefinitely for an event that can be caused by only one of the waiting procs.
20-Starvation:
Indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.
21-Monitors:
A high-level abstraction that provides a convenient and effective mechanism for process synchronization. Only one proc may be active within the monitor at a time.
Deadlock Problem
A set of blocked procs, each holding a resource and waiting to acquire a resource held by another proc. Sched can prevent deadlock if it has info about all procs demands. Deadlock can occur if all 4 conditions simultaneously:
- Mutual exclusion: only one proc at a time can use a resource.
- Hold and wait: a proc holding at least one resource is waiting to acquire additional resources held by other procs.
- No preemption: a resource can be released only voluntarily by the pros holding it (after it completes the task).
- Circular wait.
Safe State
When a proc requests an available resource, the system must decide if immediate allocation leaves the system in a safe state. The system is in a safe state if there is a safe sequence of all procs.
Bankers Algorithm
Always keep so many resources that satisfy the needs of at least one client. Multiple instances. Each proc must a priori claim maximum use, must return resources in a finite amount of time. When a proc requests a resource, it may have to wait.
Recovery from Deadlock
PROC Termination:
Abort all deadlocked processes (Very expensive). Abort one process at a time in this order: process priority, time process has computed and time till complete, used/needed resources, needed resources…
Resource Preemption:
Selecting a victim – minimize cost.
Rollback
– return to some safe state, restart proc for that state.
Starvation
– same process may always be picked as victim, include number of rollback in cost factor.
Memory Management
1-Physical address space –
address in internal computer memory, also called real memory
2-Logical addr space –
generated by CPU, also referred as virtual address space. It is stored in memory, on hard disk or doesn’t exist if it was not used.
3-Uses of memory:
Running program has to be placed into memory. Program is transformed to structure that can be implemented by CPU by different steps. Internal memory stores data and programs that are running or waiting. Memory management is part of OS
4-Overlays:
First solution, how to use more memory than the physical address space allows. Special instruction to switch part of the memory to access by address bus. Defined by user and implemented by compiler. Minimal support from OS.
5-Simple segments:
Address is composed with 16 bits address of segment and 16 bits address of offset inside of the segment. It is not real virtual memory, only system how to use bigger memory.
6-Segmentation:
Support for user definition of logical address space. Program is set of segments. Has smaller internal frag than Paging. Pros: Possible to move data in memory and user cannot detect this shift. It is possible to set access for segment – It is possible to detect access outside of the segment. It throws new type of error – segmentation fault Cons: How to place segments into main memory. Segments have different length. Overhead to compute physical address from virtual address (one comparison, one addition).
7-Paging:
Different solution for virtual memory implement. Paging removes the basic problem of segments – different size. All pages have the same size that is defined by CPU architecture. Fragmentation is only inside of the page (small overhead). Each page has its own position in physical memory. Divide physical memory into fixed-sized blocks called frames. Dived logical memory into blocks with the same size as frames. These blocks are called pages. OS keep track of all frames. To run process of size n pages need to find n free frames.
8-Implem of page table:
Paging is implemented in hardware. Page table is kept in main memory. Pagetable base register (PTBR) points to the page table Pagetable length register (PTLR) indicates size of the page.
9-Hash tables:
Common in address spaces > 32 bits. The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.
10-Inverted page tables:
One entry for each real page of memory. Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page. Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs. Use hash table to limit the search to one or few pagetable entries.