OS161 Assignment 2

Assignment2

Use this document as a guideline for writing high-quality code.

In this assignment you finally get to write your own code in OS161! By the end of this assignment you will:

  • Have a good understanding of the implementation of spinlocks and semaphores in OS161
  • Implement locks
  • Implement condition variables.

Step 1. Prepare

Make sure you don't have any uncommitted updates in your repo. Now, tag your repository as shown here:

1
git tag asst2-start

Now push that new tag:

1
git push --tags

Make a directory submit/asst2 in your os161 tree. You will put your file with the answers to code reading questions in that directory.

  • Physical memory and CPUs

Change sys161.conf file in ~/os161/root:

1
31 mainboard ramsize=2097152 cpus=4
  • Built-in thread tests

The thread test code uses the semaphore synchronization primitive

You should trace the execution of one of these thread tests in GDB to see how the scheduler acts, how threads are created, and what exactly happens in a context switch. You should be able to step through a call to thread_switch() and see exactly where the current thread changes.

  • Debugging concurrent programs

thread_yield() is automatically called for you at intervals that vary randomly.

Change sys161.conf file in ~/os161/root:

1
28	random seed=1

Once you are done with initial debugging/testing, remember to set the random device back to autoseed.

This should allow you to test your solutions under varying conditions and may expose scenarios that you had not anticipated, which is central to effective testing.

Step 2. Code reading exercises

  1. What happens to a thread when it exits (i.e., calls thread_exit())? What about when it sleeps?

thread_exit() detaches the thread from the process, checks the stack guard band, turns interrupts off on this processor and performs a thread switch(find another thread to run).

thread.c 777:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
 * Cause the current thread to exit.
 *
 * The parts of the thread structure we don't actually need to run
 * should be cleaned up right away. The rest has to wait until
 * thread_destroy is called from exorcise().
 *
 * Does not return.
 */
void
    thread_exit(void)
{
    struct thread *cur;

    cur = curthread;

    /*
	 * Detach from our process. You might need to move this action
	 * around, depending on how your wait/exit works.
	 */
    proc_remthread(cur);

    /* Make sure we *are* detached (move this only if you're sure!) */
    KASSERT(cur->t_proc == NULL);

    /* Check the stack guard band. */
    thread_checkstack(cur);

    /* Interrupts off on this processor */
    splhigh();
    thread_switch(S_ZOMBIE, NULL, NULL);
    panic("braaaaaaaiiiiiiiiiiinssssss\n");
}

First, wchan_sleep makes sure that we are not in an interrupt handler, hold the specific spinlock associated with the wait channel WC and no others. Then, it performs a thread switch, and puts the thread go to sleep on the specified wait channel WC before finding another thread to run. Lastly, when being woken up, it locks the spinlock again before returning.

thread.c 1026:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * Yield the cpu to another process, and go to sleep, on the specified
 * wait channel WC, whose associated spinlock is LK. Calling wakeup on
 * the channel will make the thread runnable again. The spinlock must
 * be locked. The call to thread_switch unlocks it; we relock it
 * before returning.
 */
void
    wchan_sleep(struct wchan *wc, struct spinlock *lk)
{
    /* may not sleep in an interrupt handler */
    KASSERT(!curthread->t_in_interrupt);

    /* must hold the spinlock */
    KASSERT(spinlock_do_i_hold(lk));

    /* must not hold other spinlocks */
    KASSERT(curcpu->c_spinlocks == 1);

    thread_switch(S_SLEEP, wc, lk);
    spinlock_acquire(lk);
}
  1. What function(s) handle(s) a context switch?

thread.c 560:

thread_switch()

Machine-dependent functions for working on switchframes:

During context switch, switch what is saved on the kernel stack.

switchframe_switch()

  1. What does it mean for a thread to be in each of the possible thread states?

During context switching, we need to put the thread in the right place according to its newstate.

  • S_RUN:

    For S_RUN, it means the thread is currently running. A thread should never be put into the S_RUN state within thread_switch. But if it does, call panic.

  • S_READY: A thread in the S_READY state is ready to run but is not currently running. thread_make_runnable is called to add it to the run queue so that the scheduler can pick it up for execution later.

  • S_SLEEP: A thread in the S_SLEEP state is blocked, waiting to be woken up. The thread is added to the wait channel wc, and it will remain in this state until a wakeup call (like wchan_wake) signals it. After putting the thread on the list, we release the spinlock associated with the wait channel wc.

  • S_ZOMBIE: A thread in the S_ZOMBIE state has finished its execution but has not yet been fully cleaned up. The thread is added to the CPU's zombie list c_zombies, where it waits to be freed.

