Which sync object has a resource counter. Thread synchronization tools in Windows OS (critical sections, mutexes, semaphores, events)
When multiple processes (or multiple threads of the same process) access a resource at the same time, a synchronization problem occurs. Since a thread in Win32 can be stopped at any point in time unknown to it in advance, a situation is possible when one of the threads did not have time to complete the modification of a resource (for example, a memory area mapped to a file), but was stopped, and another thread tried to access the same resource. At this point, the resource is in an inconsistent state, and the consequences of accessing it can be the most unexpected - from data corruption to memory protection violations.
The main idea behind thread synchronization in Win32 is the use of synchronization objects and wait functions. Objects can be in one of two states - Signaled or Not Signaled. The wait functions block the execution of a thread while the specified object is in the Not Signaled state. Thus, a thread that needs exclusive access to a resource must set some synchronization object to the non-signaled state, and reset it to the signaled state when it is finished. Other threads must call a wait function before accessing this resource, which allows them to wait for the resource to be freed.
Let's take a look at what synchronization objects and functions the Win32 API provides us with.
Synchronization functions
Synchronization functions fall into two main categories: functions that expect a single object, and functions that expect one of several objects.
Functions that expect a single object
The simplest wait function is the WaitForSingleObject function:
Function WaitForSingleObject(hHandle: THandle; // object identifier dwMilliseconds: DWORD // wait period): DWORD; stdcall;
The function waits for the hHandle object to become signaled within dwMilliseconds milliseconds. If you pass INFINITE as the dwMilliseconds parameter, the function will wait indefinitely. If dwMilliseconds is 0, then the function checks the state of the object and returns immediately.
The function returns one of the following values:
The following code fragment denies access to Action1 until the ObjectHandle object transitions to the signaled state (for example, in this way you can wait for the process to complete by passing its identifier received by the CreateProcess function as ObjectHandle):
VarReason: DWORD; ErrorCode: DWORD; Action1.Enabled:= FALSE; try repeat Application.ProcessMessages; Reason:= WailForSingleObject(ObjectHandle, 10); if Reason = WAIT_FAILED then begin ErrorCode:= GetLastError; raise Exception.CreateFmt('Wait for object failed with error: %d', ); end; until reason<>WAIT_TIMEOUT; finally Actionl.Enabled:= TRUE; end;
In the case when, simultaneously with waiting for an object, another object needs to be signaled, the SignalObjectAndWait function can be used:
Function SignalObjectAndWait(hObjectToSignal: THandle; // object that will be put into // signal state hObjectToWaitOn: THandle; // object, which the expects function dwMilliseconds: DWORD; // wait period bAlertable: BOOL // specifies whether the function should // return control in case of a request to // complete an I/O operation): DWORD; stdcall;
The return values are similar to the WaitForSingleObject function.
The hObjectToSignal object can be a semaphore, an event, or a mutex. The bAlertable parameter determines whether the wait for an object will be interrupted if the operating system asks the thread to end an asynchronous I/O operation or an asynchronous procedure call. This will be discussed in more detail below.
Functions that expect multiple objects
Sometimes it is necessary to delay the execution of a thread until one or all of the objects in a group are fired. To solve this problem, the following functions are used:
Type TWOHandleArray = array of THandle; PWOHandleArray = ^TWOHandleArray; function WaitForMultipleObjects(nCount: DWORD; // Sets the number of objects lpHandles: PWOHandleArray; // Address of an array of objects bWaitAll: BOOL; // Sets whether to wait for all // objects or any dwMilliseconds: DWORD // Wait period): DWORD; stdcall;
The function returns one of the following values:
|
A number in the range from WAIT_OBJECT_0 to WAIT_OBJECT_0 + nCount - 1 |
If bWaitAll is TRUE, then this number means that all objects have entered the signaled state. If FALSE - then, subtracting from the returned value WAIT_OBJECT_0, we get the index of the object in the lpHandles array |
|
A number in the range from WAIT_ABANDONED_0 to WAIT_ABANDONED_0 + nCount - 1 |
If bWaitAll is TRUE, it means that all objects went into the signaled state, but at least one of the threads that owned them terminated without making the object signaled. If FALSE, then, subtracting from the returned values WAIT_ABANDONED_0, we will get the index of the object in the lpHandles array, while the thread owner of this object terminated without making it a signal |
| WAIT_TIMEOUT | Waiting period expired |
| WAIT_FAILED | An error has occurred |
For example, in the following code snippet, the program tries to modify two different resources shared between threads:
Var Handles: array of THandle; Reason: DWORD; RestIndex: Integer; ... Handles := OpenMutex(SYNCHRONIZE, FALSE, 'FirstResource'); Handles := OpenMutex(SYNCHRONIZE, FALSE, 'SecondResource'); // Waiting for the first Reason object:= WaitForMultipleObjects(2, @Handles, FALSE, INFINITE); case Reason of WAIT_FAILED: RaiseLastWin32Error; WAIT_OBJECT_0, WAIT_ABANDONED_0: begin ModifyFirstResource; RestIndex:= 1; end; WAIT_OBJECT_0 + 1, WAIT_ABANDONED_0 + 1: begin ModifySecondResource; RestIndex:= 0; end; // WAIT_TIMEOUT cannot occur end; // Now wait for the next object to be released if WailForSingleObject(Handles, INFINITE) = WAIT_FAILED then RaiseLastWin32Error; // Wait, modify the remaining resource if RestIndex = 0 then ModifyFirstResource else ModifySecondResource;
The technique described above can be used if you know for sure that the delay in waiting for an object will be negligible. Otherwise, your program will be "frozen" and will not even be able to redraw its window. If the delay period can be significant, then you need to give the program the opportunity to respond to Windows messages. The way out can be to use functions with a limited wait period (and call again if WAIT_TIMEOUT is returned) or the MsgWaitForMultipleObjects function:
Function MsgWaitForMultipleObjects(nCount: DWORD; // number of synchronization objects var pHandles; // address of array of objects fWaitAll: BOOL; // Specifies whether to wait for all // objects or any dwMilliseconds, // Wait period dwWakeMask: DWORD // Event type , interrupting the wait): DWORD; stdcall;
The main difference between this function and the previous one is the dwWakeMask parameter, which is a combination of QS_XXX bit flags and sets the types of messages that interrupt the function waiting regardless of the state of the expected objects. For example, the QS_KEY mask allows you to interrupt the wait when WM_KEYUP, WM_KEYDOWN, WM_SYSKEYUP, or WM_SYSKEYDOWN messages appear in the queue, and the QS_PAINT mask allows WM_PAINT messages. For a complete list of valid values for dwWakeMask, see the Windows SDK documentation. When the thread that called the function appears in the queue of messages matching the specified mask, the function returns the value WAIT_OBJECT_0 + nCount. Once this value is received, your program can process it and call the wait function again. Consider an example of running an external application (it is necessary that the calling program does not respond to user input for the duration of its operation, but its window must continue to be redrawn):
Procedure TForm1.Button1Click(Sender: TObject); var PI: TProcessInformation; SI: TStartupInfo; Reason: DWORD; Msg:TMsg; begin // Initialize the TStartupInfo structure FillChar(SI, SizeOf(SI), 0); SI.cb:= SizeOf(SI); // Run external program Win32Check(CreateProcess(NIL, "COMMAND.COM", NIL, NIL, FALSE, 0, NIL, NIL, SI, PI)); //************************************************** ** // Try replacing the code below with the line // WaitForSingleObject(PI.hProcess, INFINITE); // and see how the program will react to // moving other windows over its window //****************************** ******************** repeat // Wait for child process to finish or repaint message // WM_PAINT Reason:= MsgWaitForMultipleObjects(1, PI.hProcess, FALSE, INFINITE, QS_PAINT) ; if Reason = WAIT_OBJECT_0 + 1 then begin // WM_PAINT appeared in the message queue - Windows // requires to refresh the program window. // Remove the message from the queue PeekMessage(Msg, 0, WM_PAINT, WM_PAINT, PM_REMOVE); // And redraw our window Update; end; // Repeat the loop until the child process exits until Reason = WAIT_OBJECT_0; // Remove messages accumulated there from the queue while PeekMessage(Msg, 0, 0, 0, PM_REMOVE) do; CloseHandle(PI.hProcess); CloseHandle(PI.hThread) end;
If windows are created explicitly (using the CreateWindow function) or implicitly (using TForm, DDE, COM) in the thread that calls the wait functions, the thread must process messages. Because broadcast messages are sent to all windows in the system, a thread not handling messages can cause a deadlock (the system waits for the thread to process the message, the thread for the system or other threads to release the object) and cause Windows to hang. If your program has such fragments, you should use MsgWaitForMultipleObjects or MsgWaitForMultipleObjectsEx and let the wait be interrupted to process messages. The algorithm is similar to the above example.
Abort wait on request to complete an I/O operation or APC
Windows supports asynchronous procedure calls. When creating each thread (thread), a queue of asynchronous procedure calls (APC queue) is associated with it. The operating system (or the user application - using the QueueUserAPC function) can place requests to execute functions in the context of this thread. These functions cannot be executed immediately because the thread may be busy. Therefore, the operating system calls them when a thread calls one of the following wait functions:
Function SleepEx(dwMilliseconds: DWORD; // Timeout period bAlertable: BOOL // specifies whether the function should // return control if an asynchronous procedure call is // requested): DWORD; stdcall; function WaitForSingleObjectEx(hHandle: THandle; // Object identifier dwMilliseconds: DWORD; // Wait period bAlertable: BOOL // specifies whether the function should // return control if an asynchronous procedure call is // requested): DWORD; stdcall; function WaitForMultipleObjectsEx(nCount: DWORD; // number of objects lpHandles: PWOHandleArray;// address of an array of object identifiers bWaitAll: BOOL; // Specifies whether to wait for all // objects or any dwMilliseconds: DWORD; // Wait period bAlertable: BOOL / / specifies whether the function should // return control in case of a request for // an asynchronous procedure call): DWORD; stdcall; function SignalObjectAndWait(hObjectToSignal: THandle; // object to be signaled // hObjectToWaitOn: THandle; // object the function is waiting for dwMilliseconds: DWORD; // wait period bAlertable: BOOL // specifies whether the function should return / / control in case of request for // asynchronous procedure call): DWORD; stdcall; function MsgWaitForMultipleObjectsEx(nCount: DWORD; // number of synchronization objects var pHandles; // address of an array of objects fWaitAll: BOOL; // Specifies whether to wait for all // objects or any dwMilliseconds, // Wait period dwWakeMask: DWORD // Event type dwFlags: DWORD // Additional flags): DWORD; stdcall;
If the bAlertable parameter is TRUE (or if dwFlags in the MsgWaitForMultipleObjectsEx function contains MWMO_ALERTABLE), then when a request for an asynchronous procedure call appears in the APC queue, the operating system makes calls to all procedures in the queue, after which the function returns WAIT_IO_COMPLETION.
This mechanism allows you to implement, for example, asynchronous I/O. A thread can initiate the background execution of one or more I/O operations with the ReadFileEx or WriteFileEx functions by passing them the addresses of the completion handler functions. When completed, the calls to these functions will be queued for asynchronous procedure calls. In turn, the thread that initiated the operations, when it is ready to process the results, can use one of the above wait functions to allow the operating system to call the handler functions. Since the APC queue is implemented at the OS kernel level, it is more efficient than the message queue and allows for much more efficient I/O.
Event (event)
Event allows you to notify one or more waiting threads of the occurrence of an event. Event happens:
The CreateEvent function is used to create an object:
Function CreateEvent(lpEventAttributes: PSecurityAttributes; // Structure address // TSecurityAttributes bManualReset, // Specifies whether the Event will be triggered // manually (TRUE) or automatically (FALSE) bInitialState: BOOL; // Sets the initial state. If TRUE - // object in signaled state lpName: PChar // Name or NIL if no name is required): THandle; stdcall; // Returns the ID of the // created object The TSecurityAttributes structure is described as follows: TSecurityAttributes = record nLength: DWORD; // The size of the structure, should // be initialized as // SizeOf(TSecurityAttributes) lpSecurityDescriptor: Pointer; // Address of the security descriptor. // Ignored on Windows 95 and 98 // You can normally specify NIL bInheritHandle: BOOL; // Sets whether child processes // can inherit the object end;
You can pass NIL as the lpEventAttributes parameter if you do not want special permissions under Windows NT or the ability for child processes to inherit the object. In this case, the object cannot be inherited by child processes, and a "default" security descriptor is assigned to it.
The lpName parameter allows you to share objects between processes. If lpName matches the name of an already existing Event object created by the current or any other process, then the function does not create a new object, but returns the identifier of the existing one. This ignores the bManualReset, bInitialState, and lpSecurityDescriptor parameters. You can check whether an object has been created or an existing one is being used, as follows:
HEvent:= CreateEvent(NIL, TRUE, FALSE, 'EventName'); if hEvent = 0 then RaiseLastWin32Error; if GetLastError = ERROR_ALREADY_EXISTS then begin // Use the previously created object end;
If the object is used for synchronization within a single process, it can be declared as a global variable and created without a name.
The object name must not match the name of any existing Semaphore, Mutex, Job, Waitable Timer, or FileMapping object. If the names match, the function returns an error.
If you know that the Event has already been created, you can use the OpenEvent function instead of CreateEvent to access it:
Function OpenEvent(dwDesiredAccess: DWORD; // Sets access rights to the object bInheritHandle: BOOL; // Sets whether the object can be inherited // by child processes lpName: PChar // Object name): THandle; stdcall;
The function returns the object identifier or 0 - in case of an error. The dwDesiredAccess parameter can take one of the following values:
After receiving the identifier, you can start using it. The following functions are available for this:
Function SetEvent(hEvent: THandle): BOOL; stdcall;
Sets an object to the signaled state
Function ResetEvent(hEvent: THandle): BOOL; stdcall;
Resets an object, setting it to the non-signaled state
Function PulseEvent(hEvent: THandle): BOOL; stdcall
Sets an object to the signaled state, lets all wait functions that are waiting for this object run, and then resets it again.
The Windows API uses events to perform asynchronous I/O operations. The following example shows how an application initiates a write to two files at the same time and then waits for the write to complete before continuing; this approach can provide better performance for high I/O than sequential writes:
Var Events: array of THandle; // Array of synchronization objects Overlapped: array of TOverlapped; ... // Create synchronization objects Events := CreateEvent(NIL, TRUE, FALSE, NIL); Events := CreateEvent(NIL, TRUE, FALSE, NIL); // Initialize structures TOverlapped FillChar(Overlapped, SizeOf(Overlapped), 0); Overlapped.hEvent:= Events; Overlapped.hEvent:= Events; // Start writing to files asynchronously WriteFile(hFirstFile, FirstBuffer, SizeOf(FirstBuffer), FirstFileWritten, @Overlapped); WriteFile(hSecondFile, SecondBuffer, SizeOf(SecondBuffer), SecondFileWritten, @Overlapped); // Wait for both files to finish writing WaitForMultipleObjects(2, @Events, TRUE, INFINITE); // Destroy synchronization objects CloseHandle(Events); CloseHandle(Events)
Upon completion of work with the object, it must be destroyed by the CloseHandle function.
Delphi provides the TEvent class, which encapsulates the functionality of the Event object. The class is located in the SyncObjs.pas module and is declared as follows:
Type TWaitResult = (wrSignaled, wrTimeout, wrAbandoned, wrError); TEvent = class(THandleObject) public constructor Create(EventAttributes: PSecurityAttributes; ManualReset, InitialState: Boolean; const Name: string); function WaitFor(Timeout: DWORD): TWaitResult; procedure SetEvent; procedure ResetEvent; end;
The purpose of the methods obviously follows from their names. Using this class allows you not to go into the intricacies of implementing the called Windows API functions. For the simplest cases, another class with a simplified constructor is declared:
Type TSimpleEvent = class(TEvent) public constructor Create; end; ... constructor TSimpleEvent.Create; begin FHandle:= CreateEvent(nil, True, False, nil); end;
Mutex (Mutually Exclusive)
A mutex is a synchronization object that is signaled only when it is not owned by any process. As soon as at least one process requests ownership of the mutex, it goes into the non-signaled state and remains so until it is released by the owner. This behavior allows mutexes to be used to synchronize the sharing of multiple processes on a shared resource. The following function is used to create a mutex:
Function CreateMutex(lpMutexAttributes: PSecurityAttributes; // Structure address // TSecurityAttributes bInitialOwner: BOOL; // Specifies whether the process will // own the mutex immediately after creation lpName: PChar // Mutex name): THandle; stdcall;
The function returns the identifier of the created object or 0. If the mutex with the given name has already been created, its identifier is returned. In this case, the GetLastError function will return the error code ERROR_ALREDY_EXISTS. The name must not match the name of an already existing Semaphore, Event, Job, Waitable Timer, or FileMapping object.
If it is not known whether a mutex with the same name already exists, the program must not request ownership of the object at creation (that is, it must pass bInitialOwner to FALSE).
If the mutex already exists, the application can get its ID using the OpenMutex function:
Function OpenMutex(dwDesiredAccess: DWORD; // Sets access rights to the object bInheritHandle: BOOL; // Sets whether the object can be inherited // by child processes lpName: PChar // Object name): THandle; stdcall;
The function returns the identifier of the open mutex, or 0 in case of an error. The mutex goes into the signaled state after the wait function to which its identifier was passed is fired. To return to the non-signaled state, use the ReleaseMutex function:
Function ReleaseMutex(hMutex: THandle): BOOL; stdcall;
If multiple processes communicate, for example through a memory-mapped file, then each of them must contain the following code to ensure correct access to the shared resource:
Var Mutex: THandle; // On program initialization Mutex:= CreateMutex(NIL, FALSE, 'UniqueMutexName'); if Mutex = 0 then RaiseLastWin32Error; ... // Resource access WaitForSingleObject(Mutex, INFINITE); try // Accessing the resource, acquiring the mutex ensures // that other processes trying to access // will be stopped at the WaitForSingleObject function ... finally // The resource is finished, release it // for other processes ReleaseMutex(Mutex) ; end; ... // At the end of the program CloseHandle(Mutex);
It is convenient to encapsulate such code in a class that creates a protected resource. A mutex has properties and methods for operating on a resource, protecting them with synchronization functions.
Of course, if working with a resource can take a significant amount of time, then you must either use the MsgWaitForSingleObject function, or call WaitForSingleObject in a zero-wait loop, checking the return code. Otherwise, your application will be frozen. Always protect the capture-release of a synchronization object with a try ... finally block, otherwise an error while handling a resource will block all processes waiting for it to be freed.
Semaphore (semaphore)
A semaphore is a counter containing an integer ranging from 0 to the maximum value specified when it was created. The counter is decremented each time the thread successfully terminates the wait function using the semaphore and incremented by calling the ReleaseSemaphore function. When the semaphore reaches the value 0, it goes into a non-signaled state; for any other values of the counter, its state is signaled. This behavior allows a semaphore to be used as an access limiter to a resource that supports a predetermined number of connections.
The CreateSemaphore function is used to create a semaphore:
Function CreateSemaphore(lpSemaphoreAttributes: PSecurityAttributes; // Structure address // TSecurityAttributes lInitialCount, // Initial counter value lMaximumCount: Longint; // Maximum counter value lpName: PChar // Object name): THandle; stdcall;
The function returns the identifier of the created semaphore, or 0 if the object creation failed.
The lMaximumCount parameter specifies the maximum value of the semaphore counter, lInitialCount specifies the initial value of the counter and must be in the range 0 to lMaximumCount. lpName specifies the name of the semaphore. If the system already has a semaphore with the same name, then a new one is not created, but the identifier of the existing semaphore is returned. If the semaphore is used within a single process, you can create it without a name by passing NIL as lpName. The semaphore name must not match the name of an already existing event, mutex, waitable timer, job, or file-mapping object.
The identifier of a previously created semaphore can also be obtained from the OpenSemaphore function:
Function OpenSemaphore(dwDesiredAccess: DWORD; // Sets access rights to the object bInheritHandle: BOOL; // Sets whether the object can be inherited // by child processes lpName: PChar // Object name): THandle; stdcall;
The dwDesiredAccess parameter can take one of the following values:
To increment a semaphore counter, use the ReleaseSemaphore function:
Function ReleaseSemaphore(hSemaphore: THandle; // Identifier of the semaphore lReleaseCount: Longint; // The counter will be incremented by this amount lpPreviousCount: Pointer // Address of a 32-bit variable that takes // the previous counter value): BOOL; stdcall;
If the value of the counter after the execution of the function exceeds the maximum set for it by the CreateSemaphore function, then ReleaseSemaphore returns FALSE and the value of the semaphore is not changed. NIL can be passed as the lpPreviousCount parameter if we do not need this value.
Let's consider an example of an application that launches several tasks in separate threads (for example, a program for downloading files from the Internet in the background). If the number of simultaneously executing tasks is too large, this will lead to unjustified loading of the channel. Therefore, we implement the threads in which the task will be executed in such a way that when their number exceeds a predetermined value, the thread would stop and wait for the previously launched tasks to complete:
Unit LimitedThread; interface uses Classes; type TLimitedThread = class(TThread) procedure Execute; override; end; implementation uses Windows; const MAX_THREAD_COUNT = 10; var Semaphore: THandle; procedure TLlimitedThread.Execute; begin // Decrement the semaphore counter. If by this time // MAX_THREAD_COUNT threads have already been started, the counter is 0 and the semaphore is // in a non-signaled state. The thread will be frozen until // one of the previously started threads completes. WaitForSingleObject(Semaphore, INFINITE); // Here is the code responsible for the functionality of the thread, // for example, downloading a file... // The thread has exited, increment the semaphore counter, and // allow other threads to start processing. ReleaseSemaphore(Semaphore, 1, NIL); end; initialization // Create a semaphore when the program starts Semaphore:= CreateSemaphore(NIL, MAX_THREAD_COUNT, MAX_THREAD_COUNT, NIL); finalization // Destroy the semaphore when the program ends CloseHandle(Semaphore); end;
Lecture No. 9. Synchronization of processes and threads
1. Purposes and means of synchronization.
2. Synchronization mechanisms.
1. Purposes and means of synchronization
There is a fairly large class of operating system tools that provide mutual synchronization of processes and threads. The need for thread synchronization arises only in multiprogramming. operating system and is associated with the sharing of hardware and information resources computing system. Synchronization is necessary to avoid races and deadlocks when exchanging data between threads, sharing data, accessing the processor and I/O devices.
In many operating systems, these tools are called interprocess communication tools - Inter Process Communications (IPC), which reflects the historical primacy of the concept of "process" in relation to the concept of "thread". Usually, IPC tools include not only interprocess synchronization tools, but also interprocess data exchange tools.
The execution of a thread in a multiprogramming environment is always asynchronous. It is very difficult to say with complete certainty at what stage of execution the process will be at a certain point in time. Even in single-program mode, it is not always possible to accurately estimate the time to complete a task. This time in many cases significantly depends on the value of the initial data, which affects the number of cycles, the direction of the program branching, the time of performing I / O operations, etc. Since the initial data at different moments of the task launch can be different, the execution time individual stages and the task as a whole is a very uncertain value.
Even more uncertain is the execution time of a program in a multiprogram system. The moments when threads are interrupted, the time they spend in queues for shared resources, the order in which threads are selected for execution - all these events are the result of a combination of many circumstances and can be interpreted as random. At best, it is possible to estimate the probabilistic characteristics of the computational process, for example, the probability of its completion in a given period of time.
Thus, threads in the general case (when the programmer has not taken special measures to synchronize them) flow independently, asynchronously to each other. This is true both for threads of the same process executing a common program code, and for threads of different processes, each of which executes its own program.
Any interaction between processes or threads is associated with their synchronization, which consists in matching their speeds by suspending the flow until some event occurs and then activating it when this event occurs. Synchronization is at the heart of any interaction between threads, whether it is related to the sharing of resources or to the exchange of data. For example, a receiving thread should only access data after it has been buffered by the sending thread. If the receiving thread has accessed the data before it reaches the buffer, then it must be suspended.
When sharing hardware resources, synchronization is also essential. When, for example, an active thread needs access to a serial port, and another thread that is in exclusive mode is using this port in exclusive mode. this moment in the idle state, the OS suspends the active thread and does not activate it until the port it needs is free. Synchronization with events external to the computing system is often also needed, for example, reactions to pressing the Ctrl + C key combination.
Hundreds of resource allocation and release events occur in the system every second, and the OS must have reliable and efficient means that would allow it to synchronize threads with events occurring in the system.
To synchronize the threads of application programs, the programmer can use both his own synchronization tools and techniques, and the tools of the operating system. For example, two threads of the same application process can coordinate their work using a global boolean variable available to both of them, which is set to one when some event occurs, for example, one thread produces the data needed to continue the work of another. However, in many cases, the synchronization facilities provided by the operating system in the form of system calls are more efficient or even the only possible means. Thus, threads belonging to different processes do not have the ability to interfere in any way with each other's work. Without the mediation of the operating system, they cannot suspend each other or notify of an event that has occurred. Synchronization tools are used by the operating system not only to synchronize application processes, but also for its internal needs.
Typically, operating system developers provide application and system programmers with a wide range of synchronization tools. These tools can form a hierarchy when more complex ones are built on the basis of simpler tools, and also be functionally specialized, for example, tools for synchronizing threads of one process, tools for synchronizing threads different processes when exchanging data, etc. Often functionality different synchronization system calls overlap, so that a programmer can use several calls to solve one problem, depending on their personal preferences.
The need for synchronization and race
Neglecting synchronization issues in a multi-threaded system can lead to an incorrect solution of the problem or even to the crash of the system. Consider, for example (Fig. 4.16), the problem of maintaining a database of customers of some enterprise. Each client is assigned a separate record in the database, which, among other fields, contains the Order and Payment fields. The program that maintains the database is designed as a single process that has several threads, including thread A, which enters information about orders received from customers into the database, and thread B, which records information about payments by customers for invoices in the database. Both of these threads work together on a common database file using the same type of algorithms, including three steps.
2. Enter a new value in the Order field (for flow A) or Payment (for flow B).
3. Return the modified record to the database file.
https://pandia.ru/text/78/239/images/image002_238.gif" width="505" height="374 src=">
Rice. 4.17. Influence of relative flow velocities on the result of solving the problem
critical section
An important concept of thread synchronization is the concept of a "critical section" of a program. critical section is a part of the program, the result of which can change unpredictably if the variables related to this part of the program are changed by other threads at a time when the execution of this part has not yet completed. The critical section is always defined with respect to certain critical data in case of inconsistent change of which undesirable effects may occur. In the previous example, the records of the database file were such critical data. All threads that work with critical data must have a critical section defined. Note that in different threads the critical section generally consists of different instruction sequences.
To eliminate the effect of race conditions on critical data, it is necessary to ensure that only one thread is in the critical section associated with this data at any given time. It doesn't matter if the thread is in the active or suspended state. This approach is called mutual exclusion. The operating system uses different ways to implement mutual exclusion. Some methods are suitable for mutual exclusion when only threads of one process enter the critical section, while others can provide mutual exclusion for threads of different processes.
The simplest and at the same time the most inefficient way to achieve mutual exclusion is to allow the operating system to allow a thread to disable any interrupts while it is in the critical section. However, this method is practically not used, since it is dangerous to trust system control to a user thread - it can take a long time for the processor, and if a thread in a critical section crashes, the entire system will crash, because interrupts will never be allowed.
2. Synchronization mechanisms.
Blocking variables
To synchronize the threads of a single process, an application programmer can use global blocking variables. With these variables, to which all threads of the process have direct access, the programmer works without resorting to OS system calls.
Which would disable interrupts throughout the entire verification and installation operation.
The implementation of mutual exclusion in the way described above has a significant drawback: during the time when one thread is in the critical section, another thread that needs the same resource, having gained access to the processor, will continuously poll the blocking variable, wasting the processor time allocated to it, which could be used to execute some other thread. To eliminate this shortcoming, many operating systems provide special system calls for working with critical sections.
On fig. Figure 4-19 shows how these functions implement mutual exclusion in the Windows NT operating system. Before starting to change critical data, the thread executes the EnterCriticalSection() system call. As part of this call, first, as in the previous case, a check is made for a blocking variable that reflects the state of a critical resource. If the system call determined that the resource is busy (F(D) = 0), unlike the previous case, it does not perform a cyclic poll, but puts the thread in the waiting state (D) and makes a mark that this thread should be activated, when the corresponding resource becomes free. The thread that is currently using this resource, after leaving the critical section, it must execute the LeaveCriticalSectionO system function, as a result of which the blocking variable takes the value corresponding to the free state of the resource (F(D) = 1), and the operating system scans the queue of threads waiting for this resource and transfers the first thread from the queue to the state readiness.
Overhead" href="/text/category/nakladnie_rashodi/" rel="bookmark">OS overhead for implementing the critical section entry and exit function may exceed the savings.
semaphores
A generalization of blocking variables are the so-called Dijkstra's semaphores. Instead of binary variables, Dijkstra suggested using variables that can take non-negative integer values. Such variables used to synchronize computational processes are called semaphores.
To work with semaphores, two primitives are introduced, traditionally denoted by P and V. Let the variable S be a semaphore. Then the actions V(S) and P(S) are defined as follows.
* V(S): Variable S is incremented by 1 in a single action. Sampling, growing and storing cannot be interrupted. The variable S is not accessed by other threads during this operation.
* P(S): decrease S by 1 if possible. If 5=0 and it is impossible to decrease S while remaining in the region of non-negative integers, then in this case the thread calling operation P waits until this decrease becomes possible. A successful check and a decrease are also an indivisible operation.
No interrupts are allowed during the execution of the V and P primitives.
In the particular case where the semaphore S can only take on the values 0 and 1, it becomes a blocking variable, which is often called a binary semaphore for this reason. The P operation contains the potential for the thread that is executing it to enter a waiting state, while the V operation may, under some circumstances, wake up another thread suspended by the P operation.
Consider the use of semaphores on a classic example of the interaction of two threads running in multiprogramming mode, one of which writes data to the buffer pool, and the other reads them from the buffer pool. Let the buffer pool consist of N buffers, each of which can contain one record. In general, a writer thread and a reader thread can have different speeds and access the buffer pool at varying rates. In one period, the write speed may exceed the read speed, in the other - vice versa. For the correct joint work The writer thread must pause when all buffers are full and wake up when at least one buffer is freed. In contrast, the reader thread should pause when all buffers are empty and wake up when at least one entry appears.
We introduce two semaphores: e - the number of empty buffers, and f - the number of filled buffers, and in the initial state e = N, and f = 0. Then the work of threads with a common buffer pool can be described as follows (Fig. 4.20).
The writer thread first of all performs the P(e) operation, with which it checks whether there are empty buffers in the buffer pool. In accordance with the semantics of the P operation, if the semaphore e is equal to 0 (that is, there are no free buffers at the moment), then the writer thread enters the waiting state. If the value of e is a positive number, then it reduces the number of free buffers, writes data to the next free buffer, and then increases the number of occupied buffers with the V(f) operation. The reader thread acts in a similar way, with the difference that it starts by checking for full buffers, and after reading the data, it increases the number of free buffers.
DIV_ADBLOCK860">
A semaphore can also be used as a blocking variable. In the above example, in order to avoid collisions when working with a shared memory area, we will assume that writing to the buffer and reading from the buffer are critical sections. Mutual exclusion will be provided using the binary semaphore b (Fig. 4.21). Both threads, after checking the availability of buffers, must check the availability of the critical section.
https://pandia.ru/text/78/239/images/image007_110.jpg" width="495" height="639 src=">
Rice. 4.22. Occurrence of deadlocks during program execution
NOTE
Deadlocks must be distinguished from simple queues, although both occur when sharing resources and look similar on the surface: a thread is suspended and waiting for a resource to be released. However, queuing is a normal occurrence, an inherent sign of high resource utilization when requests arrive randomly. The queue appears when the resource is not available at the moment, but will become free after some time, allowing the thread to continue executing. A dead end, as its name implies, is in some way an unsolvable situation. A necessary condition for the occurrence of a deadlock is the need for a thread in several resources at once.
In the considered examples, the deadlock was formed by two threads, but more threads can mutually block each other. On fig. Figure 2.23 shows such a distribution of resources Ri between several threads Tj, which led to the occurrence of deadlocks. Arrows indicate the flow's need for resources. A solid arrow means that the corresponding resource has been allocated to a thread, while a dashed arrow connects a thread to a resource that is needed but cannot be allocated yet because it is being occupied by another thread. For example, thread T1 needs resources R1 and R2 to perform work, of which only one is allocated - R1, and resource R2 is held by thread T2. None of the four threads shown in the figure can continue their work, since they do not have all the resources necessary for this.
The impossibility of threads to complete the work they have started due to the occurrence of deadlocks reduces the performance of the computing system. Therefore, much attention is paid to the problem of deadlock prevention. In the event that a deadlock does occur, the system must provide the administrator-operator with the means by which he could recognize the deadlock, distinguish it from a normal blockage due to temporary unavailability of resources. And finally, if a deadlock is diagnosed, then means are needed to remove the deadlocks and restore the normal computing process.
The owner" href="/text/category/vladeletc/" rel="bookmark">owner by setting it to the non-signaled state, and enters the critical section. the mutex is free and does not belong to any thread, if any thread is waiting for it to become free, then it becomes the next owner of this mutex, at the same time the mutex goes into the non-signaled state.
Event object (in this case, the word "event" is used in a narrow sense, as a designation specific type Synchronization Objects) is typically used not to access data, but to notify other threads that some activity has been completed. Let, for example, in some application work is organized in such a way that one thread reads data from a file into a memory buffer, and other threads process this data, then the first thread reads a new portion of data, and other threads process it again, and so on. At the beginning of work, the first thread sets the event object to the non-signaled state. All other threads have made a call to Wait(X), where X is the event pointer, and are in a suspended state, waiting for that event to occur. As soon as the buffer fills up, the first thread notifies the operating system by issuing a Set(X) call. The operating system looks through the queue of waiting threads and activates all threads that are waiting for this event.
Signals
Signal allows a task to respond to an event that can be generated by the operating system or another task. Signals drop out interrupting a task and performing predetermined actions. Signals can be generated synchronously, that is, as a result of the work of the process itself, or they can be sent to the process by another process, that is, they can be generated asynchronously. Synchronous signals most often come from the processor's interrupt system and indicate process actions blocked by the hardware, such as division by zero, addressing error, memory protection violation, etc.
An example of an asynchronous signal is a signal from a terminal. Many operating systems provide for the prompt removal of a process from execution. To do this, the user can press some combination of keys (Ctrl + C, Ctrl + Break), as a result of which the OS generates a signal and sends it to the active process. The signal can arrive at any time during the execution of the process (that is, it is asynchronous), requiring the process to terminate immediately. In this case, the reaction to the signal is the unconditional termination of the process.
A set of signals can be defined in the system. The program code of the process that received the signal can either ignore it, or react to it with a standard action (for example, terminate), or perform specific actions defined by the application programmer. In the latter case, it is necessary to provide special system calls in the program code, with the help of which the operating system is informed which procedure should be performed in response to the arrival of a particular signal.
Signals provide a logical link between processes and between processes and users (terminals). Since sending a signal requires knowledge of the process ID, communication through signals is possible only between related processes that can learn about each other's IDs.
AT distributed systems, consisting of several processors, each of which has its own main memory, blocking variables, semaphores, signals, and other similar facilities based on shared memory are unusable. In such systems, synchronization can only be realized through the exchange of messages.
This synchronization object can only be used locally within the process that created it. The rest of the objects can be used to synchronize the threads of different processes. The name of the object “critical section” is associated with some abstract selection of a part of the program code (section) that performs some operations, the order of which cannot be violated. That is, an attempt by two different threads to simultaneously execute the code of this section will result in an error.
For example, it may be convenient to protect writer functions with such a section, since simultaneous access by several writers should be excluded.
Two operations are introduced for the critical section:
enter the section While any thread is in the critical section, all other threads will automatically stop waiting when they try to enter it. A thread that has already entered this section can enter it multiple times without waiting for it to be freed.
leave the section When a thread leaves a section, the counter of the number of entries of this thread into the section is decremented, so that the section will be freed for other threads only if the thread exits the section as many times as it entered it. When a critical section is released, only one thread will be awakened, waiting for permission to enter this section.
Generally speaking, in other non-Win32 APIs (such as OS/2), the critical section is not treated as a synchronization object, but as a piece of program code that can be executed by only one application thread. That is, entering the critical section is considered as a temporary shutdown of the thread switching mechanism until the exit from this section. In the Win32 API, critical sections are treated as objects, which leads to some confusion -- they are very similar in their properties to unnamed exclusive objects ( mutex, see below).
When using critical sections, you need to make sure that too large code fragments are not allocated to the section, as this can lead to significant delays in the execution of other threads.
For example, in relation to the already considered heaps, it does not make sense to protect all heap functions with a critical section, since reader functions can be executed in parallel. Moreover, the use of a critical section even for synchronizing writers actually seems to be inconvenient - since in order to synchronize a writer with readers, the latter will still have to enter this section, which practically leads to the protection of all functions by a single section.
There are several cases of effective use of critical sections:
readers do not conflict with writers (only writers need to be protected);
all threads have roughly equal access rights (say, you can't single out pure writers and readers);
when constructing compound synchronizing objects, consisting of several standard ones, to protect sequential operations on a compound object.
The Windows operating system supports four types of synchronization object.
- The first type is a classic semaphore and can be used to control access to certain resources by a limited number of threads. The shared resource in this case can be used by one and only one thread, or by a certain number of threads from the set claiming this resource. Semaphores are implemented as simple counters that increment when a thread releases the semaphore and decrement when the thread acquires the semaphore.
- The second type of synchronization object is called an exclusive semaphore (mutex). Exclusive semaphores are used to partition resources so that one and only one thread can use them at any given time. Obviously, an exclusive semaphore is a special type of regular semaphore.
- The third type of synchronization object is the event. Events can be used to block access to a resource until another thread signals its release.
- The fourth type of synchronization object is the critical section. When a thread enters a critical section, no other thread can start executing it until the thread working with it exits it.
It should be noted that thread synchronization using critical sections can only be carried out within the framework of one process, since it is impossible to transfer the address of a critical section from one process to another, since the critical section is located in the scope of global variables of the running process.
A semaphore is created using the CreateSemaphore function. The number of tasks that simultaneously have access to some resource is determined by one of the function parameters. If the value of this function is 1, then the semaphore works as an exclusive one. At successful creation semaphore, its handle is returned, otherwise null. The WaitForSingleObject function provides a wait mode for a semaphore. One of the parameters specifies its timeout in milliseconds. If the value of this parameter is INFINITE, then the timeout is indefinite. Upon successful completion of the function, the value of the counter associated with the semaphore is decremented by more than one. The ReleaseSemaphore() function releases the semaphore, allowing another thread to use it.
An exclusive mutex semaphore is created using the CreateMutex() function, which returns the identifier of the created object, or null on error. If necessary, the object is released using the universal CloseHandle() function. Knowing the name of the mutex object, it can be opened using the OpenMutex() function. With this feature, multiple threads can open the same object and then wait on it at the same time. Once the name of an object is known to a thread, it can acquire it using the WaitForSingleObject or WaitForMultipleObjects functions. A mutex object is released using the ReleaseMutex() function.
An event is created using the CreateEvent function. It returns a handle to the generated event, or null on failure. After creating an event, the thread simply waits for it to occur using the WaitForSingleObject function, setting the handle to this event as the first parameter for it. Thus, the execution of the thread is suspended until the corresponding event occurs. After calling the SetEvent function, the process that is waiting for this event using the WaitForSingleObject function will continue its execution. The event can be reset using the ResetEvent function.
Threads can be in one of several states:
Ready(ready) - located in the pool of threads awaiting execution;
Running(execution) - running on the processor;
Waiting(waiting), also called idle or suspended, suspended - in a waiting state, which ends with the thread starting to run (Running state) or entering the state Ready;
Terminated (completion) - execution of all commands of the thread has been completed. It can be removed later. If the stream is not removed, the system can reset it to its original state for later use.
Thread Synchronization
Running threads often need to communicate in some way. For example, if multiple threads are trying to access some global data, then each thread needs to protect the data from being modified by another thread. Sometimes one thread needs to know when another thread has finished executing a task. Such interaction is mandatory between threads of both one and different processes.
Thread Synchronization ( thread synchronization) is a generalized term referring to the process of interaction and interconnection of flows. Note that thread synchronization requires the operating system itself to act as an intermediary. Threads cannot interact with each other without her participation.
There are several methods for synchronizing threads in Win32. It happens that in a particular situation one method is more preferable than another. Let's take a quick look at these methods.
Critical sections
One method for synchronizing threads is to use critical sections. This is the only thread synchronization method that does not involve the Windows kernel. (The critical section is not a kernel object). However, this method can only be used to synchronize threads in a single process.
A critical section is a piece of code that can only be executed by one of the threads at a time. If the code used to initialize an array is placed in a critical section, then other threads will not be able to enter this section of code until the first thread completes its execution.
Before using a critical section, you must initialize it using the Win32 API procedure InitializeCriticalSection(), which is defined (in Delphi) as follows:
procedure InitializeCriticalSection(var IpCriticalSection: TRTLCriticalSection); stdcall;
The IpCriticalSection parameter is an entry of type TRTLCriticalSection that is passed by reference. The exact definition of the TRTLCriticalSection entry is of little importance, since you are unlikely to ever look into its contents. All you need to do is pass an uninitialized entry to the IpCtitical Section parameter, and that entry will be populated by the procedure immediately.
After filling the record in the program, you can create a critical section by placing some portion of its text between calls to the EnterCriticalSection() and LeaveCriticalSection() functions. These procedures are defined as follows:
procedure EnterCriticalSection(var IpCriticalSection: TRTLCriticalSection); stdcall;
procedure LeaveCriticalSection(var IpCriticalSection: TRTLCriticalSection); stdcall;
The IpCriticalSection parameter that is passed to these procedures is nothing more than an entry created by the InitializeCriticalSection() procedure.
Function EnterCriticalSection checks to see if another thread is already executing the critical section of its program associated with the given critical section object. If not, the thread is allowed to execute its critical code, or rather, it is not prevented from doing so. If so, then the thread that made the request is put into a waiting state, and a record is made of the request. Since records need to be created, the critical section object is a data structure.
When the function LeaveCriticalSection is called by the thread that currently owns permission to execute its critical section of code associated with this critical section object, the system can check to see if there is another thread in the queue waiting for this object to be freed. The system can then bring the waiting thread out of the waiting state, and it will continue its work (in the time slices allocated to it).
When you are done with the TRTLCriticalSection entry, you must release it by calling the DeleteCriticalSection() procedure, which is defined as follows:
procedure DeleteCriticalSection(var IpCriticalSection: TRTLCriticalSection); stdcall;
