Mongo DB

OS concept 2011. 12. 12. 23:52

2011년 11월 infoq에 mongo DB에 대한 글이 하나 실렸다. 

http://www.infoq.com/news/2011/11/MongoDB-Criticism

주로 아래 두개의 글을 참조해서 만들어진 것이다. 
- http://blog.schmichael.com/2011/11/05/failing-with-mongodb/
-  http://pastebin.com/raw.php?i=FD3xe6Jt

글에 따르면, mongo db의 한계로 지적한 내용은 다음과 같다.  
- global write lock으로 인한 성능 문제
- 이상한 replication에 따른 데이터 손실 (레코드 손실)
- 부하가 많은 상황에서의 샤딩, replication 문제
- 데이터셋을 몽땅 날리는 문제
- recovery가 안되는 문제


mongo DB가 nosql 에서는 가장 잘 나가고 있는데,
초기 버전이다 보니 scale과 replication 부분에서 다양한 문제들을 만나면서 버그들이 나오는 것 같다.
어서 빨리 안정화가 되길.. 10gen 화이팅~


'OS concept' 카테고리의 다른 글

구글 크롬 OS 30분 맛보기  (0) 2011.05.20
Endian 유래  (0) 2006.07.20
임베디드 시스템의 기본 #1  (0) 2006.07.20
실시간 운영체제 종류  (0) 2006.01.23
Synchronization primitives  (0) 2005.02.28
Posted by '김용환'
,


첨부파일 참조

'OS concept' 카테고리의 다른 글

Mongo DB  (0) 2011.12.12
Endian 유래  (0) 2006.07.20
임베디드 시스템의 기본 #1  (0) 2006.07.20
실시간 운영체제 종류  (0) 2006.01.23
Synchronization primitives  (0) 2005.02.28
Posted by '김용환'
,

Endian 유래

OS concept 2006. 7. 20. 07:38
http://en.wikipedia.org/wiki/Gulliver's_Travels  
In the discipline of Computer Architecture, the terms big-endian and little-endian are used to describe two possible ways of laying out bytes in memory (see endianness). One of the conflicts in the book is between people who preferred cracking open their soft-boiled eggs from the little end, and the people who preferred the big end.


다들 다 아는 내용이겠지만, 걸리버의 여행기로부터 Little endian과 Big endian의 유래가 나왔다가 한다. 뾰족한 부분 혹은 둥글한 부분을 깨는 부분에 따라서 유래가 나왔다.

Big Endian과 Little Endian은 알아도 Medium Endian이라는 것도 있다.
명확히 알기 위해서 http://en.wikipedia.org/wiki/Endianness 를 참조한다.

100번에 4A3B2C1D를 저장한다고 가정해 보자.
 
각 종류마다 저장방식이 다르다.
 
Big-endian
100 101 102 103
... 4A 3B 2C 1D ...


Little-endian

100 101 102 103
... 1D 2C 3B 4A ...



Middle-endian

100 101 102 103
... 3B 4A 1D 2C ...

or alternatively:

100 101 102 103
... 2C 1D 4A 3B ...



middle endian방식은 mixed라고 불려진다.

운영체제가 지원하는 endian 지원 방식을 헛갈리지 말자~

'OS concept' 카테고리의 다른 글

Mongo DB  (0) 2011.12.12
구글 크롬 OS 30분 맛보기  (0) 2011.05.20
임베디드 시스템의 기본 #1  (0) 2006.07.20
실시간 운영체제 종류  (0) 2006.01.23
Synchronization primitives  (0) 2005.02.28
Posted by '김용환'
,
시스템의 동작 싸이클은 다음과 같다.
아마도 이 틀에서 거의 바뀌지는 않을 것이다.


int main() // Entry point
{
   init();  // H/W, 인터럽트, 모듈의 초기화

   while(1) {
       // 무한 동작
       // 모듈을 실행시킨다.
   }

   return TRUE;
}


// Interrupt Hander: callback 형태로 구현
int getFib() {

}

'OS concept' 카테고리의 다른 글

구글 크롬 OS 30분 맛보기  (0) 2011.05.20
Endian 유래  (0) 2006.07.20
실시간 운영체제 종류  (0) 2006.01.23
Synchronization primitives  (0) 2005.02.28
Multi-Threaded Programming With POSIX Threads  (0) 2005.02.28
Posted by '김용환'
,

VxWork, Ada, BeOS, Chous OS, eCos, 프리 RTOS, ITRON, LunxOS, MicrioC/OS-2, OS-9, OSE, OSEK/VDX, pSos, QNX, RMX, RSX-11, RTOS-UH, VRTX, Velos, 윈도우 CE, RT 리눅스, RTAI

 

성공적인 상용 운영체제 - VxWorks, 윈도우 CE

비사용 운영체제 - linux

'OS concept' 카테고리의 다른 글

Endian 유래  (0) 2006.07.20
임베디드 시스템의 기본 #1  (0) 2006.07.20
Synchronization primitives  (0) 2005.02.28
Multi-Threaded Programming With POSIX Threads  (0) 2005.02.28
Application Development Guide --Conditional variable  (0) 2005.02.28
Posted by '김용환'
,

Synchronization primitives

Note that there are no "official" definitions for these terms, so different texts and implementations associate slightly different characteristics with each primitive.

semaphores
Two operations, performed by any thread:
original Dijkstra P() V()
Tanenbaum down() up()
POSIX sem_wait() sem_post()
Silberschatz wait() signal()
operation while (s==0) {wait}; s-- s++
Note that signals are saved, unlike condition variables. Useful for counting resources (initial value > 1), to implement mutexes (initial value 1) or to signal completion of code across threads (initial value 0). Some semaphore implementations allow decrementing by more than one.
mutex
Also known as a lock. Supports lock/unlock operation. In many implementations, the same thread must lock and unlock, but different threads can share the same mutex. POSIX says: "Mutexes have ownership, unlike semaphores. Although any thread, within the scope of a mutex, can get an unlocked mutex and lock access to the same critical section of code, only the thread that locked a mutex can unlock it." Can be implemented via a semaphore.
binary semaphore
Semaphore that can take two values, 0 and 1. Can be used as a mutex or to signal completion of code across threads.
locks
Same as mutex.
events (from Tanenbaum, Nutt)
Nutt: similar to condition variables, without the mutex
signals (from Tanenbaum)
Signals are "interrupts" that cause a process to asynchronously either abort or jump to a signal handler designated by the process. Pending system calls are interrupted and return an error indication. Also used in conjunction with semaphores and condition variables.
condition variables
Condition variables allow several threads to share a monitor (region). Condition variables support two operations, signal() and wait(). Some implementations (Java, POSIX) also support a "broadcast" signal (notifyAll() in Java, pthread_cond_broadcast in POSIX). A thread that reaches a wait in a monitor always waits until another thread sends a signal. If several threads are waiting on a condition variable, signal awakens one of them, while the broadcast signal awakens all.

The choice of threads being signaled depends on the implementation. Most implementations make no guarantees.

Condition variables are not counters (i.e., unlike semaphors). Signals do not accumulate. If there is nobody waiting for a signal, the signal is lost.

AND synchronization (Nutt, p. 222)
Obtains all required semaphores or none at all. Can possibly be implemented using a T&S with a bit mask.
monitors
Class or segment of code that can only be executed by one thread at a time. Variables within the monitor can only be accessed by routines in the monitor. Monitor often use condition variables to allow blocking within the monitor.
Test-and-set machine instructions
Atomic instruction that sets the value of a memory location to "true". It returns the value the memory location had before setting it. It can be used to implement semaphores and locks. It does not block.
property lock semaphore condition variable
method that blocks calling thread (ANSI) acquire(), mutex_lock() sem_wait() pthread_cond_wait()
method that releases mutex_unlock() (same thread) sem_post() (same or other thread) pthread_cond_signal() (other thread)
method that probes without blocking pthread_mutex_trylock() sem_trywait() not available
behavior of first thread to reach wait doesn't block doesn't block unless semaphore initialized to zero blocks
data members
List *threads;   /* waiting threads */
boolean locked;
List *threads;
unsigned int count;
List *threads;
Lock *mutex;

FAQ

Is a lock variable and a mutex the same thing?
Yes. Unfortunately, you'll also find mutex used as the name for a semaphore variable (e.g., Silberschatz, p. 174)
Is an event and a condition variable the same thing, except an event signals all processes waiting on it and a condition variable signals only one process?
Condition variables are used with monitors, i.e., in association with a mutex, events are used by themselves. Both can use "broadcast" signaling, as in notifyAll in Java.
Is a mutex and a conditional variable the same thing except a mutex has a value associated with it and a conditional variable does not?
No, if no other process has locked the mutex, the thread will "pass by" the mutex without waiting. For a condition variable, the thread will always wait until being signaled.
How is thread blocking really implemented?
Text books typically show some kind of waiting operation that blocks the thread when it needs to wait for a resource. However, this doesn't really work unless you had some kind of message system and a single thread per processor. Thus, in reality, a thread will put itself on the queue for a synchronization primitive and then suspend itself. When the synchronization variable unlocks (gets signaled, etc.), the calling process removes the first waiting thread from the queue and puts its back on the ready queue for scheduling. With condition variables, the signaling thread may also suspend itself.
What is the typical use of condition variables?
Condition variables not used to protect anything. The associated mutex does, but that's no different from a lock. A CV is a mechanism to temporarily release the lock until some event occurs that makes it sensible for the waiting thread to continue.

Thus, the thread calling the wait() often looks something like

lock to protect variables;
while (1) {
  wait (until work/message/condition/event arrives, 
    possibly from one of several sources; unlock mutex while waiting);
  get new work, protected by mutex;
}
This is sometimes called a worker thread.

Any of the threads that are sources for work then do

while (1) {
  read(); /* some blocking operation on a channel/file/network socket */
  get lock;
  put work on some queue protected by lock;
  release lock; /* be sure to do this *before* signaling 
    - otherwise the wait() in the worker thread can't return */
  signal to worke thread;  /* we got work for you! */
}
R4000 synchronization primitives
Posted by '김용환'
,


[
LUPG Home] [Tutorials] [Related Material] [Essays] [Project Ideas] [Send Comments]

v1.2

Multi-Threaded Programming With POSIX Threads

Table Of Contents:

  1. Before We Start...
  2. What Is a Thread? Why Use Threads?
  3. Creating And Destroying Threads
  4. Synchronizing Threads With Mutexes
    1. What Is A Mutex?
    2. Creating And Initializing A Mutex
    3. Locking And Unlocking A Mutex
    4. Destroying A Mutex
    5. Using A Mutex - A Complete Example
    6. Starvation And Deadlock Situations
  5. Refined Synchronization - Condition Variables
    1. What Is A Condition Variable?
    2. Creating And Initializing A Condition Variable
    3. Signaling A Condition Variable
    4. Waiting On A Condition Variable
    5. Destroying A Condition Variable
    6. A Real Condition For A Condition Variable
    7. Using A Condition Variable - A Complete Example
  6. "Private" thread data - Thread-Specific Data
    1. Overview Of Thread-Specific Data Support
    2. Allocating Thread-Specific Data Block
    3. Accessing Thread-Specific Data
    4. Deleting Thread-Specific Data Block
    5. A Complete Example
  7. Thread Cancellation And Termination
    1. Canceling A Thread
    2. Setting Thread Cancellation State
    3. Cancellation Points
    4. Setting Thread Cleanup Functions
    5. Synchronizing On Threads Exiting
    6. Detaching A Thread
    7. Threads Cancellation - A Complete Example
  8. Using Threads For Responsive User Interface Programming
    1. User Interaction - A Complete Example
  9. Using 3rd-Party Libraries In A Multi-Threaded Application
  10. Using A Threads-Aware Debugger


Before We Start...