thread.c: thread_switch(): 595:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* Put the thread in the right place. */
switch (newstate) {
    case S_RUN:
        panic("Illegal S_RUN in thread_switch\n");
    case S_READY:
        thread_make_runnable(cur, true /*have lock*/);
        break;
    case S_SLEEP:
        cur->t_wchan_name = wc->wc_name;
        /*
		 * Add the thread to the list in the wait channel, and
		 * unlock same. To avoid a race with someone else
		 * calling wchan_wake*, we must keep the wchan's
		 * associated spinlock locked from the point the
		 * caller of wchan_sleep locked it until the thread is
		 * on the list.
		 */
        threadlist_addtail(&wc->wc_threads, cur);
        spinlock_release(lk);
        break;
    case S_ZOMBIE:
        cur->t_wchan_name = "ZOMBIE";
        threadlist_addtail(&curcpu->c_zombies, cur);
        break;
}
cur->t_state = newstate;
  1. What does it mean to turn interrupts off? How is this accomplished? Why is it important to turn off interrupts in the thread subsystem code?

Turning interrupts off means that the current processor is temporarily prevented from responding to hardware interrupts, meaning that the current CPU cannot perform a context switch.

In os161, turning interrupts off is accomplished by changing the processor's interrupt priority level(IPL). The function splhigh() is used to set the IPL to its highest level to disable all interrupts.

1
2
/* Explicitly disable interrupts on this processor */
spl = splhigh();

It is important to turn off interrupts in the thread subsystem code. When we perform operations on threads such as context switching, blocking threads, exit threads, we don't want to be interrupted. If we are interrupted during those operations, we may lose important information of the thread. For example, if we are interrupted during context switching when we are saving the thread's state, we may lose the state during interrupts. Turning off interrupts also helps avoid deadlock and improve performance.

  1. What happens when a thread wakes up another thread? How does a sleeping thread get to run again?

When a thread wants to wake up another thread, it calls the function wchan_wakeone, the function grabs a thread from the wait channel and then calls thread_make_runnable to make the target thread runnable.

In thread_make_runnable, the target thread should lock the run queue of the CPU, ensuring only one thread in the run queue can modify the CPU. Then it puts the target thread on the run queue of the CPU.

  1. What function(s) choose(s) the next thread to run?

thread_switch

  1. How does it (do they) pick the next thread?

schedule and thread_switch both use threadlist_remhead function, which removes and returns the first thread from the run queue of the current CPU, which is the next thread to run.

  1. What role does the hardware timer play in scheduling? What hardware independent function is called on a timer interrupt?

The hardware timer generates periodic interrupts to allow the operating system to regain control of the CPU at regular intervals, ensuring that it can check the status of threads and make scheduling decisions.

hardclock is the hardware independent function called on a timer interrupt.

  1. Describe how wchan_sleep() and wchan_wakeone() are used to implement semaphores.

For function V, wchan_wakeone() is called after it increments sem_count and wants to wake up another thread.

For function P, wchan_sleep is called when sem_count = 0 and wants to put the thread to sleep waiting to be awakened. It should be called after we lock the wait channel(using semaphore spinlock) so that we can put the thread to sleep while also release the wait channel lock afterwards. After being woken up, it locks the wait channel again before returning.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct semaphore {
    char *sem_name;
    struct wchan *sem_wchan;
    struct spinlock sem_lock;
    volatile unsigned sem_count;
}

void
    V(struct semaphore *sem)
{
    KASSERT(sem != NULL);

    spinlock_acquire(&sem->sem_lock);

    sem->sem_count++;
    KASSERT(sem->sem_count > 0);
    wchan_wakeone(sem->sem_wchan, &sem->sem_lock);

    spinlock_release(&sem->sem_lock);
}

