Starting from:
$35

$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

More products