ec4205_task1.md

Task 1) Pintos Thread System

1. How the switching between threads occur?

schedule() is responsible for switching threads in threads/thread.c.

static void
schedule (void) 
{
  struct thread *cur = running_thread ();
  struct thread *next = next_thread_to_run ();
  struct thread *prev = NULL;

  ASSERT (intr_get_level () == INTR_OFF);
  ASSERT (cur->status != THREAD_RUNNING);
  ASSERT (is_thread (next));

  if (cur != next)
    prev = switch_threads (cur, next);
  thread_schedule_tail (prev);
}

First, schedule() assigns thread structure into cur and next.

• running_thread() returns the running thread, coping the CPU's stack pointer into esp and rounding that down to the start of a page.
• next_thread_to_run() chooses and returns the next thread to be scheduled. If ready_list is empty in checking by list_empty(&ready_list), the funtion returns idle_thread. Otherwise, the funtions returns the front of the current run queue by list_pop_front(&ready_list).

Therefore, cur points to the current running thread and next points next thread to be scheduled.

Second, schedule() raises error if

• intr_get_level() is not equal to INTR_OFF. intr_get_level() in threads/interrupt.h returns current interrupt state. enum intr_level is divied into two cases, INTR_OFF or INTR_ON, denoting that interrupts are disabled or enabled, respectively.
• state of the current thread is THREAD_RUNNING. The state member of struct thread is decleared in threads/thread.h. The thread's state, one of the following: THREAD_RUNNING, THREAD_READY, THREAD_BLOCKED, and THREAD_DYING. Each state denotes running, ready to run, waiting, and being destoryed, respectively.
• next is invalid. is_thread() checks if the argument is to point a valid thread by NULL checking and magic member checking.

Third, schedule() switches context from cur to next unless cur is equal to next, meaning that there is no need to run the context switch. Context switching is done by switch_threads(), which is decleared in threads/switch.h and is implemented in threads/switch.S as assember language routine. The code for switch_threads() in threads/switch.S is the following.

.globl switch_threads
.func switch_threads
switch_threads:
	pushl %ebx
	pushl %ebp
	pushl %esi
	pushl %edi

.globl thread_stack_ofs
	mov thread_stack_ofs, %edx

	movl SWITCH_CUR(%esp), %eax
	movl %esp, (%eax,%edx,1)

	movl SWITCH_NEXT(%esp), %ecx
	movl (%ecx,%edx,1), %esp

	popl %edi
	popl %esi
	popl %ebp
	popl %ebx
        ret
.endfunc

The global variable thread_stack_ofs is declared in line 587 of threads/thread.c stores offset of stack member within struct thread. The macro keyword SWITCH_CUR and SWITCH_NEXT is declared in threads/switch.h and refers 20 and 24, repectively. (Indeed, the structure of switch_threads_frame is defined in threads/switch.h.)

switch_threads() is excuted in the following step :

• stores the registors %ebx, %ebp, %esi, and %edi.
• %edx is assigned as offset of stack member within struct thread.
• saves the CPU's current stack pointer in the current struct thread's stack member.
• restores the new thread's stack into the CPU's stack pointer.
• restores the registors %ebx, %ebp, %esi, and %edi.
• returns.

Consequentially, switch_theads(cur, next) switches from cur to next, returning cur in next's context.

Lastly, the rest of the scheduler is implemented in thread_schedule_tail(). thread_schedule_tail() is implemented in threads/thread.c.

void
thread_schedule_tail (struct thread *prev)
{
  struct thread *cur = running_thread ();
  
  ASSERT (intr_get_level () == INTR_OFF);

  cur->status = THREAD_RUNNING;

  thread_ticks = 0;

#ifdef USERPROG
  process_activate ();
#endif

  if (prev != NULL && prev->status == THREAD_DYING && prev != initial_thread) 
    {
      ASSERT (prev != cur);
      palloc_free_page (prev);
    }
}

process_activate() is implemented in line 123 of userprog/process.c, which is to set up the CPU for running user code in the current thread. This function is called on every context switch. palloc_free_page() is implemented in line 146 of threads/palloc.c. This function is for the special case of palloc_free_multiple() for the intend to free only the one page.

thread_schedule_tail() is excuted in the following step :

• again, gets the new current thread cur and checks that intr_get_level() is not equal to INTR_OFF.
• marks the new thread as running.
• sets up the CPU for running user code in the current thread.
• frees the page that contained the dying thread's struct thread and stack if the thread we just switched from is in the dying state. (but not free initial_thread because its memory was not obtained via palloc().)

2. How the provieded scheduler works?

There are two important functions to determine heuristic of the provieded scheduler behavior.

1. thread_unblock()

void
thread_unblock (struct thread *t) 
{
  enum intr_level old_level;

  ASSERT (is_thread (t));

  old_level = intr_disable ();
  ASSERT (t->status == THREAD_BLOCKED);
  list_push_back (&ready_list, &t->elem);
  t->status = THREAD_READY;
  intr_set_level (old_level);
}

