Project 6: User-level threads

Due: May. 22, 2025, 2:30 pm (submission: by email)
Submit a report to TA: SeungWon Yoo ( email: swyoo98@kaist.ac.kr )
Name your report file with “hw6_[your studentid]”. ex: hw6_20201234.zip

In this project, you will make xv6 to support multi thread. Thread is flow of execution while process is program that is on execution. In a single thread system such as now version of xv6, process can have only one thread, so thread is same with process in that system. However, in a multi thread system, process can have more than one thread. In that system, multiple flow of execution can be executed sharing same address space. We will provide program code that including whole code to maintain thread on user level. But it does not have complete function for thread switching but have just prototyspe. Moreover, because they are user level functions, threads cannot leverage timer interrupt for time sharing between each thread. For this reason, thread have to explicitly call thread_yield() function to switch to another thread. The purpose of this homework is to resolve these problems.

Part One : Get the code for project
See the resource tab below. Source code, uthread.c and uthread_switch.S, have been uploaded. Download these files, compile these programs, create ELF file _uthread, and run it on xv6.

Download Resource : homework-09

First, download source code and places them on xv6 directory.

Second, edit Makefile so that compile these codes and create ELF file _uthread. Add the following rule to the xv6 Makefile after the _forktest rule that is placed on line 153 approximately.

_uthread: uthread.o uthread_switch.o
	$(LD) $(LDFLAGS) -N -e main -Ttext 0 -o _uthread uthread.o uthread_switch.o $(ULIB)
	$(OBJDUMP) -S _uthread > uthread.asm

Note that above code is 3 line code. Each code start with words like _uthread, $(LD), and $(OBJDUMP) respectively and the start of 2 bottom line is tab not the spaces. Add _uthread in the Makefile to the list of user programs defined by UPROGS like below. UPROGS is defined in line 168 approximately.

UPROGS=\
	…
	_uthread

Part Two : Thread switching in user level
Run xv6, then run uthread from the xv6 shell. The xv6 kernel will print an error message about uthread encountering a page fault. Your job is to complete thread_switch.S, so that you see output similar to this (make sure to run with CPUS=1):

$ make CPUS=1 qemu-nox
...
xv6...
cpu0: starting
init: starting sh
$ uthread
my thread running
my thread 0x2A30
my thread running
my thread 0x4A40
my thread 0x2A30
my thread 0x4A40
my thread 0x2A30
my thread 0x4A40
....

uthread creates two threads and switches back and forth between them. Each thread prints “my thread …” and then yields to give the other thread a chance to run.

To observe the above output, you need to complete thread_switch.S, but before jumping into uthread_switch.S, first understand how uthread.c uses thread_switch. uthread.c has two global variables current_thread and next_thread. Each is a pointer to a thread structure. The thread structure has a stack for a thread and a saved stack pointer (sp, which points into the thread’s stack). The job of uthread_switch is to save the current thread state into the structure pointed to by current_thread, restore next_thread’s state, and make current_thread point to where next_thread was pointing to, so that when uthread_switch returns next_thread is running and is the current_thread.

You should study thread_create, which sets up the initial stack for a new thread. It provides hints about what thread_switch should do. The intent is that thread_switch use the assembly instructions popal and pushal to restore and save all eight x86 registers. Note that thread_create simulates eight pushed registers (32 bytes) on a new thread’s stack.

To write the assembly in thread_switch, you need to know how the C compiler lays out struct thread in memory, which is as follows:

--------------------
| 4 bytes for state|
--------------------
| stack size bytes |
| for stack        |
--------------------
| 4 bytes for sp   |
--------------------  <--- current_thread
     ......

     ......
--------------------
| 4 bytes for state|
--------------------
| stack size bytes |
| for stack        |
--------------------
| 4 bytes for sp   |
--------------------  <--- next_thread

The variables next_thread and current_thread each contain the address of a struct thread. To write the sp field of the struct that current_thread points to, you should write assembly like this:

movl current_thread, %eax
movl %esp, (%eax)

