$29
LAB 2: PROCESS SYNCHRONIZATION IN XV6 SOLUTION
In this lab, you will implement a synchronization solution using locks and condition variables to guarantee a specific execution ordering among two processes. Make sure that you start from a fresh copy of the Xv6 code.
1. PART 1: THREE PROCESSES - A PARENT AND TWO CHILDREN
In the first part you will write a small user-land program that has a parent process forking two child processes, resulting in a total of three processes: the parent process and the two children.
#include "types.h"
#include "stat.h"
#include "user.h"
//We want Child 1 to execute first, then Child 2, and finally Parent.
int main() {
int pid = fork(); //fork the first child
if(pid < 0) {
printf(1, "Error forking first child.\n");
} else if (pid == 0) {
printf(1, "Child 1 Executing\n"); } else {
pid = fork(); //fork the second child
if(pid < 0) {
printf(1, "Error forking second child.\n");
} else if(pid == 0) {
printf(1, "Child 2 Executing\n"); } else {
printf(1, "Parent Waiting\n"); int i;
for(i=0; i< 2; i++)
wait();
printf(1, "Children completed\n");
printf(1, "Parent Executing\n");
printf(1, "Parent exiting.\n");
}
}
exit();
}
Think of the statements as placeholders for the code that each
• process runsprintf(1,. "<X> executing\n")
What is the effect of the parent process calling
two times?
to the
1. Put the previous code into a file named
inside your Xv6 source code folder. Add
•
wait()
. (You may refer to the
variable inside your Makefile. Compile and run Xv6 by typing
UPROGS
race.c
race\
instructions of setting up your Xv6 environment from Lab 1.)
make qemu-nox
2. Run the user-land program inside Xv6 by typing
.
at the Xv6 prompt. Notice the order of execution of the
three processes. Run the program
•
race
Do you always get the same order of execution?
multiple times
•
Does Child 1 always execute (print Child 1 Executing) before Child 2?
line before the line where Child 1 prints "Child Executing".
3. Add•a
•
What do you notice?
sleep(5);
Can we guarantee that Child 1 always execute before Child 2?
2. PART 2: SPIN LOCKS
We will start by defining a spinlock that we can use in our user -land program. Xv6 already has a spinlock (see spinlock.c) that it uses inside its kernel and is coded in somehow a complex way to handle concurrency caused by interrupts. We don't need most of the complexity, so will write our own light- weight version of spinlocks. We will put our code inside ulib.c, which includes functions accessible to user-land programs.
4. Inside ulib.c, add
after the #includeline: "spinlock.h"
#include "types.h"
Also, add the following function definitions:
void
init_lock(struct spinlock * lk) {
lk->locked = 0;
}
void lock(struct spinlock * lk) {
while(xchg(&lk->locked, 1) != 0)
;
}
void unlock(struct spinlock * lk) {
xchg(&lk->locked, 0);
}
We are still using the
defined in spinlock.h but we will only use its
field. Initializing the lock and unlocking it both work by setting
to 0. Locking uses the
2
struct spinlock
locked
locked
atomic instruction, which sets the contents of its first parameter (a memory address) to the second xchgparameter and returns the old value of the contents of the first parameter.
5. Inside user.h, add the following function prototypes:
void init_lock(struct spinlock *);
void lock(struct spinlock *);
to the endvoidoftheunlockfileand(structaddthe followingspinlocktwo*);lines into the beginning of the file:
struct condvar;
Now, westructhaveourspispinlockslock;in place. We can use them inside race.c:
struct spinlock lk;
init_lock(&lk);
lock(&lk);
//critical section
We will useunlock(condition&lk)variables to be able to make Child 2 sleep (block) until Child 1 finishes execution.
3.
PART 3: CONDITION VARIABLES
We will use condition variables to ensure that Child 1 always executes before Child 2. We will add
two system calls to Xv6:
and
to wait (sleep) on a condition variable and
to wakeup (signal) all sleeping processes on a condition variable.
cv wait()
cv_signal()
Recall that both waiting and signaling a condition variable has to be called after acquiring a lock
(that's why we defined our spinlock in Part 2).
releases the lock before sleeping and
reacquires it after waking up.
cv_wait
6. First, define the condition variable structure in condvar.h as follows.
#include "spinlock.h"
struct condvar {
struct spinlock lk;
A condition variable has a spin lock.
};
7.
Let's then add the two system calls.
Inside syscall.h, add the following two lines:
#define SYS_cv_signal 22
Inside usys.S, add:
23
#define SYS_cv_wait
SYSCALL(cv_signal)
SYSCALL(cv_wait)
3
Inside syscall.c, add:
and
extern int sys_cv_signal(void);
extern int sys_cv_wait(void);
[SYS_cv_wait] sys_cv_wait,
Inside user[SYS.h, addcv_signal] sys_cv_signal,
to the beginningstruct andcondvar;
int cv _wait( struct condvar *);
to the end of the system calls section of the file.
int cv _signal(stru t
c ndvar * );
Our condition variable implementation depends heavily on the sleep/wakeup mechanism
implemented inside Xv6 (Please read
sleep
on Page 65 of the Xv6 book). We will again
define a more light-weight version of the
function to use our light-weight spinlocks defined in
Part 2 instead of Xv6's spinlocks.
Sl
and Wakeup
8. Inside proc.c, add the following function definition:
void
sleep1(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();
if(p == 0)
panic("sleep");
if(lk == 0)
panic("sleep without lk");
acquire(&ptable.lock);
lk->locked = 0;
• Go to sleep. p->chan = chan; p->state = SLEEPING;
sched();
• Tidy up. p->chan = 0;
release(&ptable.lock);
while(xchg(&lk->locked, 1) != 0)
4;
After a couple of sanity checks, the function acquires the process table lock
to be
}
(), which works on the process table. Then, it releases the spinlock (by setting
able to call
ptable.lock
to 0) and goes to sleep by setting the process state to SLEEPING, setting the channel that the
sched
(). After the process wakes up,
process sleeps on, and switching into the scheduler by calling
locked
lock and reacquires the spinlock (using the
instruction).
it releases the
9. Inside
, add the following function prototype in the
sched
section:
ptable
xchg
defs.h
//proc.c
10. Inside sysproc.c add
void
sleep1(void*, struct spinlock*);
after the #includeline: "condvar.h"
and add the#includefollowing"typessyscall. h"implementations:
int
sys_cv_signal(void)
{
int i;
struct condvar *cv;
argint(0, &i);
cv = (struct condvar *) i;
wakeup(cv);
return 0;
}
int
sys_cv_wait(void)
{
int i;
struct condvar *cv;
argint(0, &i);
cv = (struct condvar *) i;
sleep1(cv, &(cv->lk));
return 0;
}
to the end. In both functions, the code starts with retrieving the argument ( )
from the stack: struct condvar * argint(0, &i);
The addresscvof =the( structconditioncondvarvariable is*)usedi; as the channel passed over to the function defined in Step 8. The address of the condition variable is unique and this is all sleep1whatwe need: a unique channel number to sleep and to get waked up on.
5
After seeing what the two system calls do, why do you think we had to add system calls for the operations on condition variables? Why not just have these operations as functions in ulib.c as we did for the spinlock?
4. PART 4: USING THE CONDITION VARIABLES
We can then modify race.c to use a condition variable to guarantee process ordering.
#include "types.h"
#include "stat.h"
#include "user.h"
#include "condvar.h"
//We want Child 1 to execute first, then Child 2, and finally Parent. int main() {
struct condvar cv;
init_lock(&cv.lk);
int pid = fork(); //fork the first child
if(pid < 0) {
printf(1, "Error forking first child.\n");
} else if (pid == 0) { sleep(5);
printf(1, "Child 1 Executing\n"); lock(&cv.lk);
cv_signal(&cv); unlock(&cv.lk);
} else {
pid = fork(); //fork the second
if(pid < 0) {
printf(1, "Error forking second child.\n");
} else if(pid == 0) { lock(&cv.lk); cv_wait(&cv); unlock(&cv.lk);
printf(1, "Child 2 Executing\n"); } else {
printf(1, "Parent Waiting\n"); int i;
for(i=0; i< 2; i++) wait();
printf(1, "Children completed\n"); printf(1, "Parent Executing\n"); printf(1, "Parent exiting.\n");
}
}
exit();
6
Note the }highlighted parts. A condition variable is declared. Its spinlock is initialized. Then Child 1 signals the condition variable after acquiring the spinlock. Child 2 sleeps on the condition variable after acquiring the spinlock as well.
Compile and run the modified race program.
• Does Child 1 always execute before Child 2?
5. PART 5: LOST WAKEUPS
deadlock
. If Child 2 gets to sleep
after
Does it happen that the program gets stuck? This is called a
Child 1 signals, the wakeup signal is lost (i.e., never received by Child 2). In this case, Child 2 has no
way of being awaked.
To solve this problem, we need to enclose the cv wait() call inside a while loop. We need some
form of a flag that gets set by Child 1 when it is done executing. Child 2 will then do
while(flag is not set)
cv wait();
This way, even if Child 1 sets the flag and signals before Child 2 executes the while loop, Child 2 will
shared
file
not avoid going to sleep because the flag will be set.
for that. Other methods for
The flag has to be
between the two processes. We will use a
sharing are shared memory and pipes.
To create a file,
To write iintot thefd file,=open("flag", O_RDWR | O_CREATE);
Checkingwrite(fd,theflaghas "done"tobenon,-4blocking);. The system call is blocking. Reading the size of the file is not. So, we will check the flag by readingreadthefile size. To read the size of a file,
struct stat stats;
fstat(fd, &stats);
printf(1, "file size = %d\n", stats.size);
Now, we are ready to write the while loop inside Child 2. It will loop until the file size is greater than zero, which happens when Child 1 writes "done" into the file after it finishes execution.
lock(&cv.lk);
struct stat stats;
fstat(fd, &stats);
printf(1, "file size = %d\n", stats.size);
while(stats.size <= 0){
cv_wait(&cv);
fstat(fd,7 &stats);
printf(1, "file size = %d\n", stats.size);
}
The newunlorace.c k(is:&cv.lk);
#include "types.h"
#include "stat.h"
#include "user.h"
#include "condvar.h"
#include "fcntl.h"
//We want Child 1 to execute first, then Child 2, and finally Parent. int main() {
struct condvar cv;
int fd = open("flag", O_RDWR | O_CREATE); init_lock(&cv.lk);
int pid = fork(); //fork the first child
if(pid < 0) {
printf(1, "Error forking first child.\n");
} else if (pid == 0) { sleep(5);
printf(1, "Child 1 Executing\n"); lock(&cv.lk);
write(fd, "done", 4); cv_signal(&cv); unlock(&cv.lk);
} else {
pid = fork(); //fork the second
if(pid < 0) {
printf(1, "Error forking second child.\n");
} else if(pid == 0) { lock(&cv.lk); struct stat stats; fstat(fd, &stats);
printf(1, "file size = %d\n", stats.size); while(stats.size <= 0){
cv_wait(&cv); fstat(fd, &stats);
printf(1, "file size = %d\n", stats.size);
}
unlock(&cv.lk);
printf(1, "Child 2 Executing\n"); } else {
printf(1, "Parent Waiting\n");
int i;
for(i=0; i< 2; i++)
wait();
8
printf(1, "Children completed\n");
printf(1, "Parent Executing\n");
printf(1, "Parent exiting.\n");
}
}
close(fd);
unlink("flag");
exit();
Note the highlighted parts and also note that we are closing the file and deleting it before the parent
}
exits. This is to start afresh the next time we run the program.
Compile and run race.c many times.
•
Is it always the case that Child 1 executes before Child 2?
•
Do you observe deadlocks?
Of course, synchronization bugs cannot be ruled out by running a program many times. Formal proof is typically the preferred way especially for safety- and mission- critical systems. There are tools that help with this kind of formal proofs.
6. SUBMISSION INSTRUCTIONS
Submit to Gradescope the files that you have modified within the source code of xv6. You should modify the following files only:
• syscall.h
• syscall.c
• user.h
• usys.S
• proc.c
• sysproc.c
• Makefile
• condvar.h
• defs.h
• ulib.c
Your submission will be graded by compiling and running it and reviewing the source code.
9
