Class 21: Bakers and Philosophers

Posted: Tue 15 April 2014

Project Design Meetings are this week. Your team should come to the design meeting prepared to explain what you are doing for your project and why, what you have done so far, your plan for finishing, and any questions you have.

Your team should submit a Project Submission Option by Monday, 21 April (4:59pm). But, the earlier you submit the more likely you are to receive your first choice.

Readings

The recommended text has a full chapter on Concurrency, including:

Concurrency and Threads
Thread API
Locks
Lock-based Concurrent Data Structures
Condition Variables
Semaphores
Common Concurrency Problems
Event-based Concurrency

These sections cover some of the topics we covered in class, as well as many other relevant and interesting topics. Because they use C with the pthread library, some of the specifics are quite different from Rust programming but the main ideas are the same (and Sarah and Robert are working on rewriting some of them for their project).

The main topic of the next class will be OS design focusing on microkernels and beyond. Much of the material will be based on this paper: Kevin Elphinstone and Gernot Heiser, From L3 to seL4: What Have We Learnt in 20 Years of L4 Microkernels?, SOSP 2013.

Mutual Exclusion

Why is it worthwhile to study mutual exclusion protocols?

Why is it a waste of time to study mutual exclusion protocols?

How hard it is to invent a protocol that provides mutual exclusion without liveness guarantees?

How does Dijkstra prove mutual exclusion?

What assumption does Lamport's solution give up that Dijkstra's solution relies on?

comments powered by Disqus


Class 20: Mutual Exclusion

Posted: Thu 10 April 2014

PS4 Assessment due after your demo (by tomorrow at the latest)
Project Idea due by 11:59pm Thursday (tonight).

Mutual Exclusion

Requirements:

  1. Only one thread may be in the critical section at any time.
  2. Each must eventually be able to enter its critical section.
  3. Must be symmetrical (all run same program, cannot introduce static priority).
  4. Cannot make any assumptions about speed of threads.

What's "wrong" with this solution?

loop {
    if turn == i:     
         critical_section;
         turn = i + 1;
}

What's "wrong" with this solution?

loop {
    if not lock: 
         lock = true;
         critical_section;
         lock = false;
}

Test and Set

Atomic instruction that: - returns current value of v - sets value of v to true

How can you implement mutual exclusion using test-and-set?

ARM's Exclusion Instructions

LDREX dest location
     dest = location
     Sets monitor on location in Exclusive state

STREX success value location
     Conditionally store into exclusive .
     If permitted, = 1 and = .
     If not, = 0 and value unchanged.

Context switch clears monitor (Open) state.

ARM Synchronization Primitives

lock_mutex(lock):
try_again:    
        LDREX R2, [lock]
        if R2 goto try_again
        STREX R2, 1, [lock]
        if not R2 goto try_again

unlock_mutex(lock):
        STR [lock], 0

Why don't we need to use STREX in unlock?

How should this be different if we care about energy?

Dijkstra's Solution

   loop {         
         b[i] := false
L1:  if k != i 
               c[i] := true
                     if b[k]:
                          k := i
                  goto L1
         else:
               c[i] := false
               for j in [1, ..., N]:
                    if j != i and not c[j]:
                         goto L1  
               critical section;   
               c[i] := true
               b[i] := true    
    }

Why is this guaranteed to provide mutual exclusion?

How do we know threads will make progress?

Dijkstra's Cry for Generalization

comments powered by Disqus


Class 19: Synchronization (Tue 08 April 2014)

Submitting PS4 (Sat 05 April 2014)

Class 18: System Calls (Thu 03 April 2014)

PS3 Reference Solution (Wed 02 April 2014)

Class 17: Flash! (Tue 01 April 2014)

Class 16: Storage (Thu 27 March 2014)

Class 15: IronKernel Developers (Thu 20 March 2014)

Class 14: Entering Ring Naught (Tue 18 March 2014)

Exam 1 Comments (Sun 16 March 2014)

Class 13: The Internet (Thu 06 March 2014)

Class 12: Scheduling in Linux and Web Servers (Tue 04 March 2014)

PS3 Demos and Submission (Sun 02 March 2014)

Problem Set 3 Benchmarking (Fri 28 February 2014)

Class 11: Smarter Scheduling (Thu 27 February 2014)

Class 10: SSL, Sharing, and Scheduling (Tue 25 February 2014)

Class 9: Pointers in Rust (Tue 18 February 2014)

Problem Set 3 (Sun 16 February 2014)

PS2 Reference Solution (Fri 14 February 2014)

Class 8: Managing Memory (Tue 11 February 2014)

Updates (Sun 09 February 2014)

Submitting PS2 (Sat 08 February 2014)

Class 7: Double Faults (Thu 06 February 2014)

Class 6: Making a Process (Virtualizing Memory) (Tue 04 February 2014)

PS2 Demos, Videos (Mon 03 February 2014)

Class 5: Gash Has No Privileges (Thu 30 January 2014)

Class 4: Once Upon a Process (Tue 28 January 2014)

PS1 Submission (Sun 26 January 2014)

Class 3: Zero to a Billion in 4.86 Years (Thu 23 January 2014)

Survey Comments (Thu 23 January 2014)

Improving Rust's Error Messages (Wed 22 January 2014)

PS1 and Tutorial (Mon 20 January 2014)

Class 2: Getting Rustified (Thu 16 January 2014)

Class 1: What is an Operating System? (Tue 14 January 2014)

Spring 2014 cs4414 Course (Sat 11 January 2014)


Pages

  • Amazon EC2
  • Challenges
  • Forum
  • Getting Started with Github
  • IRC
  • Open Discussion Forum
  • Pages
  • Problem Set 3 - Zhtta Server - Benchmarking
  • Problem Set 0 - Tutorial and Course Registration
  • Problem Set 1 - zhttpto Web Server
  • Problem Set 2 - The Good Auld Shell
  • Problem Set 2 - Exploration 1
  • Problem Set 2 - Exploration 2
  • Problem Set 3 - Zhtta Web Server
  • Problem Set 4 - IronKernel
  • PS4 - Setup Commands
  • Open Enrollment
  • Survey Comments
  • Syllabus
  • Forum
  • Using Materials
  • Videos
  • VirtualBox
  • Working on Github in cs4414
  • Setting up your Zhtta Server on EC2