This tutorial is an attempt to help you become familiar with multi-threaded programming with the POSIX threads (pthreads) library, and attempts to show how its features can be used in "real-life" programs. It explains the different tools defined by the library, shows how to use them, and then gives an example of using them to solve programming problems. There is an implicit assumption that the user has some theoretical familiarity with paralell programming (or multi-processing) concepts. Users without such background might find the concepts harder to grasp. A seperate tutorial will be prepared to explain the theoreticl background and terms to those who are familiar only with normal "serial" programming.

I would assume that users which are familiar with asynchronous programming models, such as those used in windowing environments (X, Motif), will find it easier to grasp the concepts of multi-threaded programming.

When talking about POSIX threads, one cannot avoid the question "Which draft of the POSIX threads standard shall be used?". As this threads standard has been revised over a period of several years, one will find that implementations adhering to different drafts of the standard have a different set of functions, different default values, and different nuances. Since this tutorial was written using a Linux system with the kernel-level LinuxThreads library, v0.5, programmers with access to other systems, using different versions of pthreads, should refer to their system's manuals in case of incompatibilities. Also, since some of the example programs are using blocking system calls, they won't work with user-level threading libraries (refer to our parallel programming theory tutorial for more information).
Having said that, i'd try to check the example programs on other systems as well (Solaris 2.5 comes to mind), to make it more "cross-platform".


What Is a Thread? Why Use Threads

A thread is a semi-process, that has its own stack, and executes a given piece of code. Unlike a real process, the thread normally shares its memory with other threads (where as for processes we usually have a different memory area for each one of them). A Thread Group is a set of threads all executing inside the same process. They all share the same memory, and thus can access the same global variables, same heap memory, same set of file descriptors, etc. All these threads execute in parallel (i.e. using time slices, or if the system has several processors, then really in parallel).

The advantage of using a thread group instead of a normal serial program is that several operations may be carried out in parallel, and thus events can be handled immediately as they arrive (for example, if we have one thread handling a user interface, and another thread handling database queries, we can execute a heavy query requested by the user, and still respond to user input while the query is executed).

The advantage of using a thread group over using a process group is that context switching between threads is much faster than context switching between processes (context switching means that the system switches from running one thread or process, to running another thread or process). Also, communications between two threads is usually faster and easier to implement than communications between two processes.

On the other hand, because threads in a group all use the same memory space, if one of them corrupts the contents of its memory, other threads might suffer as well. With processes, the operating system normally protects processes from one another, and thus if one corrupts its own memory space, other processes won't suffer. Another advantage of using processes is that they can run on different machines, while all the threads have to run on the same machine (at least normally).


Creating And Destroying Threads

When a multi-threaded program starts executing, it has one thread running, which executes the main() function of the program. This is already a full-fledged thread, with its own thread ID. In order to create a new thread, the program should use the pthread_create() function. Here is how to use it:



#include <stdio.h>       /* standard I/O routines                 */
#include <pthread.h>     /* pthread functions and data structures */

/* function to be executed by the new thread */
void*
do_loop(void* data)
{
    int i;			/* counter, to print numbers */
    int j;			/* counter, for delay        */
    int me = *((int*)data);     /* thread identifying number */

    for (i=0; i<10; i++) {
	for (j=0; j<500000; j++) /* delay loop */
	    ;
        printf("'%d' - Got '%d'\n", me, i);
    }

    /* terminate the thread */
    pthread_exit(NULL);
}

/* like any C program, program's execution begins in main */
int
main(int argc, char* argv[])
{
    int        thr_id;         /* thread ID for the newly created thread */
    pthread_t  p_thread;       /* thread's structure                     */
    int        a         = 1;  /* thread 1 identifying number            */
    int        b         = 2;  /* thread 2 identifying number            */

    /* create a new thread that will execute 'do_loop()' */
    thr_id = pthread_create(&p_thread, NULL, do_loop, (void*)&a);
    /* run 'do_loop()' in the main thread as well */
    do_loop((void*)&b);
    
    /* NOT REACHED */
    return 0;
}

A few notes should be mentioned about this program:

  1. Note that the main program is also a thread, so it executes the do_loop() function in parallel to the thread it creates.
  2. pthread_create() gets 4 parameters. The first parameter is used by pthread_create() to supply the program with information about the thread. The second parameter is used to set some attributes for the new thread. In our case we supplied a NULL pointer to tell pthread_create() to use the default values. The third parameter is the name of the function that the thread will start executing. The forth parameter is an argument to pass to this function. Note the cast to a 'void*'. It is not required by ANSI-C syntax, but is placed here for clarification.
  3. The delay loop inside the function is used only to demonstrate that the threads are executing in parallel. Use a larger delay value if your CPU runs too fast, and you see all the printouts of one thread before the other.
  4. The call to pthread_exit() Causes the current thread to exit and free any thread-specific resources it is taking. There is no need to use this call at the end of the thread's top function, since when it returns, the thread would exit automatically anyway. This function is useful if we want to exit a thread in the middle of its execution.

In order to compile a multi-threaded program using gcc, we need to link it with the pthreads library. Assuming you have this library already installed on your system, here is how to compile our first program:

gcc pthread_create.c -o pthread_create -lpthread

Note that for some of the programs later on this tutorial, one may need to add a '-D_GNU_SOURCE' flag to this compile line, to get the source compiled.

The source code for this program may be found in the pthread_create.c file.


Synchronizing Threads With Mutexes

One of the basic problems when running several threads that use the same memory space, is making sure they don't "step on each other's toes". By this we refer to the problem of using a data structure from two different threads.

For instance, consider the case where two threads try to update two variables. One tries to set both to 0, and the other tries to set both to 1. If both threads would try to do that at the same time, we might get with a situation where one variable contains 1, and one contains 0. This is because a context-switch (we already know what this is by now, right?) might occur after the first tread zeroed out the first variable, then the second thread would set both variables to 1, and when the first thread resumes operation, it will zero out the second variable, thus getting the first variable set to '1', and the second set to '0'.


What Is A Mutex?

A basic mechanism supplied by the pthreads library to solve this problem, is called a mutex. A mutex is a lock that guarantees three things:

  1. Atomicity - Locking a mutex is an atomic operation, meaning that the operating system (or threads library) assures you that if you locked a mutex, no other thread succeeded in locking this mutex at the same time.
  2. Singularity - If a thread managed to lock a mutex, it is assured that no other thread will be able to lock the thread until the original thread releases the lock.
  3. Non-Busy Wait - If a thread attempts to lock a thread that was locked by a second thread, the first thread will be suspended (and will not consume any CPU resources) until the lock is freed by the second thread. At this time, the first thread will wake up and continue execution, having the mutex locked by it.

From these three points we can see how a mutex can be used to assure exclusive access to variables (or in general critical code sections). Here is some pseudo-code that updates the two variables we were talking about in the previous section, and can be used by the first thread:

lock mutex 'X1'.
set first variable to '0'.
set second variable to '0'.
unlock mutex 'X1'.


Meanwhile, the second thread will do something like this:

lock mutex 'X1'.
set first variable to '1'.
set second variable to '1'.
unlock mutex 'X1'.


Assuming both threads use the same mutex, we are assured that after they both ran through this code, either both variables are set to '0', or both are set to '1'. You'd note this requires some work from the programmer - If a third thread was to access these variables via some code that does not use this mutex, it still might mess up the variable's contents. Thus, it is important to enclose all the code that accesses these variables in a small set of functions, and always use only these functions to access these variables.


Creating And Initializing A Mutex

In order to create a mutex, we first need to declare a variable of type pthread_mutex_t, and then initialize it. The simplest way it by assigning it the PTHREAD_MUTEX_INITIALIZER constant. So we'll use a code that looks something like this:


pthread_mutex_t a_mutex = PTHREAD_MUTEX_INITIALIZER;


One note should be made here: This type of initialization creates a mutex called 'fast mutex'. This means that if a thread locks the mutex and then tries to lock it again, it'll get stuck - it will be in a deadlock.

There is another type of mutex, called 'recursive mutex', which allows the thread that locked it, to lock it several more times, without getting blocked (but other threads that try to lock the mutex now will get blocked). If the thread then unlocks the mutex, it'll still be locked, until it is unlocked the same amount of times as it was locked. This is similar to the way modern door locks work - if you turned it twice clockwise to lock it, you need to turn it twice counter-clockwise to unlock it. This kind of mutex can be created by assigning the constant PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP to a mutex variable.


Locking And Unlocking A Mutex

In order to lock a mutex, we may use the function pthread_mutex_lock(). This function attempts to lock the mutex, or block the thread if the mutex is already locked by another thread. In this case, when the mutex is unlocked by the first process, the function will return with the mutex locked by our process. Here is how to lock a mutex (assuming it was initialized earlier):


int rc = pthread_mutex_lock(&a_mutex);
if (rc) { /* an error has occurred */
    perror("pthread_mutex_lock");
    pthread_exit(NULL);
}
/* mutex is now locked - do your stuff. */
.
.


After the thread did what it had to (change variables or data structures, handle file, or whatever it intended to do), it should free the mutex, using the pthread_mutex_unlock() function, like this:


rc = pthread_mutex_unlock(&a_mutex);
if (rc) {
    perror("pthread_mutex_unlock");
    pthread_exit(NULL);
}


Destroying A Mutex

After we finished using a mutex, we should destroy it. Finished using means no thread needs it at all. If only one thread finished with the mutex, it should leave it alive, for the other threads that might still need to use it. Once all finished using it, the last one can destroy it using the pthread_mutex_destroy() function:


rc = pthread_mutex_destroy(&a_mutex);


After this call, this variable (a_mutex) may not be used as a mutex any more, unless it is initialized again. Thus, if one destroys a mutex too early, and another thread tries to lock or unlock it, that thread will get a EINVAL error code from the lock or unlock function.


Using A Mutex - A Complete Example

After we have seen the full life cycle of a mutex, lets see an example program that uses a mutex. The program introduces two employees competing for the "employee of the day" title, and the glory that comes with it. To simulate that in a rapid pace, the program employs 3 threads: one that promotes Danny to "employee of the day", one that promotes Moshe to that situation, and a third thread that makes sure that the employee of the day's contents is consistent (i.e. contains exactly the data of one employee).
Two copies of the program are supplied. One that uses a mutex, and one that does not. Try them both, to see the differences, and be convinced that mutexes are essential in a multi-threaded environment.

The programs themselves are in the files accompanying this tutorial. The one that uses a mutex is employee-with-mutex.c. The one that does not use a mutex is employee-without-mutex.c. Read the comments inside the source files to get a better understanding of how they work.


Starvation And Deadlock Situations

Again we should remember that pthread_mutex_lock() might block for a non-determined duration, in case of the mutex being already locked. If it remains locked forever, it is said that our poor thread is "starved" - it was trying to acquire a resource, but never got it. It is up to the programmer to ensure that such starvation won't occur. The pthread library does not help us with that.

The pthread library might, however, figure out a "deadlock". A deadlock is a situation in which a set of threads are all waiting for resources taken by other threads, all in the same set. Naturally, if all threads are blocked waiting for a mutex, none of them will ever come back to life again. The pthread library keeps track of such situations, and thus would fail the last thread trying to call pthread_mutex_lock(), with an error of type EDEADLK. The programmer should check for such a value, and take steps to solve the deadlock somehow.


Refined Synchronization - Condition Variables

As we've seen before with mutexes, they allow for simple coordination - exclusive access to a resource. However, we often need to be able to make real synchronization between threads:

  • In a server, one thread reads requests from clients, and dispatches them to several threads for handling. These threads need to be notified when there is data to process, otherwise they should wait without consuming CPU time.
  • In a GUI (Graphical User Interface) Application, one thread reads user input, another handles graphical output, and a third thread sends requests to a server and handles its replies. The server-handling thread needs to be able to notify the graphics-drawing thread when a reply from the server arrived, so it will immediately show it to the user. The user-input thread needs to be always responsive to the user, for example, to allow her to cancel long operations currently executed by the server-handling thread.
