advanced code snippet search

Posted By

keigoi on 09/13/09


Tagged

concurrency pthread multithread fairness signal mutex


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

keigoi


pthread sleeper fairness

 / Published in: C
 

this snippet is for checking fairness of context switching in your environment.

the snippet does not runs two threads directly, but it switches two threads explicitly, by using a monitor (a mutex and a condition variable).

Some programming languges take such indirect concurrent execution mechanism for native threads. Programming languges which support \"native threads\" but does not support conccurent GC must stop the whole process in order to collect garbages safely. Since native threads generally are not capable of disabling preemption, the runtime must pause all threads except for one that runs GC.

compile with:<br/>gcc -lpthread filename.c

there is a `global lock\' and two threads. each thread runs work() in the same way, only except its parameter. each of two threads increments the counter hit_count[i] where i is the id of the thread.

after 1 second, the program outputs statistics and terminates.

SIGALRM. thread0: 1899, thread1: 2333, switch:20

if your pthread library is fair, the first two numbers are nearly equal to each other, and the third number is 20 or so.

unfortunately, my Mac OS X (10.5.8) has turned to be unfair:

SIGALRM. thread0: 4086, thread1: 215, switch:2

on the contrary, linux (debian 5.0, kenel 2.6.26) has shown to be fair. please post your results in the comments.

The linux kernel 2.6 (>= 2.6.23) is likely to be fair, because it is equipped with the Completely Fair Scheduler. This scheduler is aware of \'sleeper fairness\'.

see also:http://snipplr.com/view/19509/ if your pthread is shown to be \'unfair\', this O\'Caml snippet will also stops for a while.

UPDATE: added volatile to the shared variables.

Expand | Embed | Plain Text 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include <unistd.h>
  5. #include <pthread.h>
  6. #include <signal.h>
  7. #include <sys/time.h>
  8.  
  9. #define TIMEOUT 50000 // context switch rate, in microseconds
  10. #define WAIT_COUNT 0x10000 // busy wait count
  11. #define EXIT_AFTER 1  // exit after 1 sec
  12.  
  13.  
  14. // monitor
  15. pthread_mutex_t mutex;
  16. pthread_cond_t cond;
  17.  
  18. volatile int locked; // the `world' is locked or not
  19. volatile int waiters; // number of waiting threads
  20. volatile int signal_has_come; // 1 if context switch signal has come
  21.  
  22. // thread that fire periodic signal for context switch
  23. void* thread_tick(void* arg) {
  24. 	while(1) {
  25. 		// fprintf(stdout, "tick\n"); fflush(stdout); 
  26. 		signal_has_come = 1;
  27. 		struct timespec to;
  28. 		to.tv_sec = 0;
  29. 		to.tv_nsec = TIMEOUT * 1000;
  30. 		nanosleep(&to, 0);
  31. 	}
  32. }
  33.  
  34. // release the global lock
  35. void unlock_world() {
  36. 	pthread_mutex_lock(&mutex);
  37. 	locked = 0;
  38. 	pthread_mutex_unlock(&mutex);
  39. 	// fprintf(stdout, "released global lock (%d)\n", (int)pthread_self()); fflush(stdout);
  40. 	pthread_cond_signal(&cond);
  41. }
  42.  
  43. // obtain the global lock
  44. void lock_world() {
  45. 	pthread_mutex_lock(&mutex);
  46. 	while(locked) {
  47. 		// fprintf(stdout, "locked. sleeping.. (%d)\n", (int)pthread_self()); fflush(stdout);
  48. 		waiters++;
  49. 		pthread_cond_wait(&cond, &mutex);
  50. 		waiters--;
  51. 	}
  52. 	locked = 1;
  53. 	pthread_mutex_unlock(&mutex);
  54. 	// fprintf(stdout,"got global lock. restart. (%d)\n", (int)pthread_self());
  55. }
  56.  
  57. // yield to switch to the other thread
  58. void yield() {
  59. 	if(0==waiters) return;
  60. 	unlock_world();
  61. 	sched_yield();
  62. 	lock_world();
  63. }
  64.  
  65. void check_signal_and_yield() {
  66. 	if(signal_has_come) {
  67. 		signal_has_come=0;
  68. 		yield();
  69. 	}
  70. }
  71.  
  72. int hit_count[2]; // count how many times the loop is executed, for each thread
  73. int prev;
  74. int switch_count;
  75.  
  76. void work(int i) {
  77. 	while(1) {
  78.  
  79. 		// count
  80. 		hit_count[i]++;
  81. 		if(i!=prev) { prev=i; switch_count++;}
  82.  
  83. 		// yield
  84. 		check_signal_and_yield();
  85.  
  86. 		// fprintf(stdout,"working. %d\n", (int)pthread_self());
  87.  
  88. 		// busy waiting
  89. 		int i;
  90. 		for(i=0; i<WAIT_COUNT; i++);
  91. 	}
  92. }
  93.  
  94.  
  95. void* thread_start(void* arg) {
  96. 	// fprintf(stdout, "new thread start. %d\n", (int)pthread_self()); fflush(stdout); 
  97. 	lock_world();
  98. 	work(1);
  99. 	return 0;
  100. }
  101.  
  102.  
  103. // exit after specified second.
  104. void interrupt_handler(int sig) {
  105. 	fprintf(stdout, "SIGALRM. thread0: %d, thread1: %d, switch:%d\n", hit_count[0], hit_count[1], switch_count); fflush(stdout);
  106. 	exit(0);
  107. }
  108.  
  109. // set up the stop watch
  110. void set_stop_alarm() {
  111. 	void(*oldact)(int);
  112. 	oldact = signal(SIGALRM, interrupt_handler);
  113. 	assert(SIG_ERR!=oldact);
  114. 	struct itimerval itv;
  115. 	itv.it_value.tv_sec = EXIT_AFTER;
  116. 	itv.it_value.tv_usec = 0;
  117. 	itv.it_interval = itv.it_value;
  118. 	setitimer(ITIMER_REAL, &itv, 0);
  119. }
  120.  
  121. int main(int argc, char** argv) {
  122.  
  123. 	// set up the stop watch
  124. 	set_stop_alarm();
  125.  
  126. 	// set up mutex and condition variable for monitor
  127. 	int r = pthread_mutex_init(&mutex, 0);
  128. 	assert(0==r);
  129. 	r = pthread_cond_init(&cond, 0);
  130. 	assert(0==r);
  131.  
  132. 	// start the sub thread
  133. 	pthread_t th;
  134. 	pthread_create(&th, 0, thread_start, 0);
  135.  
  136. 	// start the tick thread
  137. 	pthread_t th2;
  138. 	pthread_create(&th2, 0, thread_tick, 0);
  139.  
  140. 	// start the main thread
  141. 	lock_world();
  142. 	work(0);
  143. 	return 0;
  144. }

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: deepsoul on September 14, 2009

