Ceng 328 Operating Systems
Final
May 31, 2004 09.00-11.00

Part A. Each question is 5 points
1 Describe internal and external fragmentation and explain the difference between them. Which one occurs in paging systems? Which one occurs in systems using pure segmentation?






2 How does segmentation differ from paging?






3 What is starvation, give an example?






4 What is the memory management unit (MMU) and what does it do?






5 What is the difference between a physical address and a vitrual address? Assume we have a system that performs dynamic relocation of processes in physical memory. A process that has just started needs 2000 total bytes of memory in its address space. The OS currently has two free regions: the first between physical addresses of 1000 and 2000, and the second between physical addresses 5000 and 7000. What value would end up in the base register for this process, and what value would be in the bounds register? (write down any assumptions that you make about the bounds register)
Value of base:
Value of bounds:






6 Estimated total average acces time in disks is given as the following formula

$$T_a=T_s+{1 \over 2r}+{b \over rN}$$

i.Describe each term in the formula








ii. The following values are given; fill the table
$T_s=3$ ms,
$r=5000$rpm, At 5000 rpm, one revolution per 9ms$\Rightarrow$ average delay 4.5ms
768B sect, 480 sect/track,
Read a file with 3840 sectors (=2.88MB)

File stored compactly (adjacent tracks): Read first track

Average seek
Rot. Delay
Read 480 sectors
Total
All sectors

Sectors distributed randomly over the disk: Read any sector

Average seek
Rot. Delay
Read 1 sectors
Total
All

Part B. Each question is 10 points
7 Five batch jobs A through E, arrive at a computer center at almost the same time. They have;

Process	Burst Time	Priority
P1	10	3
P2	6	5
P3	2	2
P4	4	1
P5	8	4

5 being the highest priority. For each of the following scheduling algorithms, determine the mean process turaround time. Ignore process switching overhead.
(a) round robin; assume that the system is multiprogrammed, and that each job gets its fair share of the CPU
(b) priority scheduling; assume that only one job at a time runs, until it finishes.
(c) FCFS; assume that only one job at a time runs, until it finishes.
(d) SJF-nonpreemptive; assume that only one job at a time runs, until it finishes.

Process	RR	PS	FCFS	SJF
P1
P2
P3
P4
P5
Average

8 Explain the UNIX index node (inode) structure in detail.












9 One way to use contiguous allocation of the disk and not suffer from holes is to compact the disk every time a file is removed. Since all files are contiguous, copying a requires a seek and rotational delay to read the file, followed by the transfer at full speed. Writing a file back requires the same work. Assuming a seek time of 5 msec, a rotational delay of 4 msec, a transfer rate of 8 MB/sec, and an average file size of 8 KB, how long does it take to read a file into main memory then write it back to the disk at new location? Using these numbers, how long would it take to compact half of a 16-GB disk?
(Hints: $1 K \mapsto 2^{10}$; $8 K \mapsto 2^{3} 1 K$; $8 M \mapsto 2^{3} 1 K 1 K$; $8 G \mapsto 2^{3} 1 K 1 K 1 K$; Do not use calculator)







Part C. Each question is 20 points
10 Write a pseudocode (or C) for file copying. Don't forget the error checking and reporting but keep as minimal. The buffer size and output mode are 2048 bytes and 777, respectively.











11 The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write pseudo code to coordinate the barber and the customers.
Hints: Need a global counter for the number of customers that are currently waiting in a chair. Use 3 semaphores - one for the customers ( barber waits til a customer signals they are ready), one for the barber ( customer waits til barber signals he is ready ) and one for the critical section (where the global counter is modified).












Part D. Each bonus question is 10 points
12 Solve the followings;
i. A system has two processes and three identical resources. each process needs a maximum of two resources. Is deadlock possible? Explain your answer.




ii. Consider previous problem again, but now with p processes each needing a maximum of m resources and a total of r resources available. What condition must hold to make the system deadlock free?




13 In a system with pure paging, assume we have a 32-bit address space, and a 4 KB page size.
i. How many bits of an address specify the logical page number (a.k.a. the virtual page number), and how many bits specify the offset?




ii. Let's say we are translating the logical address 0x00010033; if each logical page is mapped to a physical page that is a single page number higher (i.e., logical page 10 is mapped to physical page 11, logical page 11 is mapped to physical page 12), what is the translated physical address?
(Hint for part ii.: $16^3=4096$)