This saves %esp in current_thread->sp. This works because sp is at offset 0 in the struct. You can study the assembly the compiler generates for uthread.c by looking at uthread.asm.

Part Three : Time sharing of user threads
After fill thread_switch out, it can use multi thread system. However, thread switching is triggered only when a thread call thread_scheduler or thread_yield that is also call thread_scheduler.

Other multi thread system use time sharing to perform thread switching. It is not different from process switching. We will impose time sharing to uthread. The uthread pass address of user level scheduler function when it create thread. The kernel maintain the address of user level scheduler function by each process. When a timer interrupt is occurred, check if the thread scheduling is needed or not. If it is needed, it modify trap frame to call scheduler and call function that is should called originally after scheduler has returned.

We will modify some part of kernel including proc.h, proc.c and trap.c. We will make process maintain the address of user level scheduler function to struct proc.

struct proc{
  ...
  uint scheduler;	// address of user level scheduler function.
};

Add following new system call, uthread_create. It have one argument, address of user level scheduler function. It have a return value that indicates if it is success or not. To add new system call, so many files have to be modified. To learn how to add new system call, please refer to homework 6.

int
sys_uthread_create(void)
{
  struct proc *p;
  int func;

  if (argint(0, &func) < 0)
    return -1;

  p = myproc();

  if (p->scheduler == 0)
    p->scheduler = (uint)func;

  return 0;
}

Once a timer interrupt is occurred, the following code is executed.

void
trap(struct trapframe *tf)
{
  ...
  switch(tf->trapno){
  case T_IRQ0 + IRQ_TIMER:
    if(cpuid() == 0){
      acquire(&tickslock);
      ticks++;
      wakeup(&ticks);
      release(&tickslock);
    }
    lapiceoi();
    // Add new code here
    break;
    ...
  }
  ...
}

Write new code to a bold line and make it call scheduler and original return code.

How can change a process to call user level scheduler after trap has been returned? How can make original return code of trap into return code of user level scheduler?

Some conditions should be satisfied.

Does this process have more than one thread? In other world, have this thread called system call, uthread_create?
Should it call scheduler when a timer interrupt has been occurred at kernel mode? In other word, how can we handle a timer interrupt that has been occurred when a user thread execute system call? How can find whether an interrupt has been occurred on kernel mode? (Hint: Please refer default section of the switch statement on trap.)

To test your code, modify uthread code and run it.

First, make code calling thread_yield comment. Then, add a code to call system call, uthread_create, at the end of the body of thread_create like below.

void
thread_create(void (*func)())
{
  ...
  t->state = RUNNABLE;
  uthread_create(thread_schedule);
}
...
static void
mythread(void)
{
  int i;
  for (i = 0; i < 100; i++) {
    printf(1, "my thread 0x%x\n", (int) current_thread);
    //thread_yield();
  }
  printf(1, "my thread: exit\n");
  current_thread->state = FREE;
  thread_schedule();
}

The uthread.c still needs modification. After you add just 2 lines like above to uthread.c, it will face some bug (It may not complete all of loops and be exited). Find reason and fix it. If you have completed, run and check if it is work correctly like below. Please remind that you have run xv6 with CPUS=1 option.

$ make CPUS=1 qemu-nox
...
init: starting sh
$ uthread
...
my thread 0x49Dd 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x290
my thread 0x49D0
my thread 0x49D0
my thread 0x49D0
my thread 0x49D0
my thread 0x49D0
my thread 0x49D0
my thread 0x49D0
C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8
my thread 0x29C8my thread 0x49D0
my thread 0x49D0
my thread: exit

my thread 0x29C8
my thread: exit
thread_schedule: no runnable threads
$

Please feel free to add more field to struct proc and modify sys_uthread_create function. However, if you have added more field to struct proc or modified sys_uthread_create, you must specify that on report. Please submit three files, modified uthread_switch.S, modified trap.c, and report describing your code.

Submit : modified uthread_switch.S and trap.c file and report.