CPE555A – Embedded Real-Time Systems
Solutions3
- (25 points) Consider the strict alternation algorithm shown in Slide 41, Lecture 6. Does the busy waiting solution using the turn variable work when the processes are running on two CPUs, sharing a common memory?
Yes. The variable turn is written only when a CPU leaves the critical region. Turn is like a token which is passed between the two CPUs.
- (25 points) Consider the following set of processes P1 and P2:
P1: { P2:{
shared int x; shared int x;
x = 7; x = 7;
while (1) { while (1) {
x--; x--;
x++; x++;
if (x != 7) { if (x != 7) {
printf(``x is %d'',x) printf(``x is %d'',x)
} }
} }
} }
Show an execution (i.e., trace the sequence of inter-leavings of statements) such that the statement x is 7 is printed.
In the following, the test for the value of x by P1 is interleaved with the increment of x P2. Thus, x was not equal to 7 when the test was performed, but was equal to 7 by the time the value of x was read from memory for printing.
M(x)
P1: x--; 6
P1: x++; 7
P2: x--; 6
P1: if (x != 7) 6
P2: x++; 7
P1: printf("x is %d", x); 7
"x is 7" is printed.
- (25 points) Consider Peterson’s the algorithm discussed in class. Suppose process 0 runs at priority 5 and process 1 runs at priority 6. The scheduler runs the highest priority process. Does Peterson's solution to the mutual exclusion problem work when process scheduling is preemptive (i.e, a higher priority process preempts the lower priority process)? How about when it is non-preemptive
enter_region(i)
Execute critical section(i)
leave_region(i)
It obviously works when we do not have preemption of the lower-priority thread with the higher-priority thread. The lower priority thread completes its critical region and leaves it before the scheduler dispatches the higher priority thread. With preemption turned on, the lower priority thread may complete its critical region but before it can execute leave_region(), it is switched out and the higher priority thread starts executing enter_region() which is busy waiting. Enter_region() keeps spinning. Because the lower priority thread is not scheduled, it never leaves its critical region. We have deadlock.
In fact at the beginning turn=0. So the process with turn=1 runs first, neither process can even enter its critical region!
- (25 points) In the program below, what is the output at "LINE C" and "LINE P"? Why?
int value = 0 ;
void *runner(void *param) ; /* the thread */
int main(int argc, char *argv[])
{
int pid ;
pthread_t tid ;
pthread_attr_t attr ;
pid = fork() ;
if (pid == 0) /* child process */
{
pthread_attr_init(&attr) ;
pthread_create(&tid, &attr, runner, NULL) ;
pthread_join(tid, NULL) ;
printf("CHILD: value = %d\n", value) ; /* LINE C */
}
else if (pid > 0) /* parent process */
{
wait(NULL) ;
printf("PARENT: value = %d\n", value) ; /* LINE P */
}
}
void *runner(void *param)
{
value = 5 ;
pthread_exit(0) ;
}
The key is that the global variable value is separately copied in the address spaces of the CHILD and the PARENT processes. After fork, they have an independent existence.
In Line C the CHILD runs a thread which changes value=5 in the address space of the CHILD. It then joins the thread and waits for the thread to exit. Therefore LINE C will print value=5. The PARENT does not spawn a thread so the global value in the PARENT’s address space. Line P will print value=0.