CS 350

An OS is a system that manages resources, creates execution environments, loads programs, and provides common services and utilities.

• Started as simple I/O libraries, batch processors.

Three Views of an OS

1. Application View: What services does it provide?
2. System View: What problem does it solve?
3. Implementation View: How is it built?

Application View

Provides an execution environment for running programs.

• Provides program with processor time and memory space that it needs.
• Provides interfaces through which program can use networks, storage, I/O devices, other system hardware components. We want to abstract hardware from application programs.
• Isolates running programs from another and prevents undesirable interactions.

System View

• Manages hardware resources of a computer system including processors, memory, disks, network interfaces, I/O devices, etc.
• Allocates resources among running programs.
• Controls the sharing of resources among programs.

The OS itself also uses resources.

Implementation View

• Concurrency arises naturally in an OS when it supports concurrent applications, because it must interact directly with the hardware.
• Hardware interactions impose timing constraints.

Kernel: Part of OS that responds to system calls, interrupts, and exceptions.

Operating System: OS as a while includes the kernel, and may include other related programs to provide services for applications.

• Utility programs.
• Command interpreters.
• Programming libraries.

The execution environment provides by the OS includes a variety of abstractions.

• Files and file systems. Secondary storage.
• Address spaces. Primary memory (RAM).
• Processes, threads. Program execution.
• Sockets, pipes. Network or other message channels.

Threads and Concurrency

Better utilization of the CPU.

What is a tread? It is a sequence of instructions.

• A normal sequential program consists of a single thread of execution.
• Threads provide a way for programmers to express concurrency in a program.
• In threaded concurrent programs, there are multiple threads of execution, all occuring at the same time.

OS/161 Thread Interface.

kern/include/thread.h

int thread_fork(
    const char* name,
    struct proc* proc,
    void (*func)(void*, unsigned long),
    void* data1,
    unsigned long data2);

// Terminate the calling thread.
void thread_exit(void);

// Voluntarily yield execution.
void thread_yield(void);

Implementing Concurrent Threads

What options exist?

1. Hardware support. P processors, C cores, M multithreading per core. PCM threads can execute simultaneously.
2. Timesharing. Multiple threads take turns on the same hardware, rapidly switching between threads.
3. Hardware support and timesharing. PCM threads running simultaneously with timesharing.

Context Switching

Various Stack Frames \to thread_yield \to thread_switch \to switchframe.

kern/arch/mips/thread/switch.S

switchframe_switch:
    /* a0: switchframe pointer of old thread. */
    /* a1: switchframe pointer of new thread. */

    /* Allocate space for 10 registers. */
    addi sp, sp, -40
    /* Return address. */
    sw ra, 36(sp)
    /* Globals pointer. */
    sw gp, 32(sp)
    sw s8, 28(sp)
    sw s6, 24(sp)
    sw s5, 20(sp)
    sw s4, 16(sp)
    sw s3, 12(sp)
    sw s2, 8(sp)
    sw s1, 4(sp)
    sw s0, 0(sp)

    /* Store old stack pointer in old thread. */
    sw sp, 0(a0)

Loading data from the new stack pointer is similar. Uses nop operation in order to ensure loads have completed before usage.

Context Switch Causes

1. Running thread calls thread_yield. Voluntarily allows other threads to run.
2. Running thread calls thread_exit. Running thread is terminated.
3. Running thread blocks, with call to wchan_sleep.
4. Running thread is preempted. Involuntarily stops running.

Thread States

1. Running. Currently executing.
2. Ready. Ready to execute.
3. Blocked. Waiting for something, not ready to execute.

Timesharing and Preemption

• Timesharing. Concurrency achieved by rapidly switching between theads.
  • How rapidly? Scheduling quantum.
  • Must have an upper bound on how long a thread can run before it must yield the CPU.
• How do you stop a running thread that never yields, blocks, or exits?
  • Preemption forces a running thread to stop running.
  • Thread library must have a means of “getting control”.
  • Normally accomplished using interrupts.
    • Thread library places a procedure called an interrupt handler.
    1. Creates a trap frame to record thread context at the time of the interrupt.
    2. Determines which device caused interrupt, device-specific processing.
    3. Restores saved thread context from trap frame and resumes execution of the thread.

Preemptive Scheduling

• Preemptive scheduler uses the scheduling quantum to impose a time limit on running threads.
• Periodic timer interrupts allow running time to be tracked.
• If thread run too long, timer interrupt handler preempts the thread by calling thread_yield.
• Preempted thread changes state from running to ready, and is placed on the ready queue.
• Scheduled quantum is reset each time a thread gets to run, no concept of leftover time.

OS/161 threads use preemptive round-robin scheduling.

Every time an interrupt is called, a trap frame is the first. Then the interrupt handler stack frame is called, followed by the normal context switching procedures.

When returning from the trap_frame, the original state is restored.

Locks (Mutex)

Before entering a critical section, acquire a lock. Upon leaving, release the lock.

Implemented in hardware because we need an atomic test-and-set.

Acquire(bool* lock) {
    while (Xchg(true, lock) == true);
}
Release(bool* lock) {
    *lock = false;
}

printf forces the execution of threads to be a certain way, and can hide race conditions in your code!

ARM

