106 OS homework 2-2 成果報告書

組長：B10415034 鍾雅淳

github: https://github.com/yvonne2059/xv6-public

🙂 使用情境說明(包含流程圖)

Counter

A global variable g_counter is used as a counter for all threads,which is initialized as 0.
Then, we can start to create threads to increase the count of g_counter.
Finally, we can use clone() to create and start all the threads as well as join() to wait for all the threads.

Semaphores

sem_init(), sem_destroy(), sem_wait() and sem_signal() four system calls is implemented to make semaphore function.

sem_init() initialize the id and size
sem_destroy() delete the target semaphore.
sem_wait() wait until a unit of the resource becomes available, and decrease semaphore value by given number.
sem_signal() increase the value of semaphore variable by given number.

Flow

Start->Initialize Semaphore , stack, g_counter->Create thread->Wait thread->

Join thread->Thread test->Destroy Semaphore->Exit

😇 成功畫面

Call thread test to test the system calls

🏃 實作過程(修改哪些檔案[含圖片])

create semaphore.c

struct semaphore {
  int value;
  int active;
  struct spinlock lock;
} sem[32];

//initiallize the semophore table
void
seminit(void)
{
  int i;
  for(i = 0; i < NSEMS; ++i)
  {
    initlock(&sem[i].lock, "semmaphore");
    sem[i].active = 0;
    sem[i].value = 0;
  }
}

int
sem_init(int num, int max)
{
  // check if the entry is valid
  if(num < 0 || num > NSEMS)
    return -1;

  acquire(&sem[num].lock);
  // check if the entry is actived
  if(sem[num].active != 0) 
    return -1;
  sem[num].value = max;
  sem[num].active = 1;
  release(&sem[num].lock);

  return 0;
}

int
sem_destroy(int num)
{
  // check if the entry is valid
  if(num < 0 || num > NSEMS)
    return -1;

  acquire(&sem[num].lock);
  // check if the entry is actived
  if(sem[num].active != 1) 
    return -1;
  sem[num].active = 0;
  release(&sem[num].lock);

  return 0;
}

int
sem_wait(int num, int count)
{
  // check if  valid
  if(num < 0 || num > NSEMS)
    return -1;

  acquire(&sem[num].lock);
  // check if active
  if(sem[num].active == 0) 
    return -1;
  // if there is no enough lock, sleep
  while(sem[num].value <= count - 1)
  {
    sleep(&sem[num], &sem[num].lock);
  }
  sem[num].value -= count;
  release(&sem[num].lock);

  return 0;
}

int
sem_signal(int num, int count)
{
  // check if the entry is valid
  if(num < 0 || num > NSEMS)
    return -1;

  acquire(&sem[num].lock);
  // check if the entry is actived
  if(sem[num].active == 0) 
    return -1; 
  // the thread exit the critical section, return a lock
  sem[num].value += count;
  // if there is any available lock, call wakeup
  if(sem[num].value > 0) 
    wakeup(&sem[num]);
  release(&sem[num].lock);

  return 0;
}

Add system calls in syscall.c ,syscall.h user.h, uSys.S

syscall.h

syscall.c

user.h

int sem_destroy(int);
int sem_wait(int, int);
int sem_signal(int, int);
int clone(void*, void*, void*);
int join(void**);

uSys.S

SYSCALL(sem_init)
SYSCALL(sem_destroy)
SYSCALL(sem_wait)
SYSCALL(sem_signal)
SYSCALL(clone)
SYSCALL(join)

Add system call of semaphore and proc in defs.h

//semaphore.c
 void            seminit(void);
 int             sem_init(int, int);
 int             sem_destroy(int);
 int             sem_wait(int, int);
 int             sem_signal(int, int);
 
 //proc.c
 void            userinit(void);
 int             wait(void);
 void            wakeup(void*);
 void            yield(void);
 int             clone(void*, void*, void*);
 int             join(void**);

Implement the system calls in proc.c and sysproc.c

proc.c

int
clone(void* function, void *arg, void *stack)
{
  int i, pid;
  struct proc *np;

  // Allocate process.
  if((np = allocproc()) == 0)
    return -1;

  np->sz = proc->sz;
  // if the process calling clone is itself a thread,
  // copy its parent to the new thread
  if (proc->isthread == 0) {
    np->parent = proc;
  }
  else {
    np->parent = proc->parent;
  }
  *np->tf = *proc->tf;

  // Clear %eax so that fork returns 0 in the child.
  np->tf->eax = 0;

  // reallocate old process's page table to new process
  np->pgdir = proc->pgdir;
  // modified the return ip to thread function
  np->tf->eip = (int)function;
  // modified the thread indicator's value
  np->isthread = 1;
  // modified the stack
  np->stack = (int)stack;
  np->tf->esp = (int)stack + 4092; // move esp to the top of the new stack
  *((int *)(np->tf->esp)) = (int)arg; // push the argument
  *((int *)(np->tf->esp - 4)) = 0xFFFFFFFF; // push the return address
  np->tf->esp -= 4;

  for(i = 0; i < NOFILE; i++)
    if(proc->ofile[i])
      np->ofile[i] = filedup(proc->ofile[i]);
  np->cwd = idup(proc->cwd);

  safestrcpy(np->name, proc->name, sizeof(proc->name));
 
  pid = np->pid;

  
  acquire(&ptable.lock);
  np->state = RUNNABLE;
  release(&ptable.lock);

  // exit();
  return pid;
}