All these examples require the ability to send notifications between threads. This is where condition variables are brought into the picture.


What Is A Condition Variable?

A condition variable is a mechanism that allows threads to wait (without wasting CPU cycles) for some even to occur. Several threads may wait on a condition variable, until some other thread signals this condition variable (thus sending a notification). At this time, one of the threads waiting on this condition variable wakes up, and can act on the event. It is possible to also wake up all threads waiting on this condition variable by using a broadcast method on this variable.

Note that a condition variable does not provide locking. Thus, a mutex is used along with the condition variable, to provide the necessary locking when accessing this condition variable.


Creating And Initializing A Condition Variable

Creation of a condition variable requires defining a variable of type pthread_cond_t, and initializing it properly. Initialization may be done with either a simple use of a macro named PTHREAD_COND_INITIALIZER or the usage of the pthread_cond_init() function. We will show the first form here:

pthread_cond_t got_request = PTHREAD_COND_INITIALIZER;

This defines a condition variable named 'got_request', and initializes it.

Note: since the PTHREAD_COND_INITIALIZER is actually a structure initializer, it may be used to initialize a condition variable only when it is declared. In order to initialize it during runtime, one must use the pthread_cond_init() function.


Signaling A Condition Variable

In order to signal a condition variable, one should either the pthread_cond_signal() function (to wake up a only one thread waiting on this variable), or the pthread_cond_broadcast() function (to wake up all threads waiting on this variable). Here is an example using signal, assuming 'got_request' is a properly initialized condition variable:

int rc = pthread_cond_signal(&got_request);

Or by using the broadcast function:

int rc = pthread_cond_broadcast(&got_request);

When either function returns, 'rc' is set to 0 on success, and to a non-zero value on failure. In such a case (failure), the return value denotes the error that occured (EINVAL denotes that the given parameter is not a condition variable. ENOMEM denotes that the system has run out of memory.

Note: success of a signaling operation does not mean any thread was awakened - it might be that no thread was waiting on the condition variable, and thus the signaling does nothing (i.e. the signal is lost).
It is also not remembered for future use - if after the signaling function returns another thread starts waiting on this condition variable, a further signal is required to wake it up.


Waiting On A Condition Variable

If one thread signals the condition variable, other threads would probably want to wait for this signal. They may do so using one of two functions, pthread_cond_wait() or pthread_cond_timedwait(). Each of these functions takes a condition variable, and a mutex (which should be locked before calling the wait function), unlocks the mutex, and waits until the condition variable is signaled, suspending the thread's execution. If this signaling causes the thread to awake (see discussion of pthread_cond_signal() earlier), the mutex is automagically locked again by the wait funciton, and the wait function returns.

The only difference between these two functions is that pthread_cond_timedwait() allows the programmer to specify a timeout for the waiting, after which the function always returns, with a proper error value (ETIMEDOUT) to notify that condition variable was NOT signaled before the timeout passed. The pthread_cond_wait() would wait indefinitely if it was never signaled.

Here is how to use these two functions. We make the assumption that 'got_request' is a properly initialized condition variable, and that 'request_mutex' is a properly initialized mutex. First, we try the pthread_cond_wait() function:


/* first, lock the mutex */
int rc = pthread_mutex_lock(&request_mutex);
if (rc) { /* an error has occurred */
    perror("pthread_mutex_lock");
    pthread_exit(NULL);
}
/* mutex is now locked - wait on the condition variable.             */
/* During the execution of pthread_cond_wait, the mutex is unlocked. */
rc = pthread_cond_wait(&got_request, &request_mutex);
if (rc == 0) { /* we were awakened due to the cond. variable being signaled */
               /* The mutex is now locked again by pthread_cond_wait()      */
    /* do your stuff... */
    .
}
/* finally, unlock the mutex */
pthread_mutex_unlock(&request_mutex);


Now an example using the pthread_cond_timedwait() function:


#include <sys/time.h>     /* struct timeval definition           */
#include <unistd.h>       /* declaration of gettimeofday()       */

struct timeval  now;            /* time when we started waiting        */
struct timespec timeout;        /* timeout value for the wait function */
int             done;           /* are we done waiting?                */

/* first, lock the mutex */
int rc = pthread_mutex_lock(&a_mutex);
if (rc) { /* an error has occurred */
    perror("pthread_mutex_lock");
    pthread_exit(NULL);
}
/* mutex is now locked */

/* get current time */ 
gettimeofday(&now);
/* prepare timeout value.              */
/* Note that we need an absolute time. */
timeout.tv_sec = now.tv_sec + 5
timeout.tv_nsec = now.tv_usec * 1000; /* timeval uses micro-seconds.         */
                                      /* timespec uses nano-seconds.         */
                                      /* 1 micro-second = 1000 nano-seconds. */

/* wait on the condition variable. */
/* we use a loop, since a Unix signal might stop the wait before the timeout */
done = 0;
while (!done) {
    /* remember that pthread_cond_timedwait() unlocks the mutex on entrance */
    rc = pthread_cond_timedwait(&got_request, &request_mutex, &timeout);
    switch(rc) {
        case 0:  /* we were awakened due to the cond. variable being signaled */
                 /* the mutex was now locked again by pthread_cond_timedwait. */
            /* do your stuff here... */
            .
            .
            done = 0;
            break;
        default:        /* some error occurred (e.g. we got a Unix signal) */
            if (errno == ETIMEDOUT) { /* our time is up */
                done = 0;
            }
            break;      /* break this switch, but re-do the while loop.   */
    }
}
/* finally, unlock the mutex */
pthread_mutex_unlock(&request_mutex);


As you can see, the timed wait version is way more complex, and thus better be wrapped up by some function, rather than being re-coded in every necessary location.

Note: it might be that a condition variable that has 2 or more threads waiting on it is signaled many times, and yet one of the threads waiting on it never awakened. This is because we are not guaranteed which of the waiting threads is awakened when the variable is signaled. It might be that the awakened thread quickly comes back to waiting on the condition variables, and gets awakened again when the variable is signaled again, and so on. The situation for the un-awakened thread is called 'starvation'. It is up to the programmer to make sure this situation does not occur if it implies bad behavior. Yet, in our server example from before, this situation might indicate requests are coming in a very slow pace, and thus perhaps we have too many threads waiting to service requests. In this case, this situation is actually good, as it means every request is handled immediately when it arrives.

Note 2: when the mutex is being broadcast (using pthread_cond_broadcast), this does not mean all threads are running together. Each of them tries to lock the mutex again before returning from their wait function, and thus they'll start running one by one, each one locking the mutex, doing their work, and freeing the mutex before the next thread gets its chance to run.


Destroying A Condition Variable

After we are done using a condition variable, we should destroy it, to free any system resources it might be using. This can be done using the pthread_cond_destroy(). In order for this to work, there should be no threads waiting on this condition variable. Here is how to use this function, again, assuming 'got_request' is a pre-initialized condition variable:


int rc = pthread_cond_destroy(&got_request);
if (rc == EBUSY) { /* some thread is still waiting on this condition variable */
    /* handle this case here... */
    .
    .
}


What if some thread is still waiting on this variable? depending on the case, it might imply some flaw in the usage of this variable, or just lack of proper thread cleanup code. It is probably good to alert the programmer, at least during debug phase of the program, of such a case. It might mean nothing, but it might be significant.


A Real Condition For A Condition Variable

A note should be taken about condition variables - they are usually pointless without some real condition checking combined with them. To make this clear, lets consider the server example we introduced earlier. Assume that we use the 'got_request' condition variable to signal that a new request has arrived that needs handling, and is held in some requests queue. If we had threads waiting on the condition variable when this variable is signaled, we are assured that one of these threads will awake and handle this request.

However, what if all threads are busy handling previous requests, when a new one arrives? the signaling of the condition variable will do nothing (since all threads are busy doing other things, NOT waiting on the condition variable now), and after all threads finish handling their current request, they come back to wait on the variable, which won't necessarily be signaled again (for example, if no new requests arrive). Thus, there is at least one request pending, while all handling threads are blocked, waiting for a signal.

In order to overcome this problem, we may set some integer variable to denote the number of pending requests, and have each thread check the value of this variable before waiting on the variable. If this variable's value is positive, some request is pending, and the thread should go and handle it, instead of going to sleep. Further more, a thread that handled a request, should reduce the value of this variable by one, to make the count correct.
Lets see how this affects the waiting code we have seen above.



/* number of pending requests, initially none */
int num_requests = 0;
.
.
/* first, lock the mutex */
int rc = pthread_mutex_lock(&request_mutex);
if (rc) { /* an error has occurred */
    perror("pthread_mutex_lock");
    pthread_exit(NULL);
}
/* mutex is now locked - wait on the condition variable */
/* if there are no requests to be handled.              */
rc = 0;
if (num_requests == 0)
    rc = pthread_cond_wait(&got_request, &request_mutex);
if (num_requests > 0 && rc == 0) { /* we have a request pending */
        /* unlock mutex - so other threads would be able to handle */
        /* other reqeusts waiting in the queue paralelly.          */
        rc = pthread_mutex_unlock(&request_mutex);
        /* do your stuff... */
        .
        .
        /* decrease count of pending requests */
        num_requests--;
        /* and lock the mutex again - to remain symmetrical,. */
        rc = pthread_mutex_lock(&request_mutex);
    }
}
/* finally, unlock the mutex */
pthread_mutex_unlock(&request_mutex);


Using A Condition Variable - A Complete Example

As an example for the actual usage of condition variables, we will show a program that simulates the server we have described earlier - one thread, the receiver, gets client requests. It inserts the requests to a linked list, and a hoard of threads, the handlers, are handling these requests. For simplicity, in our simulation, the receiver thread creates requests and does not read them from real clients.

The program source is available in the file thread-pool-server.c, and contains many comments. Please read the source file first, and then read the following clarifying notes.

  1. The 'main' function first launches the handler threads, and then performs the chord of the receiver thread, via its main loop.
  2. A single mutex is used both to protect the condition variable, and to protect the linked list of waiting requests. This simplifies the design. As an exercise, you may think how to divide these roles into two mutexes.
  3. The mutex itself MUST be a recursive mutex. In order to see why, look at the code of the 'handle_requests_loop' function. You will notice that it first locks the mutex, and afterwards calls the 'get_request' function, which locks the mutex again. If we used a non-recursive mutex, we'd get locked indefinitely in the mutex locking operation of the 'get_request' function.
    You may argue that we could remove the mutex locking in the 'get_request' function, and thus remove the double-locking problem, but this is a flawed design - in a larger program, we might call the 'get_request' function from other places in the code, and we'll need to check for proper locking of the mutex in each of them.
  4. As a rule, when using recursive mutexes, we should try to make sure that each lock operation is accompanied by a matching unlock operation in the same function. Otherwise, it will be very hard to make sure that after locking the mutex several times, it is being unlocked the same number of times, and deadlocks would occur.
  5. The implicit unlocking and re-locking of the mutex on the call to the pthread_cond_wait() function is confusing at first. It is best to add a comment regarding this behavior in the code, or else someone that reads this code might accidentally add a further mutex lock.
  6. When a handler thread handles a request - it should free the mutex, to avoid blocking all the other handler threads. After it finished handling the request, it should lock the mutex again, and check if there are more requests to handle.


"Private" thread data - Thread-Specific Data

In "normal", single-thread programs, we sometimes find the need to use a global variable. Ok, so good old teach' told us it is bad practice to have global variables, but they sometimes do come handy. Especially if they are static variables - meaning, they are recognized only on the scope of a single file.

In multi-threaded programs, we also might find a need for such variables. We should note, however, that the same variable is accessible from all the threads, so we need to protect access to it using a mutex, which is extra overhead. Further more, we sometimes need to have a variable that is 'global', but only for a specific thread. Or the same 'global' variable should have different values in different threads. For example, consider a program that needs to have one globally accessible linked list in each thread, but note the same list. Further, we want the same code to be executed by all threads. In this case, the global pointer to the start of the list should be point to a different address in each thread.