Surprise, surprise: I just tested my Linux box and obtained

SIGALRM. thread0: 4891, thread1: 412, switch:3

as the most unfair of several runs with the unchanged program. Setting EXIT_AFTER to 10 gives

SIGALRM. thread0: 9090, thread1: 43200, switch:15

as the worst result. With EXIT_AFTER=100 the worst case is:

SIGALRM. thread0: 184344, thread1: 338777, switch:63

As one can see, the results become fairer as the test time and the number of task switches increases.

Probable reason: My kernel was compiled with the option CONFIG_HZ_250=y. This means the interrupt timer frequency on which the scheduler depends is set to 250 Hz. The kernel config help calls this the compromise between 100Hz (for servers, few interrupts that would reduce overall performance) and 1000Hz (for desktops, fastest response to user events). A low timer frequency gives infrequent task switches and therefore little "fairness". Stock distribution kernels tend to be built with 1000Hz timer frequency, hence the fair results you saw. Look at /boot/config- to check.

Thanks for the program! I will test some other Linux boxes I have access to which run distribution kernels and post the results.

Posted By: deepsoul on September 14, 2009

That should have been: Look at /boot/config- to ckeck.

Posted By: deepsoul on September 14, 2009

Another try: Look at /boot/config-<your kernel version> to check. Sorry this took so long.

Posted By: keigoi on September 15, 2009

Thanks for comments, deepsoul!

Actually, this code simulates context switching in O'Caml programming language (native code, compiled with ocamlopt). I suppose other scripting languages like Ruby and Python might take similar scheduling mechanism. Sorry for incomplete explanation. I will revise it.

After googlin' some words like fairness pthread scheduling etc, I found this wikipedia page:

Completely Fair Scheduler

according to this, the kernel which version is greater or equal to 2.6.23, which is supposed to be equipped with CFS, will provide CPU time to each threads fairly, even if a thread waits for long time because of locked mutex.

I suppose that the reason of unfairness in other OSs is that the `fairness' of their scheduling algorithm does not take into account sleeping threads.

I found CONFIG_HZ in my linux (kernel 2.6.26, which is "fair"): 




CONFIGHZ100 is not set



CONFIGHZ250=y



CONFIGHZ300 is not set



CONFIGHZ1000 is not set



CONFIGHZ=250
hence I suppose that CONFIGHZ parameter is irrelevant for fairness in this case.

Posted By: deepsoul on September 17, 2009

Oh well, there goes that theory. It would have been crass if a factor of 4 in the timer frequency had caused a factor of 100 in the timescale at which scheduling becomes fair, so this puts the world right in a way.

But I have in the mean time tested three other linux systems. All (including the one above) run kernels with versions 2.6.23 or later, so use the CFS scheduler. Except for one, they gave the same results as the first machine above - fairness only at minute timescales. This one is distinguished by being a single-core CPU. The others are dual-core or (one of them) an Intel Atom which is treated as dual-core due to hyperthreading. This is the cause of the discrepancy: When I restrict the program to run on one core only (with the command taskset 0x1), the scheduling is perfectly fair on all machines at the default test time of one second! Your program seemed to run almost exclusively on one CPU anyway, but I saw this only visually from xosview, so it may simply give inaccurate results on multi-cores.

Finally, I tested a windoze box (compiled and run via Cygwin). It behaved not quite as fairly as the single-core linux results, but decently. A typical result:

SIGALRM. thread0: 1970, thread1: 2543, switch:6

You need to login to post a comment.