void
    P(struct semaphore *sem)
{
    KASSERT(sem != NULL);
    KASSERT(curthread->t_in_interrupt == false);

    /* Use the semaphore spinlock to protect the wchan as well. */
    spinlock_acquire(&sem->sem_lock);
    while (sem->sem_count == 0) {
        wchan_sleep(sem->sem_wchan, &sem->sem_lock);
        // sem_lock is also the wait channel lock.
        // Before returning from sleep, we should relock.
    }
    KASSERT(sem->sem_count > 0);
    sem->sem_count--;
    spinlock_release(&sem->sem_lock);
}
  1. How does the implementation of wchan ensure that a thread never misses a wakeup signal: that another thread cannot attempt to awaken the first thread just as it is preparing to sleep, but before it is actually placed into the sleep queue?

In P, wchan_sleep is called after we acquire the semaphore spinlock(spinlock_acquire(&sem->sem_lock)), which also serves as locking the wait channel. In this way, when we call wchan_sleep to put the current thread to sleep, no other threads can manipulate the wait channel(i.e. by calling wchan_wakeone). That is to say, no threads can sneak in and try to awaken the thread during its "sleep" process.

1
2
3
4
5
6
7
/* Use the semaphore spinlock to protect the wchan as well. */
spinlock_acquire(&sem->sem_lock);
while (sem->sem_count == 0) {
    wchan_sleep(sem->sem_wchan, &sem->sem_lock);
    // sem_lock is also the wait channel lock.
    // Before returning from sleep, we should relock.
}

Step 3. Implement locks for OS161

The interface for the lock struct is defined in kern/include/synch.h. Stub code is provided in kern/thread/synch.c.

Requirements:

  1. Comply to the interface. Take a look at the stub code provided in kern/thread/synch.c. Your implementation must conform to this API. Please don't change it, as this will break the tests that we will use to test your assignment.
  2. Mutual exclusion. It's probably a no-brainer that your locks must provide mutual exclusion. You are going to implement the simplest semantics of locks: only one thread can hold a lock at any given time.
  3. No busy-waiting. If you carefully read the OS161 code, you noticed that there is an implementation of spinlocks. Spinlocks derive their name from the method that they use to wait until the lock becomes available: they spin, or busy-wait, hogging the CPU and checking if the lock became available. While this is perfectly fine for short critical section and only on a multiprocessor system (why?), a general implementation of locks must be more universal. We must be able to use them on a system with a single CPU and for long critical sections, e.g., those involving I/O operations, where it makes no sense to busy-wait on the CPU. Therefore, your locks implementation must not busy-wait on a taken lock. It must give up the CPU until the lock becomes available.

Implementation

FAQs

How to avoid busy-waiting?

When a thread tries to acquire the lock, if the lock is not avaiable, we puts the thread to sleep. After the thread holding the lock releases the lock, it wakes up another thread waiting on the wait channel.

How to protect the lock and the wait channel?

We use the spinlock provided by the os161 stub code to protect both the lock and the wait channel.

Code

lock structure:

1
2
3
4
5
6
7
8
9
10
struct lock
{
    char *lk_name;
    // add what you need here
    // (don't forget to mark things volatile as needed)
    volatile int lk_hold;        /* 0 means the lock is free, while 1 means the lock is held */
    struct wchan *lk_wchan;      /* wait channel, lists of threads waiting to get the lock */
    struct spinlock lk_spinlock; /* protect the lock and the wait channel */
    struct thread *lk_holder;    /* thread that holds the lock */
};

lock methods:

1
2
3
4
5
struct lock *lock_create(const char *name);
void lock_destroy(struct lock *);
void lock_acquire(struct lock *);
void lock_release(struct lock *);
bool lock_do_i_hold(struct lock *);

Methods Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/* Create the lock. */
struct lock *
    lock_create(const char *name)
{
    struct lock *lock;

    lock = kmalloc(sizeof(struct lock));
    if (lock == NULL)
    {
        return NULL;
    }

    lock->lk_name = kstrdup(name);
    if (lock->lk_name == NULL)
    {
        kfree(lock);
        return NULL;
    }

    // add stuff here as needed

    spinlock_init(&lock->lk_spinlock);            /* initialize spinlock */
    lock->lk_wchan = wchan_create(lock->lk_name); /* create wait channel */
    /* if failing to create wait channel, free the lock */
    if (lock->lk_wchan == NULL)
    {
        kfree(lock->lk_name);
        kfree(lock);
        return NULL;
    }
    /* initially no thread is holding the lock */
    lock->lk_holder = NULL;
    lock->lk_hold = 0;

    return lock;
}

