Operating Systems – CSCI 402
5.2 Interrupts
32
321 0
Copyright ý . Systems – CSCI 402
Interrupt Handling – Overview
Interrupt Handling
Deferred Work
Directed Processing
APCs Signals
Interrupts
Threads
Thread preemption
33
321 0
Copyright ý . Cheng
3) an interrupt handler running on the same processor that accesses the same data structure
4) an interrupt handler running on another processor might access the same data structure
34
12 INT
Futex is a solution to (1) and (2)
let¡¯s look at (3) and (4) now (kernel only)
INT
Operating Systems – CSCI 402
Thread Synchronization
Recall asynchronous activies that may require concurrency control 1) another thread running on the same processor may preempt
this thread and accesses the same data structure
2) another thread running on another processor might access the same data structure
mutex Memory
34
321 0
Copyright ý . Systems – CSCI 402
Interrupt Handling
We are focusing on dealing with synchronization/concurrency issues
What to do if you have non-preemption kernels?
in these systems, a kernel thread can never be preempted by another thread
may switch to interrupt context, but return to same thread threads running in privileged mode yield the processor only voluntarily
this makes the kernel a lot easier to implement!
because don¡¯t have to implement locking inside the kernel for every shared data structure (although sometimes, mutex is still needed to synchronize kernel threads)
done in early Unix systems done in weenix
this is like your kernel 1 with DRIVERS=1 in Config.mk
use interrupt masking to access variables shared with ISRs 35
321 0
Copyright ý . Systems – CSCI 402
Interrupt Handling
What to do if you have preemption kernels?
threads running in privileged mode may be forced to yield the processor
so you disable preemption
then you can use interrupt masking
for multiple CPUs, use a spin lock to lock out other CPUs
How do you disable preemption?
just use a global variable
before you preempt a kernel thread, check this global flag if the flag says preemption is disabled, don¡¯t preempt CurrentThread
36
321 0
Copyright ý . Systems – CSCI 402
Interrupt Masking
Unmask interrupts interrupt current processing (if interrupt is pending)
What causes interrupts to be masked?
the occurrence of a particular class of interrupts masks further occurences
i.e., inside an interrupt service routine (ISR)
explicit programmatic action
some architectures impose a hierarchy of interrupt levels
e.g., Intel architectures use APIC (Advanced Programmable Interrupt Controller)
37
321 0
Copyright ý . -Preemptive Kernel Synchronization
int X = 0;
void AccessXThread() {
…
X = X+1;
… }}
void AccessXInterrupt() {
…
X = X+1; …
Operating Systems – CSCI 402
34
12
INT INT
Copyright ý . Cheng
mutex Memory
38
321 0
Non-Preemptive Kernel Synchronization
int X = 0;
void AccessXThread() {
…
X = X+1;
… }}
Sharing a variable between a thread and an interrupt handler
since we have a non-preemptive kernel, the only thing that can prevent a kernel thread from executing till completion is an interrupt
The above code does not work
cannot use locks to fix it
analogous to cannot use mutex inside a signal handler
321 0
void AccessXInterrupt() {
…
X = X+1; …
Operating Systems – CSCI 402
39
Copyright ý . Cheng
}
Non-Preemptive Kernel Synchronization
int X = 0;
void AccessXThread() {
int oldIPL;
oldIPL = setIPL(IHLevel);
X = X+1;
void AccessXInterrupt() {
…
setIPL(oldIPL);
Solution is to mask the interrupt
X = X+1;
… }
this is analogous to the solution in Ch 2 to mask signals seems to work well in a non-preemptive kernel
let¡¯s look at something more realistic
Q: what data structures do you really share between
thread code and an interrupt service routine? A: an I/O queue and the RunQueue
321 0
40
Operating Systems – CSCI 402
Copyright ý . Cheng
int disk_write(…) {
…
startIO(); // start disk operation
…
enqueue(disk_waitq, CurrentThread);
thread_switch();
// wait for disk operation to complete
… }
void disk_intr(…) {
thread_t *thread;
…
// handle disk interrupt
…
thread = dequeue(disk_waitq);
if (thread != 0) {
enqueue(RunQueue, thread);
// wakeup waiting thread
}
… }
File System
Operating Systems – CSCI 402
More Relistic Example: Disk I/O
App
write()
disk_write()
41
321 0
Copyright ý . Cheng
1
startIO(); // start disk operation
…
enqueue(disk_waitq, CurrentThread); before enqueue() thread_switch(); this is a synchronization
// wait for disk operation to compplreobtlem / race condition …
2
}
void disk_intr(…) {
thread_t *thread;
…
// handle disk interrupt
…
thread = dequeue(disk_waitq);
if (thread != 0) {
enqueue(RunQueue, thread);
// wakeup waiting thread
}
… }
More Relistic Example: Disk I/O
int disk_write(…) {
…
Problem
disk may be too fast disk_intr() gets called
Operating Systems – CSCI 402
42
321 0
Copyright ý . Disk I/O
int disk_write(…) {
… Solution
// wait for disk operation to complete
setIPL(oldIPL);
… }
Operating Systems – CSCI 402
int oldIPL = setIPL(diskIPL);
startIO(); // start disk operation
…
enqueue(disk_waitq, CurrentThread);
thread_switch();
mask disk interrupt
43
321 0
Copyright ý . Cheng
int oldIPL = setIPL(diskIPL);
startIO(); // start disk operation
…
enqueue(disk_waitq, CurrentThread);
thread_switch();
mask disk interrupt
// wait for disk operation to complete
setIPL(oldIPL);
… }
Doesn¡¯t quite work!
thread_switch() will switch to another thread and won¡¯t return back here any time soon to unmask interrupt
who will enable the disk interrupt?
complication caused by the fact that thread_switch() does not function like a normal procedure call
moving setIPL(oldIPL) to before thread_switch()
may have race condition in accessing the RunQueue Copyright ý . Cheng
321 0
44
Operating Systems – CSCI 402
Improved Disk I/O
int disk_write(…) {
… Solution
Modified thread_switch
Operating Systems – CSCI 402
void thread_switch() {
thread_t *OldThread;
int oldIPL;
oldIPL = setIPL(HIGH_IPL);
// protect access to RunQueue by
// masking all interrupts
while(queue_empty(RunQueue)) {
// repeatedly allow interrupts,
// then check RunQueue
setIPL(0); // unmask all interrupts
setIPL(HIGH_IPL);
}
// We found a runnable thread
OldThread = CurrentThread;
CurrentThread = dequeue(RunQueue);
swapcontext(OldThread->context,
CurrentThread->context);
setIPL(oldIPL);
}
IMPORTANT: must only access RunQueue when all interrupts are blocked
because RunQueue is accessed in all interrupt handlers
You can (and should) use this in kernel 1
321 0
45
Copyright ý . thread_switch
void thread_switch() {
thread_t *OldThread;
int oldIPL;
oldIPL = setIPL(HIGH_IPL);
This code is actually much more tricky that it looks
it can be invoked by a thread that¡¯s not doing I/O
// protect access to RunQueue by
oldIPL is the oldIPL of a // masking all interrupts
different thread!
// repeatedly allow interrupts,
// then check RunQueue
setIPL(HIGH_IPL);
}
// We found a runnable thread
while(queue_empty(RunQueue)) {
OldThread = CurrentThread;
CurrentThread = dequeue(RunQueue);
setIPL(oldIPL);
}
You can use this in kernel 1 & 2
thread and set IPL to 0 (disk interrupt enabled)
CurrentThread->context);
calls thread_switch() it¡¯s not doing I/O
its oldIPL is set to 0
Operating Systems – CSCI 402
Stack
Thread object
setIPL(0); // unmask all interrupts
Let¡¯s say that another thread
Stack
Thread object
swapcontext(OldThread->context,
Now we call thread_switch() our oldIPL set to diskIPL
then we switch to this other
46
321 0
Copyright ý . thread_switch
void thread_switch() {
thread_t *OldThread;
int oldIPL;
oldIPL = setIPL(HIGH_IPL);
// protect access to RunQueue by
// masking all interrupts
while(queue_empty(RunQueue)) {
// repeatedly allow interrupts,
// then check RunQueue
setIPL(0); // unmask all interrupts
setIPL(HIGH_IPL);
}
// We found a runnable thread
OldThread = CurrentThread;
CurrentThread = dequeue(RunQueue);
swapcontext(OldThread->context,
CurrentThread->context);
setIPL(oldIPL);
}
Problem – busy waiting
can take a long time to get an interrupt
the correct way to wait is to wait while sleeping since there¡¯s nothing to run, should halt the CPU
Note:
it¡¯s okay to do this in kernel 1 and kernel 2
this wont¡¯ work for kernel 3
Operating Systems – CSCI 402
You can use this in kernel 1 & 2
321 0
47
Copyright ý . thread_switch
void thread_switch() {
thread_t *OldThread;
int oldIPL;
oldIPL = setIPL(HIGH_IPL);
// protect access to RunQueue by
// masking all interrupts
while(queue_empty(RunQueue)) {
// repeatedly allow interrupts,
// then check RunQueue
setIPL(0); // unmask all interrupts
HLT // enable interrupt & halt CPU
setIPL(HIGH_IPL);
}
// We found a runnable thread
OldThread = CurrentThread;
CurrentThread = dequeue(RunQueue);
swapcontext(OldThread->context,
CurrentThread->context);
setIPL(oldIPL);
}
If you decide to halt the CPU in weenix, need to watch out for a race condition
this code does not “wait” properly
the correct way to wait for an asynchronous event is:
1) disable/block it
2) if event hasn¡¯t ocurred, enable/unblock and wait for it in one atomic operation
Note:
you have to do it this way (and fix the race condition) for kernel 3
or live with the possibility of system freezing
321 0
Operating Systems – CSCI 402
48
Copyright ý . Cheng
the same data structure
3) an interrupt handler running on the same processor that
accesses the same data structure
4) an interrupt handler running on another processor might
access the same data structure
34
12
INT INT
Operating Systems – CSCI 402
Preemptive Kernels & Multiple CPUs
What¡¯s different?
Recall asynchronous activies that may require concurrency control 1) another thread running on the same processor may preempt
this thread and accesses the same data structure
2) another thread running on another processor might access
mutex Memory
49
321 0
Copyright ý . Cheng
void AccessXThread() {
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
void AccessXInterrupt() {
…
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Does it work?
Solution?
int X = 0;
SpinLock_t L = UNLOCKED;
no, can deadlock in AccessXInterrupt() in case (1) when thread code and interrupt handler runs on the same processor
321 0
Operating Systems – CSCI 402
50
Copyright ý . = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Operating Systems – CSCI 402
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Does it work?
34
12
INT INT
mutex Memory
51
321 0
Copyright ý . = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Operating Systems – CSCI 402
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Does it work?
34
12
INT INT
mutex Memory
52
321 0
Copyright ý . = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Operating Systems – CSCI 402
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Does it work?
34
12
INT INT
mutex Memory
53
321 0
Copyright ý . Cheng
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
X = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Operating Systems – CSCI 402
Does it work?
34
12
INT INT
Copyright ý . Cheng
mutex Memory
54
321 0
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
X = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Operating Systems – CSCI 402
Does it work?
yes
order is important
13
24
INT INT
Copyright ý . Cheng
mutex Memory
55
321 0
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
X = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
Can we switch the order of DisablePreemption() and MaskInterrupts()?
if you mask interrupt first, what would happen if you switch to a thread what would mess with interrupt masking?
Operating Systems – CSCI 402
56
321 0
Copyright ý . Cheng
void AccessXThread() {
DisablePreemption();
MaskInterrupts();
SpinLock(&L);
void AccessXInterrupt() {
…
X = X+1;
SpinUnlock(&L);
UnMaskInterrupts();
EnablePreemption();
}
SpinLock(&L);
X = X+1;
SpinUnlock(&L);
…
}
What X are we really talking about?
Solution …
int X = 0;
SpinLock_t L = UNLOCKED;
it may be the RunQueue (use highest IPL)
it may be the I/O queue (use appropriate IPL)
it may be a futex queue (no need to mask interrupt)
Operating Systems – CSCI 402
57
321 0
Copyright ý . Systems – CSCI 402
Interrupt Threads?
Solaris allows interrupts to be handled as threads
Does it make sense to handle interrupts with threads?
perhaps similar to using sigwait for handling signals with threads
what would be the advantages?
what would be the disadvantages?
58
321 0
Copyright ý . Systems – CSCI 402
Interrupt Threads
void InterruptHandler( ) {
// deal with interrupt
…
if (!MoreWork)
return;
else
BecomeThread( );
…
P(Semaphore); // sleep!
… }
59
321 0
Copyright ý . Systems – CSCI 402
Interrupt Threads In Action
Thread¡¯s Frames
Thread Control Block
Copyright ý . Cheng
2 1
3
Interrupt Handler¡¯s Frames
Interrupted Context
Thread Control Block
60
321 0