Ok, I think we can wrap this part of the problem. I'll run a small
addition to the statistics collection that will also check how many
times the same thread got the mutex consecutively. This will tell us
something about performance.
In a nutshell:
Use pthread_mutex_lock for only exclusion
Maybe thread attributes can change that (untested)
Use pthread_mutex_timedlock for exclusion + priority change in case of
too long waits. Will get lower performance.
Program at end. Results are as followed. Without priority change:
> $ time ./mutex_fair 6
> Thread b7d98bb0 started as thread #0
> Thread b7597bb0 started as thread #1
> Thread b6d96bb0 started as thread #2
> Thread b6595bb0 started as thread #3
> Thread b5d94bb0 started as thread #4
> Thread b5593bb0 started as thread #5
> Results: 395792 111838 7553221 498126 320367 724004
> Results: 623730 111838 13458754 498126 320367 9869077
> Results: 623730 111838 13458754 498126 10192755 14416234
> Results: 19163946 111838 35907977 498126 29674476 14643637
> Joined thread #0
> Joined thread #1
> Joined thread #2
> Joined thread #3
> Joined thread #4
> Joined thread #5
>
> real 0m8.777s
> user 0m8.233s
> sys 0m0.380s
Most used thread got the mutex 72 times for each time least used thread
got it.
With timedlock and a 0.1 second timeout:
> $ time ./mutex_fair 6
> Thread b7da6bb0 started as thread #0
> Thread b75a5bb0 started as thread #1
> Thread b6da4bb0 started as thread #2
> Thread b65a3bb0 started as thread #3
> Thread b5da2bb0 started as thread #4
> Thread b55a1bb0 started as thread #5
> Results: 2852 57012 114954 97632 357801 154461
> Results: 2852 57012 176089 377855 634999 428648
> Results: 31550 83700 204804 425340 1011929 817958
> pthread_mutex_timedlock failed: Success
> Results: 181551 231094 354143 577373 1152547 969284
> Results: 297874 351201 474741 696265 1295251 1100891
> Results: 440600 504119 627584 847712 1437084 1253289
> Results: 548432 654929 778629 1001537 1599504 1402274
> Results: 681859 785418 867405 1179841 1780464 1584119
> Results: 859849 921206 1047168 1309851 1871284 1764591
> Results: 990446 1100281 1227914 1445484 2052189 1854569
> Results: 1125700 1233886 1319379 1624517 2230711 2035560
> Results: 1307544 1369130 1497557 1756951 2321953 2213568
> Results: 1441995 1549919 1676220 1891251 2500647 2304783
> Results: 1576616 1683722 1766659 2071452 2678464 2483494
> Results: 1754499 1818919 1946200 2175026 2769526 2663642
> Results: 1856764 1996615 2126777 2337628 2950355 2754470
> Results: 2024608 2086378 2214844 2516532 3091801 2934781
> Results: 2205276 2264676 2396315 2606854 3217196 3076760
> Results: 2387000 2399299 2486901 2780300 3390310 3201740
> Results: 2478196 2531551 2667284 2964074 3520276 3380980
> Results: 2659065 2709210 2849255 3054460 3655238 3512449
> Results: 2840315 2839026 2938351 3235128 3833992 3648681
> Results: 2930747 2974351 3117280 3418028 3965263 3829507
> Results: 3108708 3155375 3298702 3505974 4102287 3960456
> Results: 3289462 3256856 3387043 3684332 4283493 4097233
> Results: 3377812 3423473 3564672 3865019 4384306 4279687
> Results: 3559600 3604518 3725082 3954728 4546210 4367398
> Results: 3693387 3691563 3827869 4131480 4720410 4541837
> Results: 3815900 3868486 4005810 4263683 4803955 4719603
> Results: 3997789 4049251 4137211 4394030 4986031 4810363
> Results: 4129815 4140353 4266945 4576975 5167346 4992164
> Results: 4261345 4321552 4448901 4707123 5257203 5172771
> Results: 4443252 4502672 4580360 4838369 5439858 5262272
> Results: 4573538 4592039 4711704 5018898 5619361 5444819
> Results: 4708135 4771941 4892763 5124289 5706556 5624195
> Results: 4889495 4950239 4996824 5288305 5888373 5712760
> Results: 4978967 5038607 5158844 5468951 6053305 5895051
> Results: 5160781 5219422 5339597 5556225 6154734 6059371
> Results: 5339713 5385070 5427522 5736271 6336187 6162057
> Results: 5428024 5487641 5605000 5912647 6501961 6342727
> Results: 5610236 5668894 5783667 6000739 6603734 6507082
> Results: 5788118 5835152 5871600 6181770 6784483 6608441
> Results: 5876141 5936850 6053209 6360177 6950687 6789233
> Results: 6057241 6116597 6231435 6448244 7052522 6929870
> Results: 6241708 6214392 6322636 6629259 7230103 7057189
> Results: 6332980 6377503 6505332 6789435 7320574 7237138
> Results: 6508655 6553480 6603906 6893009 7503313 7328163
> Results: 6598735 6642327 6775812 7069614 7667393 7507551
> Results: 6770454 6817577 6897193 7166047 7765691 7592879
> Results: 6861332 6908359 7040236 7351208 7885148 7772795
> Results: 7007784 6997040 7126996 7438966 8031606 7863176
> Results: 7123160 7172345 7304824 7527766 8120470 7990658
> Results: 7300981 7296215 7395202 7707100 8301114 8132354
> Results: 7391286 7437672 7575236 7889099 8424956 8308246
> Results: 7573124 7616231 7755646 7979485 8568162 8403232
> Results: 7704489 7706719 7846107 8160074 8747445 8574954
> Results: 7840514 7887153 8022074 8284878 8837481 8753276
> Results: 8018636 8065133 8115708 8426722 9017394 8844150
> Results: 8108334 8156591 8288476 8604923 9195275 9018688
> Results: 8285536 8337150 8471786 8695952 9285417 9161188
> Results: 8462666 8449994 8565226 8877325 9464017 9283063
> Results: 8552881 8605733 8744141 9048569 9555023 9462808
> Results: 8731118 8786819 8916385 9145145 9733190 9553885
> Results: 8904972 8877174 9012455 9327038 9911957 9729821
> Results: 9001678 9053377 9193102 9501725 10002608 9909171
> Results: 9181471 9233215 9333332 9597954 10178693 9999903
> Results: 9322431 9322167 9461071 9780004 10357847 10178570
> Results: 9447292 9502787 9639913 9920683 10448503 10358771
> Results: 9626585 9683327 9781801 10044958 10629523 10449234
> pthread_mutex_timedlock failed: Success
> Results: 9762212 9774393 9906201 10223109 10809599 10627681
> Results: 9854284 9865093 9994434 10267863 10863962 10717523
> Results: 10032744 10046364 10129079 10398396 11045073 10808892
> Results: 10168381 10136741 10258705 10576519 11225954 10989720
> Results: 10298724 10315669 10439514 10714836 11316223 11168429
> Results: 10479108 10495051 10577364 10845218 11495424 11259825
> Results: 10569949 10586320 10703886 11023450 11668451 11438447
> Results: 10745284 10769450 10882253 11114834 11765476 11608362
> Results: 10922438 10903588 10973556 11288981 11944696 11708274
> Results: 11012720 11033481 11152897 11467682 12082806 11889270
> Results: 11192426 11211615 11333388 11558494 12209300 12024813
> Results: 11373133 11346969 11423603 11738985 12388679 12154198
> Results: 11463708 11477015 11603968 11920482 12524122 12333516
> Results: 11642995 11655770 11786144 12011200 12654382 12468103
> Results: 11825036 11790292 11876329 12191397 12832592 12599105
> Results: 11915128 11920843 12057323 12373701 12966247 12778706
> Results: 12093216 12103088 12239378 12461911 13097288 12883226
> Results: 12274853 12204654 12324335 12641506 13278035 13044146
> Results: 12362440 12369151 12499723 12823571 13379116 13225678
> Results: 12541629 12549902 12680000 12911089 13544023 13325913
> Results: 12723586 12649639 12770156 13092167 13726412 13488174
> Results: 12812663 12813034 12951107 13274289 13824708 13669771
> Results: 12994412 12995899 13132698 13364139 13990209 13765062
> Results: 13175708 13090718 13222226 13545251 14171699 13931966
> Results: 13266001 13259882 13404519 13726733 14263568 14114567
> Results: 13449533 13441456 13553050 13815116 14435574 14204424
> Results: 13566483 13529646 13669245 13996650 14616217 14385319
> Results: 13716791 13712310 13848640 14084686 14703580 14563309
> Results: 13897552 13887633 13937464 14262597 14886430 14653542
> Results: 13987320 13978029 14115651 14444455 15061143 14834809
> Results: 14168731 14160229 14296311 14534263 15150813 15007348
> pthread_mutex_timedlock failed: Success
> pthread_mutex_timedlock failed: Illegal seek
> Results: 14347438 14326871 14383789 14711795 15327507 15099648
> Results: 14435733 14427867 14565687 14891298 15493304 15281115
> Results: 14617261 14609258 14744419 14978940 15593728 15445908
> Results: 14795719 14775348 14832741 15160005 15775370 15547124
> Results: 14883776 14875861 15014241 15339325 15941222 15728240
> Results: 15064979 15056791 15191463 15427755 16042027 15895426
> Results: 15245737 15220755 15282097 15609136 16221614 15996273
> Results: 15336457 15321668 15462386 15788730 16386558 16174949
> Results: 15517517 15500536 15642886 15879045 16487558 16340003
> Results: 15697983 15661738 15733681 16059736 16666889 16443874
> Results: 15789388 15765889 15914336 16238148 16827579 16622789
> Results: 15970182 15945332 16095605 16329561 16931251 16783380
> Results: 16147465 16105383 16187011 16506262 17108273 16888636
> Results: 16238465 16210687 16366202 16685105 17263683 17068917
> Results: 16326826 16268521 16366202 16685105 17284429 17068917
> Joined thread #0
> Joined thread #1
> Joined thread #2
> Joined thread #3
> Joined thread #4
> Joined thread #5
>
> real 1m56.938s
> user 0m25.850s
> sys 1m27.589s
Most used thread got the mutex 1.06 times for each time the least used
thread got it. Ratio between processing time: fair version took 12.9
times longer to execute.
Again, this time with 0.4 second timeout:
> Results: 17172169 16075279 16116535 16066999 17691407 16877611
> real 1m58.011s
> user 0m26.166s
> sys 1m28.294s
Unfairness ratio: 1.1
Slowdown ratio: 13.45
Trying significantly lower timeouts - 0.01 second:
> Results: 16569256 16572919 16642712 16660443 16691948 16862722
>
> real 1m55.915s
> user 0m25.310s
> sys 1m27.781s
Unfairness ratio: 1.02
Slowdown: 13.2
So we see that using mutex timedlock is better than forcing yield, as it
provides smaller slowdown (compare our 1:13 factor with Muli's reported
1:20 factor), while still providing reasonable fairness. It seems each
programmer is free to select her own tradeoff, performance vs. fairness,
and use the appropriate function calls. That's a reasonable position to
be in, assuming you understand the trade offs.
Shachar
#include <pthread.h>
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <errno.h>
#define TEST_SIZE 100000000
#define TIMEOUT 10000
volatile int results[TEST_SIZE], position=0;
#if 1
void acquire( pthread_mutex_t *mutex )
{
struct timeval tv;
struct timespec ts;
int res=-1;
do {
gettimeofday(&tv, NULL);
// Add the timeout
tv.tv_usec+=TIMEOUT;
if( tv.tv_usec>1000000 ) {
tv.tv_usec-=1000000;
tv.tv_sec++;
}
ts.tv_sec=tv.tv_sec;
ts.tv_nsec=tv.tv_usec*1000;
res=pthread_mutex_timedlock( mutex, &ts );
} while( res!=0 && errno==ETIMEDOUT );
if( res!=0 )
perror("pthread_mutex_timedlock failed");
}
#else
void acquire( pthread_mutex_t *mutex )
{
pthread_mutex_lock(mutex);
}
#endif
int worker( int threadnum )
{
static pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;
//pthread_attr_setschedpolicy( NULL, SCHED_FIFO);
printf("Thread %lx started as thread #%d\n", pthread_self(), threadnum);
acquire(&mutex);
while( position<TEST_SIZE ) {
// printf("results[%d]=%d\n", position, threadnum);
results[position++]=threadnum;
pthread_mutex_unlock(&mutex);
acquire(&mutex);
}
pthread_mutex_unlock(&mutex);
return 0;
}
int *histo;
void printres(int numthreads)
{
int i;
printf("Results: ");
for( i=0; i<numthreads; ++i )
printf("%d ", histo[i]);
printf("\n");
}
int main(int argc, char * argv[] )
{
int numthreads=atoi(argv[1]);
if( argc<2 || numthreads==0 )
exit(1);
pthread_t *threads=calloc(sizeof(pthread_t), numthreads);
histo=calloc(sizeof(int), numthreads);
int i;
int oldpos=position;
for( i=0; i<numthreads; ++i ) {
pthread_create(threads+i, NULL, (void *(*)(void *))worker, (void *)i);
}
/* Reap the results every second */
while( oldpos<TEST_SIZE ) {
sleep(1);
for( ; oldpos<position; ++oldpos ) {
histo[results[oldpos]]++;
}
printres(numthreads);
}
for( i=0; i<numthreads; ++i ) {
pthread_join( threads[i], NULL );
printf("Joined thread #%d\n", i);
}
return 0;
}
