http://www.cs.cf.ac.uk/Dave/C/node32.html
Subsections
Threads can be created by any thread and joined by any other.
The main thread: In this example the main thread's sole purpose is to create new threads. Threads A, B, and C are created by the main thread. Notice that thread B is created suspended. After creating the new threads, the main thread exits. Also notice that the main thread exited by calling thr_exit(). If the main thread had used the exit() call, the whole process would have exited. The main thread's exit status and resources are held until it is joined by thread C.
Thread A: The first thing thread A does after it is created is to create thread D. Thread A then simulates some processing and then exits, using thr_exit(). Notice that thread A was created with the THR_DETACHED flag, so thread A's resources will be immediately reclaimed upon its exit. There is no way for thread A's exit status to be collected by a thr_join() call.
Thread B: Thread B was created in a suspended state, so it is not able to run until thread D continues it by making the thr_continue() call. After thread B is continued, it simulates some processing and then exits. Thread B's exit status and thread resources are held until joined by thread E.
Thread C: The first thing that thread C does is to create thread F. Thread C then joins the main thread. This action will collect the main thread's exit status and allow the main thread's resources to be reused by another thread. Thread C will block, waiting for the main thread to exit, if the main thread has not yet called thr_exit(). After joining the main thread, thread C will simulate some processing and then exit. Again, the exit status and thread resources are held until joined by thread E.
Thread D: Thread D immediately creates thread E. After creating thread E, thread D continues thread B by making the thr_continue() call. This call will allow thread B to start its execution. Thread D then tries to join thread E, blocking until thread E has exited. Thread D then simulates some processing and exits. If all went well, thread D should be the last nondaemon thread running. When thread D exits, it should do two things: stop the execution of any daemon threads and stop the execution of the process.
Thread E: Thread E starts by joining two threads, threads B and C. Thread E will block, waiting for each of these thread to exit. Thread E will then simulate some processing and will exit. Thread E's exit status and thread resources are held by the operating system until joined by thread D.
Thread F: Thread F was created as a bound, daemon thread by using the THR_BOUND and THR_DAEMON flags in the thr_create() call. This means that it will run on its own LWP until all the nondaemon threads have exited the process. This type of thread can be used when you want some type of "background" processing to always be running, except when all the "regular" threads have exited the process. If thread F was created as a non-daemon thread, then it would continue to run forever, because a process will continue while there is at least one thread still running. Thread F will exit when all the nondaemon threads have exited. In this case, thread D should be the last nondaemon thread running, so when thread D exits, it will also cause thread F to exit.
This example, however trivial, shows how threads behave differently, based on their creation options. It also shows what happens on the exit of a thread, again based on how it was created. If you understand this example and how it flows, you should have a good understanding of how to use thr_create() and thr_join() in your own programs. Hopefully you can also see how easy it is to create and join threads.
The source to multi_thr.c:
The main thread first initializes the data structure and the mutex variable. It then sets a level of concurrency and creates the worker threads. The main thread then blocks by joining all the threads. When all the threads have exited, the main thread prints the results.
The worker threads modify the shared data structure from within a loop. Each time the threads need to modify the shared data, they lock the mutex variable associated with the shared data. After modifying the data, the threads unlock the mutex, allowing another thread access to the data.
This example may look quite simple, but it shows how important it is to control access to a simple, shared data structure. The results can be quite different if the mutex variable is not used.
The source to array.c:
The main thread creates the counter thread and then loops, waiting for user input. When the user presses the Return key, the main thread suspends the counter thread and then prints the value of the global variable. The main thread prints the value of the global variable under the protection of a mutex lock.
The problem arises in this example when the main thread suspends the counter thread while the counter thread is holding the mutex lock. After the main thread suspends the counter thread, it tries to lock the mutex variable. Since the mutex variable is already held by the counter thread, which is suspended, the main thread deadlocks.
This example may run fine for a while, as long as the counter thread just happens to be suspended when it is not holding the mutex lock. The example demonstrates how tricky some programming issues can be when you deal with threads.
The source to susp_lock.c
This example shows how you can implement a signal handler thread that will service all asynchronous signals that are sent to your process. This is an easy way to deal with signals, because only one thread is needed to handle all the signals. It also makes it easy when you create new threads within the process, because you need not worry about signals in any of the threads.
First, in the main thread, mask out all signals and then create a signal handling thread. Since threads inherit the signal mask from their creator, any new threads created after the new signal mask will also mask all signals. This idea is key, because the only thread that will receive signals is the one thread that does not block all the signals.
The signal handler thread waits for all incoming signals with the sigwait() call. This call unmasks the signals given to it and then blocks until a signal arrives. When a signal arrives, sigwait() masks the signals again and then returns with the signal ID of the incoming signal.
You can extend this example for use in your application code to handle all your signals. Notice also that this signal concept could be added in your existing nonthreaded code as a simpler way to deal with signals.
The source to thr_sig.c
This example shows how semaphores from the threads library can be used between processes. Note that this program does not use threads; it is just using the lightweight semaphores available from the threads library.
When using synchronization variables between processes, it is important to make sure that only one process initializes the variable. If both processes try to initialize the synchronization variable, then one of the processes will overwrite the state of the variable set by the other process.
The source to ipc.c
Two condition variables control access to the buffer. One condition variable is used to tell if the buffer is full, and the other is used to tell if the buffer is empty. When the producer wants to add an item to the buffer, it checks to see if the buffer is full; if it is full the producer blocks on the cond_wait() call, waiting for an item to be removed from the buffer. When the consumer removes an item from the buffer, the buffer is no longer full, so the producer is awakened from the cond_wait() call. The producer is then allowed to add another item to the buffer.
The consumer works, in many ways, the same as the producer. The consumer uses the other condition variable to determine if the buffer is empty. When the consumer wants to remove an item from the buffer, it checks to see if it is empty. If the buffer is empty, the consumer then blocks on the cond_wait() call, waiting for an item to be added to the buffer. When the producer adds an item to the buffer, the consumer's condition is satisfied, so it can then remove an item from the buffer.
The example copies a file by reading data into a shared buffer (producer) and then writing data out to the new file (consumer). The Buf data structure is used to hold both the buffered data and the condition variables that control the flow of the data.
The main thread opens both files, initializes the Buf data structure, creates the consumer thread, and then assumes the role of the producer. The producer reads data from the input file, then places the data into an open buffer position. If no buffer positions are available, then the producer waits via the cond_wait() call. After the producer has read all the data from the input file, it closes the file and waits for (joins) the consumer thread.
The consumer thread reads from a shared buffer and then writes the data to the output file. If no buffers positions are available, then the consumer waits for the producer to fill a buffer position. After the consumer has read all the data, it closes the output file and exits.
If the input file and the output file were residing on different physical disks, then this example could execute the reads and writes in parallel. This parallelism would significantly increase the throughput of the example through the use of threads.
The source to prod_cons.c:
A standard socket server should listen on a socket port and, when a message arrives, fork a process to service the request. Since a fork() system call would be used in a nonthreaded program, any communication between the parent and child would have to be done through some sort of interprocess communication.
We can replace the fork() call with a thr_create() call. Doing so offers a few advantages: thr_create() can create a thread much faster then a fork() could create a new process, and any communication between the server and the new thread can be done with common variables. This technique makes the implementation of the socket server much easier to understand and should also make it respond much faster to incoming requests.
The server program first sets up all the needed socket information. This is the basic setup for most socket servers. The server then enters an endless loop, waiting to service a socket port. When a message is sent to the socket port, the server wakes up and creates a new thread to handle the request. Notice that the server creates the new thread as a detached thread and also passes the socket descriptor as an argument to the new thread.
The newly created thread can then read or write, in any fashion it wants, to the socket descriptor that was passed to it. At this point the server could be creating a new thread or waiting for the next message to arrive. The key is that the server thread does not care what happens to the new thread after it creates it.
In our example, the created thread reads from the socket descriptor and then increments a global variable. This global variable keeps track of the number of requests that were made to the server. Notice that a mutex lock is used to protect access to the shared global variable. The lock is needed because many threads might try to increment the same variable at the same time. The mutex lock provides serial access to the shared variable. See how easy it is to share information among the new threads! If each of the threads were a process, then a significant effort would have to be made to share this information among the processes.
The client piece of the example sends a given number of messages to the server. This client code could also be run from different machines by multiple users, thus increasing the need for concurrency in the server process.
The source code to soc_server.c:
We have said before that anything you can do with threads, you can do without them. This may be a case where it would be very hard to do without threads. If you have some spare time (and lots of memory), try implementing this program by using processes, instead of threads. If you try this, you will see why threads can have an advantage over processes.
This program takes as an argument the number of threads to create. Notice that all the threads are created with a user-defined stack size, which limits the amount of memory that the threads will need for execution. The stack size for a given thread can be hard to calculate, so some testing usually needs to be done to see if the chosen stack size will work. You may want to change the stack size in this program and see how much you can lower it before things stop working. The Solaris threads library provides the thr_min_stack() call, which returns the minimum allowed stack size. Take care when adjusting the size of a threads stack. A stack overflow can happen quite easily to a thread with a small stack.
After each thread is created, it blocks, waiting on a mutex variable. This mutex variable was locked before any of the threads were created, which prevents the threads from proceeding in their execution. When all of the threads have been created and the user presses Return, the mutex variable is unlocked, allowing all the threads to proceed.
After the main thread has created all the threads, it waits for user input and then tries to join all the threads. Notice that the thr_join() call does not care what thread it joins; it is just counting the number of joins it makes.
This example is rather trivial and does not serve any real purpose except to show that it is possible to create a lot of threads in one process. However, there are situations when many threads are needed in an application. An example might be a network port server, where a thread is created each time an incoming or outgoing request is made.
The source to many_thr.c:
Since this book does not cover the concerns that arise with real-time programming, we have included this code only as an example of how to promote a thread into the real-time class. You must be very careful when you use real-time threads in your applications. For more information on real-time programming, see the Solaris documentation.
This example should be safe from the pitfalls of real-time programs because of its simplicity. However, changing this code in any way could have adverse affects on your system.
The example creates a new thread from the main thread. This new thread is then promoted to the real-time class by looking up the real-time class ID and then setting a real-time priority for the thread. After the thread is running in realtime, it simulates some processing. Since a thread in the real-time class can have an infinite time quantum, the process is allowed to stay on a CPU as long as it likes. The time quantum is the amount of time a thread is allowed to stay running on a CPU. For the timesharing class, the time quantum (time-slice) is 1/100th of a second by default.
In this example, we set the time quantum for the real-time thread to infinity. That is, it can stay running as long as it likes; it will not be preempted or scheduled off the CPU. If you run this example on a UP machine, it will have the effect of stopping your system for a few seconds while the thread simulates its processing. The system does not actually stop, it is just working in the real-time thread. When the real-time thread finishes its processing, it exits and the system returns to normal.
Using real-time threads can be quite useful when you need an extremely high priority and response time but can also cause big problems if it not used properly. Also note that this example must be run as root or have root execute permissions.
The source to rt_thr.c:
This example simulates a multithreaded search for a given number by taking random guesses at a target number. The intent here is to simulate the same type of search that a database might execute. For example, a database might create threads to start searching for a data item; after some amount of time, one or more threads might return with the target data item.
If a thread guesses the number correctly, there is no need for the other threads to continue their search. This is where thread cancellation can help. The thread that finds the number first should cancel the other threads that are still searching for the item and then return the results of the search.
The threads involved in the search can call a cleanup function that can clean up the threads resources before it exits. In this case, the cleanup function prints the progress of the thread when it was cancelled.
The source to posix_cancel.c:
In the example, thr_continue() and thr_suspend() calls continue and suspend a given thread, respectively. Although both of these calls are valid, use caution when implementing them. It is very hard to determine where a thread is in its execution. Because of this, you may not be able to tell where the thread will suspend when the call to thr_suspend() is made. This behavior can cause problems in threaded code if not used properly.
The following example uses thr_continue() and thr_suspend() to try to control when a thread starts and stops. The example looks trivial, but, as you will see, can cause a big problem.
Do you see the problem? If you guessed that the program would eventually suspend itself, you were correct! The example attempts to flip-flop between the main thread and a subroutine thread. Each thread continues the other thread and then suspends itself.
Thread A continues thread B and then suspends thread A; now the continued thread B can continue thread A and then suspend itself. This should continue back and forth all day long, right? Wrong! We can't guarantee that each thread will continue the other thread and then suspend itself in one atomic action, so a software race condition could be created. Calling thr_continue() on a running thread and calling thr_suspend() on a suspended thread has no effect, so we don't know if a thread is already running or suspended.
If thread A continues thread B and if between the time thread A suspends itself, thread B continues thread A, then both of the threads will call thr_suspend(). This is the race condition in this program that will cause the whole process to become suspended.
It is very hard to use these calls, because you never really know the state of a thread. If you don't know exactly where a thread is in its execution, then you don't know what locks it holds and where it will stop when you suspend it.
The source to sw_race.c
You can also filter the files that you want Tgrep to search like you can with find. The next two commands do the same thing, just Tgrep gets it done faster.
Dave Marshall
1/5/1999 thr_create
The -p option will allow Tgrep to search only files that match the "regular expression" file pattern string. This option does NOT use shell expression, so to stop Tgrep from seeing a file named foobar.cyou must add the "$" meta character to the pattern and escape the real ``.'' character.
Some of the other Tgrep only options are -r, -C, -P, -e, -B, -S and -Z. The -r option stops Tgrep from searching any sub-directories, in other words, search only the local directory, but -l was taken. The -C option will search for and print "continued" lines like you find in Makefile. Note the differences in the results of grep and Tgrep run in the current directory.
The Tgrep output prints the continued lines that ended with the "character. In the case of grep I would not have seen the three values assigned to SUBDIRS, but Tgrep shows them to me (Common, Solaris, Posix).
The -P option I use when I am sending the output of a long search to a file and want to see the "progress" of the search. The -P option will print a "." (dot) on stderr for every file (or groups of files depending on the value of the -P argument) Tgrep searches.
The -e option will change the way Tgrep uses the target string. Tgrep uses two different patter matching systems. The first (with out the -e option) is a literal string match call Boyer-Moore. If the -e option is used, then a MT-Safe PD version of regular expression is used to search for the target string as a regexp with meta characters in it. The regular expression method is slower, but Tgrep needed the functionality. The -Z option will print help on the meta characters Tgrep uses.
The -B option tells Tgrep to use the value of the environment variable called TGLIMIT to limit the number of threads it will use during a search. This option has no affect if TGLIMIT is not set. Tgrep can "eat" a system alive, so the -B option was a way to run Tgrep on a system with out having other users scream at you.
The last new option is -S. If you want to see how things went while Tgrep was searching, you can use this option to print statistic about the number of files, lines, bytes, matches, threads created, etc.
Here is an example of the -S options output. (again run in the current directory)
The Tgrep.c source code is:
Dave Marshall
1/5/1999
Subsections
- Using thr_create() and thr_join()
- Arrays
- Deadlock
- Signal Handler
- Interprocess Synchronization
- The Producer / Consumer Problem
- A Socket Server
- Using Many Threads
- Real-time Thread Example
- POSIX Cancellation
- Software Race Condition
- Tgrep: Threadeds version of UNIX grep
- Multithreaded Quicksort
Thread programming examples
This chapter gives some full code examples of thread programs. These examles are taken from a variety of sources:- The sun workshop developers web page http://www.sun.com/workshop/threads/share-code/ on threads is an excelleny source
- The web page http://www.sun.com/workshop/threads/Berg-Lewis/examples.html where example from the Threads Primer Book by D. Berg anD B. Lewis are also a major resource.
Using thr_create() and thr_join()
This example exercises the thr_create() and thr_join() calls. There is not a parent/child relationship between threads as there is for processes. This can easily be seen in this example, because threads are created and joined by many different threads in the process. The example also shows how threads behave when created with different attributes and options.Threads can be created by any thread and joined by any other.
The main thread: In this example the main thread's sole purpose is to create new threads. Threads A, B, and C are created by the main thread. Notice that thread B is created suspended. After creating the new threads, the main thread exits. Also notice that the main thread exited by calling thr_exit(). If the main thread had used the exit() call, the whole process would have exited. The main thread's exit status and resources are held until it is joined by thread C.
Thread A: The first thing thread A does after it is created is to create thread D. Thread A then simulates some processing and then exits, using thr_exit(). Notice that thread A was created with the THR_DETACHED flag, so thread A's resources will be immediately reclaimed upon its exit. There is no way for thread A's exit status to be collected by a thr_join() call.
Thread B: Thread B was created in a suspended state, so it is not able to run until thread D continues it by making the thr_continue() call. After thread B is continued, it simulates some processing and then exits. Thread B's exit status and thread resources are held until joined by thread E.
Thread C: The first thing that thread C does is to create thread F. Thread C then joins the main thread. This action will collect the main thread's exit status and allow the main thread's resources to be reused by another thread. Thread C will block, waiting for the main thread to exit, if the main thread has not yet called thr_exit(). After joining the main thread, thread C will simulate some processing and then exit. Again, the exit status and thread resources are held until joined by thread E.
Thread D: Thread D immediately creates thread E. After creating thread E, thread D continues thread B by making the thr_continue() call. This call will allow thread B to start its execution. Thread D then tries to join thread E, blocking until thread E has exited. Thread D then simulates some processing and exits. If all went well, thread D should be the last nondaemon thread running. When thread D exits, it should do two things: stop the execution of any daemon threads and stop the execution of the process.
Thread E: Thread E starts by joining two threads, threads B and C. Thread E will block, waiting for each of these thread to exit. Thread E will then simulate some processing and will exit. Thread E's exit status and thread resources are held by the operating system until joined by thread D.
Thread F: Thread F was created as a bound, daemon thread by using the THR_BOUND and THR_DAEMON flags in the thr_create() call. This means that it will run on its own LWP until all the nondaemon threads have exited the process. This type of thread can be used when you want some type of "background" processing to always be running, except when all the "regular" threads have exited the process. If thread F was created as a non-daemon thread, then it would continue to run forever, because a process will continue while there is at least one thread still running. Thread F will exit when all the nondaemon threads have exited. In this case, thread D should be the last nondaemon thread running, so when thread D exits, it will also cause thread F to exit.
This example, however trivial, shows how threads behave differently, based on their creation options. It also shows what happens on the exit of a thread, again based on how it was created. If you understand this example and how it flows, you should have a good understanding of how to use thr_create() and thr_join() in your own programs. Hopefully you can also see how easy it is to create and join threads.
The source to multi_thr.c:
#define _REENTRANT
#include <stdio.h>
#include <thread.h>
/* Function prototypes for thread routines */
void *sub_a(void *);
void *sub_b(void *);
void *sub_c(void *);
void *sub_d(void *);
void *sub_e(void *);
void *sub_f(void *);
thread_t thr_a, thr_b, thr_c;
void main()
{
thread_t main_thr;
main_thr = thr_self();
printf("Main thread = %d\n", main_thr);
if (thr_create(NULL, 0, sub_b, NULL, THR_SUSPENDED|THR_NEW_LWP, &thr_b))
fprintf(stderr,"Can't create thr_b\n"), exit(1);
if (thr_create(NULL, 0, sub_a, (void *)thr_b, THR_NEW_LWP, &thr_a))
fprintf(stderr,"Can't create thr_a\n"), exit(1);
if (thr_create(NULL, 0, sub_c, (void *)main_thr, THR_NEW_LWP, &thr_c))
fprintf(stderr,"Can't create thr_c\n"), exit(1);
printf("Main Created threads A:%d B:%d C:%d\n", thr_a, thr_b, thr_c);
printf("Main Thread exiting...\n");
thr_exit((void *)main_thr);
}
void *sub_a(void *arg)
{
thread_t thr_b = (thread_t) arg;
thread_t thr_d;
int i;
printf("A: In thread A...\n");
if (thr_create(NULL, 0, sub_d, (void *)thr_b, THR_NEW_LWP, &thr_d))
fprintf(stderr, "Can't create thr_d\n"), exit(1);
printf("A: Created thread D:%d\n", thr_d);
/* process
*/
for (i=0;i<1000000*(int)thr_self();i++);
printf("A: Thread exiting...\n");
thr_exit((void *)77);
}
void * sub_b(void *arg)
{
int i;
printf("B: In thread B...\n");
/* process
*/
for (i=0;i<1000000*(int)thr_self();i++);
printf("B: Thread exiting...\n");
thr_exit((void *)66);
}
void * sub_c(void *arg)
{
void *status;
int i;
thread_t main_thr, ret_thr;
main_thr = (thread_t)arg;
printf("C: In thread C...\n");
if (thr_create(NULL, 0, sub_f, (void *)0, THR_BOUND|THR_DAEMON, NULL))
fprintf(stderr, "Can't create thr_f\n"), exit(1);
printf("C: Join main thread\n");
if (thr_join(main_thr,(thread_t *)&ret_thr, &status))
fprintf(stderr, "thr_join Error\n"), exit(1);
printf("C: Main thread (%d) returned thread (%d) w/status %d\n", main_thr, ret_thr, (int) status);
/* process
*/
for (i=0;i<1000000*(int)thr_self();i++);
printf("C: Thread exiting...\n");
thr_exit((void *)88);
}
void * sub_d(void *arg)
{
thread_t thr_b = (thread_t) arg;
int i;
thread_t thr_e, ret_thr;
void *status;
printf("D: In thread D...\n");
if (thr_create(NULL, 0, sub_e, NULL, THR_NEW_LWP, &thr_e))
fprintf(stderr,"Can't create thr_e\n"), exit(1);
printf("D: Created thread E:%d\n", thr_e);
printf("D: Continue B thread = %d\n", thr_b);
thr_continue(thr_b);
printf("D: Join E thread\n");
if(thr_join(thr_e,(thread_t *)&ret_thr, &status))
fprintf(stderr,"thr_join Error\n"), exit(1);
printf("D: E thread (%d) returned thread (%d) w/status %d\n", thr_e,
ret_thr, (int) status);
/* process
*/
for (i=0;i<1000000*(int)thr_self();i++);
printf("D: Thread exiting...\n");
thr_exit((void *)55);
}
void * sub_e(void *arg)
{
int i;
thread_t ret_thr;
void *status;
printf("E: In thread E...\n");
printf("E: Join A thread\n");
if(thr_join(thr_a,(thread_t *)&ret_thr, &status))
fprintf(stderr,"thr_join Error\n"), exit(1);
printf("E: A thread (%d) returned thread (%d) w/status %d\n", ret_thr, ret_thr, (int) status);
printf("E: Join B thread\n");
if(thr_join(thr_b,(thread_t *)&ret_thr, &status))
fprintf(stderr,"thr_join Error\n"), exit(1);
printf("E: B thread (%d) returned thread (%d) w/status %d\n", thr_b, ret_thr, (int) status);
printf("E: Join C thread\n");
if(thr_join(thr_c,(thread_t *)&ret_thr, &status))
fprintf(stderr,"thr_join Error\n"), exit(1);
printf("E: C thread (%d) returned thread (%d) w/status %d\n", thr_c, ret_thr, (int) status);
for (i=0;i<1000000*(int)thr_self();i++);
printf("E: Thread exiting...\n");
thr_exit((void *)44);
}
void *sub_f(void *arg)
{
int i;
printf("F: In thread F...\n");
while (1) {
for (i=0;i<10000000;i++);
printf("F: Thread F is still running...\n");
}
}
Arrays
This example uses a data structure that contains multiple arrays of data. Multiple threads will concurrently vie for access to the arrays. To control this access, a mutex variable is used within the data structure to lock the entire array and serialize the access to the data.The main thread first initializes the data structure and the mutex variable. It then sets a level of concurrency and creates the worker threads. The main thread then blocks by joining all the threads. When all the threads have exited, the main thread prints the results.
The worker threads modify the shared data structure from within a loop. Each time the threads need to modify the shared data, they lock the mutex variable associated with the shared data. After modifying the data, the threads unlock the mutex, allowing another thread access to the data.
This example may look quite simple, but it shows how important it is to control access to a simple, shared data structure. The results can be quite different if the mutex variable is not used.
The source to array.c:
#define _REENTRANT<br />#include <stdio.h><br />#include <thread.h><br /><br />/* sample array data structure */<br />struct {<br /> mutex_t data_lock[5];<br /> int int_val[5];<br /> float float_val[5];<br /> } Data;<br /><br />/* thread function */<br />void *Add_to_Value();<br /><br />main()<br />{<br />int i;<br /><br />/* initialize the mutexes and data */<br />for (i=0; i<5; i++) {<br /> mutex_init(&Data.data_lock[i], USYNC_THREAD, 0);<br /> Data.int_val[i] = 0;<br /> Data.float_val[i] = 0;<br /> }<br /><br />/* set concurrency and create the threads */<br />thr_setconcurrency(4);<br /><br />for (i=0; i<5; i++)<br /> thr_create(NULL, 0, Add_to_Value, (void *)(2*i), 0, NULL);<br /><br />/* wait till all threads have finished */<br />for (i=0; i<5; i++)<br /> thr_join(0,0,0);<br /><br />/* print the results */<br />printf("Final Values.....\n");<br /><br />for (i=0; i<5; i++) {<br /> printf("integer value[%d] =\t%d\n", i, Data.int_val[i]);<br /> printf("float value[%d] =\t%.0f\n\n", i, Data.float_val[i]);<br /> }<br /><br />return(0);<br />}<br /><br /><br />/* Threaded routine */<br />void *Add_to_Value(void *arg)<br />{<br />int inval = (int) arg;<br />int i;<br /><br />for (i=0;i<10000;i++){<br /> mutex_lock(&Data.data_lock[i%5]);<br /> Data.int_val[i%5] += inval;<br /> Data.float_val[i%5] += (float) 1.5 * inval;<br /> mutex_unlock(&Data.data_lock[i%5]);<br /> }<br /><br />return((void *)0);<br />}<br />Deadlock
This example demonstrates how a deadlock can occur in multithreaded programs that use synchronization variables. In this example a thread is created that continually adds a value to a global variable. The thread uses a mutex lock to protect the global data.The main thread creates the counter thread and then loops, waiting for user input. When the user presses the Return key, the main thread suspends the counter thread and then prints the value of the global variable. The main thread prints the value of the global variable under the protection of a mutex lock.
The problem arises in this example when the main thread suspends the counter thread while the counter thread is holding the mutex lock. After the main thread suspends the counter thread, it tries to lock the mutex variable. Since the mutex variable is already held by the counter thread, which is suspended, the main thread deadlocks.
This example may run fine for a while, as long as the counter thread just happens to be suspended when it is not holding the mutex lock. The example demonstrates how tricky some programming issues can be when you deal with threads.
The source to susp_lock.c
#define _REENTRANT<br />#include <stdio.h><br />#include <thread.h><br /><br />/* Prototype for thread subroutine */<br />void *counter(void *);<br /><br />int count;<br />mutex_t count_lock;<br /><br />main()<br />{<br />char str[80];<br />thread_t ctid;<br /><br />/* create the thread counter subroutine */<br />thr_create(NULL, 0, counter, 0, THR_NEW_LWP|THR_DETACHED, &ctid);<br /><br />while(1) {<br /> gets(str);<br /> thr_suspend(ctid);<br /><br /> mutex_lock(&count_lock);<br /> printf("\n\nCOUNT = %d\n\n", count);<br /> mutex_unlock(&count_lock);<br /><br /> thr_continue(ctid);<br /> }<br /><br />return(0);<br />}<br /><br />void *counter(void *arg)<br />{<br />int i;<br /><br />while (1) {<br /> printf("."); fflush(stdout);<br /><br /> mutex_lock(&count_lock);<br /> count++;<br /><br /> for (i=0;i<50000;i++);<br /><br /> mutex_unlock(&count_lock);<br /><br /> for (i=0;i<50000;i++);<br /> }<br /><br />return((void *)0);<br />}<br />Signal Handler
This example shows how easy it is to handle signals in multithreaded programs. In most programs, a different signal handler would be needed to service each type of signal that you wanted to catch. Writing each of the signal handlers can be time consuming and can be a real pain to debug.This example shows how you can implement a signal handler thread that will service all asynchronous signals that are sent to your process. This is an easy way to deal with signals, because only one thread is needed to handle all the signals. It also makes it easy when you create new threads within the process, because you need not worry about signals in any of the threads.
First, in the main thread, mask out all signals and then create a signal handling thread. Since threads inherit the signal mask from their creator, any new threads created after the new signal mask will also mask all signals. This idea is key, because the only thread that will receive signals is the one thread that does not block all the signals.
The signal handler thread waits for all incoming signals with the sigwait() call. This call unmasks the signals given to it and then blocks until a signal arrives. When a signal arrives, sigwait() masks the signals again and then returns with the signal ID of the incoming signal.
You can extend this example for use in your application code to handle all your signals. Notice also that this signal concept could be added in your existing nonthreaded code as a simpler way to deal with signals.
The source to thr_sig.c
#define _REENTRANT<br />#include <stdio.h><br />#include <thread.h><br />#include <signal.h><br />#include <sys/types.h><br /><br />void *signal_hand(void *);<br /><br />main()<br />{<br />sigset_t set;<br /><br />/* block all signals in main thread. Any other threads that are<br /> created after this will also block all signals */<br /><br />sigfillset(&set); <br /><br />thr_sigsetmask(SIG_SETMASK, &set, NULL);<br /><br />/* create a signal handler thread. This thread will catch all<br /> signals and decide what to do with them. This will only<br /> catch nondirected signals. (I.e., if a thread causes a SIGFPE <br /> then that thread will get that signal. */<br /><br />thr_create(NULL, 0, signal_hand, 0, THR_NEW_LWP|THR_DAEMON|THR_DETACHED, NULL);<br /><br />while (1) {<br /> /*<br /> Do your normal processing here....<br /> */<br /> } /* end of while */<br /><br />return(0);<br />}<br /><br />void *signal_hand(void *arg)<br />{<br />sigset_t set;<br />int sig;<br /><br />sigfillset(&set); /* catch all signals */<br /><br />while (1) {<br /> /* wait for a signal to arrive */<br /><br /> switch (sig=sigwait(&set)) {<br /><br /> /* here you would add whatever signal you needed to catch */<br /> case SIGINT : {<br /> printf("Interrupted with signal %d, exiting...\n", sig);<br /> exit(0); <br /> }<br /><br /> default : printf("GOT A SIGNAL = %d\n", sig); <br /> } /* end of switch */<br /> } /* end of while */<br /><br />return((void *)0);<br />} /* end of signal_hand */<br />Another example of a signal handler, sig_kill.c: /*<br />* Multithreaded Demo Source<br />* <br />* Copyright (C) 1995 by Sun Microsystems, Inc.<br />* All rights reserved.<br />* <br />* This file is a product of SunSoft, Inc. and is provided for<br />* unrestricted use provided that this legend is included on all<br />* media and as a part of the software program in whole or part.<br />* Users may copy, modify or distribute this file at will.<br />* <br />* THIS FILE IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND INCLUDING<br />* THE WARRANTIES OF DESIGN, MERCHANTIBILITY AND FITNESS FOR A PARTICULAR<br />* PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE PRACTICE.<br />* <br />* This file is provided with no support and without any obligation on the<br />* part of SunSoft, Inc. to assist in its use, correction, modification or<br />* enhancement.<br />* <br />* SUNSOFT AND SUN MICROSYSTEMS, INC. SHALL HAVE NO LIABILITY WITH RESPECT<br />* TO THE INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THIS<br />* FILE OR ANY PART THEREOF.<br />* <br />* IN NO EVENT WILL SUNSOFT OR SUN MICROSYSTEMS, INC. BE LIABLE FOR ANY<br />* LOST REVENUE OR PROFITS OR OTHER SPECIAL, INDIRECT AND CONSEQUENTIAL<br />* DAMAGES, EVEN IF THEY HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH<br />* DAMAGES.<br />* <br />* SunSoft, Inc.<br />* 2550 Garcia Avenue<br />* Mountain View, California 94043<br />*/<br /><br />/* <br /> * Rich Schiavi writes: Sept 11, 1994<br /> *<br /> * I believe the recommended way to kill certain threads is<br /> * using a signal handler which then will exit that particular<br /> * thread properly. I'm not sure the exact reason (I can't remember), but<br /> * if you take out the signal_handler routine in my example, you will see what<br /> * you describe, as the main process dies even if you send the<br /> * thr_kill to the specific thread.<br /><br /> * I whipped up a real quick simple example which shows this using<br /> * some sleep()s to get a good simulation.<br /> */<br /><br />#include <stdio.h><br />#include <thread.h><br />#include <signal.h><br /><br />static thread_t one_tid, two_tid, main_thread;<br />static void *first_thread();<br />static void *second_thread();<br />void ExitHandler(int);<br /><br />static mutex_t first_mutex, second_mutex;<br />int first_active = 1 ; <br />int second_active = 1;<br /><br />main()<br /><br />{<br /> int i;<br /> struct sigaction act;<br /><br /> act.sa_handler = ExitHandler;<br /> (void) sigemptyset(&act.sa_mask);<br /> (void) sigaction(SIGTERM, &act, NULL); <br /><br /> mutex_init(&first_mutex, 0 , 0);<br /> mutex_init(&second_mutex, 0 , 0);<br /> main_thread = thr_self();<br /><br /> thr_create(NULL,0,first_thread,0,THR_NEW_LWP,&one_tid);<br /> thr_create(NULL,0,second_thread,0,THR_NEW_LWP,&two_tid); <br /><br /> for (i = 0; i < 10; i++){<br /> fprintf(stderr, "main loop: %d\n", i);<br /> if (i == 5) {<br /> thr_kill(one_tid, SIGTERM);<br /> }<br /> sleep(3);<br /> }<br /> thr_kill(two_tid, SIGTERM);<br /> sleep(5);<br /> fprintf(stderr, "main exit\n");<br />}<br /><br />static void *first_thread()<br />{<br /> int i = 0;<br /> <br /> fprintf(stderr, "first_thread id: %d\n", thr_self());<br /> while (first_active){<br /> fprintf(stderr, "first_thread: %d\n", i++); <br /> sleep(2);<br /> }<br /> fprintf(stderr, "first_thread exit\n");<br />}<br /><br />static void *second_thread()<br />{<br /> int i = 0;<br /><br /> fprintf(stderr, "second_thread id: %d\n", thr_self());<br /><br /> while (second_active){<br /> fprintf(stderr, "second_thread: %d\n", i++);<br /> sleep(3);<br /> }<br /> fprintf(stderr, "second_thread exit\n");<br />}<br /><br />void ExitHandler(int sig)<br />{<br /> thread_t id;<br /><br /> id = thr_self();<br /><br /> fprintf(stderr, "ExitHandler thread id: %d\n", id);<br /> thr_exit(0);<br /><br />}<br />Interprocess Synchronization
This example uses some of the synchronization variables available in the threads library to synchronize access to a resource shared between two processes. The synchronization variables used in the threads library are an advantage over standard IPC synchronization mechanisms because of their speed. The synchronization variables in the threads libraries have been tuned to be very lightweight and very fast. This speed can be an advantage when your application is spending time synchronizing between processes.This example shows how semaphores from the threads library can be used between processes. Note that this program does not use threads; it is just using the lightweight semaphores available from the threads library.
When using synchronization variables between processes, it is important to make sure that only one process initializes the variable. If both processes try to initialize the synchronization variable, then one of the processes will overwrite the state of the variable set by the other process.
The source to ipc.c
#include <stdio.h><br />#include <fcntl.h><br />#include <sys/mman.h><br />#include <synch.h><br />#include <sys/types.h><br />#include <unistd.h><br /><br />/* a structure that will be used between processes */<br />typedef struct {<br /> sema_t mysema;<br /> int num;<br />} buf_t;<br /><br />main()<br />{<br />int i, j, fd;<br />buf_t *buf;<br /><br />/* open a file to use in a memory mapping */<br />fd = open("/dev/zero", O_RDWR);<br /><br />/* create a shared memory map with the open file for the data <br /> structure that will be shared between processes */<br />buf=(buf_t *)mmap(NULL, sizeof(buf_t), PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);<br /><br />/* initialize the semaphore -- note the USYNC_PROCESS flag; this makes<br /> the semaphore visible from a process level */<br />sema_init(&buf->mysema, 0, USYNC_PROCESS, 0);<br /><br />/* fork a new process */<br />if (fork() == 0) {<br /> /* The child will run this section of code */<br /> for (j=0;j<5;j++)<br /> {<br /> /* have the child "wait" for the semaphore */<br /><br /> printf("Child PID(%d): waiting...\n", getpid());<br /> sema_wait(&buf->mysema);<br /><br /> /* the child decremented the semaphore */<br /><br /> printf("Child PID(%d): decrement semaphore.\n", getpid());<br /> }<br /> /* exit the child process */<br /> printf("Child PID(%d): exiting...\n", getpid());<br /> exit(0);<br /> }<br /><br />/* The parent will run this section of code */<br />/* give the child a chance to start running */<br /><br />sleep(2);<br /><br />for (i=0;i<5;i++)<br /> {<br /> /* increment (post) the semaphore */<br /><br /> printf("Parent PID(%d): posting semaphore.\n", getpid());<br /> sema_post(&buf->mysema);<br /><br /> /* wait a second */<br /> sleep(1);<br /> }<br /><br />/* exit the parent process */<br />printf("Parent PID(%d): exiting...\n", getpid());<br /><br />return(0);<br />}<br />The Producer / Consumer Problem
This example will show how condition variables can be used to control access of reads and writes to a buffer. This example can also be thought as a producer/consumer problem, where the producer adds items to the buffer and the consumer removes items from the buffer.Two condition variables control access to the buffer. One condition variable is used to tell if the buffer is full, and the other is used to tell if the buffer is empty. When the producer wants to add an item to the buffer, it checks to see if the buffer is full; if it is full the producer blocks on the cond_wait() call, waiting for an item to be removed from the buffer. When the consumer removes an item from the buffer, the buffer is no longer full, so the producer is awakened from the cond_wait() call. The producer is then allowed to add another item to the buffer.
The consumer works, in many ways, the same as the producer. The consumer uses the other condition variable to determine if the buffer is empty. When the consumer wants to remove an item from the buffer, it checks to see if it is empty. If the buffer is empty, the consumer then blocks on the cond_wait() call, waiting for an item to be added to the buffer. When the producer adds an item to the buffer, the consumer's condition is satisfied, so it can then remove an item from the buffer.
The example copies a file by reading data into a shared buffer (producer) and then writing data out to the new file (consumer). The Buf data structure is used to hold both the buffered data and the condition variables that control the flow of the data.
The main thread opens both files, initializes the Buf data structure, creates the consumer thread, and then assumes the role of the producer. The producer reads data from the input file, then places the data into an open buffer position. If no buffer positions are available, then the producer waits via the cond_wait() call. After the producer has read all the data from the input file, it closes the file and waits for (joins) the consumer thread.
The consumer thread reads from a shared buffer and then writes the data to the output file. If no buffers positions are available, then the consumer waits for the producer to fill a buffer position. After the consumer has read all the data, it closes the output file and exits.
If the input file and the output file were residing on different physical disks, then this example could execute the reads and writes in parallel. This parallelism would significantly increase the throughput of the example through the use of threads.
The source to prod_cons.c:
#define _REEENTRANT<br />#include <stdio.h><br />#include <thread.h><br />#include <fcntl.h><br />#include <unistd.h><br />#include <sys/stat.h><br />#include <sys/types.h><br />#include <sys/uio.h><br /><br />#define BUFSIZE 512<br />#define BUFCNT 4<br /><br />/* this is the data structure that is used between the producer<br /> and consumer threads */<br /><br />struct {<br /> char buffer[BUFCNT][BUFSIZE];<br /> int byteinbuf[BUFCNT];<br /> mutex_t buflock;<br /> mutex_t donelock;<br /> cond_t adddata;<br /> cond_t remdata;<br /> int nextadd, nextrem, occ, done;<br />} Buf;<br /><br />/* function prototype */<br />void *consumer(void *);<br /><br />main(int argc, char **argv)<br />{<br />int ifd, ofd;<br />thread_t cons_thr;<br /><br />/* check the command line arguments */<br />if (argc != 3)<br /> printf("Usage: %s <infile> <outfile>\n", argv[0]), exit(0);<br /><br />/* open the input file for the producer to use */<br />if ((ifd = open(argv[1], O_RDONLY)) == -1)<br /> {<br /> fprintf(stderr, "Can't open file %s\n", argv[1]);<br /> exit(1);<br /> }<br /><br />/* open the output file for the consumer to use */<br />if ((ofd = open(argv[2], O_WRONLY|O_CREAT, 0666)) == -1)<br /> {<br /> fprintf(stderr, "Can't open file %s\n", argv[2]);<br /> exit(1);<br /> }<br /><br />/* zero the counters */<br />Buf.nextadd = Buf.nextrem = Buf.occ = Buf.done = 0;<br /><br />/* set the thread concurrency to 2 so the producer and consumer can<br /> run concurrently */<br /><br />thr_setconcurrency(2);<br /><br />/* create the consumer thread */<br />thr_create(NULL, 0, consumer, (void *)ofd, NULL, &cons_thr);<br /><br />/* the producer ! */<br />while (1) {<br /><br /> /* lock the mutex */<br /> mutex_lock(&Buf.buflock);<br /><br /> /* check to see if any buffers are empty */<br /> /* If not then wait for that condition to become true */<br /><br /> while (Buf.occ == BUFCNT)<br /> cond_wait(&Buf.remdata, &Buf.buflock);<br /><br /> /* read from the file and put data into a buffer */<br /> Buf.byteinbuf[Buf.nextadd] = read(ifd,Buf.buffer[Buf.nextadd],BUFSIZE);<br /><br /> /* check to see if done reading */<br /> if (Buf.byteinbuf[Buf.nextadd] == 0) {<br /><br /> /* lock the done lock */<br /> mutex_lock(&Buf.donelock);<br /><br /> /* set the done flag and release the mutex lock */<br /> Buf.done = 1;<br /><br /> mutex_unlock(&Buf.donelock);<br /><br /> /* signal the consumer to start consuming */<br /> cond_signal(&Buf.adddata);<br /><br /> /* release the buffer mutex */<br /> mutex_unlock(&Buf.buflock);<br /><br /> /* leave the while looop */<br /> break;<br /> }<br /><br /> /* set the next buffer to fill */<br /> Buf.nextadd = ++Buf.nextadd % BUFCNT;<br /><br /> /* increment the number of buffers that are filled */<br /> Buf.occ++;<br /><br /> /* signal the consumer to start consuming */<br /> cond_signal(&Buf.adddata);<br /><br /> /* release the mutex */<br /> mutex_unlock(&Buf.buflock);<br /> }<br /><br />close(ifd);<br /><br />/* wait for the consumer to finish */<br />thr_join(cons_thr, 0, NULL);<br /><br />/* exit the program */<br />return(0);<br />}<br /><br /><br />/* The consumer thread */<br />void *consumer(void *arg)<br />{<br />int fd = (int) arg;<br /><br />/* check to see if any buffers are filled or if the done flag is set */<br />while (1) {<br /><br /> /* lock the mutex */<br /> mutex_lock(&Buf.buflock);<br /><br /> if (!Buf.occ && Buf.done) {<br /> mutex_unlock(&Buf.buflock);<br /> break;<br /> }<br /><br /> /* check to see if any buffers are filled */<br /> /* if not then wait for the condition to become true */<br /><br /> while (Buf.occ == 0 && !Buf.done)<br /> cond_wait(&Buf.adddata, &Buf.buflock);<br /><br /> /* write the data from the buffer to the file */<br /> write(fd, Buf.buffer[Buf.nextrem], Buf.byteinbuf[Buf.nextrem]);<br /><br /> /* set the next buffer to write from */<br /> Buf.nextrem = ++Buf.nextrem % BUFCNT;<br /><br /> /* decrement the number of buffers that are full */<br /> Buf.occ--;<br /><br /> /* signal the producer that a buffer is empty */<br /> cond_signal(&Buf.remdata);<br /><br /> /* release the mutex */<br /> mutex_unlock(&Buf.buflock);<br /> }<br /><br />/* exit the thread */<br />thr_exit((void *)0);<br />}<br />A Socket Server
The socket server example uses threads to implement a "standard" socket port server. The example shows how easy it is to use thr_create() calls in the place of fork() calls in existing programs.A standard socket server should listen on a socket port and, when a message arrives, fork a process to service the request. Since a fork() system call would be used in a nonthreaded program, any communication between the parent and child would have to be done through some sort of interprocess communication.
We can replace the fork() call with a thr_create() call. Doing so offers a few advantages: thr_create() can create a thread much faster then a fork() could create a new process, and any communication between the server and the new thread can be done with common variables. This technique makes the implementation of the socket server much easier to understand and should also make it respond much faster to incoming requests.
The server program first sets up all the needed socket information. This is the basic setup for most socket servers. The server then enters an endless loop, waiting to service a socket port. When a message is sent to the socket port, the server wakes up and creates a new thread to handle the request. Notice that the server creates the new thread as a detached thread and also passes the socket descriptor as an argument to the new thread.
The newly created thread can then read or write, in any fashion it wants, to the socket descriptor that was passed to it. At this point the server could be creating a new thread or waiting for the next message to arrive. The key is that the server thread does not care what happens to the new thread after it creates it.
In our example, the created thread reads from the socket descriptor and then increments a global variable. This global variable keeps track of the number of requests that were made to the server. Notice that a mutex lock is used to protect access to the shared global variable. The lock is needed because many threads might try to increment the same variable at the same time. The mutex lock provides serial access to the shared variable. See how easy it is to share information among the new threads! If each of the threads were a process, then a significant effort would have to be made to share this information among the processes.
The client piece of the example sends a given number of messages to the server. This client code could also be run from different machines by multiple users, thus increasing the need for concurrency in the server process.
The source code to soc_server.c:
#define _REENTRANT<br />#include <stdio.h><br />#include <sys/types.h><br />#include <sys/socket.h><br />#include <netinet/in.h><br />#include <string.h><br />#include <sys/uio.h><br />#include <unistd.h><br />#include <thread.h><br /><br />/* the TCP port that is used for this example */<br />#define TCP_PORT 6500<br /><br />/* function prototypes and global variables */<br />void *do_chld(void *);<br />mutex_t lock;<br />int service_count;<br /><br />main()<br />{<br /> int sockfd, newsockfd, clilen;<br /> struct sockaddr_in cli_addr, serv_addr;<br /> thread_t chld_thr;<br /><br /> if((sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0)<br /> fprintf(stderr,"server: can't open stream socket\n"), exit(0);<br /><br /> memset((char *) &serv_addr, 0, sizeof(serv_addr));<br /> serv_addr.sin_family = AF_INET;<br /> serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);<br /> serv_addr.sin_port = htons(TCP_PORT);<br /> <br /> if(bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)) < <br />0)<br /> fprintf(stderr,"server: can't bind local address\n"), exit(0);<br /><br /> /* set the level of thread concurrency we desire */<br /> thr_setconcurrency(5);<br /><br /> listen(sockfd, 5);<br /><br /> for(;;){<br /> clilen = sizeof(cli_addr);<br /> newsockfd = accept(sockfd, (struct sockaddr *) &cli_addr, <br />&clilen);<br /><br /> if(newsockfd < 0)<br /> fprintf(stderr,"server: accept error\n"), exit(0);<br /><br /> /* create a new thread to process the incomming request */<br /> thr_create(NULL, 0, do_chld, (void *) newsockfd, THR_DETACHED, <br />&chld_thr);<br /><br /> /* the server is now free to accept another socket request */<br /> }<br /> return(0);<br />}<br /><br />/* <br /> This is the routine that is executed from a new thread <br />*/<br /><br />void *do_chld(void *arg)<br />{<br />int mysocfd = (int) arg;<br />char data[100];<br />int i;<br /><br /> printf("Child thread [%d]: Socket number = %d\n", thr_self(), mysocfd);<br /><br /> /* read from the given socket */<br /> read(mysocfd, data, 40);<br /><br /> printf("Child thread [%d]: My data = %s\n", thr_self(), data);<br /><br /> /* simulate some processing */<br /> for (i=0;i<1000000*thr_self();i++);<br /><br /> printf("Child [%d]: Done Processing...\n", thr_self()); <br /><br /> /* use a mutex to update the global service counter */<br /> mutex_lock(&lock);<br /><br /> service_count++;<br /> mutex_unlock(&lock);<br /><br /> printf("Child thread [%d]: The total sockets served = %d\n", thr_self(), service_count);<br /><br /> /* close the socket and exit this thread */<br /> close(mysocfd);<br /> thr_exit((void *)0);<br />}<br />Using Many Threads
This example that shows how easy it is to create many threads of execution in Solaris. Because of the lightweight nature of threads, it is possible to create literally thousands of threads. Most applications may not need a very large number of threads, but this example shows just how lightweight the threads can be.We have said before that anything you can do with threads, you can do without them. This may be a case where it would be very hard to do without threads. If you have some spare time (and lots of memory), try implementing this program by using processes, instead of threads. If you try this, you will see why threads can have an advantage over processes.
This program takes as an argument the number of threads to create. Notice that all the threads are created with a user-defined stack size, which limits the amount of memory that the threads will need for execution. The stack size for a given thread can be hard to calculate, so some testing usually needs to be done to see if the chosen stack size will work. You may want to change the stack size in this program and see how much you can lower it before things stop working. The Solaris threads library provides the thr_min_stack() call, which returns the minimum allowed stack size. Take care when adjusting the size of a threads stack. A stack overflow can happen quite easily to a thread with a small stack.
After each thread is created, it blocks, waiting on a mutex variable. This mutex variable was locked before any of the threads were created, which prevents the threads from proceeding in their execution. When all of the threads have been created and the user presses Return, the mutex variable is unlocked, allowing all the threads to proceed.
After the main thread has created all the threads, it waits for user input and then tries to join all the threads. Notice that the thr_join() call does not care what thread it joins; it is just counting the number of joins it makes.
This example is rather trivial and does not serve any real purpose except to show that it is possible to create a lot of threads in one process. However, there are situations when many threads are needed in an application. An example might be a network port server, where a thread is created each time an incoming or outgoing request is made.
The source to many_thr.c:
#define _REENTRANT<br />#include <stdio.h><br />#include <stdlib.h><br />#include <thread.h><br /><br />/* function prototypes and global varaibles */<br />void *thr_sub(void *);<br />mutex_t lock;<br /><br />main(int argc, char **argv)<br />{<br />int i, thr_count = 100;<br />char buf;<br /><br />/* check to see if user passed an argument<br /> -- if so, set the number of threads to the value<br /> passed to the program */<br /><br />if (argc == 2) thr_count = atoi(argv[1]);<br /><br />printf("Creating %d threads...\n", thr_count);<br /><br />/* lock the mutex variable -- this mutex is being used to <br /> keep all the other threads created from proceeding */<br /><br />mutex_lock(&lock);<br /><br />/* create all the threads -- Note that a specific stack size is<br /> given. Since the created threads will not use all of the<br /> default stack size, we can save memory by reducing the threads'<br /> stack size */<br /><br />for (i=0;i<thr_count;i++) {<br /> thr_create(NULL,2048,thr_sub,0,0,NULL);<br /> }<br /><br />printf("%d threads have been created and are running!\n", i);<br />printf("Press <return> to join all the threads...\n", i);<br /><br />/* wait till user presses return, then join all the threads */<br />gets(&buf);<br /><br />printf("Joining %d threads...\n", thr_count);<br /><br />/* now unlock the mutex variable, to let all the threads proceed */<br />mutex_unlock(&lock);<br /><br />/* join the threads */<br />for (i=0;i<thr_count;i++) <br /> thr_join(0,0,0);<br /><br />printf("All %d threads have been joined, exiting...\n", thr_count);<br />return(0);<br />}<br /><br />/* The routine that is executed by the created threads */<br /><br />void *thr_sub(void *arg)<br />{<br />/* try to lock the mutex variable -- since the main thread has<br /> locked the mutex before the threads were created, this thread<br /> will block until the main thread unlock the mutex */<br /><br />mutex_lock(&lock);<br /><br />printf("Thread %d is exiting...\n", thr_self());<br /><br />/* unlock the mutex to allow another thread to proceed */<br />mutex_unlock(&lock);<br /><br />/* exit the thread */<br />return((void *)0);<br />}<br />Real-time Thread Example
This example uses the Solaris real-time extensions to make a single bound thread within a process run in the real-time scheduling class. Using a thread in the real-time class is more desirable than running a whole process in the real-time class, because of the many problems that can arise with a process in a real-time state. For example, it would not be desirable for a process to perform any I/O or large memory operations while in realtime, because a real-time process has priority over system-related processes; if a real-time process requests a page fault, it can starve, waiting for the system to fault in a new page. We can limit this exposure by using threads to execute only the instructions that need to run in realtime.Since this book does not cover the concerns that arise with real-time programming, we have included this code only as an example of how to promote a thread into the real-time class. You must be very careful when you use real-time threads in your applications. For more information on real-time programming, see the Solaris documentation.
This example should be safe from the pitfalls of real-time programs because of its simplicity. However, changing this code in any way could have adverse affects on your system.
The example creates a new thread from the main thread. This new thread is then promoted to the real-time class by looking up the real-time class ID and then setting a real-time priority for the thread. After the thread is running in realtime, it simulates some processing. Since a thread in the real-time class can have an infinite time quantum, the process is allowed to stay on a CPU as long as it likes. The time quantum is the amount of time a thread is allowed to stay running on a CPU. For the timesharing class, the time quantum (time-slice) is 1/100th of a second by default.
In this example, we set the time quantum for the real-time thread to infinity. That is, it can stay running as long as it likes; it will not be preempted or scheduled off the CPU. If you run this example on a UP machine, it will have the effect of stopping your system for a few seconds while the thread simulates its processing. The system does not actually stop, it is just working in the real-time thread. When the real-time thread finishes its processing, it exits and the system returns to normal.
Using real-time threads can be quite useful when you need an extremely high priority and response time but can also cause big problems if it not used properly. Also note that this example must be run as root or have root execute permissions.
The source to rt_thr.c:
#define _REENTRANT<br />#include <stdio.h><br />#include <thread.h><br />#include <string.h><br />#include <sys/priocntl.h><br />#include <sys/rtpriocntl.h><br /><br />/* thread prototype */<br />void *rt_thread(void *);<br /><br />main()<br />{<br /><br />/* create the thread that will run in realtime */<br />thr_create(NULL, 0, rt_thread, 0, THR_DETACHED, 0);<br /><br />/* loop here forever, this thread is the TS scheduling class */<br />while (1) {<br /> printf("MAIN: In time share class... running\n"); <br /> sleep(1);<br /> }<br /><br />return(0);<br />}<br /><br />/*<br /> This is the routine that is called by the created thread<br />*/<br /><br />void *rt_thread(void *arg)<br />{<br />pcinfo_t pcinfo;<br />pcparms_t pcparms;<br />int i;<br /><br />/* let the main thread run for a bit */<br />sleep(4);<br /><br />/* get the class ID for the real-time class */<br />strcpy(pcinfo.pc_clname, "RT");<br /><br />if (priocntl(0, 0, PC_GETCID, (caddr_t)&pcinfo) == -1)<br /> fprintf(stderr, "getting RT class id\n"), exit(1);<br /><br />/* set up the real-time parameters */<br />pcparms.pc_cid = pcinfo.pc_cid;<br />((rtparms_t *)pcparms.pc_clparms)->rt_pri = 10;<br />((rtparms_t *)pcparms.pc_clparms)->rt_tqnsecs = 0;<br /><br />/* set an infinite time quantum */<br />((rtparms_t *)pcparms.pc_clparms)->rt_tqsecs = RT_TQINF; <br /><br />/* move this thread to the real-time scheduling class */<br />if (priocntl(P_LWPID, P_MYID, PC_SETPARMS, (caddr_t)&pcparms) == -1)<br /> fprintf(stderr, "Setting RT mode\n"), exit(1);<br /><br />/* simulate some processing */<br />for (i=0;i<100000000;i++);<br /><br />printf("RT_THREAD: NOW EXITING...\n");<br />thr_exit((void *)0);<br />}<br />POSIX Cancellation
This example uses the POSIX thread cancellation capability to kill a thread that is no longer needed. Random termination of a thread can cause problems in threaded applications, because a thread may be holding a critical lock when it is terminated. Since the lock was help before the thread was terminated, another thread may deadlock, waiting for that same lock. The thread cancellation capability enables you to control when a thread can be terminated. The example also demonstrates the capabilities of the POSIX thread library in implementing a program that performs a multithreaded search.This example simulates a multithreaded search for a given number by taking random guesses at a target number. The intent here is to simulate the same type of search that a database might execute. For example, a database might create threads to start searching for a data item; after some amount of time, one or more threads might return with the target data item.
If a thread guesses the number correctly, there is no need for the other threads to continue their search. This is where thread cancellation can help. The thread that finds the number first should cancel the other threads that are still searching for the item and then return the results of the search.
The threads involved in the search can call a cleanup function that can clean up the threads resources before it exits. In this case, the cleanup function prints the progress of the thread when it was cancelled.
The source to posix_cancel.c:
#define _REENTRANT<br />#include <stdio.h><br />#include <unistd.h><br />#include <stdlib.h><br />#include <sys/types.h><br />#include <pthread.h><br /><br />/* defines the number of searching threads */<br />#define NUM_THREADS 25<br /><br />/* function prototypes */<br />void *search(void *);<br />void print_it(void *);<br /><br />/* global variables */<br />pthread_t threads[NUM_THREADS];<br />pthread_mutex_t lock;<br />int tries;<br /><br />main()<br />{<br />int i;<br />int pid;<br /><br />/* create a number to search for */<br />pid = getpid();<br /><br />/* initialize the mutex lock */<br />pthread_mutex_init(&lock, NULL); <br />printf("Searching for the number = %d...\n", pid);<br /><br />/* create the searching threads */<br />for (i=0;i<NUM_THREADS;i++)<br /> pthread_create(&threads[i], NULL, search, (void *)pid);<br /><br />/* wait for (join) all the searching threads */<br />for (i=0;i<NUM_THREADS;i++) <br /> pthread_join(threads[i], NULL);<br /><br />printf("It took %d tries to find the number.\n", tries);<br /><br />/* exit this thread */<br />pthread_exit((void *)0);<br />}<br /><br />/*<br /> This is the cleanup function that is called when <br /> the threads are cancelled <br />*/<br /><br />void print_it(void *arg)<br />{<br />int *try = (int *) arg;<br />pthread_t tid;<br /><br />/* get the calling thread's ID */<br />tid = pthread_self();<br /><br />/* print where the thread was in its search when it was cancelled */<br />printf("Thread %d was canceled on its %d try.\n", tid, *try); <br />}<br /><br />/*<br /> This is the search routine that is executed in each thread <br />*/<br /><br />void *search(void *arg)<br />{<br />int num = (int) arg;<br />int i=0, j;<br />pthread_t tid;<br /><br />/* get the calling thread ID */<br />tid = pthread_self();<br /><br />/* use the thread ID to set the seed for the random number generator */<br />srand(tid);<br /><br />/* set the cancellation parameters --<br /> - Enable thread cancellation <br /> - Defer the action of the cancellation <br />*/<br /><br />pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL);<br />pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED, NULL);<br /><br />/* push the cleanup routine (print_it) onto the thread<br /> cleanup stack. This routine will be called when the <br /> thread is cancelled. Also note that the pthread_cleanup_push<br /> call must have a matching pthread_cleanup_pop call. The<br /> push and pop calls MUST be at the same lexical level <br /> within the code */<br /><br />/* pass address of `i' since the current value of `i' is not <br /> the one we want to use in the cleanup function */<br /><br />pthread_cleanup_push(print_it, (void *)&i);<br /><br />/* loop forever */<br />while (1) {<br /> i++;<br /><br /> /* does the random number match the target number? */<br /> if (num == rand()) {<br /><br /> /* try to lock the mutex lock --<br /> if locked, check to see if the thread has been cancelled<br /> if not locked then continue */<br /><br /> while (pthread_mutex_trylock(&lock) == EBUSY)<br /> pthread_testcancel();<br /><br /> /* set the global variable for the number of tries */<br /><br /> tries = i;<br /><br /> printf("thread %d found the number!\n", tid);<br /><br /> /* cancel all the other threads */<br /> for (j=0;j<NUM_THREADS;j++) <br /> if (threads[j] != tid) pthread_cancel(threads[j]);<br /><br /> /* break out of the while loop */<br /> break;<br /> }<br /><br /> /* every 100 tries check to see if the thread has been cancelled <br /> if the thread has not been cancelled then yield the thread's<br /> LWP to another thread that may be able to run */<br /><br /> if (i%100 == 0) {<br /> pthread_testcancel();<br /> sched_yield();<br /> }<br /> }<br /><br />/* The only way we can get here is when the thread breaks out<br /> of the while loop. In this case the thread that makes it here<br /> has found the number we are looking for and does not need to run<br /> the thread cleanup function. This is why the pthread_cleanup_pop<br /> function is called with a 0 argument; this will pop the cleanup<br /> function off the stack without executing it */<br /><br />pthread_cleanup_pop(0);<br />return((void *)0);<br />}<br />Software Race Condition
This example shows a trivial software race condition. A software race condition occurs when the execution of a program is affected by the order and timing of a threads execution. Most software race conditions can be alleviated by using synchronization variables to control the threads' timing and access of shared resources. If a program depends on order of execution, then threading that program may not be a good solution, because the order in which threads execute is nondeterministic.In the example, thr_continue() and thr_suspend() calls continue and suspend a given thread, respectively. Although both of these calls are valid, use caution when implementing them. It is very hard to determine where a thread is in its execution. Because of this, you may not be able to tell where the thread will suspend when the call to thr_suspend() is made. This behavior can cause problems in threaded code if not used properly.
The following example uses thr_continue() and thr_suspend() to try to control when a thread starts and stops. The example looks trivial, but, as you will see, can cause a big problem.
Do you see the problem? If you guessed that the program would eventually suspend itself, you were correct! The example attempts to flip-flop between the main thread and a subroutine thread. Each thread continues the other thread and then suspends itself.
Thread A continues thread B and then suspends thread A; now the continued thread B can continue thread A and then suspend itself. This should continue back and forth all day long, right? Wrong! We can't guarantee that each thread will continue the other thread and then suspend itself in one atomic action, so a software race condition could be created. Calling thr_continue() on a running thread and calling thr_suspend() on a suspended thread has no effect, so we don't know if a thread is already running or suspended.
If thread A continues thread B and if between the time thread A suspends itself, thread B continues thread A, then both of the threads will call thr_suspend(). This is the race condition in this program that will cause the whole process to become suspended.
It is very hard to use these calls, because you never really know the state of a thread. If you don't know exactly where a thread is in its execution, then you don't know what locks it holds and where it will stop when you suspend it.
The source to sw_race.c
Tgrep: Threadeds version of UNIX grep
Tgrep is a multi-threaded version of grep. Tgrep supports all but the -w (word search) options of the normal grep command, and a few options that are only avaliable to Tgrep. The real change from grep, is that Tgrep will recurse down through sub-directories and search all files for the target string. Tgrep searches files like the following command:find <start path> -name "<file/directory pattern>" -exec \ (Line wrapped)<br /> grep <options> <target> /dev/null {} \;<br />An example of this would be (run from this Tgrep directory) % find . -exec grep thr_create /dev/null {} \;<br />./Solaris/main.c: if (thr_create(NULL,0,SigThread,NULL,THR_DAEMON,NULL)) {<br />./Solaris/main.c: err = thr_create(NULL,0,cascade,(void *)work,<br />./Solaris/main.c: err = thr_create(NULL,0,search_thr,(void *)work,<br />%<br />Running the same command with timex: <br />real 4.26<br />user 0.64<br />sys 2.81<br />The same search run with Tgrep would be % {\tt Tgrep} thr_create<br />./Solaris/main.c: if (thr_create(NULL,0,SigThread,NULL,THR_DAEMON,NULL)) {<br />./Solaris/main.c: err = thr_create(NULL,0,cascade,(void *)work,<br />./Solaris/main.c: err = thr_create(NULL,0,search_thr,(void *)work,<br />%<br />Running the same command with timex:<br />real 0.79<br />user 0.62<br />sys 1.50<br />Tgrep gets the results almost four times faster. The numbers above where gathered on a SS20 running 5.5 (build 18) with 4 50MHz CPUs. You can also filter the files that you want Tgrep to search like you can with find. The next two commands do the same thing, just Tgrep gets it done faster.
find . -name "*.c" -exec grep thr_create /dev/null {} \;<br />and<br />{\tt Tgrep} -p '.*\.cDave Marshall
1/5/1999 thr_create
The -p option will allow Tgrep to search only files that match the "regular expression" file pattern string. This option does NOT use shell expression, so to stop Tgrep from seeing a file named foobar.cyou must add the "$" meta character to the pattern and escape the real ``.'' character.
Some of the other Tgrep only options are -r, -C, -P, -e, -B, -S and -Z. The -r option stops Tgrep from searching any sub-directories, in other words, search only the local directory, but -l was taken. The -C option will search for and print "continued" lines like you find in Makefile. Note the differences in the results of grep and Tgrep run in the current directory.
The Tgrep output prints the continued lines that ended with the "character. In the case of grep I would not have seen the three values assigned to SUBDIRS, but Tgrep shows them to me (Common, Solaris, Posix).
The -P option I use when I am sending the output of a long search to a file and want to see the "progress" of the search. The -P option will print a "." (dot) on stderr for every file (or groups of files depending on the value of the -P argument) Tgrep searches.
The -e option will change the way Tgrep uses the target string. Tgrep uses two different patter matching systems. The first (with out the -e option) is a literal string match call Boyer-Moore. If the -e option is used, then a MT-Safe PD version of regular expression is used to search for the target string as a regexp with meta characters in it. The regular expression method is slower, but Tgrep needed the functionality. The -Z option will print help on the meta characters Tgrep uses.
The -B option tells Tgrep to use the value of the environment variable called TGLIMIT to limit the number of threads it will use during a search. This option has no affect if TGLIMIT is not set. Tgrep can "eat" a system alive, so the -B option was a way to run Tgrep on a system with out having other users scream at you.
The last new option is -S. If you want to see how things went while Tgrep was searching, you can use this option to print statistic about the number of files, lines, bytes, matches, threads created, etc.
Here is an example of the -S options output. (again run in the current directory)
% {\tt Tgrep} -S zimzap<br /><br />----------------- {\tt Tgrep} Stats. --------------------<br />Number of directories searched: 7<br />Number of files searched: 37<br />Number of lines searched: 9504<br />Number of matching lines to target: 0<br />Number of cascade threads created: 7<br />Number of search threads created: 20<br />Number of search threads from pool: 17<br />Search thread pool hit rate: 45.95%<br />Search pool overall size: 20<br />Search pool size limit: 58<br />Number of search threads destroyed: 0<br />Max # of threads running concurrenly: 20<br />Total run time, in seconds. 1<br />Work stopped due to no FD's: (058) 0 Times, 0.00%<br />Work stopped due to no work on Q: 19 Times, 43.18%<br />Work stopped due to TGLIMITS: (Unlimited) 0 Times, 0.00%<br />----------------------------------------------------<br />%<br />For more information on the usage and options, see the man page Tgrep The Tgrep.c source code is:
/* Copyright (c) 1993, 1994 Ron Winacott */<br />/* This program may be used, copied, modified, and redistributed freely */<br />/* for ANY purpose, so long as this notice remains intact. */<br /><br />#define _REENTRANT<br /><br />#include <stdio.h><br />#include <string.h><br />#include <stdlib.h> <br />#include <unistd.h><br />#include <assert.h><br />#include <errno.h><br />#include <signal.h><br />#include <ctype.h> <br />#include <sys/types.h><br />#include <time.h><br />#include <sys/stat.h><br />#ifdef __sparc<br />#include <note.h> /* warlock/locklint */<br />#else<br />#define NOTE(s) <br />#endif<br />#include <dirent.h><br />#include <fcntl.h><br />#include <sys/uio.h><br />#include <thread.h> <br />#include <synch.h><br /><br />#include "version.h"<br />#include "pmatch.h"<br />#include "debug.h" <br /><br />#define PATH_MAX 1024 /* max # of characters in a path name */<br />#define HOLD_FDS 6 /* stdin,out,err and a buffer */<br />#define UNLIMITED 99999 /* The default tglimit */<br />#define MAXREGEXP 10 /* max number of -e options */<br /><br />#define FB_BLOCK 0x00001<br />#define FC_COUNT 0x00002<br />#define FH_HOLDNAME 0x00004<br />#define FI_IGNCASE 0x00008<br />#define FL_NAMEONLY 0x00010<br />#define FN_NUMBER 0x00020<br />#define FS_NOERROR 0x00040<br />#define FV_REVERSE 0x00080<br />#define FW_WORD 0x00100<br />#define FR_RECUR 0x00200<br />#define FU_UNSORT 0x00400<br />#define FX_STDIN 0x00800<br />#define TG_BATCH 0x01000<br />#define TG_FILEPAT 0x02000<br />#define FE_REGEXP 0x04000<br />#define FS_STATS 0x08000<br />#define FC_LINE 0x10000<br />#define TG_PROGRESS 0x20000<br /><br />#define FILET 1<br />#define DIRT 2<br />#define ALPHASIZ 128<br /><br />/*<br /> * New data types <br /> */<br /><br />typedef struct work_st {<br /> char *path;<br /> int tp;<br /> struct work_st *next;<br />} work_t;<br /><br />typedef struct out_st {<br /> char *line;<br /> int line_count;<br /> long byte_count;<br /> struct out_st *next;<br />} out_t;<br /><br />typedef struct bm_pattern { /* Boyer - Moore pattern */<br /> short p_m; /* length of pattern string */<br /> short p_r[ALPHASIZ]; /* "r" vector */<br /> short *p_R; /* "R" vector */<br /> char *p_pat; /* pattern string */<br />} BM_PATTERN;<br /><br /><br />/*<br /> * Prototypes<br /> */<br /><br />/* bmpmatch.c */<br />extern BM_PATTERN *bm_makepat(char *);<br />extern char *bm_pmatch(BM_PATTERN *, register char *);<br />extern void bm_freepat(BM_PATTERN *);<br />/* pmatch.c */<br />extern char *pmatch(register PATTERN *, register char *, int *);<br />extern PATTERN *makepat(char *string, char *);<br />extern void freepat(register PATTERN *);<br />extern void printpat(PATTERN *);<br /><br />#include "proto.h" /* function prototypes of main.c */<br /><br />void *SigThread(void *arg);<br />void sig_print_stats(void);<br /><br />/*<br /> * Global data<br /> */<br /><br />BM_PATTERN *bm_pat; /* the global target read only after main */<br />NOTE(READ_ONLY_DATA(bm_pat))<br /><br />PATTERN *pm_pat[MAXREGEXP]; /* global targets read only for pmatch */<br />NOTE(READ_ONLY_DATA(pm_pat))<br /><br />mutex_t global_count_lk; <br />int global_count = 0;<br />NOTE(MUTEX_PROTECTS_DATA(global_count_lk, global_count))<br />NOTE(DATA_READABLE_WITHOUT_LOCK(global_count)) /* see prnt_stats() */<br /><br />work_t *work_q = NULL;<br />cond_t work_q_cv;<br />mutex_t work_q_lk;<br />int all_done = 0;<br />int work_cnt = 0;<br />int current_open_files = 0;<br />int tglimit = UNLIMITED; /* if -B limit the number of threads */<br />NOTE(MUTEX_PROTECTS_DATA(work_q_lk, work_q all_done work_cnt \<br /> current_open_files tglimit))<br /><br />work_t *search_q = NULL;<br />mutex_t search_q_lk;<br />cond_t search_q_cv;<br />int search_pool_cnt = 0; /* the count in the pool now */<br />int search_thr_limit = 0; /* the max in the pool */<br />NOTE(MUTEX_PROTECTS_DATA(search_q_lk, search_q search_pool_cnt))<br />NOTE(DATA_READABLE_WITHOUT_LOCK(search_pool_cnt)) /* see prnt_stats() */<br />NOTE(READ_ONLY_DATA(search_thr_limit))<br /><br />work_t *cascade_q = NULL;<br />mutex_t cascade_q_lk;<br />cond_t cascade_q_cv;<br />int cascade_pool_cnt = 0;<br />int cascade_thr_limit = 0;<br />NOTE(MUTEX_PROTECTS_DATA(cascade_q_lk, cascade_q cascade_pool_cnt))<br />NOTE(DATA_READABLE_WITHOUT_LOCK(cascade_pool_cnt)) /* see prnt_stats() */<br />NOTE(READ_ONLY_DATA(cascade_thr_limit))<br /><br />int running = 0;<br />mutex_t running_lk;<br />NOTE(MUTEX_PROTECTS_DATA(running_lk, running))<br /><br />sigset_t set, oldset;<br />NOTE(READ_ONLY_DATA(set oldset))<br /><br />mutex_t stat_lk;<br />time_t st_start = 0;<br />int st_dir_search = 0;<br />int st_file_search = 0;<br />int st_line_search = 0;<br />int st_cascade = 0;<br />int st_cascade_pool = 0;<br />int st_cascade_destroy = 0;<br />int st_search = 0;<br />int st_pool = 0;<br />int st_maxrun = 0;<br />int st_worknull = 0;<br />int st_workfds = 0;<br />int st_worklimit = 0;<br />int st_destroy = 0;<br />NOTE(MUTEX_PROTECTS_DATA(stat_lk, st_start st_dir_search st_file_search \<br /> st_line_search st_cascade st_cascade_pool \<br /> st_cascade_destroy st_search st_pool st_maxrun \<br /> st_worknull st_workfds st_worklimit st_destroy))<br /><br />int progress_offset = 1;<br />NOTE(READ_ONLY_DATA(progress_offset))<br /><br />mutex_t output_print_lk;<br />/* output_print_lk used to print multi-line output only */<br />int progress = 0;<br />NOTE(MUTEX_PROTECTS_DATA(output_print_lk, progress))<br /><br />unsigned int flags = 0;<br />int regexp_cnt = 0;<br />char *string[MAXREGEXP];<br />int debug = 0;<br />int use_pmatch = 0;<br />char file_pat[255]; /* file patten match */<br />PATTERN *pm_file_pat; /* compiled file target string (pmatch()) */<br />NOTE(READ_ONLY_DATA(flags regexp_cnt string debug use_pmatch \<br /> file_pat pm_file_pat))<br /><br /><br />/*<br /> * Locking ording.<br /> */<br />NOTE(LOCK_ORDER(output_print_lk stat_lk))<br /><br />/*<br /> * Main: This is where the fun starts<br /> */<br /><br />int<br />main(int argc, char **argv)<br />{<br /> int c,out_thr_flags;<br /> long max_open_files = 0l, ncpus = 0l;<br /> extern int optind;<br /> extern char *optarg;<br /> NOTE(READ_ONLY_DATA(optind optarg))<br /> int prio = 0;<br /> struct stat sbuf;<br /> thread_t tid,dtid;<br /> void *status;<br /> char *e = NULL, *d = NULL; /* for debug flags */<br /> int debug_file = 0;<br /> int err = 0, i = 0, pm_file_len = 0;<br /> work_t *work;<br /> int restart_cnt = 10;<br /><br /> flags = FR_RECUR; /* the default */<br /><br /> thr_setprio(thr_self(),127); /* set me up HIGH */<br /> while ((c = getopt(argc, argv, "d:e:bchilnsvwruf:p:BCSZzHP:")) != EOF) {<br /> switch (c) {<br />#ifdef DEBUG <br /> case 'd':<br /> debug = atoi(optarg);<br /> if (debug == 0)<br /> debug_usage();<br /><br /> d = optarg;<br /> fprintf(stderr,"tgrep: Debug on at level(s) ");<br /> while (*d) {<br /> for (i=0; i<9; i++)<br /> if (debug_set[i].level == *d) {<br /> debug_levels |= debug_set[i].flag;<br /> fprintf(stderr,"%c ",debug_set[i].level);<br /> break;<br /> }<br /> d++;<br /> }<br /> fprintf(stderr,"\n");<br /> break;<br /> case 'f': <br /> debug_file = atoi(optarg); <br /> break;<br />#endif /* DEBUG */<br /> case 'B':<br /> flags |= TG_BATCH;<br /> if ((e = getenv("TGLIMIT"))) {<br /> tglimit = atoi(e);<br /> }<br /> else {<br /> if (!(flags & FS_NOERROR)) /* order dependent! */<br /> fprintf(stderr,"env TGLIMIT not set, overriding -B\n");<br /> flags &= ~TG_BATCH;<br /> }<br /> break;<br /> case 'p':<br /> flags |= TG_FILEPAT;<br /> strcpy(file_pat,optarg);<br /> pm_file_pat = makepat(file_pat,NULL); <br /> break;<br /> case 'P':<br /> flags |= TG_PROGRESS;<br /> progress_offset = atoi(optarg);<br /> break;<br /> case 'S': flags |= FS_STATS; break;<br /> case 'b': flags |= FB_BLOCK; break;<br /> case 'c': flags |= FC_COUNT; break;<br /> case 'h': flags |= FH_HOLDNAME; break;<br /> case 'i': flags |= FI_IGNCASE; break;<br /> case 'l': flags |= FL_NAMEONLY; break;<br /> case 'n': flags |= FN_NUMBER; break;<br /> case 's': flags |= FS_NOERROR; break;<br /> case 'v': flags |= FV_REVERSE; break;<br /> case 'w': flags |= FW_WORD; break;<br /> case 'r': flags &= ~FR_RECUR; break;<br /> case 'C': flags |= FC_LINE; break;<br /> case 'e':<br /> if (regexp_cnt == MAXREGEXP) {<br /> fprintf(stderr,"Max number of regexp's (%d) exceeded!\n",<br /> MAXREGEXP);<br /> exit(1);<br /> }<br /> flags |= FE_REGEXP;<br /> if ((string[regexp_cnt] =(char *)malloc(strlen(optarg)+1))==NULL){<br /> fprintf(stderr,"tgrep: No space for search string(s)\n");<br /> exit(1);<br /> }<br /> memset(string[regexp_cnt],0,strlen(optarg)+1);<br /> strcpy(string[regexp_cnt],optarg); <br /> regexp_cnt++;<br /> break;<br /> case 'z':<br /> case 'Z': regexp_usage();<br /> break;<br /> case 'H':<br /> case '?':<br /> default : usage();<br /> }<br /> }<br /><br /> if (!(flags & FE_REGEXP)) {<br /> if (argc - optind < 1) {<br /> fprintf(stderr,"tgrep: Must supply a search string(s) "<br /> "and file list or directory\n");<br /> usage();<br /> }<br /> if ((string[0]=(char *)malloc(strlen(argv[optind])+1))==NULL){<br /> fprintf(stderr,"tgrep: No space for search string(s)\n");<br /> exit(1);<br /> }<br /> memset(string[0],0,strlen(argv[optind])+1);<br /> strcpy(string[0],argv[optind]);<br /> regexp_cnt=1;<br /> optind++;<br /> }<br /><br /> if (flags & FI_IGNCASE)<br /> for (i=0; i<regexp_cnt; i++)<br /> uncase(string[i]);<br /><br />#ifdef __lock_lint<br /> /* <br /> ** This is NOT somthing you really want to do. This<br /> ** function calls are here ONLY for warlock/locklint !!!<br /> */<br /> pm_pat[i] = makepat(string[i],NULL);<br /> bm_pat = bm_makepat(string[0]);<br /> bm_freepat(bm_pat); /* stop it from becomming a root */<br />#else<br /> if (flags & FE_REGEXP) {<br /> for (i=0; i<regexp_cnt; i++)<br /> pm_pat[i] = makepat(string[i],NULL);<br /> use_pmatch = 1;<br /> }<br /> else {<br /> bm_pat = bm_makepat(string[0]); /* only one allowed */<br /> }<br />#endif<br /> <br /> flags |= FX_STDIN;<br /><br /> max_open_files = sysconf(_SC_OPEN_MAX);<br /> ncpus = sysconf(_SC_NPROCESSORS_ONLN);<br /> if ((max_open_files - HOLD_FDS - debug_file) < 1) {<br /> fprintf(stderr,"tgrep: You MUST have at lest ONE fd "<br /> "that can be used, check limit (>10)\n");<br /> exit(1);<br /> }<br /> search_thr_limit = max_open_files - HOLD_FDS - debug_file;<br /> cascade_thr_limit = search_thr_limit / 2;<br /> /* the number of files that can by open */<br /> current_open_files = search_thr_limit; <br /><br /> mutex_init(&stat_lk,USYNC_THREAD,"stat");<br /> mutex_init(&global_count_lk,USYNC_THREAD,"global_cnt");<br /> mutex_init(&output_print_lk,USYNC_THREAD,"output_print");<br /> mutex_init(&work_q_lk,USYNC_THREAD,"work_q");<br /> mutex_init(&running_lk,USYNC_THREAD,"running");<br /> cond_init(&work_q_cv,USYNC_THREAD,"work_q");<br /> mutex_init(&search_q_lk,USYNC_THREAD,"search_q");<br /> cond_init(&search_q_cv,USYNC_THREAD,"search_q");<br /> mutex_init(&cascade_q_lk,USYNC_THREAD,"cascade_q");<br /> cond_init(&cascade_q_cv,USYNC_THREAD,"cascade_q");<br /><br /> if ((argc == optind) && ((flags & TG_FILEPAT) || (flags & FR_RECUR))) {<br /> add_work(".",DIRT);<br /> flags = (flags & ~FX_STDIN);<br /> }<br /> for ( ; optind < argc; optind++) {<br /> restart_cnt = 10;<br /> flags = (flags & ~FX_STDIN);<br /> STAT_AGAIN:<br /> if (stat(argv[optind], &sbuf)) {<br /> if (errno == EINTR) { /* try again !, restart */<br /> if (--restart_cnt)<br /> goto STAT_AGAIN;<br /> }<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Can't stat file/dir %s, %s\n", <br /> argv[optind], strerror(errno)); <br /> continue;<br /> }<br /> switch (sbuf.st_mode & S_IFMT) {<br /> case S_IFREG :<br /> if (flags & TG_FILEPAT) {<br /> if (pmatch(pm_file_pat, argv[optind], &pm_file_len))<br /> add_work(argv[optind],FILET);<br /> }<br /> else {<br /> add_work(argv[optind],FILET);<br /> }<br /> break;<br /> case S_IFDIR :<br /> if (flags & FR_RECUR) {<br /> add_work(argv[optind],DIRT);<br /> }<br /> else {<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Can't search directory %s, "<br /> "-r option is on. Directory ignored.\n",<br /> argv[optind]);<br /> }<br /> break;<br /> }<br /> } <br /><br /> NOTE(COMPETING_THREADS_NOW) /* we are goinf threaded */<br /><br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_start = time(NULL);<br /> mutex_unlock(&stat_lk);<br />#ifdef SIGNAL_HAND<br /> /* <br /> ** setup the signal thread so the first call to SIGINT will <br /> ** only print stats, the second will interupt.<br /> */<br /> sigfillset(&set);<br /> thr_sigsetmask(SIG_SETMASK, &set, &oldset);<br /> if (thr_create(NULL,0,SigThread,NULL,THR_DAEMON,NULL)) {<br /> thr_sigsetmask(SIG_SETMASK,&oldset,NULL);<br /> fprintf(stderr,"SIGINT for stats NOT setup\n");<br /> }<br /> thr_yield(); /* give the other thread time */<br />#endif /* SIGNAL_HAND */<br /> }<br /><br /> thr_setconcurrency(3);<br /><br /> if (flags & FX_STDIN) {<br /> fprintf(stderr,"tgrep: stdin option is not coded at this time\n");<br /> exit(0); /* XXX Need to fix this SOON */<br /> search_thr(NULL); /* NULL is not understood in search_thr() */<br /> if (flags & FC_COUNT) {<br /> mutex_lock(&global_count_lk);<br /> printf("%d\n",global_count);<br /> mutex_unlock(&global_count_lk);<br /> }<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> prnt_stats();<br /> mutex_unlock(&stat_lk);<br /> }<br /> exit(0);<br /> }<br /><br /> mutex_lock(&work_q_lk);<br /> if (!work_q) {<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: No files to search.\n");<br /> exit(0);<br /> }<br /> mutex_unlock(&work_q_lk);<br /><br /> DP(DLEVEL1,("Starting to loop through the work_q for work\n"));<br /> <br /> /* OTHER THREADS ARE RUNNING */<br /> while (1) {<br /> mutex_lock(&work_q_lk);<br /> while ((work_q == NULL || current_open_files == 0 || tglimit <= 0) && <br /> all_done == 0) {<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> if (work_q == NULL)<br /> st_worknull++;<br /> if (current_open_files == 0)<br /> st_workfds++;<br /> if (tglimit <= 0)<br /> st_worklimit++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> cond_wait(&work_q_cv,&work_q_lk);<br /> }<br /> if (all_done != 0) {<br /> mutex_unlock(&work_q_lk);<br /> DP(DLEVEL1,("All_done was set to TRUE\n"));<br /> goto OUT;<br /> }<br /> work = work_q;<br /> work_q = work->next; /* maybe NULL */<br /> work->next = NULL;<br /> current_open_files--;<br /> mutex_unlock(&work_q_lk);<br /><br /> tid = 0;<br /> switch (work->tp) {<br /> case DIRT:<br /> mutex_lock(&cascade_q_lk);<br /> if (cascade_pool_cnt) {<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_cascade_pool++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> work->next = cascade_q;<br /> cascade_q = work;<br /> cond_signal(&cascade_q_cv);<br /> mutex_unlock(&cascade_q_lk);<br /> DP(DLEVEL2,("Sent work to cascade pool thread\n"));<br /> }<br /> else {<br /> mutex_unlock(&cascade_q_lk);<br /> err = thr_create(NULL,0,cascade,(void *)work,<br /> THR_DETACHED|THR_DAEMON|THR_NEW_LWP<br /> ,&tid);<br /> DP(DLEVEL2,("Sent work to new cascade thread\n"));<br /> thr_setprio(tid,64); /* set cascade to middle */<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_cascade++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> }<br /> break;<br /> case FILET:<br /> mutex_lock(&search_q_lk);<br /> if (search_pool_cnt) {<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_pool++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> work->next = search_q; /* could be null */<br /> search_q = work;<br /> cond_signal(&search_q_cv);<br /> mutex_unlock(&search_q_lk);<br /> DP(DLEVEL2,("Sent work to search pool thread\n"));<br /> }<br /> else {<br /> mutex_unlock(&search_q_lk);<br /> err = thr_create(NULL,0,search_thr,(void *)work,<br /> THR_DETACHED|THR_DAEMON|THR_NEW_LWP<br /> ,&tid);<br /> thr_setprio(tid,0); /* set search to low */<br /> DP(DLEVEL2,("Sent work to new search thread\n"));<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_search++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> }<br /> break;<br /> default:<br /> fprintf(stderr,"tgrep: Internal error, work_t->tp no valid\n");<br /> exit(1);<br /> }<br /> if (err) { /* NEED TO FIX THIS CODE. Exiting is just wrong */<br /> fprintf(stderr,"Cound not create new thread!\n");<br /> exit(1);<br /> }<br /> }<br /><br /> OUT:<br /> if (flags & TG_PROGRESS) {<br /> if (progress)<br /> fprintf(stderr,".\n");<br /> else<br /> fprintf(stderr,"\n");<br /> }<br /> /* we are done, print the stuff. All other threads ar parked */<br /> if (flags & FC_COUNT) {<br /> mutex_lock(&global_count_lk);<br /> printf("%d\n",global_count);<br /> mutex_unlock(&global_count_lk);<br /> }<br /> if (flags & FS_STATS)<br /> prnt_stats();<br /> return(0); /* should have a return from main */<br />}<br /><br /><br />/*<br /> * Add_Work: Called from the main thread, and cascade threads to add file <br /> * and directory names to the work Q.<br /> */<br />int<br />add_work(char *path,int tp)<br />{<br /> work_t *wt,*ww,*wp;<br /><br /> if ((wt = (work_t *)malloc(sizeof(work_t))) == NULL)<br /> goto ERROR; <br /> if ((wt->path = (char *)malloc(strlen(path)+1)) == NULL)<br /> goto ERROR;<br /> <br /> strcpy(wt->path,path);<br /> wt->tp = tp;<br /> wt->next = NULL;<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> if (wt->tp == DIRT)<br /> st_dir_search++;<br /> else<br /> st_file_search++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> mutex_lock(&work_q_lk);<br /> work_cnt++;<br /> wt->next = work_q;<br /> work_q = wt;<br /> cond_signal(&work_q_cv);<br /> mutex_unlock(&work_q_lk);<br /> return(0);<br /> ERROR:<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Could not add %s to work queue. Ignored\n",<br /> path);<br /> return(-1);<br />}<br /><br />/*<br /> * Search thread: Started by the main thread when a file name is found<br /> * on the work Q to be serached. If all the needed resources are ready<br /> * a new search thread will be created.<br /> */<br />void *<br />search_thr(void *arg) /* work_t *arg */<br />{ <br /> FILE *fin;<br /> char fin_buf[(BUFSIZ*4)]; /* 4 Kbytes */<br /> work_t *wt,std;<br /> int line_count;<br /> char rline[128];<br /> char cline[128];<br /> char *line;<br /> register char *p,*pp;<br /> int pm_len;<br /> int len = 0;<br /> long byte_count;<br /> long next_line;<br /> int show_line; /* for the -v option */<br /> register int slen,plen,i;<br /> out_t *out = NULL; /* this threads output list */<br /><br /> thr_setprio(thr_self(),0); /* set search to low */<br /> thr_yield();<br /> wt = (work_t *)arg; /* first pass, wt is passed to use. */<br /><br /> /* len = strlen(string);*/ /* only set on first pass */<br /> <br /> while (1) { /* reuse the search threads */<br /> /* init all back to zero */<br /> line_count = 0;<br /> byte_count = 0l;<br /> next_line = 0l;<br /> show_line = 0;<br /><br /> mutex_lock(&running_lk);<br /> running++;<br /> mutex_unlock(&running_lk);<br /> mutex_lock(&work_q_lk);<br /> tglimit--;<br /> mutex_unlock(&work_q_lk);<br /> DP(DLEVEL5,("searching file (STDIO) %s\n",wt->path));<br /><br /> if ((fin = fopen(wt->path,"r")) == NULL) {<br /> if (!(flags & FS_NOERROR)) {<br /> fprintf(stderr,"tgrep: %s. File \"%s\" not searched.\n",<br /> strerror(errno),wt->path);<br /> }<br /> goto ERROR;<br /> }<br /> setvbuf(fin,fin_buf,_IOFBF,(BUFSIZ*4)); /* XXX */<br /> DP(DLEVEL5,("Search thread has opened file %s\n",wt->path));<br /> while ((fgets(rline,127,fin)) != NULL) {<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_line_search++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> slen = strlen(rline);<br /> next_line += slen; <br /> line_count++;<br /> if (rline[slen-1] == '\n')<br /> rline[slen-1] = '\0';<br /> /*<br /> ** If the uncase flag is set, copy the read in line (rline)<br /> ** To the uncase line (cline) Set the line pointer to point at<br /> ** cline.<br /> ** If the case flag is NOT set, then point line at rline.<br /> ** line is what is compared, rline is waht is printed on a <br /> ** match.<br /> */<br /> if (flags & FI_IGNCASE) {<br /> strcpy(cline,rline);<br /> uncase(cline);<br /> line = cline;<br /> }<br /> else {<br /> line = rline;<br /> }<br /> show_line = 1; /* assume no match, if -v set */<br /> /* The old code removed */<br /> if (use_pmatch) {<br /> for (i=0; i<regexp_cnt; i++) {<br /> if (pmatch(pm_pat[i], line, &pm_len)) {<br /> if (!(flags & FV_REVERSE)) {<br /> add_output_local(&out,wt,line_count,<br /> byte_count,rline);<br /> continue_line(rline,fin,out,wt,<br /> &line_count,&byte_count);<br /> }<br /> else {<br /> show_line = 0; <br /> } /* end of if -v flag if / else block */<br /> /* <br /> ** if we get here on ANY of the regexp targets<br /> ** jump out of the loop, we found a single<br /> ** match so, do not keep looking!<br /> ** If name only, do not keep searcthing the same <br /> ** file, we found a single match, so close the file, <br /> ** print the file name and move on to the next file.<br /> */<br /> if (flags & FL_NAMEONLY) <br /> goto OUT_OF_LOOP;<br /> else<br /> goto OUT_AND_DONE;<br /> } /* end found a match if block */<br /> } /* end of the for pat[s] loop */<br /> }<br /> else {<br /> if (bm_pmatch( bm_pat, line)) {<br /> if (!(flags & FV_REVERSE)) {<br /> add_output_local(&out,wt,line_count,byte_count,rline);<br /> continue_line(rline,fin,out,wt,<br /> &line_count,&byte_count);<br /> }<br /> else {<br /> show_line = 0; <br /> }<br /> if (flags & FL_NAMEONLY) <br /> goto OUT_OF_LOOP;<br /> }<br /> }<br /> OUT_AND_DONE:<br /> if ((flags & FV_REVERSE) && show_line) { <br /> add_output_local(&out,wt,line_count,byte_count,rline);<br /> show_line = 0;<br /> }<br /> byte_count = next_line;<br /> }<br /> OUT_OF_LOOP:<br /> fclose(fin);<br /> /*<br /> ** The search part is done, but before we give back the FD,<br /> ** and park this thread in the search thread pool, print the<br /> ** local output we have gathered.<br /> */<br /> print_local_output(out,wt); /* this also frees out nodes */<br /> out = NULL; /* for the next time around, if there is one */<br /> ERROR:<br /> DP(DLEVEL5,("Search done for %s\n",wt->path));<br /> free(wt->path);<br /> free(wt);<br /><br /> notrun();<br /> mutex_lock(&search_q_lk);<br /> if (search_pool_cnt > search_thr_limit) {<br /> mutex_unlock(&search_q_lk);<br /> DP(DLEVEL5,("Search thread exiting\n"));<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_destroy++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> return(0);<br /> }<br /> else {<br /> search_pool_cnt++;<br /> while (!search_q)<br /> cond_wait(&search_q_cv,&search_q_lk);<br /> search_pool_cnt--;<br /> wt = search_q; /* we have work to do! */<br /> if (search_q->next)<br /> search_q = search_q->next;<br /> else<br /> search_q = NULL;<br /> mutex_unlock(&search_q_lk);<br /> }<br /> }<br /> /*NOTREACHED*/<br />}<br /><br />/*<br /> * Continue line: Speacial case search with the -C flag set. If you are <br /> * searching files like Makefiles, some lines may have escape char's to<br /> * contine the line on the next line. So the target string can be found, but <br /> * no data is displayed. This function continues to print the escaped line<br /> * until there are no more "\" chars found.<br /> */<br />int<br />continue_line(char *rline, FILE *fin, out_t *out, work_t *wt, <br /> int *lc, long *bc)<br />{<br /> int len;<br /> int cnt = 0;<br /> char *line;<br /> char nline[128];<br /><br /> if (!(flags & FC_LINE))<br /> return(0);<br /><br /> line = rline;<br /> AGAIN:<br /> len = strlen(line);<br /> if (line[len-1] == '\\') {<br /> if ((fgets(nline,127,fin)) == NULL) {<br /> return(cnt);<br /> }<br /> line = nline;<br /> len = strlen(line);<br /> if (line[len-1] == '\n')<br /> line[len-1] = '\0';<br /> *bc = *bc + len;<br /> *lc++;<br /> add_output_local(&out,wt,*lc,*bc,line);<br /> cnt++;<br /> goto AGAIN;<br /> }<br /> return(cnt);<br />}<br /><br />/*<br /> * cascade: This thread is started by the main thread when directory names<br /> * are found on the work Q. The thread reads all the new file, and directory<br /> * names from the directory it was started when and adds the names to the <br /> * work Q. (it finds more work!)<br /> */<br />void *<br />cascade(void *arg) /* work_t *arg */<br />{<br /> char fullpath[1025];<br /> int restart_cnt = 10;<br /> DIR *dp;<br /><br /> char dir_buf[sizeof(struct dirent) + PATH_MAX];<br /> struct dirent *dent = (struct dirent *)dir_buf;<br /> struct stat sbuf;<br /> char *fpath;<br /> work_t *wt;<br /> int fl = 0, dl = 0;<br /> int pm_file_len = 0;<br /><br /> thr_setprio(thr_self(),64); /* set search to middle */<br /> thr_yield(); /* try toi give control back to main thread */<br /> wt = (work_t *)arg;<br /><br /> while(1) {<br /> fl = 0;<br /> dl = 0;<br /> restart_cnt = 10;<br /> pm_file_len = 0;<br /><br /> mutex_lock(&running_lk);<br /> running++;<br /> mutex_unlock(&running_lk);<br /> mutex_lock(&work_q_lk);<br /> tglimit--;<br /> mutex_unlock(&work_q_lk);<br /><br /> if (!wt) {<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Bad work node passed to cascade\n");<br /> goto DONE;<br /> }<br /> fpath = (char *)wt->path;<br /> if (!fpath) {<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Bad path name passed to cascade\n");<br /> goto DONE;<br /> }<br /> DP(DLEVEL3,("Cascading on %s\n",fpath));<br /> if (( dp = opendir(fpath)) == NULL) {<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Can't open dir %s, %s. Ignored.\n",<br /> fpath,strerror(errno));<br /> goto DONE;<br /> }<br /> while ((readdir_r(dp,dent)) != NULL) {<br /> restart_cnt = 10; /* only try to restart the interupted 10 X */<br /> <br /> if (dent->d_name[0] == '.') {<br /> if (dent->d_name[1] == '.' && dent->d_name[2] == '\0') <br /> continue;<br /> if (dent->d_name[1] == '\0')<br /> continue;<br /> }<br /><br /> fl = strlen(fpath);<br /> dl = strlen(dent->d_name);<br /> if ((fl + 1 + dl) > 1024) {<br /> fprintf(stderr,"tgrep: Path %s/%s is too long. "<br /> "MaxPath = 1024\n",<br /> fpath, dent->d_name);<br /> continue; /* try the next name in this directory */<br /> }<br /> strcpy(fullpath,fpath);<br /> strcat(fullpath,"/");<br /> strcat(fullpath,dent->d_name);<br /><br /> RESTART_STAT:<br /> if (stat(fullpath,&sbuf)) {<br /> if (errno == EINTR) {<br /> if (--restart_cnt)<br /> goto RESTART_STAT;<br /> }<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Can't stat file/dir %s, %s. "<br /> "Ignored.\n",<br /> fullpath,strerror(errno));<br /> goto ERROR;<br /> }<br /><br /> switch (sbuf.st_mode & S_IFMT) {<br /> case S_IFREG :<br /> if (flags & TG_FILEPAT) {<br /> if (pmatch(pm_file_pat, dent->d_name, &pm_file_len)) {<br /> DP(DLEVEL3,("file pat match (cascade) %s\n",<br /> dent->d_name));<br /> add_work(fullpath,FILET);<br /> }<br /> }<br /> else {<br /> add_work(fullpath,FILET);<br /> DP(DLEVEL3,("cascade added file (MATCH) %s to Work Q\n",<br /> fullpath));<br /> }<br /> break;<br /> case S_IFDIR :<br /> DP(DLEVEL3,("cascade added dir %s to Work Q\n",fullpath));<br /> add_work(fullpath,DIRT);<br /> break;<br /> }<br /> }<br /><br /> ERROR:<br /> closedir(dp);<br /> DONE:<br /> free(wt->path);<br /> free(wt);<br /> notrun();<br /> mutex_lock(&cascade_q_lk);<br /> if (cascade_pool_cnt > cascade_thr_limit) {<br /> mutex_unlock(&cascade_q_lk);<br /> DP(DLEVEL5,("Cascade thread exiting\n"));<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> st_cascade_destroy++;<br /> mutex_unlock(&stat_lk);<br /> }<br /> return(0); /* thr_exit */<br /> }<br /> else {<br /> DP(DLEVEL5,("Cascade thread waiting in pool\n"));<br /> cascade_pool_cnt++;<br /> while (!cascade_q)<br /> cond_wait(&cascade_q_cv,&cascade_q_lk);<br /> cascade_pool_cnt--;<br /> wt = cascade_q; /* we have work to do! */<br /> if (cascade_q->next)<br /> cascade_q = cascade_q->next;<br /> else<br /> cascade_q = NULL;<br /> mutex_unlock(&cascade_q_lk);<br /> }<br /> }<br /> /*NOTREACHED*/<br />}<br /><br />/*<br /> * Print Local Output: Called by the search thread after it is done searching<br /> * a single file. If any oputput was saved (matching lines), the lines are <br /> * displayed as a group on stdout. <br /> */<br />int<br />print_local_output(out_t *out, work_t *wt)<br />{<br /> out_t *pp, *op;<br /> int out_count = 0;<br /> int printed = 0;<br /> int print_name = 1;<br /><br /> pp = out;<br /> mutex_lock(&output_print_lk);<br /> if (pp && (flags & TG_PROGRESS)) {<br /> progress++;<br /> if (progress >= progress_offset) {<br /> progress = 0;<br /> fprintf(stderr,".");<br /> }<br /> }<br /> while (pp) {<br /> out_count++;<br /> if (!(flags & FC_COUNT)) {<br /> if (flags & FL_NAMEONLY) { /* Pint name ONLY ! */<br /> if (!printed) {<br /> printed = 1;<br /> printf("%s\n",wt->path);<br /> }<br /> }<br /> else { /* We are printing more then just the name */<br /> if (!(flags & FH_HOLDNAME)) /* do not print name ? */<br /> printf("%s :",wt->path);<br /> if (flags & FB_BLOCK)<br /> printf("%ld:",pp->byte_count/512+1);<br /> if (flags & FN_NUMBER)<br /> printf("%d:",pp->line_count);<br /> printf("%s\n",pp->line);<br /> }<br /> }<br /> op = pp;<br /> pp = pp->next;<br /> /* free the nodes as we go down the list */<br /> free(op->line);<br /> free(op);<br /> }<br /> mutex_unlock(&output_print_lk);<br /> mutex_lock(&global_count_lk);<br /> global_count += out_count;<br /> mutex_unlock(&global_count_lk);<br /> return(0);<br />}<br /><br />/*<br /> * add output local: is called by a search thread as it finds matching lines. <br /> * the matching line, it's byte offset, line count, etc are stored until the<br /> * search thread is done searching the file, then the lines are printed as <br /> * a group. This way the lines from more then a single file are not mixed<br /> * together.<br /> */<br />int<br />add_output_local(out_t **out, work_t *wt,int lc, long bc, char *line)<br />{<br /> out_t *ot,*oo, *op;<br /><br /> if (( ot = (out_t *)malloc(sizeof(out_t))) == NULL)<br /> goto ERROR;<br /> if (( ot->line = (char *)malloc(strlen(line)+1)) == NULL)<br /> goto ERROR;<br /><br /> strcpy(ot->line,line);<br /> ot->line_count = lc;<br /> ot->byte_count = bc;<br /> <br /> if (!*out) {<br /> *out = ot;<br /> ot->next = NULL;<br /> return(0);<br /> }<br /> /* append to the END of the list, keep things sorted! */<br /> op = oo = *out; <br /> while(oo) {<br /> op = oo;<br /> oo = oo->next;<br /> }<br /> op->next = ot;<br /> ot->next = NULL;<br /> return(0);<br /> ERROR:<br /> if (!(flags & FS_NOERROR))<br /> fprintf(stderr,"tgrep: Output lost. No space. "<br /> "[%s: line %d byte %d match : %s\n",<br /> wt->path,lc,bc,line);<br /> return(1);<br />}<br /><br />/*<br /> * print stats: If the -S flag is set, after ALL files have been searched, <br /> * main thread calls this function to print the stats it keeps on how the<br /> * search went.<br /> */<br />void<br />prnt_stats(void)<br />{<br /> float a,b,c;<br /> float t = 0.0;<br /> time_t st_end = 0;<br /> char tl[80];<br /><br /> st_end = time(NULL); /* stop the clock */<br /> fprintf(stderr,"\n----------------- Tgrep Stats. --------------------\n");<br /> fprintf(stderr,"Number of directories searched: %d\n",<br /> st_dir_search);<br /> fprintf(stderr,"Number of files searched: %d\n",<br /> st_file_search);<br /> c = (float)(st_dir_search + st_file_search) / (float)(st_end - st_start);<br /> fprintf(stderr,"Dir/files per second: %3.2f\n",<br /> c);<br /> fprintf(stderr,"Number of lines searched: %d\n",<br /> st_line_search);<br /> fprintf(stderr,"Number of matching lines to target: %d\n",<br /> global_count);<br /><br /> fprintf(stderr,"Number of cascade threads created: %d\n",<br /> st_cascade);<br /> fprintf(stderr,"Number of cascade threads from pool: %d\n",<br /> st_cascade_pool);<br /> a = st_cascade_pool; b = st_dir_search;<br /> fprintf(stderr,"Cascade thread pool hit rate: %3.2f%%\n",<br /> ((a/b)*100));<br /> fprintf(stderr,"Cascade pool overall size: %d\n",<br /> cascade_pool_cnt);<br /> fprintf(stderr,"Cascade pool size limit: %d\n",<br /> cascade_thr_limit);<br /> fprintf(stderr,"Number of cascade threads destroyed: %d\n",<br /> st_cascade_destroy);<br /><br /> fprintf(stderr,"Number of search threads created: %d\n",<br /> st_search);<br /> fprintf(stderr,"Number of search threads from pool: %d\n",<br /> st_pool);<br /> a = st_pool; b = st_file_search;<br /> fprintf(stderr,"Search thread pool hit rate: %3.2f%%\n",<br /> ((a/b)*100));<br /> fprintf(stderr,"Search pool overall size: %d\n",<br /> search_pool_cnt);<br /> fprintf(stderr,"Search pool size limit: %d\n",<br /> search_thr_limit);<br /> fprintf(stderr,"Number of search threads destroyed: %d\n",<br /> st_destroy);<br /><br /> fprintf(stderr,"Max # of threads running concurrenly: %d\n",<br /> st_maxrun);<br /> fprintf(stderr,"Total run time, in seconds. %d\n",<br /> (st_end - st_start));<br /><br /> /* Why did we wait ? */<br /> a = st_workfds; b = st_dir_search+st_file_search;<br /> c = (a/b)*100; t += c;<br /> fprintf(stderr,"Work stopped due to no FD's: (%.3d) %d Times, %3.2f%%\n",<br /> search_thr_limit,st_workfds,c);<br /> a = st_worknull; b = st_dir_search+st_file_search;<br /> c = (a/b)*100; t += c;<br /> fprintf(stderr,"Work stopped due to no work on Q: %d Times, %3.2f%%\n",<br /> st_worknull,c);<br />#ifndef __lock_lint /* it is OK to read HERE with out the lock ! */<br /> if (tglimit == UNLIMITED)<br /> strcpy(tl,"Unlimited");<br /> else<br /> sprintf(tl," %.3d ",tglimit);<br />#endif<br /> a = st_worklimit; b = st_dir_search+st_file_search;<br /> c = (a/b)*100; t += c;<br /> fprintf(stderr,"Work stopped due to TGLIMIT: (%.9s) %d Times, %3.2f%%\n",<br /> tl,st_worklimit,c);<br /> fprintf(stderr,"Work continued to be handed out: %3.2f%%\n",<br /> 100.00-t);<br /> fprintf(stderr,"----------------------------------------------------\n");<br />}<br /><br />/*<br /> * not running: A glue function to track if any search threads or cascade <br /> * threads are running. When the count is zero, and the work Q is NULL,<br /> * we can safly say, WE ARE DONE.<br /> */<br />void <br />notrun (void)<br />{<br /> mutex_lock(&work_q_lk);<br /> work_cnt--;<br /> tglimit++;<br /> current_open_files++;<br /> mutex_lock(&running_lk);<br /> if (flags & FS_STATS) {<br /> mutex_lock(&stat_lk);<br /> if (running > st_maxrun) {<br /> st_maxrun = running;<br /> DP(DLEVEL6,("Max Running has increased to %d\n",st_maxrun));<br /> }<br /> mutex_unlock(&stat_lk);<br /> }<br /> running--;<br /> if (work_cnt == 0 && running == 0) {<br /> all_done = 1;<br /> DP(DLEVEL6,("Setting ALL_DONE flag to TRUE.\n"));<br /> }<br /> mutex_unlock(&running_lk);<br /> cond_signal(&work_q_cv);<br /> mutex_unlock(&work_q_lk);<br />}<br /><br />/*<br /> * uncase: A glue function. If the -i (case insensitive) flag is set, the<br /> * target strng and the read in line is converted to lower case before<br /> * comparing them.<br /> */<br />void<br />uncase(char *s)<br />{<br /> char *p;<br /><br /> for (p = s; *p != NULL; p++)<br /> *p = (char)tolower(*p);<br />}<br /><br /><br />/*<br /> * SigThread: if the -S option is set, the first ^C set to tgrep will<br /> * print the stats on the fly, the second will kill the process.<br /> */<br /><br />void *<br />SigThread(void *arg)<br />{<br /> int sig;<br /> int stats_printed = 0;<br /><br /> while (1) {<br /> sig = sigwait(&set);<br /> DP(DLEVEL7,("Signal %d caught\n",sig));<br /> switch (sig) {<br /> case -1:<br /> fprintf(stderr,"Signal error\n");<br /> break;<br /> case SIGINT:<br /> if (stats_printed)<br /> exit(1);<br /> stats_printed = 1;<br /> sig_print_stats();<br /> break;<br /> case SIGHUP:<br /> sig_print_stats();<br /> break;<br /> default:<br /> DP(DLEVEL7,("Default action taken (exit) for signal %d\n",sig));<br /> exit(1); /* default action */<br /> }<br /> }<br />}<br /><br />void<br />sig_print_stats(void)<br />{<br /> /*<br /> ** Get the output lock first<br /> ** Then get the stat lock.<br /> */<br /> mutex_lock(&output_print_lk);<br /> mutex_lock(&stat_lk);<br /> prnt_stats();<br /> mutex_unlock(&stat_lk);<br /> mutex_unlock(&output_print_lk);<br /> return;<br />}<br /><br />/*<br /> * usage: Have to have one of these.<br /> */<br />void <br />usage(void)<br />{<br /> fprintf(stderr,"usage: tgrep <options> pattern <{file,dir}>...\n");<br /> fprintf(stderr,"\n");<br /> fprintf(stderr,"Where:\n");<br />#ifdef DEBUG <br /> fprintf(stderr,"Debug -d = debug level -d <levels> (-d0 for usage)\n");<br /> fprintf(stderr,"Debug -f = block fd's from use (-f #)\n");<br />#endif <br /> fprintf(stderr," -b = show block count (512 byte block)\n");<br /> fprintf(stderr," -c = print only a line count\n");<br /> fprintf(stderr," -h = do not print file names\n");<br /> fprintf(stderr," -i = case insensitive\n");<br /> fprintf(stderr," -l = print file name only\n");<br /> fprintf(stderr," -n = print the line number with the line\n");<br /> fprintf(stderr," -s = Suppress error messages\n");<br /> fprintf(stderr," -v = print all but matching lines\n");<br />#ifdef NOT_IMP <br /> fprintf(stderr," -w = search for a \"word\"\n");<br />#endif <br /> fprintf(stderr," -r = Do not search for files in all "<br /> "sub-directories\n");<br /> fprintf(stderr," -C = show continued lines (\"\\\")\n");<br /> fprintf(stderr," -p = File name regexp pattern. (Quote it)\n");<br /> fprintf(stderr," -P = show progress. -P 1 prints a DOT on stderr\n"<br /> " for each file it finds, -P 10 prints a DOT\n"<br /> " on stderr for each 10 files it finds, etc...\n");<br /> fprintf(stderr," -e = expression search.(regexp) More then one\n");<br /> fprintf(stderr," -B = limit the number of threads to TGLIMIT\n");<br /> fprintf(stderr," -S = Print thread stats when done.\n");<br /> fprintf(stderr," -Z = Print help on the regexp used.\n");<br /> fprintf(stderr,"\n");<br /> fprintf(stderr,"Notes:\n");<br /> fprintf(stderr," If you start tgrep with only a directory name\n");<br /> fprintf(stderr," and no file names, you must not have the -r option\n");<br /> fprintf(stderr," set or you will get no output.\n");<br /> fprintf(stderr," To search stdin (piped input), you must set -r\n");<br /> fprintf(stderr," Tgrep will search ALL files in ALL \n");<br /> fprintf(stderr," sub-directories. (like */* */*/* */*/*/* etc..)\n");<br /> fprintf(stderr," if you supply a directory name.\n");<br /> fprintf(stderr," If you do not supply a file, or directory name,\n");<br /> fprintf(stderr," and the -r option is not set, the current \n");<br /> fprintf(stderr," directory \".\" will be used.\n");<br /> fprintf(stderr," All the other options should work \"like\" grep\n");<br /> fprintf(stderr," The -p patten is regexp, tgrep will search only\n");<br /> fprintf(stderr," the file names that match the patten\n");<br /> fprintf(stderr,"\n");<br /> fprintf(stderr," Tgrep Version %s\n",Tgrep_Version);<br /> fprintf(stderr,"\n");<br /> fprintf(stderr," Copy Right By Ron Winacott, 1993-1995.\n");<br /> fprintf(stderr,"\n");<br /> exit(0);<br />}<br /><br />/*<br /> * regexp usage: Tell the world about tgrep custom (THREAD SAFE) regexp!<br /> */<br />int <br />regexp_usage (void)<br />{<br /> fprintf(stderr,"usage: tgrep <options> -e \"pattern\" <-e ...> "<br /> "<{file,dir}>...\n");<br /> fprintf(stderr,"\n");<br /> fprintf(stderr,"metachars:\n");<br /> fprintf(stderr," . - match any character\n");<br /> fprintf(stderr," * - match 0 or more occurrences of pervious char\n");<br /> fprintf(stderr," + - match 1 or more occurrences of pervious char.\n");<br /> fprintf(stderr," ^ - match at begining of string\n");<br /> fprintf(stderr," $ - match end of string\n");<br /> fprintf(stderr," [ - start of character class\n");<br /> fprintf(stderr," ] - end of character class\n");<br /> fprintf(stderr," ( - start of a new pattern\n");<br /> fprintf(stderr," ) - end of a new pattern\n");<br /> fprintf(stderr," @(n)c - match <c> at column <n>\n");<br /> fprintf(stderr," | - match either pattern\n");<br /> fprintf(stderr," \\ - escape any special characters\n");<br /> fprintf(stderr," \\c - escape any special characters\n");<br /> fprintf(stderr," \\o - turn on any special characters\n");<br /> fprintf(stderr,"\n");<br /> fprintf(stderr,"To match two diffrerent patterns in the same command\n");<br /> fprintf(stderr,"Use the or function. \n"<br /> "ie: tgrep -e \"(pat1)|(pat2)\" file\n"<br /> "This will match any line with \"pat1\" or \"pat2\" in it.\n");<br /> fprintf(stderr,"You can also use up to %d -e expresions\n",MAXREGEXP);<br /> fprintf(stderr,"RegExp Pattern matching brought to you by Marc Staveley\n");<br /> exit(0);<br />}<br /><br />/*<br /> * debug usage: If compiled with -DDEBUG, turn it on, and tell the world<br /> * how to get tgrep to print debug info on different threads.<br /> */<br />#ifdef DEBUG<br />void<br />debug_usage(void)<br />{<br /> int i = 0;<br /><br /> fprintf(stderr,"DEBUG usage and levels:\n");<br /> fprintf(stderr,"--------------------------------------------------\n");<br /> fprintf(stderr,"Level code\n");<br /> fprintf(stderr,"--------------------------------------------------\n");<br /> fprintf(stderr,"0 This message.\n");<br /> for (i=0; i<9; i++) {<br /> fprintf(stderr,"%d %s\n",i+1,debug_set[i].name);<br /> }<br /> fprintf(stderr,"--------------------------------------------------\n");<br /> fprintf(stderr,"You can or the levels together like -d134 for levels\n");<br /> fprintf(stderr,"1 and 3 and 4.\n");<br /> fprintf(stderr,"\n");<br /> exit(0);<br />}<br />#endif<br />Multithreaded Quicksort
The following example tquick.cimplements the quicksort algorithm using threads./*<br />* Multithreaded Demo Source<br />* <br />* Copyright (C) 1995 by Sun Microsystems, Inc.<br />* All rights reserved.<br />* <br />* This file is a product of SunSoft, Inc. and is provided for<br />* unrestricted use provided that this legend is included on all<br />* media and as a part of the software program in whole or part.<br />* Users may copy, modify or distribute this file at will.<br />* <br />* THIS FILE IS PROVIDED AS IS WITH NO WARRANTIES OF ANY KIND INCLUDING<br />* THE WARRANTIES OF DESIGN, MERCHANTIBILITY AND FITNESS FOR A PARTICULAR<br />* PURPOSE, OR ARISING FROM A COURSE OF DEALING, USAGE OR TRADE PRACTICE.<br />* <br />* This file is provided with no support and without any obligation on the<br />* part of SunSoft, Inc. to assist in its use, correction, modification or<br />* enhancement.<br />* <br />* SUNSOFT AND SUN MICROSYSTEMS, INC. SHALL HAVE NO LIABILITY WITH RESPECT<br />* TO THE INFRINGEMENT OF COPYRIGHTS, TRADE SECRETS OR ANY PATENTS BY THIS<br />* FILE OR ANY PART THEREOF.<br />* <br />* IN NO EVENT WILL SUNSOFT OR SUN MICROSYSTEMS, INC. BE LIABLE FOR ANY<br />* LOST REVENUE OR PROFITS OR OTHER SPECIAL, INDIRECT AND CONSEQUENTIAL<br />* DAMAGES, EVEN IF THEY HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH<br />* DAMAGES.<br />* <br />* SunSoft, Inc.<br />* 2550 Garcia Avenue<br />* Mountain View, California 94043<br />*/<br /><br />/*<br /> * multiple-thread quick-sort. See man page for qsort(3c) for info.<br /> * Works fine on uniprocessor machines as well.<br /> *<br /> * Written by: Richard Pettit (Richard.Pettit@West.Sun.COM)<br /> */<br /><br />#include <unistd.h><br />#include <stdlib.h><br />#include <thread.h><br /><br />/* don't create more threads for less than this */<br />#define SLICE_THRESH 4096<br /><br />/* how many threads per lwp */<br />#define THR_PER_LWP 4<br /><br />/* cast the void to a one byte quanitity and compute the offset */<br />#define SUB(a, n) ((void *) (((unsigned char *) (a)) + ((n) * width)))<br /><br />typedef struct {<br /> void *sa_base;<br /> int sa_nel;<br /> size_t sa_width;<br /> int (*sa_compar)(const void *, const void *);<br />} sort_args_t;<br /><br />/* for all instances of quicksort */<br />static int threads_avail;<br /><br />#define SWAP(a, i, j, width) \<br />{ \<br /> int n; \<br /> unsigned char uc; \<br /> unsigned short us; \<br /> unsigned long ul; \<br /> unsigned long long ull; \<br /> \<br /> if (SUB(a, i) == pivot) \<br /> pivot = SUB(a, j); \<br /> else if (SUB(a, j) == pivot) \<br /> pivot = SUB(a, i); \<br /> \<br /> /* one of the more convoluted swaps I've done */ \<br /> switch(width) { \<br /> case 1: \<br /> uc = *((unsigned char *) SUB(a, i)); \<br /> *((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); \<br /> *((unsigned char *) SUB(a, j)) = uc; \<br /> break; \<br /> case 2: \<br /> us = *((unsigned short *) SUB(a, i)); \<br /> *((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); \<br /> *((unsigned short *) SUB(a, j)) = us; \<br /> break; \<br /> case 4: \<br /> ul = *((unsigned long *) SUB(a, i)); \<br /> *((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j)); \<br /> *((unsigned long *) SUB(a, j)) = ul; \<br /> break; \<br /> case 8: \<br /> ull = *((unsigned long long *) SUB(a, i)); \<br /> *((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); \<br /> *((unsigned long long *) SUB(a, j)) = ull; \<br /> break; \<br /> default: \<br /> for(n=0; n<width; n++) { \<br /> uc = ((unsigned char *) SUB(a, i))[n]; \<br /> ((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; \<br /> ((unsigned char *) SUB(a, j))[n] = uc; \<br /> } \<br /> break; \<br /> } \<br />}<br /><br />static void *<br />_quicksort(void *arg)<br />{<br /> sort_args_t *sargs = (sort_args_t *) arg;<br /> register void *a = sargs->sa_base;<br /> int n = sargs->sa_nel;<br /> int width = sargs->sa_width;<br /> int (*compar)(const void *, const void *) = sargs->sa_compar;<br /> register int i;<br /> register int j;<br /> int z;<br /> int thread_count = 0;<br /> void *t;<br /> void *b[3];<br /> void *pivot = 0;<br /> sort_args_t sort_args[2];<br /> thread_t tid;<br /><br /> /* find the pivot point */<br /> switch(n) {<br /> case 0:<br /> case 1:<br /> return 0;<br /> case 2:<br /> if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {<br /> SWAP(a, 0, 1, width);<br /> }<br /> return 0;<br /> case 3:<br /> /* three sort */<br /> if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {<br /> SWAP(a, 0, 1, width);<br /> }<br /> /* the first two are now ordered, now order the second two */<br /> if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {<br /> SWAP(a, 2, 1, width);<br /> }<br /> /* should the second be moved to the first? */<br /> if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {<br /> SWAP(a, 1, 0, width);<br /> }<br /> return 0;<br /> default:<br /> if (n > 3) {<br /> b[0] = SUB(a, 0);<br /> b[1] = SUB(a, n / 2);<br /> b[2] = SUB(a, n - 1);<br /> /* three sort */<br /> if ((*compar)(b[0], b[1]) > 0) {<br /> t = b[0];<br /> b[0] = b[1];<br /> b[1] = t;<br /> }<br /> /* the first two are now ordered, now order the second two */<br /> if ((*compar)(b[2], b[1]) < 0) {<br /> t = b[1];<br /> b[1] = b[2];<br /> b[2] = t;<br /> }<br /> /* should the second be moved to the first? */<br /> if ((*compar)(b[1], b[0]) < 0) {<br /> t = b[0];<br /> b[0] = b[1];<br /> b[1] = t;<br /> }<br /> if ((*compar)(b[0], b[2]) != 0)<br /> if ((*compar)(b[0], b[1]) < 0)<br /> pivot = b[1];<br /> else<br /> pivot = b[2];<br /> }<br /> break;<br /> }<br /> if (pivot == 0)<br /> for(i=1; i<n; i++) {<br /> if (z = (*compar)(SUB(a, 0), SUB(a, i))) {<br /> pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);<br /> break;<br /> }<br /> }<br /> if (pivot == 0)<br /> return;<br /><br /> /* sort */<br /> i = 0;<br /> j = n - 1;<br /> while(i <= j) {<br /> while((*compar)(SUB(a, i), pivot) < 0)<br /> ++i;<br /> while((*compar)(SUB(a, j), pivot) >= 0)<br /> --j;<br /> if (i < j) {<br /> SWAP(a, i, j, width);<br /> ++i;<br /> --j;<br /> }<br /> }<br /><br /> /* sort the sides judiciously */<br /> switch(i) {<br /> case 0:<br /> case 1:<br /> break;<br /> case 2:<br /> if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {<br /> SWAP(a, 0, 1, width);<br /> }<br /> break;<br /> case 3:<br /> /* three sort */<br /> if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {<br /> SWAP(a, 0, 1, width);<br /> }<br /> /* the first two are now ordered, now order the second two */<br /> if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {<br /> SWAP(a, 2, 1, width);<br /> }<br /> /* should the second be moved to the first? */<br /> if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {<br /> SWAP(a, 1, 0, width);<br /> }<br /> break;<br /> default:<br /> sort_args[0].sa_base = a;<br /> sort_args[0].sa_nel = i;<br /> sort_args[0].sa_width = width;<br /> sort_args[0].sa_compar = compar;<br /> if ((threads_avail > 0) && (i > SLICE_THRESH)) {<br /> threads_avail--;<br /> thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid);<br /> thread_count = 1;<br /> } else<br /> _quicksort(&sort_args[0]);<br /> break;<br /> }<br /> j = n - i;<br /> switch(j) {<br /> case 1:<br /> break;<br /> case 2:<br /> if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {<br /> SWAP(a, i, i + 1, width);<br /> }<br /> break;<br /> case 3:<br /> /* three sort */<br /> if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {<br /> SWAP(a, i, i + 1, width);<br /> }<br /> /* the first two are now ordered, now order the second two */<br /> if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {<br /> SWAP(a, i + 2, i + 1, width);<br /> }<br /> /* should the second be moved to the first? */<br /> if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {<br /> SWAP(a, i + 1, i, width);<br /> }<br /> break;<br /> default:<br /> sort_args[1].sa_base = SUB(a, i);<br /> sort_args[1].sa_nel = j;<br /> sort_args[1].sa_width = width;<br /> sort_args[1].sa_compar = compar;<br /> if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) {<br /> threads_avail--;<br /> thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid);<br /> thread_count = 1;<br /> } else<br /> _quicksort(&sort_args[1]);<br /> break;<br /> }<br /> if (thread_count) {<br /> thr_join(tid, 0, 0);<br /> threads_avail++;<br /> }<br /> return 0;<br />}<br /><br />void<br />quicksort(void *a, size_t n, size_t width,<br /> int (*compar)(const void *, const void *))<br />{<br /> static int ncpus = -1;<br /> sort_args_t sort_args;<br /><br /> if (ncpus == -1) {<br /> ncpus = sysconf( _SC_NPROCESSORS_ONLN);<br /><br /> /* lwp for each cpu */<br /> if ((ncpus > 1) && (thr_getconcurrency() < ncpus))<br /> thr_setconcurrency(ncpus);<br /><br /> /* thread count not to exceed THR_PER_LWP per lwp */<br /> threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP);<br /> }<br /> sort_args.sa_base = a;<br /> sort_args.sa_nel = n;<br /> sort_args.sa_width = width;<br /> sort_args.sa_compar = compar;<br /> (void) _quicksort(&sort_args);<br />}<br />Dave Marshall
1/5/1999
No comments:
Post a Comment