1. Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections.
A semaphore is initialized to the number of allowable open socket connections. When a connection is accepted, the acquire ( ) method is called. When a connection is released, the release ( ) method is called. If the system reaches the number of allowable socket connections, subsequent calls to acquire ( ) will block until an existing connection is terminated and the release method is invoked.
2. What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.
A process is waiting for an event to occur and it does so by executing instructions.
A process is waiting for an event to occur in some waiting queue (e.g. I/O, semaphore) and it does so without having the CPU assigned to it.
Busy waiting cannot be avoided altogether.
3. Consider the traffic deadlock depicted in Figure 1.
a. Show that the four necessary conditions for deadlock indeed hold in this example.
b. State a simple rule for avoiding deadlocks in this system.
Figure 1 Traffic deadlock.
l Mutual exclusion: Only one car may be occupying a particular spot on the road at any instant.
l Hold and wait: No car ever backs up.
l No pre-emption: No car is permitted to push another car out of the way.
l Circular wait: Each corner of the city block contains vehicles whose movement depends on the vehicles blocking the next intersection.
4. Consider the following snapshot of a system:
Allocation
Max
Available
ABCD
ABCD
ABCD
P0
0012
0012
1520
P1
1000
1750
P2
1354
2356
P3
0632
0652
P4
0014
0656
Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need?
Process
A
B
C
D
P0
0
0
0
0
P1
0
7
5
0
P2
1
0
0
2
P3
0
0
2
0
P4
0
6
4
2
b. Is the system in a safe state?
System is in safe state because resources are available (1, 5, 2, 0).
c. If a request from process P1 arrives for (0, 4, 2, 0), can the request be granted immediately?
Request from process P1 can be granted immediately. Request is (0, 4, 2, 0) and available resource is (1, 5, 2, 0).
5. A single-lane bridge connects the two Vermont villages of North tunbridge and South tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if both a northbound and a southbound farmer get on the bridge at the same time (Vermont farmers are stubborn and are unable to back up.) Using semaphores, design an algorithm that prevents deadlock. Initially, do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge or vice versa).
6. Consider a paging system with the page table stored in memory.
(a) If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?
400 nanoseconds; 200 nanoseconds to access the page table and 200 nanoseconds to access the word in memory.
(b) If we add associative registers, and 75 percent of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)
Effective access time = 0.75X (200 nanoseconds) + 0.25 X (400 nanoseconds) = 250 nanoseconds.
7. (a) Compare paging with segmentation with respect to the amount of memory required by the address translation structures in order to convert virtual addresses to physical addresses.
Paging requires more memory overhead to maintain the translation structures. Segmentation requires just two registers per segment: one to maintain the base of the segment and the other to maintain the extent of the segment. Paging on the other hand requires one entry per page, and this entry provides the physical address in which the page is located.
(b) Why are segmentation and paging sometimes combined into one scheme?
Segmentation and paging are often combined in order to improve upon each other. Segmented paging is helpful when the page table becomes very large. A large contiguous section of the page table that is unused can be collapsed into a single segment table entry with a page-table address of zero. Paged segmentation handles the case of having very long segments that require a lot of time for allocation. By paging the segments, we reduce wasted memory due to external fragmentation as well as simplify the allocation
