Question: Use semaphores to synchronize the threads of customer, cook, waiter and cleaner. In your answer, specify the semaphores used in each synchronization requirement above.

Question 1: Answer the following short questions:

(a) Name two differences between logical and physical addresses.

(b) Briefly explain how the CPU uses page table in address translation.

(c) Explain why the principle of locality is crucial to the use of virtual memory.

Question 2: In a fast food restaurant there are 30 tables, each with a single seat. Three cooks prepare meal (set lunch) and append it to a queue of capacity 10. One waiter takes a meal from the queue and delivers it to a customer who has ordered a meal. One cleaner cleans the table after a customer leaves.

a) Initially there are 50 customers, but only 30 tables available. A customer must wait until a previous customer finishes the meal and his table cleaned.

b) A cook will not start preparing a meal if there is no space left in the queue.

c) When a customer orders a meal, the waiter will go to the queue, take one meal from the queue, and deliver it to the customer. The customer can then start eating.

d) When there are no orders from customers, or when the queue is empty, the waiter has to wait.

e) After a customer finishes the meal and leaves the table, the cleaner will clean the table.

Use semaphores to synchronize the threads of customer, cook, waiter and cleaner. In your answer, specify the semaphores used in each synchronization requirement above.

void customer ( ) { int myTable;

enter restaurant;

find an available table, and store the table number in myTable; sit down on table number myTable;

order meal and pay; enjoy meal;

leave restaurant;

}

void cook ( ) { while (true) {

make a meal; append to queue;
}
}

void waiter ( ) { int orderTable;
while (true) {

take a meal from the queue;

determine the table number to deliver the meal, and store it in orderTable; deliver a meal to table number orderTable;
}
}

void cleaner ( ) { while (true) {

go to the table where a customer has just finished; clean the table;
}
}

void main ( ) { parbegin waiter(); cleaner();
cook(); cook(); cook();
customer(); customer(); ... customer(); // 50 customers
parend
}

Question 3: Assume a demand paged memory management system with the following characteristics:

page size = 4K = 212 bytes physical address space = 224 bytes logical address space = 232 bytes TLB size = 26 bytes

a) How many bits are needed to specify a logical address? Give the number of bits for the page number and offset.

b) How many page table entries can fit in the TLB if each entry only contains the information need for logical to physical translation. Show your work.

c) How many page table entries are needed when a program uses its full logical address space? What is the size (in MB) of page table, assuming each PTE contains 4 control bits.

d) Part c) indicates a serious problem that arises from having a very large logical address space. What is this problem and how could an OS solve it?

Question 4: Consider a simple segmentation system that has the following segment table:

For each of the following logical addresses ([segment number, offset]), determine the physical address or indicate if a segment fault occurs:
a) [0, 198]

b) [2, 156]

c) [1, 530]

Question 5: In a 64-bit machine, suppose we divide the logical address into multilevel paging as follows:

In other words, the system has a 3-level page table, such that the first 18-bits are for the first level, the next 15-bits are for the second level, etc. In this system, 15-bits are used to represent the frame number. Assume that the memory is accessed in bytes.

a) What is the page size in this system?

b) What is the maximum number of pages that can exist for a process?

c) What is the maximum size of the logical address?

d) What is the maximum size of physical memory?