Transcript presentation source

Chapter 6 (6.7 & 6.9 only) Threads & Mutex
• Threads
– A Thread is a basic unit of CPU utilization
consisting of a program counter, register set and
stack space.
– Remaining resources (memory space and
operating system resources, such as open files)
are shared with peer threads within the same
process.
– A thread is a lightweight process.
• By sharing a single process’ memory space and
O/S objects a program written with multiple
threads requires less overhead at context switch
time. This can lead to more efficient use of the
CPU for multi-threaded applications.
• Figure 6.10: Example of two multi-threaded
processes.
• Threads can execute the same code with different
contexts (different register sets, stack & program
counter).
• A process has at least one thread.
• Extend SOS to support threads through three new
calls:
– int CreateThread(char *startAddr, char *startStack) start a new thread; code begins at startAddr and the
stack it will use is at startStack. Call returns a Thread
ID (tid).
– int ExitThread(int returnCode) - similar to a process
Exit() call, except the last thread of a process, where
it is exactly the process Exit() call.
– int WaitThread(int tid) - block the calling thread until
the thread specified by tid calls ExitThread().
• Stack management is the responsibility of the
thread creator (except for the first thread).
• Advantages of Threads
– Provide parallel (possibly pseudo-parallel)
programming.
– Cheaper to create and destroy.
– Cheaper to context switch between.
– By definition they share memory, meaning sharedmemory based IPC is a natural and slow system calls
are not needed to communicate.
– Good for parallel algorithms that are tightly coupled
and that use the same data structures.
– Common term: multi-threaded server.
• Uses of threads
– Partition the activities of a single process (Figure
6.11).
– Permit asynchronous I/O within a process -- have a
thread wait for the I/O to complete.
– Activity replication -- a server process can create
threads on demand as services are requested. Great
example - a multi-thread web server. Another
example: disk block server (Figure 6.12).
• Thread implementation (6.7.5): not covered.
• Process - has its own address space and is
allocated CPU time.
• Process with threads - split out the concept of
CPU allocation into the thread, leaving the
process as a shell to hold everything else.
• Threads can be implemented in the operating
system or they can be implemented totally within
a user process (called user threads).
• A user process does not need to be in system
mode and use special instructions to swap stack
pointers and register sets. A timer helps, though.
• User threads are more efficient (no O/S switch).
• A process running user threads may run more
efficiently but can’t take advantage of any O/S
thread calls, since the O/S isn’t aware of the userlevel threads.
• Kernel threads are threads designed to run within
the O/S itself.
• Examples of Threads:
– O/S-level threads are built into Mach, Solaris, OS/2,
Windows NT & most modern UNIXes.
– User-level threads can be found all over. Of note -the Java language runtime supports threads. By
extension this means Java-aware browsers also
implement user-level threads (Netscape, MSIE, etc.).
• Java Threads (taken from chapter 15 of The Java
Tutorial).
– JavaSOS uses Java threads, so it’s worth covering
their specifics.
– Java thread definition: a single sequential flow of
control within a program.
– The Thread class is provided in the java.lang
package.
– You can either extend the Thread class or in the case
of a class already being extended (like the Applet
class) you can say the class implements Runnable.
– Either way you can then override a number of Thread
class methods that affect thread behavior.
• Example using extends:
class SimpleThread extends Thread {
public SimpleThread(String str) { super(str); }
public void run() {
for (int i = 0; i < 10; i++) {
System.out.println(i + “ “ + getName());
try { sleep((int) (Math.random() * 1000));
} catch (InterruptedException e) {}
}
System.out.println(“DONE! “ + getName());
}
}
• Example creating two instances of SimpleClass
and running them:
class TwoThreadsTest {
public static void main (String[] args) {
new SimpleThread(“Jamacia”).start();
new SimpleThread(“Fiji”).start();
}
}
– Notice use of overridden Thread method run().
• Example using implements:
Class Clock extends Applet implements Runnable {
public void start() {
if (clockThread == null) { // if applet just loaded
clockThread = new Thread(this, “Clock”);
clockThread.start();
}
}
public void stop() { clockThread = null; }
public void run {
while (Thread.currentThread() == clockThread) {
repaint(); // (sleep w/ exception handling) //
} }
• JavaSOS uses implements Runnable for the Java
threads. Check these files:
AppGUICounter.java, AppTests.java - the three user-level
applications are all Java threads.
HWSimulation.java:class HWSimulatedDisk
HWSimulation.java:class HWTimer
SOSStart.java:class SOSStart
• JavaSOS uses the suspend() and resume() methods of
the Thread class to block one process and start another
one running.
• Implementation of Mutual Exclusion
– Two prior solutions to the mutex problem: use of
Message Queues & that pesky ExchangeWord()
(more on this later).
– 1st solution - disable interrupts while the process is in
a critical section (no interrupts == no timer interrupt
== no context switch to some other process). Book
mentions it works well on a single-processor
machine, but neglects the downside of having a user
program running with interrupts disabled!
– 2nd solution - Use ExchangeWord(): a special
hardware instruction that allows one processor to
read and modify a word in memory without any other
processor getting access (atomic read & modify).
• Implementation of Mutual Exclusion
– Good for multiprocessor mutex solutions; exists in different forms, such as
“Test and Set”.
• Software Solutions - no special hardware instructions exist to
enforce the mutex.
• First solution by Dekker in 1965; complex.
• A simpler solution done by Peterson in 1981. Imagine two
processes, each with the same structure:
void Processn(void) {
while (1) {
DoSomeStuff();
EnterCriticalSection(0);
DoCriticalSectionStuff();
LeaveCriticalSection(0);
}
}
• To work, the processes have to agree that:
–
–
–
–
A process will not wait forever in EnterCriticalSection().
Only one process at a time can be in the critical section.
A process will spend a finite time in the critical section.
A process that wants to enter its critical section cannot be made to wait for
the other process to enter its critical section.
enum { False = 0; True = 1; };
int interested[2] = {False, False};
int turn = 0;
void EnterCriticalSection(int this_process) {
int other_process = 1 - this_process;
interested[this_process] = True;
turn = this_process;
while (turn == this_process && interested[other_process]) {
// do nothing (busy loop)
}
}
void LeaveCriticalSection(int this_process) {
interested[this_process] = False;
}
– This algorithm works with two processes contending for the critical section
and it also works if there’s only one process.
– It’s important you understand how this code works!
• Disabling Interrupts
–
–
–
–
Fast!
No busy waiting!
Uniprocessor-only solution!
Best solution for a single processor (with the exception you don’t want the
interrupts to be disable-able within user mode).
• Using ExchangeWord()
–
–
–
–
Busy waiting :(
Requires hardware assistance (memory subsystem) :(
Works with multiple processors!
Best solution for shared memory multiprocessors.
• Peterson’s algorithm (software-only solution)
–
–
–
–
Busy waiting :(
No hardware assistance required!
Works with multiple processors!
Best solution for distributed systems with no centralized control.