DEADLOCKS

1.)
DEADLOCK- A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

STARVATION – One process is active, but never gets the resource.

RACE- A synchronization problem between two processes vying for the same resource.

2.)
*Real-life example of deadlock is Bridge traffic can only be in one direction.
*Real-life example of starvation is in the staircase, when two people meet at the opposing side.The staircase can be accomodated by one person.

*Real-life example of Race is when two people arrived at the same time on the same door.

3.)
*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, …, P0} 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, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.

4.)
*Algorithm for prevention of deadlock and starvation:
public boolean tryAcquire( int n0, int n1, ... ) { if ( for all i: ni ≤ availi ) { // successful acquisition availi -= ni for all i; return true; // indicate success } else return false; // indicate failure}init) Semaphore s = new Semaphore(1,1);Thread A Thread B-------- --------s.acquire(1,0); s.acquire(0,1);s.acquire(0,1); s.acquire(1,0);Thread B--------while(true) {s.acquire(0,1);if ( s.tryAcquire(1,0) ) // if second acquisition succeedsbreak; // leave the loopelse {s.release(0,1); // release what is heldsleep( SOME_AMOUNT); // pause a bit before trying again}}run action s.value--- ------ -------(1,1)A s.acquire(1,0) (0,1)B s.acquire(0,1) (0,0)A s.acquire(0,1) A blocks on secondB s.tryAcquire(1,0) => falseB s.release(0,1) (0,1)A s.acquire(0,1) (0,0) A succeeds on second.

5.)
A-Yes! When the bridge is destroyed.
B- When there are no traffic lights.
C- To prevent deadlock make all the road to be one-way.

6.)
A. NO!
B. There is no blocked processes.
C. P2 can freely request on R1 and R2.d. P1 can freely request on R1 and R2.e. Both P1 and P2 have requested R2.1. P1 will wait after the request of P2.2. P2 will wait after the request of P1.

IT222-"OS"

Compare and Contrast

The implementation of Virtual Memory, the problem of making programs fit into available memory was left to the user.In early days, programmers had to limit the size of their programs to make sure they fit into main memory, but sometimes that wasn’t possible because the amount of memory allocated to them was too small to get the job done. It was the size of the program that counted most and the instructions for these tight programs were nearly impossible for anyone, but their authors to understand or maintain the useful life of the program was limited to the employment of its programmer. Virtual Memory. 1970. This classic paper laid out a coherent scientific and engineering framework for the architecture and performance of virtual memory. It settled the controversies about the viability of virtual memory. It was widely used as a reading in operating systems courses well into the 1980s, when the material was finally integrated into operating systems textbooks.


PAGE FAULTS