thread_unblock() transits thread, which must be in the blocked state, to the ready state, allowing it to resume running. After thread validation and status checking, list_push_back (&ready_list, &t->elem); is excuted and this is one of the key part for scheduling. list_push_back() is implemented in lib/kernel/list.c and the function works in the same way we think the element is inserted at the front of the tail of normal double linked list. The status of t changes to THREAD_READY.

Therefore, this scheduling is a typical implementation of FCFS because element of t is appended to the end of the ready queue whenever thread_unblock() is called.

2. thread_yield()

void
thread_yield (void) 
{
  struct thread *cur = thread_current ();
  enum intr_level old_level;
  
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  if (cur != idle_thread) 
    list_push_back (&ready_list, &cur->elem);
  cur->status = THREAD_READY;
  schedule ();
  intr_set_level (old_level);
}

thread_yield(), which is the function used when the current CPU occupying thread, yields CPU occupancy and adds threads to the ready_list. As discussed above, thread_yield() is also scheduled according to FCFS policy.

Above two functions implicitly show that the provided scheduling policy in Pintos is FCFS. This is because these two functions are the only functions that includes list_push_back(&ready_list, ...) code, which means that element is push back to ready list.

To explain the providied Pintos scheduler in detail, there is one more function to be locked into. This is next_thread_to_run(), which chooses and returns the next thread to be scheduled.

static struct thread *
next_thread_to_run (void) 
{
  if (list_empty (&ready_list))
    return idle_thread;
  else
    return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

next_thread_to_run() is used in schedule(). In execution of next_thread_to_run(), an idle thread is returned if ready list is empty. Otherwise, a thread located in front of ready list is popped for serving the next running thread.

Collectively, thread is pushed back to the last of ready list in thread_unblock() and thread_yeild(), and is popped from the front of ready list in next_thread_to_run(). Again, it makes us convince that the provided scheduler in Pintos is FCFS scheduler.

3. How the various synchronizations primitives work?

The simplest and most ignorant synchronization primitive implemented in vanila Pintos is the interrupt disabler located in threads/interrupt.h. However, this is not included in threads/synch.h, so we will not look into this because it is out of the scope we have to cover. Except this, there are four synchronization methods implemented in threads/synch.h.

1. Semaphores

A semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system. In general, semaphore S is a variable with an integer value, which can only be accessed by commands P and V. P is performed before entering the critical section, and V is performed when leaving the critical section. At this time, all operations that modify the variable value must satisfy atomicity. In other words, while changing a semaphore value in one process (or thread), another process should not change this value at the same time.

The struct semaphore, which is the structure covered by the semaphore implementation in Pintos, has the following simple structure. value is a semaphore S and waiters is list of waiting threads.

struct semaphore 
  {
    unsigned value;
    struct list waiters;
  };

struct semaphore is initialized by sema_init(), which sets intial value and waiters. After initialization, the two core funtions, sema_down() and sema_up(), take key part of control of synchronization. They role P operation and V operation, respectively.

void
sema_down (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  while (sema->value == 0) 
    {
      list_push_back (&sema->waiters, &thread_current ()->elem);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

sema_down() does:

• check the argument sema is not NULL.
• check the system does not run in an interrupt context. intr_context() originally located in threads/interrupt.h returns true if the system is running in an interrupt context.
• make interrupts off and get a previous interrupt state as old_level. intr_disable() also originally localed in threads/interrupt.h turns interrupts off and returns the previous interrupt state.
• wait for semaphore value to become positive. During waiting the semaphore, add repeatdly element of the current thread to list of waiting threads. thread_block() transits the running thread from the running state to the blocked state.
• decrement the semaphore value by one if waiting step passes.
• restore interrupt state as old_level.

void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  if (!list_empty (&sema->waiters)) 
    thread_unblock (list_entry (list_pop_front (&sema->waiters),
                                struct thread, elem));
  sema->value++;
  intr_set_level (old_level);
}

sema_up() does:

• As same with sema_down(), NULL checking and inturrpt state setting are procedured.
• unblock the very front thread of waiting list if list is not empty.
• increment the semaphore value by one.
• restore interrupt state as old_level.

Indeed, the implementation of its semaphore is a method using busy waiting. Though it is based on busy waiting, it will not suffer a priority decision problem because it uses waiting queue internally.

2. Locks

A lock is semaphore-like thing with an initial value of 1. The V of the lock is called "release" and the P action is called "acquisition". Compared to a semaphore, a lock has one added restriction: only the thread that acquires a lock, called the lock's "owner", is allowed to release it.

The struct lock, which is the structure covered by the locking implementation in Pintos, has the following simple structure. holder is a thread holding lock and semaphore is binary semaphore controlling access.

struct lock 
  {
    struct thread *holder;
    struct semaphore semaphore;
  };

struct lock is initialized by lock_init(), which sets holder as NULL and semaphore as one. After initialization, the two core funtions, lock_acquire() and lock_release(), take key part of control of synchronization. Before looking into two core functions, lock_held_by_current_thread() is used in both two functions.

bool
lock_held_by_current_thread (const struct lock *lock) 
{
  ASSERT (lock != NULL);

  return lock->holder == thread_current ();
}

lock_held_by_current_thread() just returns if the current thread holds lock, false otherwise.

void
lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));

  sema_down (&lock->semaphore);
  lock->holder = thread_current ();
}

