ECE 254 Notes


L01: Introduction to Operating Systems

L02: Review of Computer Architecture

L03: Operating System Structure and Traps


Motivation for Dual-Mode Operation

Invoking a System Call


L04: Processes

Process Creation

Process Destruction:

Process Family Tree

L05: Process State

Two State Model

Three State Model

Five State Model

Process on Disk: Seven State Model


L06: Processes in UNIX

Fork Bomb

L07: Inter-process Communication

Implementation Strategies

Shared Memory

File System

Message Passing

Message Queue


L08: Threads

Motivation for Threads

Thread Drawbacks

Thread States

Thread Cancellation

Thread Types

Advantages of ULT

Advantages of KLT

The Many-to-One Model

The One-to-One Model

The Many-to-Many Model

The One-to-Many Model?

L09: POSIX Threads

Thread Creation in Practice

pthread_create(pthread_t *thread, 
            const  pthread_attr_t *attributes,
            void *(*start_routine)(void *),
            void *argument);

Thread Attributes

Fork and Exec

UNIX Signals

Thread Cancellation

L10: Symmetric Multiprocessing (SMP)

Time Slicing

Parallelism and Speedup

Amdahl’s Law

$$ speedup \leqslant \frac{1}{S + \frac{1-S}{N} } $$
- can take limit to infinity and see what speedup converges on

L11: Concurrency: Synchronization and Atomicity

Serialization through Messages

Mutual Exclusion Through Flags

Test and Set

L12: Semaphores

Mutual Exclusion through Messages



Counting Semaphores

L13: Synchronization Patterns


Thread A

1. Statement A1
2. signal(sem)

Thread B

1. wait(sem)
2. Statement B2


Thread A                            Thread B
1. Statement A1                     1. Statement B1
2. signal(aArrived)                 2. signal(bArrived)
3. wait(bArrived)                   3. wait(aArrived)
4. Statement A2                     4. Statement B2

Mutual Exclusion

Thread A                            Thread B
1. wait(mutex)                      1. wait(mutex)
2. critical section                 2. critical section
3. signal(mutex)                    3. signal(mutex)



Thread K
1. wait(mutex)
2. count++
3. signal(mutex)
4. if count == n
5.  signal(barrier)
6. end if
7. wait(barrier)
8. signal(barrier)

The Reusable Barrier

Thread K
1. wait(mutex)
2. count++
3. if count == n
4.  wait(turnstile2)
5.  signal(turnstile1)
6. end if
7. signal(mutex)
8. wait(turnstile1)
9. signal(turnstile1)
10. [critical section]
11. wait(mutex)
12. count--
13. if count == 0
14. wait(turnstile1)
15. signal(turnstile2)
16. end if
17. signal(mutex)
18. wait(turnstile2)
19. signal(turnstile2)

L14: Classical Synchronization Problems

Producer-Consumer Problem

Producer                                        Consumer
1. [produce item]                               1. wait(items)
2. wait(spaces)                              2. wait(mutex)
3. wait(mutex)	                             3. [remove item from buffer]
4. [add item to buffer]                         4. signal(mutex)
5. signal(mutex)                                5. signal(spaces)
6. signal(items)                                6. [consume item]

Readers-Writers Problem

Writer                                      Reader
1. wait(turnstile)                          1. wait(turnstile)
2. wait(roomEmpty)                          2. signal(turnstile)
3. [write data]                             3. wait(mutex)
4. signal(turnstile)                        4. readers++
5. signal(roomEmpty)                        5. if readers == 1
                                            6.  wait(roomEmpty)
                                            7. end if
                                            8. signal(mutex)
                                            9. [read data]
                                            10. wait(mutex)
                                            11. readers--
                                            12. if readers == 0
                                            13.     signal(roomEmpty)
                                            14. end if
                                            15. signal(mutex)

Dining Philosophers Problem

L15: Deadlock

Thread P                        Thread Q
1. wait(a)                      1. wait(b)
2. wait(b)                      2. wait(a)
3. [critical section]           3. [critical section]
4. signal(a)                    4. signal(b)
5. signal(b)                    5. signal(a)

Reusable and Consumable Resource

Conditions for Deadlock

Dealing with Deadlock

Ignore It

Deadlock Prevention

L16: Deadlock Avoidance

Ordering of Resources

Stay Alert Stay Safe

Resource-Allocation-Graph Algorithm

Banker’s Algorithm

Other Recommendations

L17: Deadlock Detection and Recovery

General Deadlock Detection Algorithm

$$ \sum_{i=1}^{n} C_ij + A_j = E_j $$

Algorithm (ϴ(m * n 2 )

  1. Search for an unmarked process whose requests can all be satisfied with available resources in A
  2. If a process is found, add the allocated resources of that process to the available vector and mark the process.
  3. If no process was found in the search of step 1, algorithm terminates

When to Detect Deadlock

Deadlock Recovery


Mass murder


Time Travel


Victim Selection

Miscarriages of Justice

L18: Concurrency and Synchronization in POSIX

Concurrency with pthreads

Condition Variables


Concurrency Mechanisms in UNIX

Linux Kernel Concurrency Mechanisms

Atomic Operations


Counter Flag Interpretation
0 1 The spinlock is released and available
0 0 The spinlock has been acquired for writing
n (n>0) 0 The spinlock has been acquired for reading by n threads
n (n>0) 1 Invalid state