The section of the operating system that resolves these problems. It determines whether there are empty page frames in memory so the requested page can be immediately copied from secondary storage. If all page frames are busy, the page fault handler must decide which page will be swapped out. Reasons for page fault
Hardware generates a page fault for page accesses where:
the page corresponding to the requested address is not loaded in memory.
the page corresponding to the memory address accessed is loaded, but its present status is not updated in hardware.
The closely related exception known as the protection fault is generated for page accesses where:
the page is not part of the program, and so is not mapped in program memory.
the program does not have sufficient privileges to read or write the page.
the page access is legal, but it is mapped with demand paging.
Protection fault can also be generated for many other invalid accesses not related to paging.
On the x86 architecture, accesses to pages that are not present and accesses to pages that do not conform to the permission attributes for a given page (protection faults as described above) are both reported via the page fault processor exception. Internally, the processor hardware provides information to the page fault handler that indicates what sort of access triggered the fault, so that these scenarios may be differentiated from the perspective of the operating system. The usage of the term protection fault (when speaking in relation to page faults) is thus not to be confused with the general protection fault exception, which is used to signal segmentation-based memory access violations, as well as a variety of other general protection related violations (such as the use of an instruction that is not valid at the current privilege level).
Page Mapped
Page Loaded
Page Status
Page access valid
Exception
yes
yes
present
yes
No exception
yes
--
not present
yes
Page fault
no
--
--
--
Protection fault
--
--
--
no
Protection fault
[edit] Minor page fault
If the page is loaded in memory at the time the fault is generated, but its status is not updated as 'present' in hardware, then it is called a minor or soft page fault. This could happen if the memory is shared by different programs and the page is already brought into memory for other programs. Since these faults do not involve disk latency, they are faster and less expensive than major page faults.
[edit] Major page fault
If the page is not loaded in memory at the time the fault is generated, then it is called a major or hard page fault. Major faults are more expensive than minor page faults and add disk latency to the interrupted program's execution. This is the mechanism used by an operating system to increase the amount of program memory available on demand. The operating system delays loading parts of the program from disk until the program attempts to use it and the page fault is generated.
[edit] Invalid page fault
If a page fault occurs that attempts to read the memory referenced by a null pointer, the system may alternatively generate an invalid page fault. The operating system maps a dummy page for catching null pointers.
[edit] Protection fault
When a program attempts invalid page accesses, for example trying to access pages not mapped into its memory, tries to write to read-only pages, or tries to modify privileged pages, the system hardware will generate a protection fault. Not all protection faults are illegal accesses, and they are the mechanism used by an operating system to implement copy on write access to share the same copy of memory among many programs until one of the programs wants to modify its copy.
A program trying to access memory that belongs to another process is attempting 'illegal access' which generates a protection fault. The operating system handles this protection fault much like an invalid page fault: The operating system temporarily blocks 'write permission' until a page fault is generated, then creates new access information to allow the program to successfully find this memory.
Note that in terms of the x86 architecture, memory protection violations reported via the page fault mechanism (protection faults, as described in this article) are distinct from memory protection violations reported via the general protection fault mechanism. The general protection fault mechanism is used to report segmentation-based memory access violations as well as other classes of protection violations. The page fault mechanism is used to report paging-based memory protection violations.
[edit] Handling illegal accesses and invalid page faults
Illegal accesses and invalid page faults can result in a program crash, segmentation error, bus error or core dump depending on the semantics of the operating system environment. Frequently these problems are the manifestation of software bugs, but the hardware memory errors frequently caused by overclocking may corrupt pointers causing even correct software to fail.
Operating systems such as Windows and UNIX (and other UNIX-like systems) provide differing mechanisms for reporting errors caused by page faults. Windows uses structured exception handling to report page fault-based invalid accesses as access violation exceptions, and UNIX (and UNIX-like) systems typically use signals, such as SIGSEGV, to report these error conditions to programs.
If the program that received the error does not handle it, then the operating system typically performs some sort of default action, typically involving the termination of the running process that caused the error condition, and a notification to the user that the program has malfunctioned. In this vein, recent versions of Windows often report such problems with less technical error messages simply stating something along the lines of this program must close" (an experienced user or programmer with access to a debugger can still retrieve detailed information, if necessary). Additionally, recent Windows versions also write a minidump (similar in principle to a core dump) describing the state of the crashed process for later analysis alongside such less-technical error messages. UNIX and UNIX-like operating systems typically report these conditions to the user with error messages such as "segmentation violation", or "bus error".
[edit] Performance
Page faults, by their very nature, degrade the performance of a program or operating system and in the degenerate case can cause thrashing. Optimizations to programs and the operating system that reduce the number of page faults that occur improve the performance of the program or even the entire system. The two primary focuses of the optimization effort focus on reducing overall memory usage and improving memory locality. Generally, making more physical memory available also reduces page faults. Many page replacement algorithms have been proposed, implementing a heuristic to reduce the incidence of page faults.


WORKING SETS

One innovation that improved the performance of demand paging schemes was the concept of the working set. A job that set of pages residing in memory that can be accessed directly with out incurring a page fault. Working Sets Past and Present. 1980. This paper gave a complete historical summary of the extensive research stimulated by the working set model over the previous decade, in which over 200 researchers participated. By this time the theory had been strongly validated by many experiments and was an accepted basis for the architecture of virtual memory systems. Among the new conclusions articulated here are: none of the plethora of simple stochastic models of locality fit data; locality has a phase transition structure that can be modeled with a semi-Markov model; working set memory management is near optimal among all policies without perfect lookahead.


PAGE SETS

The page size implicitly sets the size of an overflow record. Overflow records are key or data items that are too large to fit on a normal database page because of their size, and are therefore stored in overflow pages. Overflow pages are pages that exist outside of the normal database structure. For this reason, there is often a significant performance penalty associated with retrieving or modifying overflow records. Selecting a page size that is too small, and which forces the creation of large numbers of overflow pages, can seriously impact the performance of an application. the page size implicitly sets the size of an overflow record. Overflow records are key or data items that are too large to fit on a normal database page because of their size, and are therefore stored in overflow pages. Overflow pages are pages that exist outside of the normal database structure. For this reason, there is often a significant performance penalty associated with. retrieving or modifying overflow records. Selecting a page size that is too small, and which forces the creation of large numbers of overflow pages, can seriously impact the performance of an application.
The size of the pages used in the underlying database can be specified by calling the DB->set_pagesize method. The minimum page size is 512 bytes and the maximum page size is 64K bytes, and must be a power of two. If no page size is specified by the application, a page size is selected based on the underlying file system I/O block size. (A page size selected in this way has a lower limit of 512 bytes and an upper limit of 16K bytes.)