Winter 2007 Midterm Solutions

About This Midterm

Problem 1

There were many different ways of doing this problem. The most common solution looked something like this:


//shared variables and semaphores with initial values:
semaphore T1_sema(0); //init'd to zero
semaphore T2_sema(0); //init'd to zero
semaphore done_sema(0); //init'd to zero



    
void ComputeZ(){




StartThread(T1);



StartThread(T2);



sema_down(done_sema);

return;



}
void T1(){


y = F3(y);

sema_up(T2_sema);


x=F1(x);

sema_down(T1_sema);


z = F3(x,y);

sema_up(done_sema);


}
void T2(){


sema_down(T2_sema);

y = F2(y);

sema_up(T1_sema);








}
Syntax didn't matter in this question as long as it was clear. 2 points were deducted for every race condition. The most common mistake was not waiting for z to be computed before ComputeZ() returns (some people fixed this retroactively for Problem 2(a), which was ok).

Problem 2

(Based on the solution to Problem 1 above)

(a)

Yes, there is no problem running ComputeZ() twice sequentially. All semaphore values end up as zero at the end of ComputeZ(), and when ComputeZ() returns, z is guaranteed to be correct.

(b)

There are multiple problems with this scenario. Many people pointed out data inconsistency issues that occur inside T1() or T2() if ComputeZ() is called twice in parallel. However, there are also race conditions inherent in Z1() and Z2() running in parallel when x and y are set (e.g., x could be set in Z1(), then overwritten by switching to Z2(), and then we might switch back to Z1() and run ComputeZ() using Z2()'s x value). To fix the second problem, you either need to run Z1() and Z2() atomically, or make x,y, and z local variables that are passed in/returned from ComputeZ instead. People lost 2 points on this problem for not providing a 'fix'. If people only provided a fix for problems inside of ComputeZ() (e.g., a lock around everything inside ComputeZ()), they lost one point. People who mentioned the race between Z1() and Z2() and offered a fix for that as well got full credit.

Problem 3

T0-S
T1-S
T1-1
T2-S
T1-2
T2-1
T2-E
T1-E
T0-E

Problem 4

Same as above because even with priority donation, T1 was the highest priority thread after T2. Hence T1 runs after T2 is blocked in both the cases.

Problem 5

(a)

1) Page tables entries of different processes can map regions of processes' virtual addresses to the same physical frames.
2) A segment table and a number of page tables (one per process segment) are associated with each process. By having two segments point to the same page table, the page table will be shared, and as a consequence also the related physical frames will be.

(b)

Yes. Each process has its own page table that maps virtual addresses to physical ones. As explained in the lecture, each entry in the page table includes protection bits (such as "read", "write") that tell the allowed operations of the process over the page. Therefore, Process 1 and Process 2 can have their page table entries (with protection bits read/write on) map the same physical frame region, while Process 3 can have its page table entries map it with only protection bit read on.

Problem 6

To emulate reference bits, use the invalid bit in the page table as follows:
-Set page permissions to “invalid” / "not present"
-On any access to the page, will get a fault - in the page fault handler, Mark as referenced

Problem 7

Position independent code (PIC) solves a problem with libraries that are shared across multiple processes. Rather than having to place a shared library at the same address in every process or re-link the library to use different addresses in different processes, PIC allows the system to run the same code at different addresses in different processes by building the library code to be easily relocatable, hence the name position independent code.