CS161 2019-02-20
Zhu, Justin

CS161 2019-02-20
Wed, Feb 20, 2019

kernel.hh #define HZ 100 // number of ticks per second //kern.cc volatile unsigned long ticks; // timer interrupts

Time is the number of itkcs

unsigned long wake_up = ticks + (regs->reg_rdi + 9) / 10

while long(wakeuptime - ticks) > 0 ) { this->yield(); }

This will solve the overflow problem as long as wake_up - ticks does not over flow the unsigned long buffer.

If there are 10 million processes, we don’t have time until the timer interrupt.

If there’s not the time to interrupt, let’s yield()

We put the user-mode part of process goes to sleep but kernel-half stays runnable. The yield goes back to run queue, check if it’s time to wake up.

We want to have the kernel-half making sure that polling is limited.


Kernel tasks often need to block until an event occurs.

A certain amount of time has elapsed as in sleep(ms)

If a keyboard data arrivees

Time fires

Lock is released.

We could have a lock instruction released where it’stime for them to get rid of hte lock.

HOw can the kernel create an efficient mechanism to handle arbitrary types of blocking events

Wait Queues

Have a queue for each type of blocking event, one for lock, keyboard, etc.

The threads will put themselves on that particular queue. Other parts of the kernel will try to wake up the sleeping tasks on the queue. True blocking is now possible!

Yield and thread were coming out and checking condition was correct.

The challenge is to get those semantics correct.

Lifetime of a Process

  1. Parent process calls fork, load executable binary from disk
  2. Then we want to put the running queue using the scheduler
  3. Blocked state has a state where a process is not on a CPU run queue
  4. The process might want I/O Synchronization

Blocked queue goes to Ready queue to scheduler to CPU. There might be a priority scheme.

OS can use more than one queue, fancier data structures than queues such as a timing wheel to implement sleep(ms)

Then the process exits and enters the finished state.

Formalizing the Blocking Problem

Let x be the subset of program state

A sleeping thread blocks until f(x) is true.

A waking thread modifies x in a way that cause f(x) to become true.

Computes f(x) == false

x_lock.lock() f(x) == false Decides to block

Wakeup: x_lock.lock() and blocks computes f(x) == false Decides to block cond_wait(&x_cond, &x_lock)

This atomically releases lock and blocks thread; when it returns, lock held by caller

x_lock.lock() Does stuff so f(x) is true cond_signal(&x_cond) and wakes up sleeping thread x_lock.unlock()

Lock the run queue

switch (newstate)

case S_READ, put the thread on the runqueue

case sleep

wchan_name = wc->wc_name

threadlist_addtail(&wc->wc_threads, cur); spinlock_release(lk); break;

/** other code where scheduler eventually dequeues a thread from runqueue and runs it

Scheduler must be aware of wait queue abstractions. Thread switch had to know about the wait queue. Design scheduler in a way that’s decoupled as much as possible.

Linux and Cickadee loosen the binding between the scheduler and the condition/wait abstraction

Maintain wait queues outsideof the scheduler, and leverage proc::yield() to expose a runnable thread to the scheduler

Sleeping thread wants to block until next timer interrupts while the waking thread runs every timer interrupt


waiter w(this) // kernel thread passes itself into the queue

w.prepare(wait-q) // sets p->state_ to proc::blocked, adds w to a linked list of waiters associated with waitq, unlocks waitq

w.block(); // calls yield, which invokes scheduler, looks at the state. If the state is blocked, then it won’t add the process to the cpu’s runqueue

If state is runnable, the p won’t block.


Interrupts must be disabled. The waitq.wake_all() takes the lock that protects the wait_queue, locks and will unlock the lock. Loop through the queue, and we create a wake function instead.

Waiter does not want to unblock until f(x) == true

Waker manipulates program state to make f(x) == true

x must be protected by x_lock

if (f(x)) { break; } x_lock.unlock(irqs); w.block(); irqs = x_lock.lock();

Kernel can be running AT MOST one CPU.