/* Clean up the lock. */
void lock_destroy(struct lock *lock)
{
    KASSERT(lock != NULL);

    // add stuff here as needed

    /* acquire the spinlock making sure no other threads can modify the lock */
    spinlock_acquire(&lock->lk_spinlock);

    KASSERT(!lock->lk_hold);                                    /* make sure the lock is not used */
    KASSERT(lock->lk_holder == NULL);                           /* make sure no thread is holding the lock */
    KASSERT(wchan_isempty(lock->lk_wchan, &lock->lk_spinlock)); /* make sure wait channel is empty */

    spinlock_release(&lock->lk_spinlock);

    wchan_destroy(lock->lk_wchan);        /* destroy the wait channel */
    spinlock_cleanup(&lock->lk_spinlock); /* clean up the spinlock */

    /* clean up the lock structure */
    kfree(lock->lk_name);
    kfree(lock);
}

/*
 * Get the lock. Only one thread can hold the lock at the same time.
 * If the lock is held by another thread, put the current thread to sleep.
 */
void lock_acquire(struct lock *lock)
{
    // Write this

    KASSERT(lock != NULL);
    /* must not acquire the lock in an interrupt handler */
    KASSERT(!curthread->t_in_interrupt);

    /* acquire the spinlock, protecting the lock and the wait channel */
    spinlock_acquire(&lock->lk_spinlock);

    /* if the lock is held by other threads, put the current thread to sleep */
    while (lock->lk_hold)
    {
        /*
                 * wchan_sleep would unlocks the spinlock before sleeping, and
                 * acquire the spinlock again before returning.
                 */
        wchan_sleep(lock->lk_wchan, &lock->lk_spinlock);
    }

    /* acquire the lock for the current thread */
    lock->lk_hold = 1;
    lock->lk_holder = curthread;

    spinlock_release(&lock->lk_spinlock);
}

/* Free the lock. Only the thread holding the lock can do this. */
void lock_release(struct lock *lock)
{
    // Write this

    KASSERT(lock != NULL);
    /* make sure the current thread is holding the lock */
    KASSERT(lock_do_i_hold(lock));

    /* acquire the spinlock, protecting the lock and the wait channel */
    spinlock_acquire(&lock->lk_spinlock);

    /* free the lock */
    lock->lk_hold = 0;
    lock->lk_holder = NULL;
    /* wake up a thread waiting on the wait channel */
    wchan_wakeone(lock->lk_wchan, &lock->lk_spinlock);

    spinlock_release(&lock->lk_spinlock);
}

/*
 * Returns true if the current thread is holding the lock.
 * Otherwise, return false.
 */
bool lock_do_i_hold(struct lock *lock)
{
    // Write this

    KASSERT(lock != NULL);

    /* if there is no current thread, nobody is holding the lock */
    if (curthread == NULL)
    {
        return false;
    }

    /* acquire the spinlock before checking whether the current threads holds the lock */
    spinlock_acquire(&lock->lk_spinlock);
    bool do_i_hold = (lock->lk_holder == curthread);
    spinlock_release(&lock->lk_spinlock);

    return do_i_hold;
}

test sy2 passes!

Step 4. Implement condition variables for OS161

Requirements:

Just like with locks, your solution must:

  1. Comply to the existing interface.
  2. Implement proper cv semantics as explained here.
  3. Not use busy-waiting to wait on cv.

Implementation

FAQs

How to protect the wait channel?

Again, we use the spinlock provided by the os161 stub code to protect the wait channel.

What do we do in wait()?

First, we check that we hold the lock.

Then, release the lock and go to sleep, protected by the spinlock.

The sleep() function releases the spinlock and atomatically re-acquires the spinlock before returning.

Therefore, after sleep returns, we need to release the spinlock explicitly and re-acquire the lock before returning.

Do we need to release the lock in signal() after we wake up another thread.

No. Users who use the cv should explicitly releases the lock after they call signal. It is not signal()'s responsibility to do so. So is the broadcast() function.

Code

CV structure:

1
2
3
4
5
6
7
8
struct cv
{
    char *cv_name;
    // add what you need here
    // (don't forget to mark things volatile as needed)
    struct wchan *cv_wchan;     /* lists of threads waiting on the cv */
    struct spinlock cv_lock;    /* protect the wait channel */
};

CV methods:

