CS 140, Project 1 Review Session

Review

Threads

• In computing and Operating Systems, a thread is a stream of execution of programmed instructions.

• A thread is associated with an execution context that includes the thread stack along with the values of key registers that determine the thread’s stack pointer, address space and other associated context.

• Context switching

• Pintos

  • struct thread (thread.h)

Scheduling

• In operating systems, the method of deciding which thread or process to run and what times
• David covered basic scheduling policies in the lecture on Wednesday
• Balance fairness, priority, deadlines, throughput and efficiency

Synchronization

• Preemptive scheduling and synchronization

  • Synchronization is important to prevent race conditions
  • Race conditions and issues of concurrency in general will be covered in more depth in class on Monday
  • For now, you should know that a race condition is a flaw in software that causes the correctness of a program to be dependent on the uncontrolled timing or sequence of events.

  • Two threads modifying the same address in memory will result in non-deterministic behavior

  • Methods of synchronization

  • Disabling interrupts
  • Synchronization primitives (synch.{h,c})

Project

Pintos

• Pintos is an Operating System created by Ben Pfaff.

• If you so wanted, you could run pintos on straight up x86 hardware, but to make your life easier, we are using hardware emulators:

  • Qemu
  • Bochs

• For the threads project, you’ll be working entirely under the threads directory of the pintos starter code

• Exception: timer.c in devices to get Alarm Clock to work

Getting Started

• follow instructions on the website
• set path appropriately
• To build, run

  “make” in pintos/src/threads

• To run, run

  “make check” in pintos/src/threads/build

  • 7/27 tests should pass off the bat

• pintos run

TODO

Alarm Clock

• Modify timersleep(int64t ticks) in timer.c
  • currently busy waits
  • instead, it should put the thread to sleep and wake it when enough time has elapsed
  • testing suite already passes a lot of the alarm clock tests

Priority Scheduling

• Implement priority scheduling

  • Each thread has one of 64 possible priority levels
  • The current scheduler just does round robin
  • Modify to run the highest priority thread that can run
  • Files: thread.{h,c}

• All cases:

  • when scheduling, select highest priority thread
  • if a thread’s priority is lowered, it should yield
  • if a higher priority wakes up (say after waiting on a lock) it should preempt lower priority threads

• Priority donation (problem: priority inversion):

  • L acquires a lock X
  • H becomes ready, preempts L and starts running
  • H attempts to acquire X

  • All threads with priority above L will run before H

  • Donation:

  • when H starts waiting on the lock that L is holding, it temporarily donates its priority to L such that L runs with H’s priority until it releases lock L

  • Handle:

    • nested donations
    • multiple donations

Advanced Scheduler

• BSD scheduler
  • Computes statistics about each thread during execution in order to set each thread’s priority
  • simpler in many ways than priority donation
  • simple algebra

Advice

• think about design before you start coding
• meet as a group and integrate often
• use source control (git)