In order to have such a pointer, we need a mechanism that enables the same global variable to have a different location in memory. This is what the thread-specific data mechanism is used for.


Overview Of Thread-Specific Data Support

In the thread-specific data (TSD) mechanism, we have notions of keys and values. Each key has a name, and pointer to some memory area. Keys with the same name in two separate threads always point to different memory locations - this is handled by the library functions that allocate memory blocks to be accessed via these keys. We have a function to create a key (invoked once per key name for the whole process), a function to allocate memory (invoked separately in each thread), and functions to de-allocate this memory for a specific thread, and a function to destroy the key, again, process-wide. we also have functions to access the data pointed to by a key, either setting its value, or returning the value it points to.


Allocating Thread-Specific Data Block

The pthread_key_create() function is used to allocate a new key. This key now becomes valid for all threads in our process. When a key is created, the value it points to defaults to NULL. Later on each thread may change its copy of the value as it wishes. Here is how to use this function:


/* rc is used to contain return values of pthread functions */
int rc;
/* define a variable to hold the key, once created.         */
pthread_key_t list_key;
/* cleanup_list is a function that can clean up some data   */
/* it is specific to our program, not to TSD                */
extern void* cleanup_list(void*);

/* create the key, supplying a function that'll be invoked when it's deleted. */
rc = pthread_key_create(&list_key, cleanup_list);


Some notes:
  1. After pthread_key_create() returns, the variable 'list_key' points to the newly created key.
  2. The function pointer passed as second parameter to pthread_key_create(), will be automatically invoked by the pthread library when our thread exits, with a pointer to the key's value as its parameter. We may supply a NULL pointer as the function pointer, and then no function will be invoked for key. Note that the function will be invoked once in each thread, even thought we created this key only once, in one thread.
    If we created several keys, their associated destructor functions will be called in an arbitrary order, regardless of the order of keys creation.
  3. If the pthread_key_create() function succeeds, it returns 0. Otherwise, it returns some error code.
  4. There is a limit of PTHREAD_KEYS_MAX keys that may exist in our process at any given time. An attempt to create a key after PTHREAD_KEYS_MAX exits, will cause a return value of EAGAIN from the pthread_key_create() function.


Accessing Thread-Specific Data

After we have created a key, we may access its value using two pthread functions: pthread_getspecific() and pthread_setspecific(). The first is used to get the value of a given key, and the second is used to set the data of a given key. A key's value is simply a void pointer (void*), so we can store in it anything that we want. Lets see how to use these functions. We assume that 'a_key' is a properly initialized variable of type pthread_key_t that contains a previously created key:



/* this variable will be used to store return codes of pthread functions */
int rc;

/* define a variable into which we'll store some data */
/* for example, and integer.                          */
int* p_num = (int*)malloc(sizeof(int));
if (!p_num) {
    fprintf(stderr, "malloc: out of memory\n";
    exit(1);
}
/* initialize our variable to some value */
(*p_num) = 4;

/* now lets store this value in our TSD key.    */
/* note that we don't store 'p_num' in our key. */
/* we store the value that p_num points to.     */
rc = pthread_setspecific(a_key, (void*)p_num);

.
.
/* and somewhere later in our code... */
.
.
/* get the value of key 'a_key' and print it. */
{
    int* p_keyval = (int*)pthread_getspecific(a_key);

    if (p_keyval != NULL) {
	printf("value of 'a_key' is: %d\n", *p_keyval);
    }
}

Note that if we set the value of the key in one thread, and try to get it in another thread, we will get a NULL, since this value is distinct for each thread.

Note also that there are two cases where pthread_getspecific() might return NULL:

  1. The key supplied as a parameter is invalid (e.g. its key wasn't created).
  2. The value of this key is NULL. This means it either wasn't initialized, or was set to NULL explicitly by a previous call to pthread_setspecific().


Deleting Thread-Specific Data Block

The pthread_key_delete() function may be used to delete keys. But do not be confused by this function's name: it does not delete memory associated with this key, nor does it call the destructor function defined during the key's creation. Thus, you still need to do memory cleanup on your own if you need to free this memory during runtime. However, since usage of global variables (and thus also thread-specific data), you usually don't need to free this memory until the thread terminate, in which case the pthread library will invoke your destructor functions anyway.

Using this function is simple. Assuming list_key is a pthread_key_t variable pointing to a properly created key, use this function like this:

int rc = pthread_key_delete(key);

the function will return 0 on success, or EINVAL if the supplied variable does not point to a valid TSD key.


A Complete Example

None yet. Give me a while to think of one...... sorry. All i can think of right now is 'global variables are evil'. I'll try to find a good example for the future. If you have a good example, please let me know.


Thread Cancellation And Termination

As we create threads, we need to think about terminating them as well. There are several issues involved here. We need to be able to terminate threads cleanly. Unlike processes, where a very ugly method of using signals is used, the folks that designed the pthreads library were a little more thoughtful. So they supplied us with a whole system of canceling a thread, cleaning up after a thread, and so on. We will discuss these methods here.


Canceling A Thread

When we want to terminate a thread, we can use the pthread_cancel function. This function gets a thread ID as a parameter, and sends a cancellation request to this thread. What this thread does with this request depends on its state. It might act on it immediately, it might act on it when it gets to a cancellation point (discussed below), or it might completely ignore it. We'll see later how to set the state of a thread and define how it acts on cancellation requests. Lets first see how to use the cancel function. We assume that 'thr_id' is a variable of type pthread_id containing the ID of a running thread:


pthread_cancel(thr_id);


The pthread_cancel() function returns 0, so we cannot know if it succeeded or not.


Setting Thread Cancellation State

A thread's cancel state may be modified using several methods. The first is by using the pthread_setcancelstate() function. This function defines whether the thread will accept cancellation requests or not. The function takes two arguments. One that sets the new cancel state, and one into which the previous cancel state is stored by the function. Here is how it is used:


int old_cancel_state;
pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &old_cancel_state);


This will disable canceling this thread. We can also enable canceling the thread like this:


int old_cancel_state;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, &old_cancel_state);


Note that you may supply a NULL pointer as the second parameter, and then you won't get the old cancel state.

A similar function, named pthread_setcanceltype() is used to define how a thread responds to a cancellation request, assuming it is in the 'ENABLED' cancel state. One option is to handle the request immediately (asynchronously). The other is to defer the request until a cancellation point. To set the first option (asynchronous cancellation), do something like:


int old_cancel_type;
pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, &old_cancel_type);


And to set the second option (deferred cancellation):


int old_cancel_type;
pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED, &old_cancel_type);


Note that you may supply a NULL pointer as the second parameter, and then you won't get the old cancel type.

You might wonder - "What if i never set the cancellation state or type of a thread?". Well, in such a case, the pthread_create() function automatically sets the thread to enabled deferred cancellation, that is, PTHREAD_CANCEL_ENABLE for the cancel mode, and PTHREAD_CANCEL_DEFERRED for the cancel type.


Cancellation Points

As we've seen, a thread might be in a state where it does not handle cancel requests immediately, but rather defers them until it reaches a cancellation point. So what are these cancellation points?

In general, any function that might suspend the execution of a thread for a long time, should be a cancellation point. In practice, this depends on the specific implementation, and how conformant it is to the relevant POSIX standard (and which version of the standard it conforms to...). The following set of pthread functions serve as cancellation points:

  • pthread_join()
  • pthread_cond_wait()
  • pthread_cond_timedwait()
  • pthread_testcancel()
  • sem_wait()
  • sigwait()
This means that if a thread executes any of these functions, it'll check for deferred cancel requests. If there is one, it will execute the cancellation sequence, and terminate. Out of these functions, pthread_testcancel() is unique - it's only purpose is to test whether a cancellation request is pending for this thread. If there is, it executes the cancellation sequence. If not, it returns immediately. This function may be used in a thread that does a lot of processing without getting into a "natural" cancellation state.

Note: In real conformant implementations of the pthreads standard, normal system calls that cause the process to block, such as read(), select(), wait() and so on, are also cancellation points. The same goes for standard C library functions that use these system calls (the various printf functions, for example).


Setting Thread Cleanup Functions

One of the features the pthreads library supplies is the ability for a thread to clean up after itself, before it exits. This is done by specifying one or more functions that will be called automatically by the pthreads library when the thread exits, either due to its own will (e.g. calling pthread_exit()), or due to it being canceled.

Two functions are supplied for this purpose. The pthread_cleanup_push() function is used to add a cleanup function to the set of cleanup functions for the current thread. The pthread_cleanup_pop() function removes the last function added with pthread_cleanup_push(). When the thread terminates, its cleanup functions are called in the reverse order of their registration. So the the last one to be registered is the first one to be called.

When the cleanup functions are called, each one is supplied with one parameter, that was supplied as the second parameter to the pthread_cleanup_push() function call. Lets see how these functions may be used. In our example we'll see how these functions may be used to clean up some memory that our thread allocates when it starts running.




/* first, here is the cleanup function we want to register.        */
/* it gets a pointer to the allocated memory, and simply frees it. */
void
cleanup_after_malloc(void* allocated_memory)
{
    if (allocated_memory)
        free(allocated_memory);
}

/* and here is our thread's function.      */
/* we use the same function we used in our */
/* thread-pool server.                     */
void*
handle_requests_loop(void* data)
{
    .
    .
    /* this variable will be used later. please read on...         */
    int old_cancel_type;

    /* allocate some memory to hold the start time of this thread. */
    /* assume MAX_TIME_LEN is a previously defined macro.          */
    char* start_time = (char*)malloc(MAX_TIME_LEN);

    /* push our cleanup handler. */
    pthread_cleanup_push(cleanup_after_malloc, (void*)start_time);
    .
    .
    /* here we start the thread's main loop, and do whatever is desired.. */
    .
    .
    .

    /* and finally, we unregister the cleanup handler. our method may seem */
    /* awkward, but please read the comments below for an explanation.     */

    /* put the thread in deferred cancellation mode.      */
    pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED, &old_cancel_type);

    /* supplying '1' means to execute the cleanup handler */
    /* prior to unregistering it. supplying '0' would     */
    /* have meant not to execute it.                      */
    pthread_cleanup_pop(1);

    /* restore the thread's previous cancellation mode.   */
    pthread_setcanceltype(old_cancel_type, NULL);
}

As we can see, we allocated some memory here, and registered a cleanup handler that will free this memory when our thread exits. After the execution of the main loop of our thread, we unregistered the cleanup handler. This must be done in the same function that registered the cleanup handler, and in the same nesting level, since both pthread_cleanup_pop() and pthread_cleanup_pop() functions are actually macros that add a '{' symbol and a '}' symbol, respectively.

As to the reason that we used that complex piece of code to unregister the cleanup handler, this is done to assure that our thread won't get canceled in the middle of the execution of our cleanup handler. This could have happened if our thread was in asynchronous cancellation mode. Thus, we made sure it was in deferred cancellation mode, then unregistered the cleanup handler, and finally restored whatever cancellation mode our thread was in previously. Note that we still assume the thread cannot be canceled in the execution of pthread_cleanup_pop() itself - this is true, since pthread_cleanup_pop() is not a cancellation point.


Synchronizing On Threads Exiting

Sometimes it is desired for a thread to wait for the end of execution of another thread. This can be done using the pthread_join() function. It receives two parameters: a variable of type pthread_t, denoting the thread to be joined, and an address of a void* variable, into which the exit code of the thread will be placed (or PTHREAD_CANCELED if the joined thread was canceled).
The pthread_join() function suspends the execution of the calling thread until the joined thread is terminated.