lock_acquire() does:

• As same with sema_down(), NULL checking and inturrpt context checking are procedured.
• Additionaly, make certain that lock is not acquired by the current thread.
• P action is excuted for locking and holder is assigned by the current thread. As a result, the current thread gets locking.

void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));

  lock->holder = NULL;
  sema_up (&lock->semaphore);
}

lock_acquire() does:

• NULL checking is procedured.
• make certain that lock is now acquired by the current thread.
• V action is excuted for locking. holder is assigned by the NULL. As a result, the current thread releases locking.

3. Monitors

A monitor is a synchronization construct that allows threads to have both mutual exclusion and the ability to wait for a certain condition to become true. Before the thread accesses the protected data, a thread first acquires the monitor lock. It is then said to be "in the monitor". While in the monitor, the thread has control over all the protected data, which it may freely examine or modify. When access to the protected data is complete, it releases the monitor lock.

Condition variables allow code in the monitor to wait for a condition to become true. Each condition variable is associated with an abstract condition. When code in the monitor needs to wait for a condition to become true, it "waits" on the associated condition variable, which releases the lock and waits for the condition to be signaled. If, on the other hand, it has caused one of these conditions to become true, it "signals" the condition to wake up one waiter, or "broadcasts" the condition to wake all of them.

The struct condition is quite simple, which only includes list of waiting threads. cond_init() also works just for initialization of waiters.

struct condition 
  {
    struct list waiters;
  };

There are three core functions for implementing monitor synchronization : cond_wait(), cond_signal(), and cond_broadcast().

void
cond_wait (struct condition *cond, struct lock *lock) 
{
  struct semaphore_elem waiter;

  ASSERT (cond != NULL);
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (lock_held_by_current_thread (lock));
  
  sema_init (&waiter.semaphore, 0);
  list_push_back (&cond->waiters, &waiter.elem);
  lock_release (lock);
  sema_down (&waiter.semaphore);
  lock_acquire (lock);
}

cond_wait() does as the following :

• check NULL condition and interrut context, and make certain that lock is now acquired by the current thread.
• call sema_init() to intialize internal waiter and push back element of initial waiter into cond->waiters.
• atomically release lock.
• wait for cond to be signaled by some other piece of code.
• reacquire lock before returning.

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) 
{
  ASSERT (cond != NULL);
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (lock_held_by_current_thread (lock));

  if (!list_empty (&cond->waiters)) 
    sema_up (&list_entry (list_pop_front (&cond->waiters),
                          struct semaphore_elem, elem)->semaphore);
}

cond_signal() does as the following :

• check NULL condition and interrut context, and make certain that lock is now acquired by the current thread.
• wake up one of them if any threads are waiting on cond (protected by monitor lock lock).
• return without performing any action if no threads are waiting.

void
cond_broadcast (struct condition *cond, struct lock *lock) 
{
  ASSERT (cond != NULL);
  ASSERT (lock != NULL);

  while (!list_empty (&cond->waiters))
    cond_signal (cond, lock);
}

cond_broadcast() wakes up all threads, if any, waiting on cond (protected by monitor lock lock).

In this implementation, sending and receiving a signal are not an atomic operation. Thus, typically the caller must recheck the condition after the wait completes and, if necessary, wait again.

4. Optimization Barriers

A barrier is a type of synchronization method. A barrier for a group of threads or processes in the source code meansn any thread/process must stop at this point and cannot proceed until all other threads/processes reach this barrier. The compiler will not reorder reads or writes of variables across the barrier or assume that a variable's value is unmodified across the barrier, except for local variables whose address is never taken.

The first reason to use an optimization barrier is when data can change asynchronously, without the compiler's knowledge. This function starts out by busy-waiting in a loop until a timer tick occurs:

/* Wait for a timer tick. */
int64_t start = ticks;
while (ticks == start)
  barrier ();

The second reason to use optimization barriers is to avoid other compiler optimizations.

while (loops-- > 0)
  barrier ();

The goal of this loop is to busy-wait by counting loops down from its original value to 0. Without the barrier, the compiler could delete the loop entirely, because it produces no useful output and has no side effects. The barrier forces the compiler to pretend that the loop body has an important effect.

The third reason to use optimization barriers is to force the ordering of memory reads or writes.

line A;
barrier();
line B

In above code, without barrior(); line, each process/thread which executes line B cannot make sure that other process/thread finishes line A. By using barrior();, we verify that all the processes/threads execute the specific program flow.

Actually, barrier() is just simply implemented as assembly language.

#define barrier() asm volatile ("" : : : "memory")