The concurrent execution of threads and processes in
Win32 is achieved by synchronization mechanisms.
Following methods/objects are used to achieve synchronization
Critical Section
– single process;
– non kernel object
Mutexes
Mutually Exclusive
Critical Section + Multi Processes
Semaphores
Semaphores – keeps trap of resource usage by no of threads
Resource acquired by thread it does Counter ++
Resource released by thread it does Counter--
Event Objects
Signal Set – Reset Events
Auro reset and manual reset
Resource
: memory location, data structure, file…
Buffer
Data
Thread 1:
data
Thread 2:
Critical Sections
• Critical Section
– Portion of a code that accesses a shared resource.
• Critical Section Object
– Provided by Win32 API
– used to enforce mutual exclusion between threads within
a single process.
– Only one Thread at a time is allowed to be “inside” the
critical section.
– Local object
• kernel object
• Define critical section object
– CRITICAL_SECTIONcritical_section;
• Initialized critical section
– VOID InitializeCriticalSection (LPCRITICAL_SECTION
lpCriticalSection);
• Deleting critical section object
– VOID DeleteCriticalSection (LPCRITICAL_SECTION
lpCriticalSection);
2005-10-19 Seong Jong Choi Multithreading_CHAPTER_4-9
• Entering the critical section
– VOID EnterCriticalSection (LPCRITICAL_SECTION
lpCriticalSection);
• Leaving the critical section
– VOID LeaveCriticalSection (LPCRITICAL_SECTION
lpCriticalSection);
• Example : Linked list
typedef struct _Node{
struct _Node *next;
int data;
} Node;
typedef struct _List{
Node *head;
CRITICAL_SECTION Critical_sec;
} List;
List *CreateList(){
List *pList = malloc(sizeof(pList));
pList->head = NULL;
InitializeCriticalSection(&pList->Critical_sec);
return pList;
}
void DeleteList(List *pList)
{
DeleteCriticalSection(&pList->Critical_sec);
free(pList);
}
void AddHead(List *pList, Node *node)
{
EnterCriticalSection(&pList->critical_sec);
node->next = pList->head;
pList->head = node;
LeaveCriticalSection(&pList->Critical_sec);
}
• Example : Linked
AddHead()
Data | head
Data | next
NULL
List
Node
Void Insert(List *pList, Node *afterNode, Node *newnode){
EnterCriticalSection(&pList->critical_sec);
if(afterNode == NULL){
AddHead(pList, newNode);
}
else{
newNode->next = afterNode->next;
afterNode->next = newNode;
}
LeaveCriticalSection(&pList->Critical_sec);
}
Node *next(List *pList, Node *node){
Node* next;
EnterCriticalSection(&pList->Critical_sec);
next = node->next;
LeaveCriticalSection(&pList->Critical_sec);
return next;
}
• Example : Linked list
Insert()
1.
Data | next
Data | next
Data | next
Data | next
Data | next
NULL
AfterNode
newNode
AfterNode
• Example : Linked list
*Next()
Data | next
node
head Data | next Data | next NULL
List node node
Data | next
next
– Critical Section
EnterCriticalSection(pCS)
EnterCriticalSection(pCS)
…
LeaveCriticalSection(pCS)
LeaveCriticalSection(pCS)
2005-10-19 Seong Jong Choi Multithreading_CHAPTER_4-17
• Minimizing Lock Time
– Don’t lock a resource for long time !
– Never call Sleep() or any of the Wait…() APIs inside of a
critical section.
– How often the resource will be used and how quickly a
thread must release the resource.
• Void Dangling Critical Sections
– LeaveCriticalSection()없이 thread가 죽는다면..?
– Critical section is not kernel object -> there is no way to
tell if the thread currently inside a critical section is
still alive.
Deadlock
Example SwapLists() –p.82
void SwapLists(List *list1, List *list2){
List *tmp_list;
EnterCriticalSection(list1->critical_sec);//context switch
EnterCriticalSection(list2->critical_sec);
tmp_list = list1->head;
list1->head = list2->head;
list2->head = tmp_list;
LeaveCriticalSection(list1->critical_sec);
LeaveCriticalSection(list2->critical_sec);
}
ThreadA SwapLists(home_address_list, work_address_list);
ThreadA SwapLists(work_address_list, home_address_list);
Deadlock
Data | next
Node
head Data | next Data | next NULL
Tmp_list Node Node
Data | next
Node
head Data | next Data | next NULL
List1 Node Node
Data | next
Node
head Data | next Data | next NULL
List2 Node Node
• Deadlock() = “The Deadly Embrace”
• Deadlock will not happen by allocating all the
resources you need as a single operation with
WaitForMultipleObjects(). (later…-> P.91)
• All-or-nothing proposition
The Dining Philosophers
The table set for the dining philosophers
eating
thinking Waiting to eat
Let’s See
the Dining.c
Mutexes
• MUTualExclusion
• Only one thread at a time is allowed to own a mutex, just as
only one thread at a time can enter a critical section.
• A kernel object that will enforce mutual exclusion between
threads even if they are in different processes.
Timeout (see Wait…() func) not
Between Processes Within the same process
Almost 100 times longer
Mutexes Critical section
The comparison of the function
DeleteCriticalSection() CloseHandle()
LeaveCriticalSection() ReleaseMutex()
WaitForSingleObject()
WaitForMultipleObjects()
MsgWaitForMultipleObjects()
EnterCriticalSection()
CreatMutex()
OpenMutex()
InitializeCriticalSection()
CRITICAL_SECTION Mutex Kernel Object
Creating Mutex
HANDLE CreateMutex(
LPSECURITY_ATTRIBUTES lpAttribute,
BOOL bInitialOwner,
LPCTSTR lpName
);
– lpAttribute: Use NULL to get the default Security Attributes.
– bInitialOwner: Set to TRUE if you want the thread that called
CreateMutex() to own the mutex.
– lpName:Any thread or process can refer to this mutex by name
• a Mutex has a reference count. You should call CloseHandle()
– CreateMutex Reference Count++
– CloseHandle Reference Count--
Opening Mutex
HANDLE OpenMutex(
DWORD dwDesiredAccess, // access
BOOL bInheritHandle, // inheritance option
LPCTSTR lpName // object name );
– dwDesiredAccess :Specifies the requested access to the mutex.
– bInheritHandle : Specifies whether the returned handle is
inheritable.
– lpName: Name to access Mutex.
– Mutex has a reference count. You should call CloseHandle()
• Locking a Mutex
– To acquire ownership of the mutex, use one of the Win32
Wait….() functions.
– If a thread waits on a non-signaled mutex then the
thread will block.
– A Mutex is signaled when no thread owns it.
– Scenario (textbook p.87 side effect)
BOOL ReleaseMutex( HANDLE hMutex );
- a thread releases ownship of the mutex by calling
ReleaseMutex().
• Handling Abandoned Mutexes
– If a thread that owns a mutex exits without calling
ReleaseMutex(), the mutex is not destroyed.
– Mutex -> unowned, nonsignaled
– Wait…() -> return : WAIT_ABANDONED_0
(~WAIT_ABANDONED_n - 1)
• Letting the Philosophers Eat
– Source
• Fixing SwapLists
Void SwapLists(struct List *list1, struct List *list2)
{
struct List *tmp_list;
HANDLE arrhandles[2];
arrHandles[0] = list1->hMutex;
arrHandles[1] = list2->hMutex;
WaitForMultipleObjects(2, arrHandles, TRUE, INFINITE);
tmp_list = list1->head;
list1->head = list2->head;
list2->head = tmp_list;
ReleaseMutex(arrHandles[0]);
ReleaseMutex(arrHandles[1]);
}
Why Have an Initial Owner?
– bInitialOwner of CreateMutex()
– It prevents a race condition.
HANDLE hMutex = CreateMutex(NULL, FALSE, “Simple Name”); <<
int result = WaitForSingleObject(hMutex, INFINITE);
– Critical Section
EnterCriticalSection(pCS)
EnterCriticalSection(pCS)
…
LeaveCriticalSection(pCS)
LeaveCriticalSection(pCS)
– Mutex
WaitforSingleObject(hMtx)
WaitforSingleObject(hMtx)
…
ReleaseMutex(hMtx)
ReleaseMutex(hMtx)
Semaphores
• They are the key ingredient in solving various
producer/consumer problems where a buffer is being read
and written at the same time.
• A semaphore in Win32 may be locked at most n times, where
n is specified when the semaphore is created.
• EX) car rental problem.
• Creating Semaphores
HANDLE CreateSemaphore(
LPSECURITY_ATTRIBUTES lpAttribute,
LONG InitialCount,
LONG MaximumCount,
LPCTSTR lpName
);
– lpAttribute: Use NULL to get the default Security Attributes.
– InitialCount: Specifies an initial count for the semaphore
object(0 <= this <= MaximemCount)
– MaximumCount: Specifies the maximum count for the
semaphore object
– lpName:Any thread or process can refer to this Semaphore by name
• Acquiring Locks
– The Value of the semaphore represents the number of
resources currently available.
– You acquire a lock on a semaphore by using any of the Wait…()
– There is no concept of ownership (Semaphore has no owner)
• Several Threads can lock a semaphore at the same time
• Semaphore can be released by any thread
• Releasing Locks
– To release a lock, call ReleaseSemaphore()
– This function increments the semaphore’s value
BOOL ReleaseSemaphore(
HANDLE hSemaphore,
LONG lReleaseCount,
LPLONG lpPreviousCount
);
hSemaphore Handle to the semaphore
lReleaseCount Increment the value of the semaphore
lpPreviousCount Return the previous value of the semaphore.
Note the there is no way to get the current value.
• Why Have an Initial Count?
– Initial Value of the semaphore
– Must be greater than or equal to zero and less than
MaximumCount
– ReleaseSemaphore() can increment the count up to its
maximum
Event Objects
• The most flexible type of synchronization object in Win32 Kernel
Object ( signaled or nonsignaled)
HANDLE CreateEvent(
LPSECURITY_ATTRIBUTES lpEventAttributes,
BOOL bManualReset, // T=AutoReset, F=Manual Reset
BOOL bInitialState, // initial state; T=signaled, F=nonsignaled
LPCTSTR lpName // object name
);
SetEvent()
Memory Operation
Set the event object to the signaled state
ResetEvent()
Set the event object to the nonsignaled state
PulseEvent()
– Memoryless operation
– Manual Reset Event: Set the event object to the signaled state, wake everything
up that is currently waiting, then return to the nonsignaled state.
– Auto Reset Event: Set the event object to the signaled state, wake up a single
waiting thread (if any), return to the nonsignaled state.
Manual Reset Event Object: Set/Reset
1. Two threads are waiting for an event object (EO).
2. SetEvent(EO) will activate all threads waiting for the EO.
3. The EO will be in nonsignaled state only after the
ResetEvent()
Auto Reset Event Object: Set
1. Two threads are waiting for an event object (EO).
2. SetEvent(EO) will activate only one thread waiting for the
EO, then return to nonsignaled state
3. If no threads are waiting, the event object's state remains
signaled,
4. Until wait (or reset()??) function.
Manual Reset Event Object: Pulse
1. Assume two threads are waiting for an event object (EO).
2. PulseEvent(EO) will activate all threads waiting for the EO,
then the EO return to the nonsignaled state.
3. If no threads are waiting, the event object's state remains
nonsignaled
Auto Reset Event Object: Pulse
1. If no threads are waiting, the event object's state remains
nonsignaled
2. Two threads are waiting for an event object (EO).
3. PulseEvent(EO) will activate a single thread waiting for the
EO, then the EO return to the nonsignaled state.
Event Objects: Summary
• If threads are waiting.
Activate one, then
Activate one, then --- nonsignaled
Auto Reset stay nonsignaled
Activate all, then
Activate all, then Nonsignaled nonsignaled
Manual Reset stay signaled
SetEvent() ResetEvent() PulseEvent()
• If no treads are waiting.
Stay signaled, --- Stay nonsignaled
Auto Reset until wait function.
Manual Reset Stay signaled Nonsignaled Stay nonsignaled
SetEvent() ResetEvent() PulseEvent()
2005-10-19 Seong Jong Choi Multithreading_CHAPTER_4-43
Summary & Questions
• PulseEvent() is an memoryless operation.
• SetEvent() is memory operation.
• Manual/auto Reset
– No threads are waiting, and current state is signaled.
What happens when PulseEvent()??
Interlocked Variables
• The simplest type of synchronization mechanism.
• Operate on a standard 32-bit long variable.
• No ability to wait
• InterlockedIncrement(LPLONG lpTarget)
• InterlockedDecrement(LPLONG lpTarget)
– These functions return a comparison against zero.
– Use these functions to maintain your object reference count.
(ex: AddRef(), Release())
Summary of Synchronization Mechanisms
• Critical Section
– Is a local object, not a kernel object
– Is fast and efficient
– Cannot be waited on more than one at a time
– Cannot determine if it was abandoned by a thread
• Mutex
– Is a kernel object
– Generates an ‘abandoned’ error if the owning thread
terminates
– Can be used in Wait…() calls
– Is Named, and can be opened across processes.
– Can only be released by the thread that owns it
• Semaphore
– Is a kernel object
– Has no owner
– Is Nameed
– Can be released by any thread
• Event Object
– Is a kernel object
– Is completely under program control
– Is good for designing new synchronization objects
– Does not queue up wake-up requests
– Is Named
• Interlocked Variable
– Useful for reference counting
No comments:
Post a Comment