For example, consider our earlier thread pool server. Looking back at the code, you'll see that we used an odd sleep() call before terminating the process. We did this since the main thread had no idea when the other threads finished processing all pending requests. We could have solved it by making the main thread run a loop of checking if no more requests are pending, but that would be a busy loop.

A cleaner way of implementing this, is by adding three changes to the code:

  1. Tell the handler threads when we are done creating requests, by setting some flag.
  2. Make the threads check, whenever the requests queue is empty, whether or not new requests are supposed to be generated. If not, then the thread should exit.
  3. Make the main thread wait for the end of execution of each of the threads it spawned.

The first 2 changes are rather easy. We create a global variable named 'done_creating_requests' and set it to '0' initially. Each thread checks the contents of this variable every time before it intends to go to wait on the condition variable (i.e. the requests queue is empty).
The main thread is modified to set this variable to '1' after it finished generating all requests. Then the condition variable is being broadcast, in case any of the threads is waiting on it, to make sure all threads go and check the 'done_creating_requests' flag.

The last change is done using a pthread_join() loop: call pthread_join() once for each handler thread. This way, we know that only after all handler threads have exited, this loop is finished, and then we may safely terminate the process. If we didn't use this loop, we might terminate the process while one of the handler threads is still handling a request.

The modified program is available in the file named thread-pool-server-with-join.c. Look for the word 'CHANGE' (in capital letters) to see the locations of the three changes.


Detaching A Thread

We have seen how threads can be joined using the pthread_join() function. In fact, threads that are in a 'join-able' state, must be joined by other threads, or else their memory resources will not be fully cleaned out. This is similar to what happens with processes whose parents didn't clean up after them (also called 'orphan' or 'zombie' processes).

If we have a thread that we wish would exit whenever it wants without the need to join it, we should put it in the detached state. This can be done either with appropriate flags to the pthread_create() function, or by using the pthread_detach() function. We'll consider the second option in our tutorial.

The pthread_detach() function gets one parameter, of type pthread_t, that denotes the thread we wish to put in the detached state. For example, we can create a thread and immediately detach it with a code similar to this:


pthread_t a_thread;   /* store the thread's structure here              */
int rc;               /* return value for pthread functions.            */
extern void* thread_loop(void*); /* declare the thread's main function. */

/* create the new thread. */
rc = pthread_create(&a_thread, NULL, thread_loop, NULL);

/* and if that succeeded, detach the newly created thread. */
if (rc == 0) {
    rc = pthread_detach(a_thread);
}