ARMTestAndSet(addr, value) {
    // Load value.
    tmp = LDREX addr
    // Store new value.
    result = STREX value, addr
    if (result == SUCCEED) return tmp
    return TRUE
}

Acquire(bool *lock) {
    while(ARMTestAndSet(lock, true) == true) {};
}

Spinlocks in OS/161

• “Spins” repeatedly until the lock is available.

  struct spinlock { volatile spinlock_data_t lk_lock; struct cpu* lk_holder; };

  void spinlock_init(struct spinlock* lk); void spinlock_acquire(struct spinlock* lk); void spinlock_release(struct spinlock* lk);

spinlock_acquire calls spinlock_data_testandset in a loop until the lock is acquired. It turns off interrupts on the cpu.

Spinlocks are not efficient, if we want large chunks of code protected, we should use a lock (mutex). The difference is that spinlocks spin, locks block.

Thread Blocking

• When a thread blocks, it stops running.
  • Context switch from blocking thread to a new thread.
  • Waits.
• Eventually, a blocked thread is signaled and awakened by another thread.

Wait Channels in OS/161

Wait channels are used to implement thread blocking.

void wchan_sleep(struct wchan* wc);
void wchan_wakeall(struct wchan* wc);
void wchan_wakeone(struct wchan* wc);
void wchan_lock(struct wchan* wc);

• Blocks calling thread on wait channel wc.
• Unblocks all threads sleeping on wait channel.
• Unblock one thread sleeping on wait channel.
• Prevent operations on wait channel.

Semaphores

• A semaphore is an object with an interger value, supporting two operations.

1. P: If the semaphore value is greater than 0, decrement. Otherwise wait until we can.
2. V: Increment the value of the semaphore.

P and V are atomic.

• Binary semaphore. Single resource, behaves like a lock but does not keep track of ownership.
• Counting semaphore. Arbitrary number of resources.

Example.

volatile int total = 0;
struct semaphore *total_sem;
total_sem = sem_create("total_mutex", 1);

void add() {
    int i;
    for (i = 0; i < N; ++i) {
        P(sem);
            total++;
        V(sem);
    }
}

Condition Variables

• Condition variable is intended to work together with a lock. Only available from within the critical section that is protected by the lock.
  • wait. Causes calling thread to block, releases the lock associated with condition variable. Reaquires lock once thread is unblocked.
    • Release lock and put me to sleep.
    • Acquire lock and return.
    • Note. Implementation of cv_wait will be asked on examinations.
    • MESA Style Rough Steps. lock wchan, release lock, sleep, acquire luck
    • Note. Reccomended to use CV on traffic question.
  • signal. If threads are blocked on signaled condition variable, one of the threads are unblocked.
  • broadcast. Like signal, but unblocks all threads blocked on that variable.

A1 Hint Aside

1. Implement locks.
2. Implement condition variables.
3. Traffic simulation.
   • Improve flow of cars through the intersecation, currently only implements one car at a time.
   • Modify synchonization with locks, CVs, semaphores.
     • Semaphores are not recommended. CVs are.

• You don’t need an individual lock for each CV.
• You are not going to own the lock as you go through the intersection.
• Need to check safely whether the car can enter the intersection and safely remove once they are out of the intersection.
  • Lock is used to protect the modification of the intersection, not for actually going through.
• Recommended number of CVs is 4.

Multiple ways to to keep track of where cars are in the intersection.

• OS/161 provides an array, queue, and a few other data structure libraries. Documentation can be found in the test directory.
  • Possible to do with simply counters.
• Can’t use wait channels directly.
• Don’t modify traffic.c

sy2, uw1, sy3 are the tests to run.

• Initialize your lock variables for CV.

Volatile and Race Conditions

• Race conditions are mostly your fault, but they can also come from the compiler and CPU.
  • Optimizations.
  • Memory models describe how threads access to memory in shared regions behave. Tells compiler and CPU which optimizations can be performed.
    • OS/161 does not have this.
    • CPU also has memory model which re-orders loads and stores. There are assembly level barriers to prevent race conditions at each level.
  • Register optimizations.
• Keyword volatile disables the optimizations forcing a value to be loaded and stored to memory with each use. Prevents compiler from re-ordering loads and stores for that variable.

Deadlocks

lock lock_a, lock_b

int FuncA() {
    lock_acquire(lock_a);
    lock_acquire(lock_b);
    ...
    lock_release(lock_a);
    lock_relase(lock_b);
}

int FuncB() {
    lock_acquire(lock_b);
    lock_acquire(lock_a);
    ...
    lock_relase(lock_b);
    lock_release(lock_a);
}

• Multiple threads are asleep waiting for each other. Deadlock.

1. No Hold and Wait. Prevent a thread from requesting resources if it currently has resources allocated to it. Either get them all at once, or have none.
2. Resource Ordering. Order the resource types and require each thread acquire resources in increasing type order.

Example.

lock A, B

try_acquire() {
    spin_acquire(lk->spin);
    if (lk->held) {
        release(lk->spin);
        return false;
    }
    lk->held = true;
    lk->owner = me;
    release(lk->spin);
    return true;
}

FuncA() {
    acquire(A)
    while(!try_acquire(B)) {
        release(A);
        acquire(A);
    }
}