Part I

1. Consider a computer that does not have a TEST AND SET LOCK instruction but does have an instruction to swap the contents of a register and a memory word in a single indivisible action. Can that be used to write a routine enter region such as the one found in Fig. 212.
2. Measurements of a certain system have shown that the average process runs for a time T before blocking on I/O. A process switch requires a time S, which is effectively wasted (overhead). For roundrobin scheduling with quantum Q, give a formula for the CPU efficiency (i.e., the useful CPU time divided by the total CPU time) for each of the following:
   • Q=
   • Q>T
   • S<Q<T
   • Q=S
   • Q nearly 0
3. Consider the interprocess-communication scheme where mailboxes are used. Suppose a process P wants to wait for two messages, one from mailbox A and one from mailbox B. What sequence of send and receive should it execute so that the messages can be received in any order?
4. Consider the following program that uses the Pthreads API. What would be the output of the program? (Note that the line numbers are for references only.)

Listing 1: pthread.c

• #include <stdio.h>
• #include <stdlib.h>
• #include <unistd.h>
• #include <pthread.h>
• #include <sys/types.h>

6

7 int value = 1;

8

9 static void *runner(void *param);

10

• int main(int argc, char **argv)
• {
• pid_t pid = fork();
• if (pid > 0) {
• printf(A = %d
  , value);
• }
• else if (pid == 0) {
• pid_t pid = fork();
• if (pid > 0) {
• printf(B = %d
  , value);
• }
• else if (pid == 0) {
• pid_t pid = fork();
• pthread_t tid;
• pthread_attr_t attr;
• pthread_attr_init(&attr);
• pthread_create(&tid, &attr, runner, NULL);
• pthread_join(tid, NULL);
• if (pid > 0)
• printf(C = %d
  , value);
• else
• printf(D = %d
  , value);
• }
• else {
• exit(1);
• }
• }
• else {
• exit(1);
• }

41

• return 0;
• }

44

• static void *runner(void *param)
• {
• value += 1;
• pthread_exit(0);
• }

Part II

Write a program to simulate the dining philosopher problem mentioned in the textbook using the Pthreads API on Linux. Make sure that your implementation is able to handle 5 philosophers and is free of race condition.