Of-course, if we wish to have a thread in the detached state immediately, using the first option (setting the detached state directly when calling pthread_create() is more efficient.


Threads Cancellation - A Complete Example

Our next example is much larger than the previous examples. It demonstrates how one could write a multi-threaded program in C, in a more or less clean manner. We take our previous thread-pool server, and enhance it in two ways. First, we add the ability to tune the number of handler threads based on the requests load. New threads are created if the requests queue becomes too large, and after the queue becomes shorter again, extra threads are canceled.

Second, we fix up the termination of the server when there are no more new requests to handle. Instead of the ugly sleep we used in our first example, this time the main thread waits for all threads to finish handling their last requests, by joining each of them using pthread_join().

The code is now being split to 4 separate files, as follows:

  1. requests_queue.c - This file contains functions to manipulate a requests queue. We took the add_request() and get_request() functions and put them here, along with a data structure that contains all the variables previously defined as globals - pointer to queue's head, counter of requests, and even pointers to the queue's mutex and condition variable. This way, all the manipulation of the data is done in a single file, and all its functions receive a pointer to a 'requests_queue' structure.
  2. handler_thread.c - this contains the functions executed by each handler thread - a function that runs the main loop (an enhanced version of the 'handle_requests_loop()' function, and a few local functions explained below). We also define a data structure to collect all the data we want to pass to each thread. We pass a pointer to such a structure as a parameter to the thread's function in the pthread_create() call, instead of using a bunch of ugly globals: the thread's ID, a pointer to the requests queue structure, and pointers to the mutex and condition variable to be used.
  3. handler_threads_pool.c - here we define an abstraction of a thread pool. We have a function to create a thread, a function to delete (cancel) a thread, and a function to delete all active handler threads, called during program termination. we define here a structure similar to that used to hold the requests queue, and thus the functions are similar. However, because we only access this pool from one thread, the main thread, we don't need to protect it using a mutex. This saves some overhead caused by mutexes. the overhead is small, but for a busy server, it might begin to become noticeable.
  4. main.c - and finally, the main function to rule them all, and in the system bind them. This function creates a requests queue, creates a threads pool, creates few handler threads, and then starts generating requests. After adding a request to the queue, it checks the queue size and the number of active handler threads, and adjusts the number of threads to the size of the queue. We use a simple water-marks algorithm here, but as you can see from the code, it can be easily be replaced by a more sophisticated algorithm. In our water-marks algorithm implementation, when the high water-mark is reached, we start creating new handler threads, to empty the queue faster. Later, when the low water-mark is reached, we start canceling the extra threads, until we are left with the original number of handler threads.

After rewriting the program in a more manageable manner, we added code that uses the newly learned pthreads functions, as follows:

  1. Each handler thread created puts itself in the deferred cancellation mode. This makes sure that when it gets canceled, it can finish handling its current request, before terminating.
  2. Each handler thread also registers a cleanup function, to unlock the mutex when it terminates. This is done, since a thread is most likely to get canceled when calling pthread_cond_wait(), which is a cancellation point. Since the function is called with the mutex locked, it might cause the thread to exit and cause all other threads to 'hang' on the mutex. Thus, unlocking the mutex in a cleanup handler (registered with the pthread_cleanup_push() function) is the proper solution.
  3. Finally, the main thread is set to clean up properly, and not brutally, as we did before. When it wishes to terminate, it calls the 'delete_handler_threads_pool()' function, which calls pthread_join for each remaining handler thread. This way, the function returns only after all handler threads finished handling their last request.

Please refer to the source code for the full details. Reading the header files first will make it easier to understand the design. To compile the program, just switch to the thread-pool-server-changes directory, and type 'gmake'.

Exercise: our last program contains some possible race condition during its termination process. Can you see what this race is all about? Can you offer a complete solution to this problem? (hint - think of what happens to threads deleted using 'delete_handler_thread()').

Exercise 2: the way we implement the water-marks algorithm might come up too slow on creation of new threads. Try thinking of a different algorithm that will shorten the average time a request stays on the queue until it gets handled. Add some code to measure this time, and experiment until you find your "optimal pool algorithm". Note - Time should be measured in very small units (using the getrusage system call), and several runs of each algorithm should be made, to get more accurate measurements.


Using Threads For Responsive User Interface Programming

One area in which threads can be very helpful is in user-interface programs. These programs are usually centered around a loop of reading user input, processing it, and showing the results of the processing. The processing part may sometimes take a while to complete, and the user is made to wait during this operation. By placing such long operations in a seperate thread, while having another thread to read user input, the program can be more responsive. It may allow the user to cancel the operation in the middle.

In graphical programs the problem is more severe, since the application should always be ready for a message from the windowing system telling it to repaint part of its window. If it's too busy executing some other task, its window will remain blank, which is rather ugly. In such a case, it is a good idea to have one thread handle the message loop of the windowing systm and always ready to get such repain requests (as well as user input). When ever this thread sees a need to do an operation that might take a long time to complete (say, more than 0.2 seconds in the worse case), it will delegate the job to a seperate thread.

In order to structure things better, we may use a third thread, to control and synchronize the user-input and task-performing threads. If the user-input thread gets any user input, it will ask the controlling thread to handle the operation. If the task-performing thread finishes its operation, it will ask the controlling thread to show the results to the user.


User Interaction - A Complete Example

As an example, we will write a simple character-mode program that counts the number of lines in a file, while allowing the user to cancel the operation in the middle.

Our main thread will launch one thread to perform the line counting, and a second thread to check for user input. After that, the main thread waits on a condition variable. When any of the threads finishes its operation, it signals this condition variable, in order to let the main thread check what happened. A global variable is used to flag whether or not a cancel request was made by the user. It is initialized to '0', but if the user-input thread receives a cancellation request (the user pressing 'e'), it sets this flag to '1', signals the condition variable, and terminates. The line-counting thread will signal the condition variable only after it finished its computation.

Before you go read the program, we should explain the use of the system() function and the 'stty' Unix command. The system() function spawns a shell in which it executes the Unix command given as a parameter. The stty Unix command is used to change terminal mode settings. We use it to switch the terminal from its default, line-buffered mode, to a character mode (also known as raw mode), so the call to getchar() in the user-input thread will return immediatly after the user presses any key. If we hadn't done so, the system will buffer all input to the program until the user presses the ENTER key. Finally, since this raw mode is not very useful (to say the least) once the program terminates and we get the shell prompt again, the user-input thread registers a cleanup function that restores the normal terminal mode, i.e. line-buffered. For more info, please refer to stty's manual page.

The program's source can be found in the file line-count.c. The name of the file whose lines it reads is hardcoded to 'very_large_data_file'. You should create a file with this name in the program's directory (large enough for the operation to take enough time). Alternatively, you may un-compress the file 'very_large_data_file.Z' found in this directory, using the command:

uncompress very_large_data_file.Z

note that this will create a 5MB(!) file named 'very_large_data_file', so make sure you have enough free disk-space before performing this operation.


Using 3rd-Party Libraries In A Multi-Threaded Application

One more point, and a very important one, should be taken by programmers employeeing multi-threading in their programs. Since a multi-threaded program might have the same function executed by different threads at the same time, one must make sure that any function that might be invoked from more than one thread at a time, is MT-safe (Multi-Thread Safe). This means that any access to data structures and other shared resources is protected using mutexes.

It may be possibe to use a non-MT-safe library in a multi-threaded programs in two ways:

  1. Use this library only from a single thread. This way we are assured that no function from the library is executed simultanouasly from two seperate threads. The problem here is that it might limit your whole design, and might force you to add more communications between threads, if another thread needs to somehow use a function from this library.
  2. Use mutexes to protect function calls to the library. This means that a single mutex is used by any thread invoking any function in this library. The mutex is locked, the function is invoked, and then the mutex is unlocked. The problem with this solution is that the locking is not done in a fine granularity - even if two functions from the library do not interfere with each other, they still cannot be invoked at the same time by seperate threads. The second thread will be blocked on the mutex until the first thread finishes the function call. You might call for using seperate mutexes for unrelated functions, but usually you've no idea how the library really works and thus cannot know which functions access the same set of resources. More than that, even if you do know that, a new version of the library might behave differently, forcing you to modify your whole locking system.
As you can see, non-MT-safe libraries need special attention, so it is best to find MT-safe libraries with a similar functionality, if possible.


Using A Threads-Aware Debugger

One last thing to note - when debugging a multi-threaded application, one needs to use a debugger that "sees" the threads in the program. Most up-to-date debuggers that come with commercial development environments are thread-aware. As for Linux, gdb as is shiped with most (all?) distributions seems to be not thread-aware. There is a project, called 'SmartGDB', that added thread support to gdb, as well as a graphical user interface (which is almost a must when debugging multi-threaded applications). However, it may be used to debug only multi-threaded applications that use the various user-level thread libraries. Debugging LinuxThreads with SmartGDB requires applying some kernel patches, that are currently available only for Linux kernels from the 2.1.X series. More information about this tool may be found at http://hegel.ittc.ukans.edu/projects/smartgdb/. There is also some information about availability of patches to the 2.0.32 kernel and gdb 4.17. This information may be found on the LinuxThreads homepage.


Side-Notes

water-marks algorithm
An algorithm used mostly when handling buffers or queues: start filling in the queue. If its size exceeds a threshold, known as the high water-mark, stop filling the queue (or start emptying it faster). Keep this state until the size of the queue becomes lower than another threshold, known as the low water-mark. At this point, resume the operation of filling the queue (or return the emptying speed to the original speed).



[
LUPG Home] [Tutorials] [Related Material] [Essays] [Project Ideas] [Send Comments]

This document is copyright (c) 1998-2002 by guy keren.

The material in this document is provided AS IS, without any expressed or implied warranty, or claim of fitness for a particular purpose. Neither the author nor any contributers shell be liable for any damages incured directly or indirectly by using the material contained in this document.

permission to copy this document (electronically or on paper, for personal or organization internal use) or publish it on-line is hereby granted, provided that the document is copied as-is, this copyright notice is preserved, and a link to the original document is written in the document's body, or in the page linking to the copy of this document.

Permission to make translations of this document is also granted, under these terms - assuming the translation preserves the meaning of the text, the copyright notice is preserved as-is, and a link to the original document is written in the document's body, or in the page linking to the copy of this document.

For any questions about the document and its license, please contact the author.

Posted by '김용환'
,

Application Development Guide --Core Components


Synchronization Objects

In a multithreaded program, you must use synchronization objects whenever there is a possibility of corruption of shared data or conflicting scheduling of threads that have mutual scheduling dependencies. The following subsections discuss two kinds of synchronization objects: mutexes and condition variables.

Mutexes

A mutex (mutual exclusion) is an object that multiple threads use to ensure the integrity of a shared resource that they access, most commonly shared data. A mutex has two states: locked and unlocked. For each piece of shared data, all threads accessing that data must use the same mutex; each thread locks the mutex before it accesses the shared data and unlocks the mutex when it is finished accessing that data. If the mutex is locked by another thread, the thread requesting the lock is blocked when it tries to lock the mutex if you call pthread_mutex_lock() (see Figure 9). The blocked thread continues and is not blocked if you call pthread_mutex_trylock().

Figure 9. Only One Thread Can Lock a Mutex



Figure a3u2j842 not displayed.

Each mutex must be initialized. (To initialize mutexes as part of the program's one-time initialization code, see "One-Time Initialization Routines".) To initialize a mutex, use the pthread_mutex_init() routine. This routine allows you to specify an attributes object, which allows you to specify the mutex type. The following are types of mutexes:

  • A fast mutex (the default) is locked only once by a thread. If the thread tries to lock the mutex again without first unlocking it, the thread waits for itself to release the first lock and deadlocks on itself.

    This type of mutex is called fast because it can be locked and unlocked more rapidly than a recursive mutex. It is the most efficient form of mutex.

  • A recursive mutex can be locked more than once by a given thread without causing a deadlock. The thread must call the pthread_mutex_unlock() routine the same number of times that it called the pthread_mutex_lock() routine before another thread can lock the mutex. Recursive mutexes have the notion of a mutex owner. When a thread successfully locks a recursive mutex, it owns that mutex and the lock count is set to 1. Any other thread attempting to lock the mutex blocks until the mutex becomes unlocked. If the owner of the mutex attempts to lock the mutex again, the lock count is incremented, and the thread continues running. When an owner unlocks a recursive mutex, the lock count is decremented. The mutex remains locked and owned until the count reaches 0 (zero). It is an error for any thread other than the owner to attempt to unlock the mutex.

    A recursive mutex is useful if a thread needs exclusive access to a piece of data, and it needs to call another routine (or itself) that needs exclusive access to the data. A recursive mutex allows nested attempts to lock the mutex to succeed rather than deadlock.

    This type of mutex requires more careful programming. Never use a recursive mutex with condition variables because the implicit unlock performed for a pthread_cond_wait() or pthread_cond_timedwait() may not actually release the mutex. In that case, no other thread can satisfy the condition of the predicate.

  • A nonrecursive mutex is locked only once by a thread, like a fast mutex. If the thread tries to lock the mutex again without first unlocking it, the thread receives an error. Thus, nonrecursive mutexes are more informative than fast mutexes because fast mutexes block in such a case, leaving it up to you to determine why the thread no longer executes. Also, if someone other than the owner tries to unlock a nonrecursive mutex, an error is returned.

To lock a mutex, use one of the following routines, depending on what you want to happen if the mutex is locked:

  • The pthread_mutex_lock() routine

    If the mutex is locked, the thread waits for the mutex to become available.

  • The pthread_mutex_trylock() routine

    If the mutex is locked, the thread continues without waiting for the mutex to become available. The thread immediately checks the return status to see if the lock was successful, and then takes whatever action is appropriate if it was not.

When a thread is finished accessing a piece of shared data, it unlocks the associated mutex by calling the pthread_mutex_unlock() routine.

If another thread is waiting on the mutex, its execution is unblocked. If more than one thread is waiting on the mutex, the scheduling policy and the thread scheduling priority determine which thread acquires the mutex. (See "Scheduling Priority Attribute" for additional information.)

You can delete a mutex and reclaim its storage by calling the pthread_mutex_destroy() routine. Use this routine only after the mutex is no longer needed by any thread. This routine may require serialization. Mutexes are automatically deleted when the program terminates.

Note: Never include DCE APIs (such as pthread_mutex_destroy()) in the termination routine of a DLL. Doing so can result in an error (such as return code 6 -- invalid handle) when termination occurs out of sequence.

Condition Variables

A condition variable allows a thread to block its own execution until some shared data reaches a particular state. Cooperating threads check the shared data and wait on the condition variable. For example, one thread in a program produces work-to-do packets and another thread consumes these packets (does the work). If the work queue is empty when the consumer thread checks it, that thread waits on a work-to-do condition variable. When the producer thread puts a packet on the queue, it signals the work-to-do condition variable.

A condition variable is used to wait for a shared resource to assume some specific state (a predicate). A mutex, on the other hand, is used to reserve some shared resource while the resource is being manipulated. For example, a thread A may need to wait for a thread B to finish a task X before thread A proceeds to execute a task Y. Thread B can tell thread A that it has finished task X by using a variable they both have access to, a condition variable called a predicate. When thread A is ready to execute task Y, it looks at the condition variable (predicate) to see if thread B is finished (see Figure 10).

Figure 10. Thread A Waits on Condition Ready, Then Wakes Up and Proceeds



Figure a3u2j373 not displayed.

First, thread A locks the mutex named mutex_ready that is associated with the condition variable. Then it reads the predicate associated with the condition variable named ready. If the predicate indicates that thread B has finished task X, then thread A can unlock the mutex and proceed with task Y. If the condition variable predicate indicated that thread B has not yet finished task X; however, then thread A waits for the condition variable to change. Thread A calls the pthreadwait primitive. Waiting on the condition variable automatically unlocks the mutex, allowing thread B to lock the mutex when it has finished task X. The lock is automatically reacquired before waking up thread A(see Figure 11).

Figure 11. Thread B Signals Condition Ready



Figure a3u2j579 not displayed.

Thread B updates the predicate named ready associated with the condition variable to the state thread A is waiting for. It also executes a signal on the condition variable while holding the mutex mutex_ready.

Thread A wakes up, verifies that the condition variable (predicate) is in the correct state, and proceeds to execute task Y (see Figure 10).

Note that, although the condition variable is used for explicit communications among threads, the communications are anonymous. Thread B does not necessarily know that thread A is waiting on the condition variable that thread B signals. And thread A does not know that it was thread B that woke it up from its wait on the condition variable.

Use the pthread_cond_init() routine to create a condition variable. To create condition variables as part of the program's one-time initialization code, see "One-Time Initialization Routines".

Use the pthread_cond_wait() routine to cause a thread to wait until the condition is signaled or broadcast. This routine specifies a condition variable and a mutex that you have locked. (If you have not locked the mutex, the results of pthread_cond_wait() are unpredictable.) This routine unlocks the mutex and causes the calling thread to wait on the condition variable until another thread calls one of the following routines:

  • The pthread_cond_signal() routine to wake one thread that is waiting on the condition variable

  • The pthread_cond_broadcast() routine to wake all threads that are waiting on a condition variable

If you want to limit the time that a thread waits for a condition to be signaled or broadcast, use the pthread_cond_timedwait() routine. This routine specifies the condition variable, mutex, and absolute time at which the wait should expire if the condition variable is not signaled or broadcast.

You can delete a condition variable and reclaim its storage by calling the pthread_cond_destroy() routine. Use this routine only after the condition variable is no longer needed by any thread. Condition variables are automatically deleted when the program terminates.

Other Synchronization Methods

There is another synchronization method that is not anonymous: the join primitive. This allows a thread to wait for another specific thread to complete its execution. When the second thread is finished, the first thread unblocks and continues its execution. Unlike mutexes and condition variables, the join primitive is not associated with any particular shared data.

Posted by '김용환'
,

http://www.sunyzero.com/zboard/view.php?id=sunycomputer&page=3&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=82

 

Subject   [C] System V 계열 세마포어(semaphore)를 통한 상호배제: 예제있음
[ 세마포어와 상호배제 : System V Semaphore 예제 ]

* 글쓴이 : Steven Kim <sunyzero@yahoo.com>
* 마지막 고친날짜 : 2003-08-20
* 이 글에 문제가 있거나 오타/이상함이 있는 경우 댓글을 첨언하여 주시면 반영하겠습니다.(if idle...)

1. 개념
세마포어(semaphore)는 상호배제(Mutual Exclusion:MUTEX) 이론을 이용하여 만들어진 운영체제에서 제공하는 기능중의 하나입니다.
세마포어를 처음 주창한 사람이 딕스트라(Dijkstra)인것은 아시죠? shortest path 알고리즘 및 여러가지 이론을 만든 수학자 아저씨...(shortest path에서는 bellman ford algorithm과 가장 많이 쓰이죠. Linear Programming쪽 공부하면 가장 처음에 배우는 앨거리듬이죠)
자 이런 세마포어는 어떤 것일까? 한번 살펴보겠습니다. 실제로 세마포어는 어떤 영역을 한번에 한녀석만 들어갈 수 있게 만든 것입니다.
쉽게 말하면 특정 영역에 A란 녀석이 쓰기를 시도할때 B란 녀석이 다시 쓰기를 하면 다 쓰고 난뒤에 그 내용이 A란 녀석이 쓴 내용인지, 혹은 B란 녀석이 쓴 내용인지 알 도리가 없습니다. 심지어 두개가 섞여버리는 수도 있습니다. 이런 경우를 방지하기 위해서 데이터를 변경할 경우엔 그 변경하는 타이밍에 다른 녀석이 접근하지 못하게 하는게 가장 좋죠. 물론 읽기를 시도할때도 쓰기가 완전히 끝난 다음에 읽도록 하는게 좋겠죠?

실제로 세마포어는 에서 P/V 오퍼레이션에 대한 것은 운영체제 책에 나오므로 읽어봅시다. P는 세마포어의 상태를 Zero로 만들고, V는 다시 양수쪽으로 바꾸게 됩니다. 그렇게 되어 현재 상태가 0 이면 기다리게 되고, 그게 자신의 차례가 되면 바로 전에 임계영역(critical section)에 있던 녀석이 빠져나가면서 V 를 해서 양수를 만들어주어 자신이 진입할 수 있도록 해줍니다.


2. 간단한 세마포어 예제(1)
자 그러면 실제로 사용되는 부분을 봅시다. 아래의 코드를 보면서 생각해봅시다.
(여기서 제공하는 것은 가장 많이 사용되는 SysV계열의 세마포어를 기준으로 합니다.)

* 설정
- 현재 아래 소스코드가 수행되는 서버는 pre-fork 된 10개의 서버가 동시에 접근가능한 부분이다.
- shm_userinfo 는 공유메모리 영역이다. 10개의 서버는 이 영역을 공유한다.
- sem_buf.sem_op 는 세마포어에 더할 값이다. -1 이면 P 오퍼레이션(lock)을 수행한다. 1 은 V 오퍼레이션(unlock)을 수행한다.
- semop()의 마지막(3번째 파라메터)는 sem_buf 배열의 갯수를 의미한다.

[code]
....(생략)....
    sem_buf.sem_num = sem_idx;        /* semaphore element index */
    sem_buf.sem_flg = SEM_UNDO;        /* SEM_UNDO flag */
    sem_buf.sem_op = -1;
    semop(sem_id, &sem_buf, 1); /* P operation : decrease */

    shm_userinfo->person[i].id = cur_id; /* critical section */
    
    sem_buf.sem_num = sem_idx;
    sem_buf.sem_flg = SEM_UNDO;
    sem_buf.sem_op = 1;
    semop(sem_id, &sem_buf, 1); /* V operation : increase */
....(생략)....
[/code]

위에서 보면 10개의 서버를 간략하게 a, b, c, ... 로 칭할때 a 가 먼저 P 를 걸고 critical section에 진입해서 데이터를 수정하고 있습니다. 이 데이터를 수정하는 도중에 b, c 프로세스가 이 부분에 진입하면서 P 를 걸고 들어오게 됩니다. P 오퍼레이션이 되면서 사용가능한 공간이 없음을 알리기 위해서 세마포어값은 0 이 됩니다. 그런 뒤에 a 가 shm_userinfo 메모리 영역을 수정하고 임계영역을 벗어나게 되면 sem_buf.sem_op = 1 을 넣고, semop() 를 호출하여 세마포어값을 증가시킵니다. 그러면 다음에 신호를 받을 녀석은 0 상태에서 1 이 되고 따라서 자신이 임계영역을 들어갈 수 있는 상태라는 것을 알게됩니다. 따라서 임계영역에 진입하면서 P 를 호출해서 0 을 만들죠.

주의) 세마포어는 위의 shm_userinfo 라는 영역이 동시에 변경되거나 변경되는 도중 읽기가 일어나는 것을 막기 위해서 사용됩니다. 그러므로 실제 상호배제는 특정 영역을 접근하는 것에 있어서 동시성을 배제하는 것이 목적이지, 연산의 순서를 정하는 것은 아닙니다.


3. System V semaphore functions
위에서 간단하게 세마포어의 사용에 대해서 봤으니 실제로 세마포어를 생성하고, 변경하고, 제거하고, 정보를 알아보는 방법도 알아봅시다.

3.1 세마포어 생성: semget

문법 : int semget ( key_t key, int nsems, int semflg )

- 반환값 : 성공: 세마포어에 접근가능한 식별자(semaphore id)를 반환합니다. 이 id로 접근가능합니다.
          실패: -1

- key   : 세마포어를 생성할 세마포어 키입니다. 일반적으로 공유메모리와 같이 쓸 경우 키값은 혼동을 피하기 위해서 같이 사용합니다. 단 몇몇 시스템은 같은 키를 사용할 수 없는 경우가 있습니다.
          만일 특정키와 중복되지 않는 키를 생성해서 사용하기 위해서는 IPC_PRIVATE를 사용할 수 있습니다(이 경우엔 반환되는 ipc id값을 저장하고 있다가 해당 semid로 접근해야 합니다)
        ex) 공유메모리키 : 0x35001000 -> 세마포어 키 : 0x35001000
