Windows NT Systems Programming: Spring 2000

[ Home | Syllabus | Course Notes | Assignments | Search]

Thread/Synchronization

Why Threads?

Unblocks user interface - compute in background but sitll respond to mouse and keyboard
Simplify coding - only worry about single client (don't need to multiplex)
Handle high priority tasks
Multiple CPUs - SMP (Symmetrical MultiProcessor supported based on threads)
Shared Address Space - Threads have high bandwidth communications through memory
Less overhead than a process - same virtual memory management
Multiple Clients = multiple threads OR multiple Transactions

ThreadClient2.jpg (41019 bytes)

Shared Address Space

PROCESS GLOBAL: All threads in a process share data

Global variables
volatile - tells system not to store data in registers - always write to memory
HEAP

THREAD LOCAL: Each thread has a private stack for local variables, function calls.
THREAD GLOBAL (TLS): WIN32 API also supports global name space limited to a single thread

Thread States

Running
Highest Priority Ready to Run Thread
Ready to Run
Waiting
- SLEEP
- Wait I/O
- Wait SOCKET
- Wait Synchronization
  - Wait Event
  - Wait SEMAPHORE
  - Wait MUTEX
  - WAIT CRITICAL SECTION

threadState2.jpg (55576 bytes)

Creating a Thread

Thread runs a special function with one parameter.
This parameter can be a pointer to any arbitrary data structure.

Waiting for a thread to finish

WIN32 supports a general WaitFor mechanism which works for many different kinds of events.

Thread safe functions

PROBLEM: writing functions which can be simultaneously used by multiple threads. The difficulty is the use of global variables. Simultaneous access to the same global variable can cause failures.
Also call by reference with shared objects.

Many systems libraries were designed in a single thread environment. Need to use thread-safe versions. OR use thread synchronization.

Related to re-entrant code.

Consider the following example for incrementing a global variable "x" in a function called by multiple threads more or less simultaneously.

x++;

Even this simple statement is NOT atomic in most implementations - on many machines, the compiler will generate code something like this:

LOADREGISTER	X,A	// load register A with value stored in memory labeled X
ADD		=1,A	// Add literal 1 to value in register A
STOREREGISTER   A,X     // Store value in register A to memory location X

If one thread executing this c++ instruction is interrupted after the Load but before the store and another thread calls the same function, the value of X will be wrong (e.g. say "X" is initially 3, first thread stores "3" in register A but is interrupted before storing it back in "X", second thread finds the value of 3 in memory location "X", increments and stores "4" in "X", then first thread resumes and stores "4" in "X" also, the value of "X" is off by one.

Let's run some experiments to show the problem. The design of revealing experiments is critical in gaining an understanding of large complex systems.

Single Thread/Process Global Variable

(Source Code is here)

// ...
#include <windows.h>	// for defining HANDLE, Sleep 

const int SLEEP_TIME = 1000;

int global1; // file global 
// This variable is accessible by all functions in this file
// this program demonstrates that the main thread can change the value that
// the "testThread" thread sees

void testThread(int* myId ); // thread prototype


void main()
{
	HANDLE testHandle; 
	DWORD threadId;
	int id = 1;

	global1 = 33;
	testHandle = CreateThread  (0, // no child process cannot inherit
			0, // gives same stack space as parent thread
			(LPTHREAD_START_ROUTINE) testThread,
			&id, // Pass in one parameter
			 0,  // Put into ready Q
			&threadID);  // system wide thread ID
	Sleep  (SLEEP_TIME);	// sleep for one second - give thread a chance
	global1 = 55;
	WaitForSingleObject(testHandle, INFINITE); 
}

void testThread(int* myId) 
{
	cout << "Started Thread ID: " << *myId << endl;
	cout << "BEFORE: Global1 is: " << global1 << endl;
	Sleep(2*SLEEP_TIME);	// give main thread chance to change global1
	cout << "AFTER: Global1 is: " << global1 << endl;
	
}

What will the output?

Multiple Threads/Global Variable

(Source Code is here)

void testThread(DWORD myId);

void main()
{
	HANDLE testHandles[2];

	testHandles[0] = CreateThread(0,0,
		(LPTHREAD_START_ROUTINE) testThread,
		(void*)id, 0, &threadId);
	id++;
	testHandles[1]  = CreateThread(0,0,
		(LPTHREAD_START_ROUTINE) testThread,
		(void*)id, 0, &threadId);
	Sleep(SLEEP_TIME);	// sleep for one second
	WaitForMultipleObjects(2, testHandles, TRUE /* wait for all */, INFINITE); 
}

// Separate file
//**** all threads started with this code will share the file global variable "global2"
// demonstrates that two instances of testThread both access the same variable
// and thus can potentially interfere with each other/ (Race condition - one of the
// complexities of writing distributed systems code)

int global2 = 12345;

void testThread(DWORD myId)
{
	int id = myId; 

	cout << "Started Thread ID: " << id << endl;
	cout << "BEFORE: Global2 is: " << global2 << endl;
	global2 = id; 
	Sleep(id*SLEEP_TIME);	// give other thread chance
	cout << "AFTER: Global2 is: " << global2 << endl;
	
}

// What will be the output?
// does it matter if the two threads sleep differently?

Thread Local Storage (TLS)

(Source Code is here)

DWORD tlsIndex;

void testThread(int* myId);

void main()
{
// . . .
	tlsIndex = TlsAlloc(); 
//tls gives each thread a private global variable
	testHandles[0] = CreateThread(0,0,
		(LPTHREAD_START_ROUTINE) testThread,
		&id, 0, &threadId);
	
	Sleep(SLEEP_TIME); // give first thread a chance to save its parameter 
//. . . separate file for thread code

extern DWORD tlsIndex; 

void checkGlobal(int); 

void testThread(int* myId)
{
	int id = *myId; 
	int global3 = id;
	TlsSetValue(tlsIndex, &global3); 

	checkGlobal(id);
	
}

void checkGlobal(int id)
{
	int* tls; 

	tls = (int*) TlsGetValue(tlsIndex); 
	cout << "BEFORE: Global3 is: " << *tls << endl;
	*tls = id*1000;
	Sleep(id*SLEEP_TIME);	// give main thread chance to change  global1
	cout << "AFTER: Global3 is: " << *tls << endl;
}

// What output?
// does the timing matter?