int
join(void **stack)
{
  struct proc *p;
  int havekids, pid;

  acquire(&ptable.lock);
  for(;;){
    // Scan through table looking for zombie children.
    havekids = 0;
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      // only wait for the child thread, but not the child process
      if(p->parent != proc || p->isthread != 1)
        continue;
      havekids = 1;
      if(p->state == ZOMBIE){
        // Found one.
        pid = p->pid;
        kfree(p->kstack);
        p->kstack = 0;
        p->state = UNUSED;
        p->pid = 0;
        p->parent = 0;
        p->name[0] = 0;
        p->killed = 0;
        release(&ptable.lock);
        return pid;
      }
    }

    //don't waiting if we don't have any children thread.
    if(!havekids || proc->killed){
      release(&ptable.lock);
      return -1;
    }

    // Wait for children to exit.  (See wakeup1 call in proc_exit.)
    sleep(proc, &ptable.lock);  //DOC: wait-sleep
    *(int*)stack = proc->stack;
  }
}

sysproc.c

int
sys_sem_init(void)
{
  int num, max;
  if(argint(0, &num) < 0)
    return -1;
  if(argint(1, &max) < 0)
    return -1;
  return sem_init(num, max);
}

int
sys_sem_destroy(void)
{
  int num;
  if(argint(0, &num) < 0)
    return -1;
  return sem_destroy(num);
}

int
sys_sem_wait(void)
{
  int num, count;
  if(argint(0, &num) < 0)
    return -1;
  if(argint(1, &count) < 0)
    return -1;
  return sem_wait(num, count);
}

int
sys_sem_signal(void)
{
  int num, count;
  if(argint(0, &num) < 0)
    return -1;
  if(argint(1, &count) < 0)
    return -1;
  return sem_signal(num, count);
}

int
sys_clone(void)
{
  int function, arg, stack;
  if(argint(0, &function) < 0)
    return -1;
  if(argint(1, &arg) < 0)
    return -1;
  if(argint(2, &stack) < 0)
    return -1;
  return clone((void*)function, (void*)arg, (void*)stack);
}

int
sys_join(void)
{
  int stack;
  if(argint(0, &stack) < 0)
    return -1;
  return join((void**)stack);
}

create thread_test.c to test

#define NUM_THREADS 2
#define TARGET_COUNT_PER_THREAD 50000
#define SEMAPHORE_NUM 0

uint g_counter;

void *thread(void *arg)
{
	int i;
	int counter;

	sleep(10);
	printf(1, "thread %d: started...\n", *(int*)arg);

	for (i=0; i<TARGET_COUNT_PER_THREAD; i++) {
		sem_wait(SEMAPHORE_NUM, 1);
		
		counter = g_counter;
		sleep(0);
		counter++;
		sleep(0);
		g_counter = counter;

		sem_signal(SEMAPHORE_NUM, 1);
	}

	exit();
}

int main(int argc, char **argv)
{
	int i, j;
	int sem_size;
	int final_counter;
	int final_target = NUM_THREADS*TARGET_COUNT_PER_THREAD;

	if (argc >= 2)
		sem_size = NUM_THREADS;
	else
		sem_size = 1;

	// Initialize semaphore to 1
	if (sem_init(SEMAPHORE_NUM, sem_size) < 0)
	{
		printf(1, "main: error initializing semaphore %d\n", SEMAPHORE_NUM);
		exit();
	}

	printf(1, "main: initialized semaphore %d to %d\n", SEMAPHORE_NUM, sem_size);

	// Initialize counter
	g_counter = 0;

	// Set up thread stuff

	// Stacks
	void *stacks[NUM_THREADS];
	// Args
	int *args[NUM_THREADS];

	// Allocate stacks and args and make sure we have them all
	// Bail if something fails
	for (i=0; i<NUM_THREADS; i++) {
		stacks[i] = (void*) malloc(4096);
		if (!stacks[i]) {
			printf(1, "main: could not get stack for thread %d, exiting...\n");
			exit();
		}

		args[i] = (int*) malloc(4);
		if (!args[i]) {
			printf(1, "main: could not get memory (for arg) for thread %d, exiting...\n");
			exit();
		}

		*args[i] = i;
	}

	printf(1, "main: running with %d threads...\n", NUM_THREADS);

	// Start all children
	for (i=0; i<NUM_THREADS; i++) {
		int pid = clone(thread, args[i], stacks[i]);
		printf(1, "main: created thread with pid %d\n", pid);
	}
	
	// Wait for all children
	for (i=0; i<NUM_THREADS; i++) {
		void *joinstack;
		join(&joinstack);
		for (j=0; j<NUM_THREADS; j++) {
			if (joinstack == stacks[i]) {
				printf(1, "main: thread %d joined...\n", i);
				break;
			}
		}

	}

	// Check the result
	final_counter = g_counter;
	printf(1, "Final counter is %d, target is %d\n", final_counter, final_target);
	if (final_counter == final_target)
		printf(1, "TEST PASSED!\n");
	else
		printf(1, "TEST FAILED!\n");
	
	// Clean up semaphore
	sem_destroy(SEMAPHORE_NUM);

	// Exit
	exit();
}

😎 結論

Multithread is actually quite simple to do, it’s mainly made up of thread_create() which create some number of threads by using clone() to create the child of threads. At the end, the main thread should call wait() (repeatedly, once per child) to wait for all the children to complete, and at this point, the main thread should add up all of the values of the elements on the list, and print out a final value.

📅 組員分工

單人作業無分工