- nsems : 생성시 세마포어 갯수를 의미합니다. 기존 세마포어에 attach 할 경우엔 이 값은 무시됩니다.
- semflg: 생성시 적용할 플래그입니다. 이 플래그들은 OR 연산으로 여러개의 플래그를 적용할 수 있습니다. 일반적으로 이 플래그는 IPC 기본 플래그와 동일합니다. 따라서 공유메모리 메세지큐의 플래그와 동일한 의미를 가집니다. 그리고 플래그들과 별개로 이 semflg의 하위 9비트는 생성권한을 의미합니다. 0777 로 주면 모든 유저가 읽기/삭제/접근이 가능합니다.
  + semflg 목록

  IPC_CREAT : 세마포어를 생성합니다.
  IPC_EXCL  : IPC_CREAT 와 같이 사용할 수 있습니다. 이미 생성되어있는 경우 -1을 반환하고 errno는 EEXIST로 세팅됩니다.


예) 0x44001100 키를 가지고 5개의 배열을 지닌 세마포어를 생성. 생성시 권한은 0660 으로 세팅, IPC_EXCL 플래그가 존재하므로 이미 존재한다면 -1 을 반환하고 errno는 EEXIST로 설정된다.

sem_id = semget(0x44001100, 5, IPC_CREAT|IPC_EXCL|0660);


3.2 세마포어 제어: semctl (semaphore control)

문법 : int semctl (int semid, int semnum, int cmd, union semun arg)

- 반환값 : 성공: 양수값
          실패: -1

- semid : semget() 에서 리턴된 세마포어 식별자(semaphore id)
- semnum: 제어할 세마포어 배열의 인덱스
- cmd   : 세마포어 제어 명령
- arg   : 세마포어 제어 명령(cmd)에 따라서 저장되거나 반환되는 세마포어 정보 공용체

arg는 다음과 같다. 이 공용체는 어떤 cmd 를 사용하는가에 따라서 다른 의미로 사용된다.
union semun {
    int val;                    /* SETVAL을 위한값 */
    struct semid_ds *buf;       /* IPC_STAT, IPC_SET을 위한 버퍼 */
    unsigned short int *array;  /* GETALL, SETALL을 위한 배열 */
    struct seminfo *__buf;      /* IPC_INFO을 위한 버퍼 */
};

cmd 을 위한 값은 다음과 같다. 당연히 이 명령들은 세마포어에 접근가능한 해당권한이 있어야 한다. 읽기명령인 경우는 읽기권한, 변경/삭제인경우는 쓰기 권한이 있어야 한다.

IPC_STAT    arg.buf 원소에 semaphore 정보를 복사합니다. 인수 semnum 는 무시된다.
            이 struct semid_ds 구조체 아래와 같습니다.

        struct semid_ds
        {
            struct ipc_perm sem_perm;     /* operation permission struct   */
            __time_t sem_otime;           /* last semop() time             */
            __time_t sem_ctime;           /* last time changed by semctl() */
            unsigned long int sem_nsems;  /* number of semaphores in set   */
        };

IPC_RMID    세마포어 설정을 즉시 제거하고, 그것의 데이타 구조는 모든 대기중인 프로세스들을 재실행한다.
            호출한 프로세스 유효 사용자ID는 수퍼유저나 세마포어설정의 생성, 소유자중의 하나이어야한다.
            인수 semnum 는 무시된다.

GETALL      arg.array 인수에 설정된 모든 세마포어 위한 semval 를 반환한다.
            변수 The argument semnum 는 무시된다.

GETNCNT     시스템 호출은 semncnt 의 값을 반환한다.

GETPID      세마포어 호출은 sempid 의 값을 반환한다. 세마포어를 호출한 프로세스의 pid를 의미한다.

GETVAL      시스템 호출은 설정의 semnum 번째에 해당하는 세마포어 배열의 semval 의 값을 리턴한다.

GETZCNT     시스템 호출은 설정의 semnum 번째에 해당하는 세마포어 배열에 semzcnt의 값을 리턴한다.
            semzcnt는 현재 블록되어있는 기다리는 프로세스 갯수이다.

SETALL      세마포어 인수배열을 사용하여 설정과 관련된 semid_ds 구조체의 sem_ctime, semval 의 값을 새로 설정한다.
            기존의 세마포어에 대해서 Undo 엔트리는 모두 소거되고 대기열에서 유휴중인 프로세스들은 semval을 0으로
            만들고 기다리게 된다. 인수 semnum은 무시된다.



3.3 세마포어 값 변경

문법 : int semop ( int semid, struct sembuf *sops, unsigned nsops )

- 반환값 : 성공:  0 리턴
          실패: -1 리턴

- semid : semget() 에서 리턴된 세마포어 식별자(semaphore id)
- sops  : 세마포어 연산을 위한 지시자 구조체, 각 구조체의 의미는 아래와 같다.
            short sem_num;  /* semaphore 배열번호: 0 = first */
            short sem_op;   /* semaphore operation          */
            short sem_flg;  /* operation flags              */
- nsops : sops 배열의 갯수, 변경할 세마포어가 여러개인 경우는 연산을 위한 sops의 배열 갯수를 의미하게 된다.


위에서 세마포어 연산을 위한 struct sembuf *sops 의 각 필드들은 각 의미를 가진다.

sem_num : 세마포어 배열번호이다. 연산을 위한 세마포어 배열의 인덱스이다.
sem_op  : 세마포어 값(semval)에 더할 값이다. 주로 1, -1 로 되어있다.
          -1은 값을 감소시키므로 P 연산에 해당하고, 1 이면 값을 증가시키므로 V 연산에 해당한다.
sem_flg : 세마포어 연산을 위한 선택적 플래그, 아래와 같은 의미를 가진다.

IPC_NOWAIT : 일반적으로 세마포어는 P 를 호출했을때 세마포어값이 0 이면 사용가능하지 않으므로 현재 임계영역에 있는 프로세스가 끝나고 V를 호출하기까지 블록됩니다. 하지만, IPC_NOWAIT를 설정한다면 errno를 EAGAIN 으로 설정하고 바로 리턴합니다. 말그대로 기다림이 없다는 것입니다.
SEM_UNDO : 이 플래그가 세팅되면 해당 프로세스가 종료될때 자동으로 작업을 취소하게 해줍니다. 따라서 어떤 프로세스가 임계영역안에서 죽는 일이 발생한다면 자동으로 해당 작업은 취소되고 다음 프로세스가 P 연산을 걸고 임계영역안으로 진입할 수 있게 됩니다.



예제) 아래는 2개의 세마포어를 바꾸는 작업이다. 실제로 0번째(첫번째 세마포어 배열), 3번째(4번째 세마포어 배열)을 동시에 바꾸는 연산을 수행한다. 또한 sem_op가 -1 이므로 P 연산에 해당하는 작업이 수행된다.
struct sembuf semops[2];

semops[0].sem_num = 0;
semops[0].sem_op  = -1;
semops[0].sem_flg = SEM_UNDO;
semops[1].sem_num = 3;
semops[1].sem_op  = -1;
semops[1].sem_flg = SEM_UNDO;
semop(semid, semops, 2);


4. 사용예
아래는 세마포어를 사용하는 실제 예제코드이다. 여러개의 프로세스가 fork()되어서 세마포어를 이용하여 상호배제를 하는 것을 볼 수 있다.

4.1 주의!
아래 예제를 넣을려고 했지만 그냥 소스파일을 올리는 것으로 대신하겠다. 실제로 src/ipc 디렉토리에 들어가서 make 로 컴파일을 하면 sysv_sem, sysv_nosem 두개의 파일이 나온다. 실제 이 파일들은 sysv_sem.c 파일에 세마포어를 사용한것과 사용하지 않은 것으로 컴파일한 것이다.

실행은 아규먼트 인자로서 fork 할 프로세스 갯수를 넣어주면 된다.
또한, 3개 이상 fork() 할 경우 3번째 프로세스는 인위적으로 abort()로 종료시키는데 세마포어 사용시 제대로 SEM_UNDO가 제대로 작동함을 보여주는 것이다. 만일 SEM_UNDO가 없다면 3번째 프로세스가 abort()로 종료되면서 모든 프로세스들은 블록될것이다.

PS) 어디에 퍼가서 사용하실때는 원본글의 출처를 밝혀주시기 바랍니다. 혹여 안밝혀도 상관없습니다. 다만 그냥 예의상... ^^*

Ref. 배타적인 자원사용에 대한 것을 자세히 공부해두면 좋다. 비동기적 프로세싱이나 커널프로그래밍에서는 이것은 필수다.
* TAS(Test-and-Set) operation : atomic한 프로세스로 서로다른 두 함수가 하나의 리소스에 동시적으로 접근할때 먼저 진입한 쪽이 1로 세팅하여 다른 함수가 진입하지 못하게 막는다. 끝나고 나갈때 0으로 돌려주면 다음 함수가 진입한다. 68000 CPU의 경우에는 하드웨어 인스트럭션으로 TAS 를 제공한다.
* Spinlock : 배타적으로 다수의 CPU에서 서로 자원의 선점을 위해서 사용되어진다. 커널내부에서 주로 사용한다.

