Performance Tests
This page contains the results of performance tests on all the presented approaches, and how to interpret them. For each algorithm multiple simulation runs are averaged to come up with individual scores. This is also done for each of the four distributions, since algorithm performance is very different depending on which distribution is used.
Degree of concurrency
The concurrency score (CS) is calculated by averaging several simulation runs, in this case 20. For simulation runs with 5 philosophers, scores close to two indicate ideal concurrency, while those under one indicate no concurrency. Since concurrent performance also depends heavily on the chosen distribution, the concurrency scores from the different distributions are averaged. Four classes are used to classify algorithms according to this Average Concurrency Score:
| Average Concurrency Score (Average CS) | Ranges |
|---|---|
| No Concurrency | 0 - 1.0 |
| Moderate Concurrency | 1.0 - 1.5 |
| Good Concurrency | 1.5 - 1.7 |
| High Concurrency | 1.7 - 2.0 |
Fairness
The two scores for eat-chance fairness, and eat-time fairness are again obtained by averaging several simulation runs.
| FS | Fairness Score |
|---|---|
| ECFS | Eat Chance Fairness Score |
| ETFS | Eat Time Fairness Score |
As both metrics are standard deviations of philosophers eat-chances or eat-times lower values indicate better fairness. Algorithm improvements are calculated in percentage decrease of standard deviation compared to the base versions of fairness enhancing algorithms. Fair Waiter is compared to Pickup Permission Waiter, Fair Tanenbaum is compared to Tanenbaum, The Circulating Token, and Restrict Token algorithms are compared to the Naive approach. Improvements above 20% can be interpreted as being significant.
Test Results
| Interval Distribution: Lower Bound = 30 ms, Upper Bound = 300 ms | ||||
|---|---|---|---|---|
| Runs per algorithm: 20 | ||||
| Simulation time: 2000 time steps | ||||
| Number of Philosophers: 5 | ||||
| Algorithm | CS | ECFS | ETFS | FS Improvement |
| Naive | 1.3259 | 0.8841 | 49.9816 | |
| Hierarchy | 1.7062 | 2.0007 | 74.0217 | |
| Asymmetric | 1.7398 | 1.9537 | 70.3715 | |
| Global Token | 0.9819 | 0.3715 | 40.3125 | 57.98% ECFS |
| Multiple Token | 1.6660 | 0.3966 | 53.2681 | 55.14% ECFS |
| Timeout (200 ms) | 1.7097 | 1.3554 | 57.9897 | |
| Instant Timeout | 1.7480 | 1.3620 | 55.2102 | |
| Eat Permission Waiter | 0.9896 | 0.5657 | 43.3324 | |
| Pickup Permission Waiter | 1.4371 | 0.9212 | 47.2592 | |
| Intelligent Waiter | 1.5580 | 1.0574 | 42.1599 | |
| Fair Eat-Time Waiter | 1.4808 | 1.2977 | 22.9090 | 51.53% ETFS |
| Fair Eat-Chance Waiter | 1.4737 | 0.3831 | 47.3039 | 58.42% ECFS |
| Two Waiters | 1.6421 | 1.6271 | 70.4407 | |
| Restrict Waiter | 1.4541 | 0.8325 | 51.4794 | |
| Table Semaphore | 1.4232 | 0.7400 | 52.9547 | |
| Restrict | 1.3584 | 0.8677 | 45.6994 | |
| Tanenbaum | 1.8070 | 1.3966 | 57.9705 | |
| Fair Eat-Time Tanenbaum | 1.8179 | 1.3611 | 58.6103 | |
| Fair Eat-Chance Tanenbaum | 1.8040 | 1.3168 | 54.5071 | 5.71% ECFS |
| Chandy-Misra | 1.6890 | 0.9507 | 51.7728 | |
| Eat-Chance Restrict Token | 1.5982 | 0.4425 | 62.5900 | 50% ECFS |
| Eat-Time Restrict Token | 1.6509 | 1.6404 | 28.7441 | 42.5% ETFS |
| Deterministic Distribution: delay = 100 ms | ||||
|---|---|---|---|---|
| Runs per algorithm: 20 | ||||
| Simulation time: 2000 time steps | ||||
| Number of Philosophers: 5 | ||||
| Algorithm | CS | ECFS | ETFS | FS Improvement |
| Naive | 1.1326 | 0.02 | 2.448 | |
| Hierarchy | 1.9647 | 0.9892 | 18.255 | |
| Asymmetric | 1.9665 | 1.2643 | 23.046 | |
| Global Token | 0.9847 | 0.0000 | 2.026 | 100% ECFS |
| Multiple Token | 1.9673 | 0.1580 | 4.668 | |
| Timeout | 1.9556 | 0.2605 | 6.093 | |
| Instant Timeout | 1.8162 | 0.7595 | 13.929 | |
| Eat Permission Waiter | 0.9841 | 0.0000 | 2.324 | |
| Pickup Permission Waiter | 1.7022 | 0.3863 | 7.854 | |
| Intelligent Waiter | 1.9097 | 0.3876 | 7.688 | |
| Fair Eat-Time Waiter | 1.6065 | 0.3515 | 6.849 | 12.8% ETFS |
| Fair Eat-Chance Waiter | 1.6768 | 0.3521 | 6.749 | 8.85% ECFS |
| Two Waiters | 1.8787 | 3.7277 | 67.677 | |
| Restrict Waiter | 1.7378 | 0.5759 | 11.406 | |
| Table Semaphore | 1.6365 | 0.4405 | 7.834 | |
| Restrict | 1.4751 | 0.0445 | 3.309 | |
| Tanenbaum | 1.9667 | 1.0002 | 18.288 | |
| Fair Eat-Time Tanenbaum | 1.9664 | 1.0896 | 19.660 | |
| Fair Eat-Chance Tanenbaum | 1.9671 | 1.3587 | 24.507 | |
| Chandy-Misra | 1.9150 | 0.3490 | 5.045 | |
| Eat-Chance Restrict Token | 1.9282 | 0.3592 | 7.490 | |
| Eat-Time Restrict Token | 1.9402 | 0.4049 | 8.179 | |
| Normal Distribution: μ = 100, σ = 50 | ||||
|---|---|---|---|---|
| Runs per algorithm: 20 | ||||
| Simulation time: 2000 time steps | ||||
| Number of Philosophers: 5 | ||||
| Algorithm | CS | ECFS | ETFS | FS Improvement |
| Naive | 1.3076 | 1.0550 | 34.4418 | |
| Hierarchy | 1.7193 | 3.1025 | 63.2627 | |
| Asymmetric | 1.7295 | 3.6586 | 50.0086 | |
| Global Token | 0.9792 | 0.2870 | 28.6236 | 72.8% ECFS |
| Multiple Token | 1.6713 | 0.4425 | 44.8131 | 58.08% ECFS |
| Timeout(200 ms) | 1.5960 | 1.8319 | 38.2872 | |
| Instant Timeout | 1.6739 | 2.3361 | 35.7533 | |
| Eat Permission Waiter | 0.9893 | 0.5588 | 31.0267 | |
| Pickup Permission Waiter | 1.4610 | 0.9458 | 38.3785 | |
| Intelligent Waiter | 1.5923 | 1.0981 | 38.2553 | |
| Fair Eat-Time Waiter | 1.4857 | 1.7760 | 15.1961 | 60.4% ETFS |
| Fair Eat-Chance Waiter | 1.4652 | 0.5399 | 37.7595 | 42.92% ECFS |
| Two Waiters | 1.6478 | 2.5900 | 60.8600 | |
| Restrict Waiter | 1.4468 | 1.0093 | 39.5061 | |
| Table Semaphore | 1.4884 | 1.1110 | 39.2123 | |
| Restrict | 1.2140 | 1.2382 | 29.7509 | |
| Tanenbaum | 1.8190 | 1.7965 | 44.6516 | |
| Fair Eat-Time Tanenbaum | 1.8078 | 1.8818 | 41.0264 | 8.12% ETFS |
| Fair Eat-Chance Tanenbaum | 1.8163 | 1.6008 | 46.6639 | 10.89% ECFS |
| Chandy-Misra | 1.4666 | 2.0112 | 22.1077 | |
| Eat-Chance Restrict Token | 1.5573 | 0.4445 | 24.3643 | 57.87% ECFS |
| Eat-Time Restrict Token | 1.6537 | 2.1990 | 21.4949 | 37.59% ETFS |
| Exponential Distribution: λ = 5 | ||||
|---|---|---|---|---|
| Runs per algorithm: 20 | ||||
| Simulation time: 2000 time steps | ||||
| Number of Philosophers: 5 | ||||
| Algorithm | CS | ECFS | ETFS | FS Improvement |
| Naive | 1.2601 | 1.1093 | 78.9417 | |
| Hierarchy | 1.5417 | 2.5310 | 99.9440 | |
| Asymmetric | 1.6314 | 2.7123 | 86.6127 | |
| Global Token | 0.9693 | 0.3115 | 67.2010 | 71.92% ECFS |
| Multiple Token | 1.4187 | 0.3386 | 96.9850 | 69.48% ECFS |
| Timeout(200 ms) | 1.5938 | 1.8307 | 81.4835 | |
| Instant Timeout | 1.6732 | 2.1489 | 88.6110 | |
| Eat Permission Waiter | 0.9912 | 0.9338 | 74.7230 | |
| Pickup Permission Waiter | 1.3412 | 1.2805 | 72.0612 | |
| Intelligent Waiter | 1.4401 | 1.3214 | 75.8088 | |
| Fair Eat-Time Waiter | 1.3444 | 1.6717 | 37.5872 | 47.84% ETFS |
| Fair Eat-Chance Waiter | 1.3832 | 0.5494 | 84.6811 | 57.09% ECFS |
| Two Waiters | 1.5052 | 1.7907 | 95.0338 | |
| Restrict Waiter | 1.3771 | 1.3168 | 77.0305 | |
| Table Semaphore | 1.3541 | 1.1065 | 85.5687 | |
| Restrict | 1.3380 | 1.3526 | 64.0767 | |
| Tanenbaum | 1.7342 | 2.0393 | 62.3498 | |
| Fair Time Tanenbaum | 1.7247 | 2.2296 | 81.7054 | |
| Fair Chance Tanenbaum | 1.7160 | 1.8871 | 76.2188 | 7.46% ECFS |
| Chandy-Misra | 1.5739 | 1.1275 | 74.7704 | |
| Eat-Chance Restrict Token | 1.4768 | 0.7649 | 90.1537 | 31.05% ECFS |
| Eat-Time Restrict Token | 1.4947 | 1.8447 | 44.6132 | 43.49% ETFS |
| Algorithm | Average CS | Subcategory |
|---|---|---|
| Naive | 1.25655 | Moderate Concurrency |
| Hierarchy | 1.732975 | High Concurrency |
| Asymmetric | 1.7668 | High Concurrency |
| Global Token | 0.978775 | No Concurrency |
| Multiple Token | 1.680825 | Good Concurrency |
| Timeout(200 ms) | 1.713775 | High Concurrency |
| Instant Timeout | 1.727825 | High Concurrency |
| Eat Permission Waiter | 0.98855 | No Concurrency |
| Pickup Permission Waiter | 1.485375 | Moderate Concurrency |
| Intelligent Waiter | 1.625025 | Good Concurrency |
| Fair Eat-Time Waiter | 1.47935 | Moderate Concurrency |
| Fair Eat-Chance Waiter | 1.499725 | Moderate Concurrency |
| Two Waiters | 1.66845 | Good Concurrency |
| Restrict Waiter | 1.50395 | Good Concurrency |
| Table Semaphore | 1.47555 | Moderate Concurrency |
| Restrict | 1.346375 | Moderate Concurrency |
| Tanenbaum | 1.831725 | High Concurrency |
| Fair Eat-Time Tanenbaum | 1.8292 | High Concurrency |
| Fair Eat-Chance Tanenbaum | 1.82585 | High Concurrency |
| Chandy-Misra | 1.661125 | Good Concurrency |
| Eat-Chance Restrict Token | 1.640125 | Good Concurrency |
| Eat-Time Restrict Token | 1.684875 | Good Concurrency |