Lecture Topics
• Multiprocessors and locks
• Spin locks
MP1 Handin and Demo Schedule
• Code must be committed to master/main branch on GitLab by
– 9:59AM on 2/18 (11:59PM on 2/18 for ZJUI)
• Handin Demo
– Monday 2/22, Starts at 6 PM: All ZJUI Students and Last names from A to J
– Tuesday 2/23, Starts at 6 PM: Last names from K to Z
Aministrivia
• PS2 Posted
Multiprocessors and Locks
• We solved the critical section problem for uniprocessors
• What about multiprocessors?
– CLI … critical section …. STI
• What is a multiprocessor?
– usually a symmetric multiprocessor (SMP)
bus
– symmetric aspect: all processors have equal latency to all memory banks
– multicore processors are similar from our perspective
P
P
P
P
M
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
M
I/O
I/O bus
Multiprocessors and Locks (cont.)
• Some non-uniform memory architecture (NUMA) machines were built
P
P
P
P
com
com
P
P
P
P
bus
bus
M
M
I/O
I/O
M
M
© Steven Lumetta, Zbigniew Kalbarczyk
ECE391
I/O bus
I/O bus
Multiprocessors and Locks (cont.)
• Multithreaded code is not protected by IF
• Why haven’t we solved the atomicity problem on
multiprocessors?
– interrupts are masked if IF is cleared!
– answer: IF is not cleared on other processors!
– just tell other processors to clear IF, too?
• too slow
• requiresaninterrupt!
• We need to use shared memory to synchronize…
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Multiprocessors and Locks (cont.)
• Logically, we use a lock
– when we want to access a piece of shared data we first look at the lock
– if it’s locked, we wait until it’s unlocked
(locked state is often represented
as 1)
– once it’s unlocked
• we lock it
• access the data
• then unlock it
(unlocked state is often represented
as 0)
shared data
© Steven Lumetta, Zbigniew Kalbarczyk
ECE391
shared data
Multiprocessors and Locks (cont.)
• Locking must be atomic with respect to other processors!
INCL (%EAX)
LOCK: Prefix – execute following instruction with bus locked
LOCK INCL(%EAX)
P1
write
read
It’s MY BUS!
M
P2
read (%EAX) add 1
put it back
ECE391
An Example of Locking Implementation
/* The caller defines int lock. Calling TestAndSet (&lock) sets lock to 1 and returns the old value of lock. If lock is 0 then TestAndSet(&lock)returns 0 and sets the lock to 1. If the lock is already set to 1 by another process or thread, then 1 is returned. The caller keeps retrying TestAndSet(&lock) until it returns 0. */
TestAndSet:
……
pushl %ebx
movl 8(%ebp), %ebx # &lock to ebx
movl $1, %eax # 1 (true) to eax
# Swap eax and lock, value 1(true) is copied to lock, eax receives old lock value
xchg %eax, (%ebx)
#Atomically exchange eax with lock.
#The atomicity of xchg guarntees that at most
#one thread holds the lock at any point in time
#return value (old value of lock) is already in eax xchg => exchanges the contents of a register with the contents of any other register or memory location
popl %ebx
……
ret
Spin Locks
•
The simplest lock – spin lock
– lock op
do {
•
try to change lock variable from 0 to 1 } while (attempt failed);
– other work to do? ignore it!
– spin in a tight loop on the lock (hence the name)
Once successful, program/interrupt handler owns the lock © Steven Lumetta, Zbigniew Kalbarczyk ECE391
•
Only the owner can unlock – How?
• (change lock variable to 0) – Need to be atomic?
• (no, only owner can change when locked)
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Spin Locks (cont.)
• Static initialization
static spinlock_t a_lock = SPIN_LOCK_UNLOCKED;
• Dynamic initialization
spin_lock_init (&a_lock);
• When is dynamic initialization safe?
– lock must not be in use (race condition!)
– other synchronization method must prevent use
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux Spin Lock API
Linux Spin Lock API – Basic Functions
void spin_lock (spinlock_t* lock);
void spin_unlock (spinlock_t* lock);
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux Spin Lock API – Testing Functions
int spin_is_locked (spinlock_t* lock);
returns 1 if held, 0 if not, but beware of races!
int spin_trylock (spinlock_t* lock);
make one attempt; returns 1 on success, 0 on failure
void spin_unlock_wait (spinlock_t* lock);
wait until available (race condition again!)
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux Spin Lock API (cont.)
• Is spinlock enough to protect a critical section?
P1
code
lock
crit. sect.
unlock
try to get lock
(forced to wait)
gets lock
interrupt (P2)
P2
© Steven Lumetta, Zbigniew Kalbarczyk
ECE391
Linux Spin Lock API (cont.)
• What about ? code
lock
try to get lock (waits forever!)
• Still need CLI/STI
• Which is first, CLI or lock? – CLI first
called a deadlock
interrupt (P1)
P1
– interrupt may occur between them, leading to scenario above
© Steven Lumetta, Zbigniew Kalbarczyk ECE391
Linux’ Lock/CLI Combo
static spinlock_t the_lock = SPIN_LOCK_UNLOCKED;
unsigned long flags;
spin_lock_irqsave (&the_lock, flags);
/* the critical section */
spin_unlock_irqrestore (&the_lock, flags);
asm volatile (”
PUSHFL
POPL %0
CLI
” : “=g” (flags)
:
: “memory” );
/* outputs */ /*inputs */ /* clobbers */
spin_lock (&the_lock);
Linux’ Lock/CLI Combo (cont)
spin_unlock (&the_lock);
asm volatile (”
PUSHL %0
POPFL
” : /* outputs */
: “g” (flags) /* inputs */
: “memory”, “cc” /* clobbers */
);
© Steven Lumetta, Zbigniew Kalbarczyk ECE391