'OS concept' 카테고리의 다른 글

Multi-Threaded Programming With POSIX Threads  (0) 2005.02.28
Application Development Guide --Conditional variable  (0) 2005.02.28
조건변수 condition variable  (0) 2005.02.18
[세마포어] [뮤텍스]  (0) 2005.02.12
인터럽트에 대해서  (0) 2005.01.19
Posted by '김용환'
,
mutex & 조건변수

윤 상배

dreamyun@yahoo.co.kr



1절. 소개

그동안 Pthread_1, Pthread_2, Pthread_3, 을 통해서 pthread 에 대한 몇가지 기본적인 내용들에 대해서 알아 보았다.

그중 Pthread_3 에서 조건변수와, mutex 잠금에 대한 설명이 있었는데, 설명만 있었고 실질적인 예를 이용한 테스트는 없었다.

이번에는 mutex 잠금과 조건변수에 대한 이해를 도울수 있는 간단한 어플리케이션을 제작해보고 어떠한 문제점을 가질수 있는지에 대한 테스트도 하게 될것이다.


2절. Mutex 잠금과 조건변수 테스트

2.1절. 테스트용 어플리케이션 개요

테스트용 어플리케이션의 이름은 mutex_con.c 로 하도록 하겠다. 이 프로그램은 3개의 쓰레드로 이루어진다. 첫 번째 쓰레드는 main 쓰레드로 나머지 2개의 쓰레드(thread 1, thread 2) 를 생성하고 (pthread_create) join 하는 일을 하게 될것이다(즉 특별히 하는일 없다). 2번째 쓰레드는 2개의 int 형 멤버변수를 가지는 구조체에 접근해서 특정한 숫자를 입력하게 된다. 3번째 쓰레드는 이 구조체에 접근해서 멤버변수의 값을 읽어와서 "뎃셈" 하고 이를 화면에 출력시켜주는 일을한다.

이때 이 구조체는 2번 쓰레드와 3번쓰레드 모두가 접근하게 되므로 mutex 잠금을 이용해서 한번에 하나의 쓰레드만 접근하도록 제어해야 될것이다.

mutex 잠금을 이용한 접근제어 외에도, 3번째 쓰레드는 2번째 쓰레드에 의해서 구조체의 값이 변경되었다는걸 감지하고, 값이 변경된 시점에서 구조체에 접근해야 한다. 즉 구조체의 값이 변경될때까지 기다려야 한다. 이 "기다림" 을 위해서 조건변수를 사용하게 된다.

이 조건변수라는 것은 간단히 말해서 신호(signal)를 주고 받는 개념이다. 한쪽에서는 신호를 기다리다가, 신호가 오면 신호를 감지해서 필요한 일을 하게 되는 개념이다.


2.2절. 조건변수를 통해 얻는 프로그래밍 상의 이점

조건변수를 사용하지 않는 다면 어떻게 될까. (물론 조건변수 대신 세마포어를 사용할수도 있으나 이는 논외로 하자.) 그렇다면 thread 2 에서는 구조체의 정보가 변경되었는지 알수 없음으로 구조체의 정보가 변경되었는지 확인하기 위해서 busy wait(바쁜대기 상태)에 놓이면서 지속적으로 값이 변경되었는지를 확인해야 할것이다.

하지만 이건 좋은 방법이 아니다. busy wait 상태란 점도 맘에 들지 않지만 실제로 thread 1 에서 값을 변경했는데 기존의 값과 같을수도 있기 때문이다. 기존의 값과 같든지 아니든지 간에 thread 2 에서는 값을 읽어들여야 하는데, 값의 변경을 확인하는 방법으론 체크자체가 불가능해 질수가 있다.

위의 문제를 해결하기 위해서 별도의 변수를 하나더 둘수 있을것이다. 그래서 thread 1 에서 구조체의 값을 변경시켰다면 이 별도의 준비한 변수의 값을 변경하는 것이다. 그리고 thread 2 에서는 바쁜 대기 상태에서 이 변수의 값이 변경되었는지 확인해서 구조체의 값을 가져오는 것이다. 이 방법을 사용하면 위의 문제를 해결할수 있겠지만, 역시 바쁜 대기 상태에 놓이게 된다는 단점을 가지게 된다.

조건 변수를 사용하면 이러한 모든 문제를 해결할수 있다. 조건 변수를 사용하게 되면 thread 2 에서는 thread 1 에서 조건변수를 통해서 시그널을 보내기 전까지 대기 상태에 놓일수 있을것이기 때문이다.

조건변수는 메모리 buffer 처리등에 유용하게 사용될수 있을것이다. 조건변수를 사용함으로써, 만약에 메모리 buffer 에 처리해야될 자료가 없다면 busy wait 상태에 놓일 필요 없이 signal 을 기다리면 될것이기 때문이다. 그래서 signal 이 도착하면 메모리 buffer 에 엑세스를 시도해서 최근의 정보를 가져오면 될것이다. 이 외에도 조건변수는 쓰레드간 동기화등과 같은 다른 영역에도 매우 유용하게 사용할수 있다.


2.3절. 작동 프로세스

작동 프로세스는 어떻게 mutex 잠금과 조건변수를 이용해서 임계영역을 보호하고 구조체의 값의 변경시점을 알수 있는지에 대한 내용을 중심으로 해서 기술할것이다.

  thread 2  
  while (1) 
  {
      mutex 잠금을 얻는다. 
      // 임계영역 시작 ----------------------------------------------
      구조체에 접근해서 값을 가져온다.  
      구조체 멤버변수의 값을 변경한다.(2씩 더한다)
      pthrad_cond_signal 를 이용해서 조건변수를 통해 신호를 보낸다. 
      // 임계영역 끝 ------------------------------------------------
      mutex 잠금을 돌려준다.
	  sleep(1);
  } 

  thread 3
  while(1)
  {
      mutex 잠금을 얻는다. 
      // 임계영역 시작 ----------------------------------------------
      pthread_cond_wait 를 이용해서 조건변수를 통해 신호가 오는지 기다린다.   
      if (신호가 도착한다면)
          두개의 구조체 멤버변수의 값을 덧셈 하고 이를 출력한다. 
      // 임계영역 끝 ------------------------------------------------
      mutex 잠금을 돌려준다.
  }
			


2.4절. 코딩

이제 작동프로세스까지 만들어졌으니, 코딩에 들어가도록 한다. 코딩에 들어가기 위해서는 작동프로세스 외에도 설계서가 필요할것이지만, 이러한 경우 매우 간단한 프로그램으로 작동프로세스 자체가 설계서나 마찬가지임으로 설계서 이런건 생략하도록 하겠다.

예제 : mutex_con.c

#include <pthread.h>
#include <string.h>
#include <unistd.h>

pthread_mutex_t mutex_lock   = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t   thread_cond  = PTHREAD_COND_INITIALIZER;

struct com_data
{
    int a;
    int b;
};

struct com_data mydata;

void *do_write(void *data)
{
    mydata.a = 0;
    mydata.b = 0;
    while(1)
    {
        pthread_mutex_lock(&mutex_lock);
        mydata.a = random() % 6000;
        mydata.b = random() % 6000;
        pthread_cond_signal(&thread_cond);
        pthread_mutex_unlock(&mutex_lock);
        sleep(2);
    }
}

void *do_read(void *data)
{
    while(1)
    {
        pthread_mutex_lock(&mutex_lock);
        pthread_cond_wait(&thread_cond, &mutex_lock);
        printf("%4d + %4d = %4d\n", mydata.a, mydata.b, mydata.a + mydata.b); 
        pthread_mutex_unlock(&mutex_lock);
    }
}

int main()
{
    pthread_t p_thread[2];
    int thr_id;
    int status;
    int a = 1;
    int b = 2;

    thr_id = pthread_create(&p_thread[0], NULL, do_write, (void *)&a); 
    thr_id = pthread_create(&p_thread[1], NULL, do_read, (void *)&b);

    pthread_join(p_thread[0], (void **) status);
    pthread_join(p_thread[1], (void **) status);

    return 0;
}

			

프로그램자체는 매우 간단하지만 조건변수의 기본적인 사용방법을 알수 있을것이다.


2.5절. 조건변수 사용시 주의해야될 사항

조건변수에는 pthread_cond_signal 과 ptherad_cond_wait 를 이용해서 신호를 주고, 기다리는 방식을 사용한다고 했다. 그렇다면 생각할수 있는게, 과연 신호가 실시간으로 전달이 될것이란걸 믿을수 있을까?

실시간으로 전달되는지 아닌지가 중요한 이유는 쓰레드가 신호를 보내고 나서 신호를 잘받았는지 기다리지 않고 바로 다음으로 넘어가 버리기 때문이다.

이건 꽤 중요한 문제가 될수도 있다. 왜냐하면 만약 신호가 실시간으로 전달되지 않는다면 신호가 미쳐 전달되기 전에 어떤 데이타가 변경되어 버리는 경우가 발생할수 있기 때문이다.

            쓰레드 공유변수 A = 0

 thread 1                                    thread 2
 while(1)                                    while(1)
 {                                           {
     쓰레드 공유변수 A++      
     신호 보냄           ------------------>     신호  기다림
  }                                           } 
                                           
			
위의 상황을 생각해 보자 최초 공유변수 A 에 0 이 들어간다. thread 1 에서 여기에 1 을 증가시키고 신호를 보낸다. thread 2 는 신호를 받고 A 의 값을 읽어 들여서 이것을 100 으로 나눈다. 그런데 신호가 늦게 보내져서 - thread 1 의 loop 회전속도가 신호를 보내는 시간보다 빠른경우 - thread 2 에서 신호를 미쳐 받기전에 A ++ 이 한번더 실행되고 A 의 값은 2가 될것이다. 이때 서야 thread 2 로 신호가 전달되었다면 결국 thread 1 에서는 2번의 데이타를 보냈는데 thread 1 는 한번의 연산만 실행한것으로 데이타 하나를 잃어 버린것과 같은 문제가 발생해 버린다.

신호는 매우 빠른 시간에 전달됨으로 보통의 경우 신호전달시간을 염두에 두어야 하는 경우는 발생하지 않을것이다. 하지만 불행하게도 염두에 두어야 하는 경우가 발생하기도 한다.

물론 우리 프로그래머들의 사전에 불가능이란 없으므로 위의 문제도 간단하게 해결가능 하다. 조건변수를 2개 쓰면 된다. thread 1 에서 신호를 보냈다면, thread 1 은 다음 루틴으로 넘어가기 전에 thread 2 에서 넘어오는 신호를 기다리도록 하면 될것이다. thread 2 는 thread 1의 신호를 받은뒤 thread 1으로 신호를 보내게 될것임으로 반드시 신호가 전달될것을 확신할수 있을것이다. 2개의 조건변수를 지원하기 위해서 2개의 mutex 잠금이 필요할것이다. 여기에서는 그 구현까지 설명하지는 않을것이다. 조금만 생각해보면 간단하게 구현 가능할것이기 때문이다.

 thread 1                                    thread 2
 while(1)                                    while(1)
 {                                           {
     쓰레드 공유변수 A++      
     신호 1 보냄           ----------------->     신호 1 기다림
	 신호 2 기다림         <----------------      신호 2 보냄
     ....                                            ....
 }                                           } 
  			

신호의 전달에 걸리는 시간은 운영체제에 따라 상당한 차이를 보인다. 그러므로 이러한 오차시간까지도 염두에 두어야할 상황이 발생한다면 시간테스트를 해야할것이다.

Posted by '김용환'
,