Operating Systems: Test 1

Open-book test. No collaboration.

Email your answers to me by the end of the class (4:15pm) today.

1. Briefly explain what threads are and what processes are? What make them different?

2. Suppose that we have exactly three threads T1, T2, and T3 within in a process sharing a common variable x with the memory location m. And the three threads run the following code concurrently, each trying to read the value of the common variable x, decrease its value by 1, and then write it back to x :

T1 : { Load the contents of x into register R1;

Decrease the contents of R1 by 1;

Store the contents of register R1 into location m;

}

T2 : { Load the contents of x into register R2;

Decrease the contents of R2 by 1;

Store the contents of register R2 into location m;

}

T3 : { Load the contents of x into register R3;

Decrease the contents of R3 by 1;

Store the contents of register R3 into location m;

}

Suppose the initial value of x in the memory location m is 3 immediately before the execution of the three threads, and each Load, Decrease, and Store operation is an atomic machine instruction. What could be the final value of x in the memory location m by the time all three threads are finished? For each possible value, write down a possible instruction execution sequence that would end in the value.

3. There are several approaches to ensure mutual exclusion when concurrent threads or processes are executing critical sections. One of the approaches is a pure software approach that requires the programmer to write his/her own code to guard the critical section and ensure mutual exclusion. For example, the following code demonstrates how a programmer can use whiles loops and a shared variable turn to ensure mutual exclusive execution of critical sections for two processes.

Process P1:

repeat

while (turn!=1){};

// Critical Section C1

turn=2;

// non-critical part N1

forever

Process P2:

repeat

while (turn!=2){};

// Critical Section C2

turn=1;

// non-critical part N2

forever

Suppose that the non-critical part N1 of P1 is extremely slow because heavy I/O operations while the non-critical part N2 of P2 can be done fairly fast. Could this code severely and unnecessarily degrade the progress of P1? Explain why or why not.

4. Following up the software approach to mutual exclusion in #3, instead of a single variable turn, we can use two shared variables flag[1] and flag[2] for the two processes to show their intention of entering their own critical sections.

Process P1:

repeat

flag[1]=true;

while(flag[2] = = true){};

Critical Section C1

flag[1]=false;

non-critical part N1

forever

Process P2:

repeat

flag[2]=true;

while(flag[1] = = true){};

Critical Section C2

flag[2]=false;

non-critical part N2

forever

Is it possible that both processes are in their critical sections? Could it sometimes end in deadlock (i.e. both are stuck in the while loops before entering the critical sections? If any of the answers is yes, please describe a scenario ending in that situation.

5. Following up the software approach to mutual exclusion in #4, we modify the code as follows.

Process P1:

flag[1]=false;

repeat

while(flag[2] = = true){};

flag[1]=true;

Critical Section C1

flag[1]=false;

non-critical part N1

forever

Process P2:

flag[2]=false;

repeat

while(flag[1] = = true){};

flag[2]=true;

Critical Section C2

flag[2]=false;

non-critical part N2

forever

6. The following is a general solution to the bounded-buffer producer/consumer problem. Note that S, N, E, are three semaphores, buffer is an array of size k that can store k item objects, while in and out are integer variables.

Initialization:

S.count=1; in=0;

N.count=0; out=0;

E.count=k;

append(v):

buffer[in]=v;

in=(in+1) mod k;

Producer:

repeat

// produce an item v;

wait(E);

wait(S);

append(v);

signal(S);

signal(N);

forever

Consumer:

repeat

wait(N);

wait(S);

w=take();

signal(S);

signal(E);

// consume an item w

forever

take():

w=buffer[out];

out=(out+1) mod k;

return w;

Now assume that we have a buffer of size 2 (i.e. k is 2). Consider the following runtime scenario: the producer first produces two item, then is blocked while trying to produce a third item; the consumer consumes the first item; then the producer wakes up to produce the third item. Please trace and write down step by step about how (i) the values of in and out and (ii) the counter values of semaphores S, N, E, are changed.

7. Consider the solution to the bounded-buffer producer/consumer problem using semaphores depicted in #6 again. The semaphores S, N, E guard the mutual exclusive access to the bounded buffer, the buffer-not-empty condition, and the buffer-not-full condition respectively. (i) Could we put wait(E) after wait(S) in the producer part of code? Explain why or why not. (ii) Could we put wait(N) after wait(S) in the consumer part of code? Explain why or why not. (iii) Is it ok to put signal(S) after signal(N) in the producer part of code? Explain why or why not. (iv) Is it ok to put signal(s) after signal(e) in the of the consumer part of code? Explain why or why not.

8. Consider the FAT12 file system for the floppy disk again in Homework#3. Let 1 KB means 1024 bytes and let 1 MB means 1024 KB. If (i) the floppy disk capacity is 2.88 MB instead of 1.44 MB and (ii) each sector contains 256 bytes (0.25 KB) instead of 512 bytes, then the number of entries in the FAT table and the number of bits in each entry need to change. What do you think should be the number of entries in the FAT table and the number of bits in each entry respectively? Explain why.