Blog

Below is the correct pseudocode of the ‘atomic swap’ mutual exclusion solution. Is indefinite postponement possible here? Explain why or why not. boolean occupied = false;startThreads();T1 T2void main() { void main() { boolean t1MustWait = true; boolean t2MustWait = true; while (!done) { while (!done) { do { do { swap(t1MustWait, occupied); swap(t2MustWait, occupied); } while (t1MustWait); } while (t2MustWait); // critical section // critical section t1MustWait = true; t2MustWait = true; occupied = false; occupied = false; // non-critical section // non-critical section } }} } The code is reproduced below with T2’s codebelow T1’s in case it is easier to read that way: T1void main() { boolean t1MustWait = true; while (!done) { do { swap(t1MustWait, occupied); } while (t1MustWait); // critical section t1MustWait = true; occupied = false; // non-critical section }}T2void main() { boolean t2MustWait = true; while (!done) { do { swap(t2MustWait, occupied); } while (t2MustWait); // critical section t2MustWait = true; occupied = false; // non-critical section }}

Why would a quantum that allows ALL processes to reach their compute-to-IO time be a poor choice?

Suppose you had a program where certain work could be done in parallel, and you expect each thread to use 2 GB of RAM. The computer on which you will run the program has 32 GB total RAM, and 8 cores. This computer is running a typical OS such as Windows or Linux and you have been given permission to run your process on it without any other users using it. So before you start your process, you close all open programs. How many threads would you use to perform this task? Give a full explanation of your answer, including all considerations that affect it.

The psuedocode of Lamport’s bakery algorithm is given below. Fully explain one example of how it can be “unfair”.   boolean[n] choosing;int[n] ticket;startThreads();Txvoid main() { int x = threadNumber; while (!done) { choosing[x] = true; ticket[x] = maxValue(ticket) + 1; choosing[x] = false; for (int i = 0; i < n; i++) { if (i == x) continue; while (choosing[i] == true) ; while (ticket[i] != 0 && ticket[i] < ticket[x]) ; if (ticket[i] == ticket[x] && i < x) while (ticket[i] != 0 && ticket[i] == ticket[x]) ; } /* CRITICAL SECTION GOES HERE */ ticket[x] = 0; /* non-critical code */ }}

Briefly describe the difference between FIFO and round robin.

Give an example of how an algorithm might use spatial locality to fetch pages in an anticipatory scheme. For this question you do not have to use an actual algorithm covered in class. If it’s easier, you can just describe what an algorithm might do to accomplish this goal

Explain the advantage of SPF (shortest process first) over FIFO for scheduling. What goal is addressed?

Explain the difference(s) between a static priority scheme and a dynamic priority scheme.

Describe a characteristic of a scheduling algorithm that would be good for a real-time system. Explain your answer.

A monitor is a construct designed to ensure mutual exclusion. It uses the concept of a thread being “inside” or “outside” to do this.