1
2
3
4
5
struct cv *cv_create(const char *name);
void cv_destroy(struct cv *);
void cv_wait(struct cv *cv, struct lock *lock);
void cv_signal(struct cv *cv, struct lock *lock);
void cv_broadcast(struct cv *cv, struct lock *lock);

Methods Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/* Create the cv. */
struct cv *
    cv_create(const char *name)
{
    struct cv *cv;

    cv = kmalloc(sizeof(struct cv));
    if (cv == NULL)
    {
        return NULL;
    }

    cv->cv_name = kstrdup(name);
    if (cv->cv_name == NULL)
    {
        kfree(cv);
        return NULL;
    }

    // add stuff here as needed

    cv->cv_wchan = wchan_create(cv->cv_name); /* create the wait channel */
    /* if failing to create wait channel, free the cv */
    if (cv->cv_wchan == NULL)
    {
        kfree(cv->cv_name);
        kfree(cv);
        return NULL;
    }
    spinlock_init(&cv->cv_lock); /* initialize the spinlock */

    return cv;
}

/* Clean up the cv. */
void cv_destroy(struct cv *cv)
{
    KASSERT(cv != NULL);

    // add stuff here as needed

    /*
         * acquire the spinlock making sure no other threads can modify the cv
         * when we check the wait channel is empty.
         */
    spinlock_acquire(&cv->cv_lock);
    KASSERT(wchan_isempty(cv->cv_wchan, &cv->cv_lock));
    spinlock_release(&cv->cv_lock);

    wchan_destroy(cv->cv_wchan);    /* destroy the wait channel */
    spinlock_cleanup(&cv->cv_lock); /* clean up the spinlock */

    kfree(cv->cv_name);
    kfree(cv);
}

/*
 * Release the supplied lock, go to sleep, and, after
 * waking up again, re-acquire the lock.
 */
void cv_wait(struct cv *cv, struct lock *lock)
{
    // Write this

    KASSERT(cv != NULL);
    KASSERT(lock != NULL);
    KASSERT(lock_do_i_hold(lock));       /* check the current thread is holding the lock passed in */
    KASSERT(!curthread->t_in_interrupt); /* make sure we are not in an interrupt handler */

    /* acquire the spinlock, protecting the wait channel */
    spinlock_acquire(&cv->cv_lock);

    /* release the lock passed in */
    lock_release(lock);
    /*
         * Before wchan_sleep puts the current thread to sleep, it releases the spinlock.
         * Before returning from wchan_sleep, it relocks the spinlock.
         */
    wchan_sleep(cv->cv_wchan, &cv->cv_lock);

    spinlock_release(&cv->cv_lock);

    /* After waking up, re-acquire the lock passed in again before returning. */
    lock_acquire(lock);
}

/* Wake up one thread that's sleeping on the cv. */
void cv_signal(struct cv *cv, struct lock *lock)
{
    // Write this

    KASSERT(cv != NULL);
    KASSERT(lock != NULL);
    KASSERT(lock_do_i_hold(lock));       /* check the current thread is holding the lock passed in */
    KASSERT(!curthread->t_in_interrupt); /* make sure we are not in an interrupt handler */

    /* acquire the spinlock before manipulating the wait channel */
    spinlock_acquire(&cv->cv_lock);

    /* wake up one thread waiting on the cv */
    wchan_wakeone(cv->cv_wchan, &cv->cv_lock);

    spinlock_release(&cv->cv_lock);
}

/* Wake up all threads sleeping on the cv. */
void cv_broadcast(struct cv *cv, struct lock *lock)
{
    // Write this

    KASSERT(cv != NULL);
    KASSERT(lock != NULL);
    KASSERT(lock_do_i_hold(lock));       /* check the current thread is holding the lock passed in */
    KASSERT(!curthread->t_in_interrupt); /* make sure we are not in an interrupt handler */

    /* acquire the spinlock before manipulating the wait channel */
    spinlock_acquire(&cv->cv_lock);

    /* wake up all threads waiting on the cv */
    wchan_wakeall(cv->cv_wchan, &cv->cv_lock);

    spinlock_release(&cv->cv_lock);
}

Test sy3 and sy4 pass!

We have finished Assignment2!😊

OS > OS161
#OS #OS161 #Synchronization
OS161 Assignment 2
http://oooscar8.github.io/2024/09/27/OS161-A2/
作者
Alex Sun
发布于
2024年9月27日
许可协议