Evaluation Data

Optimistic Semaphores with Nondeterministic Choice
Operation for Heterogeneous Manycore Systems:
Evaluation Data
Enrique Soriano-Salvador
Gorka Guardiola Muzquiz
Francisco J. Ballesteros
LSUB, GSyC, ETSIT
Universidad Rey Juan Carlos
{esoriano,paurea,nemo}@lsub.org
July 4, 2014
1
Experiment 1: Simple Mutex
• α graphs. Tukey diagrams showing the time within the critical section, including the time
required to acquire and release the mutex, in ns. It does not include the time wasted
outside the non-critical section. The size of the non-critical section (N SS), the number
of cores, and the number of concurrent processes are fixed for each graph. The X-axis
represents the size of the critical section (CSS). The times for the standard semaphores
(semacquire system call) are labeled as Std. The times for the optimistic semaphores are
labeled as Nix.
• β graphs. Tukey graphs showing the time required to increment the shared counter for
different ratios between the size of the critical section and the non-critical section. The
X-axis represents the ratio. The number of cores and processes are fixed for each graph.
• γ graphs. 3D histograms showing the ratio of semaphore operations that enter the kernel,
in %. The X-axis represents the size of the non-critical section. The Y-axis represents the
size of the critical section.
Section 4.1 presents the results for executing the experiment on 32 TCs. Section 4.2 presents
the results for 28 ACs.
2
Experiment 2: Semalt
• δ graphs: Like in the previous experiment, α are Tukey graphs showing the time required
to increment the shared counter (time in the critical section, including the time required
to acquire and release the mutex) in ns. Note that the time does not include the time
wasted in the non-critical section. The size of the non-critical section (NSS), the number
of cores, the number of concurrent processes, and the number of semaphores in the array
1
(and shared counters) are fixed for each graph. The X-axis represents the size of the critical
section (CSS). The times for the the implementation with standard semaphores are labeled
as Std. The times for the optimistic semaphores are labeled as Nix.
• graphs: Histograms showing the number of increments on each semaphore of the array.
Note that the altsems implementation tries to be fair to prevent starvation. These graphs
are shown only for 50 processes and 10 semaphores. to illustrate the difference between the
distribution of the semaphore usage for the both programs executed in this experiment.
Section 4.3 shows the results for 32 TCs.
3
Experiment 3: Tubes
• ζ graphs: Tukey graphs showing the time required to complete a round, in ns. This graphs
also represents the mean (with a point). Each graph presents the times for the three IPC
mechanisms, for different message sizes. The number of pongers is fixed for each figure.
Section 4.4 shows the results for executing the experiment on 32 TCs. Section 4.5 presents
the results for executing on 28 ACs.
2
4
Results
4.1
Experiment 1, 32 TC
4.1.1
α graphs
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 5 procs, NSS=10
(b) 5 procs, NSS=100
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 5 procs, NSS=1000
(d) 5 procs, NSS=10000
Figure 1: α graphs for 5 procs running in TCs.
3
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 5 procs, NSS=10
(b) 5 procs, NSS=100
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 5 procs, NSS=1000
(d) 5 procs, NSS=10000
Figure 2: α graphs for 5 procs running in TCs, non-blocking down()
4
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 10 procs, NSS=10
(b) 10 procs, NSS=100
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 10 procs, NSS=1000
(d) 10 procs, NSS=10000
Figure 3: α graphs for 10 procs running in TCs.
5
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 10 procs, NSS=10
(b) 10 procs, NSS=100
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
20000
nix
std
20000
10000
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 10 procs, NSS=1000
(d) 10 procs, NSS=10000
Figure 4: α graphs for 10 procs running in TCs, non-blocking down()
6
150000
Sem
100000
Time
Time
150000
nix
std
Sem
100000
nix
std
50000
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 20 procs, NSS=10
(b) 20 procs, NSS=100
200000
150000
Sem
100000
Sem
Time
Time
150000
nix
std
50000
100000
nix
std
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(c) 20 procs, NSS=1000
(d) 20 procs, NSS=10000
Figure 5: α graphs for 20 procs running in TCs.
7
30000
30000
20000
20000
Sem
Time
Time
Sem
nix
std
10000
nix
std
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 20 procs, NSS=10
(b) 20 procs, NSS=100
30000
30000
20000
20000
Sem
Time
Time
Sem
nix
std
10000
nix
std
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 20 procs, NSS=1000
(d) 20 procs, NSS=10000
Figure 6: α graphs for 20 procs running in TCs, non-blocking down()
8
1500000
1500000
1000000
1000000
Sem
Time
Time
Sem
nix
std
nix
std
500000
500000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 50 procs, NSS=10
(b) 50 procs, NSS=100
1500000
1500000
1000000
1000000
Sem
Time
Time
Sem
nix
std
nix
std
500000
500000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(c) 50 procs, NSS=1000
(d) 50 procs, NSS=10000
Figure 7: α graphs for 50 procs running in TCs.
9
10000
10000
Sem
Time
Time
Sem
nix
std
5000
nix
std
5000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 50 procs, NSS=10
(b) 50 procs, NSS=100
15000
10000
10000
Sem
nix
std
Time
Time
Sem
nix
std
5000
5000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 50 procs, NSS=1000
(d) 50 procs, NSS=10000
Figure 8: α graphs for 50 procs running in TCs, non-blocking down()
10
4e+06
4e+06
3e+06
3e+06
Sem
Time
Time
Sem
nix
std
2e+06
1e+06
nix
std
2e+06
1e+06
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 100 procs, NSS=10
(b) 100 procs, NSS=100
4e+06
4e+06
3e+06
3e+06
Sem
nix
std
Time
Time
Sem
2e+06
nix
2e+06
std
1e+06
1e+06
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 100 procs, NSS=1000
(d) 100 procs, NSS=10000
Figure 9: α graphs for 100 procs running in TCs.
11
12000
12000
10000
10000
8000
8000
Sem
Time
Time
Sem
nix
6000
std
nix
6000
4000
4000
2000
2000
std
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 100 procs, NSS=10
(b) 100 procs, NSS=100
12000
10000
10000
8000
Sem
nix
std
6000
Time
Time
Sem
nix
std
5000
4000
2000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 100 procs, NSS=1000
(d) 100 procs, NSS=10000
Figure 10: α graphs for 100 procs running in TCs, non-blocking down()
12
4.1.2
β graphs
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
40000
40000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
30000
30000
●
●
Sem
●
●
Time
●
●
●
●
●
●
●
●
●
●
●
●
●
●
std
●
●
20000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
nix
●
●
●
●
●
●
●
●
●
●
std
●
●
●
●
20000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Sem
●
nix
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Time
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
10000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
10000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0
0.1
1
10
100
1000
10000
1e+05
●
●
●
●
●
●
0.1
1
Ratio % (Critical Section / Non−Critical Section)
10
100
1000
(b) 10 procs
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
40000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
30000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
20000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Sem
●
●
●
●
●
●
nix
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
std
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
10000
●
●
●
●
●
●
●
●
0
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0.1
10000
Ratio % (Critical Section / Non−Critical Section)
(a) 5 procs
Time
0
1
10
100
1000
10000
1e+05
Ratio % (Critical Section / Non−Critical Section)
(c) 20 procs
Figure 11: β graphs for 5, 10 and 20 procs running in TCs
13
1e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
4e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
1e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Time
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
std
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
1e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
2e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
nix
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Sem
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
3e+05
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
5e+04
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Time
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Sem
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
nix
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
std
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0e+00
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0e+00
0.1
1
10
100
1000
10000
1e+05
0.1
Ratio % (Critical Section / Non−Critical Section)
1
10
100
1000
10000
Ratio % (Critical Section / Non−Critical Section)
(a) 50 procs
(b) 100 procs
Figure 12: β graphs for 50 and 100 procs running in TCs
14
1e+05
4.1.3
γ graphs
Ratio System Calls/Semaphore Operations (5 procs)
Ratio System Calls/Semaphore Operations (10 procs)
Call
Call
80
6000
4000
2000
0
2000
0
6000
8000
10000
0
0
2000
4000
Critical Section
6000
8000
10000
Critical Section
(a) 5 procs
(b) 10 procs
Ratio System Calls/Semaphore Operations (20 procs)
Call
Ratio %
40
60
80
100
down
up
10000
8000
6000
4000
Non−Critical Section
4000
20
2000
2000
0
0
0
0
2000
4000
6000
8000
10000
Critical Section
(c) 20 procs
Figure 13: γ graphs for 5, 10 and 20 procs running in TCs
15
Non−Critical Section
60
Ratio %
40
10000
8000
20
20
6000
4000
Non−Critical Section
10000
8000
0
Ratio %
40
60
80
100
down
up
100
down
up
Ratio System Calls/Semaphore Operations (50 procs)
Ratio System Calls/Semaphore Operations (100 procs)
Call
Call
80
6000
4000
2000
0
2000
0
0
2000
4000
6000
8000
10000
0
0
Critical Section
2000
4000
6000
8000
10000
Critical Section
(a) 50 procs
(b) 100 procs
Figure 14: γ graphs for 50 and 100 procs running in TCs
16
Non−Critical Section
60
Ratio %
40
10000
8000
20
20
4000
Non−Critical Section
10000
8000
6000
0
Ratio %
40
60
80
100
down
up
100
down
up
4.2
Experiment 1, 28 AC
4.2.1
α graphs
80000
80000
60000
60000
Sem
Time
Time
Sem
nix
40000
std
40000
nix
std
20000
20000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 4 procs, NSS=10
(b) 4 procs, NSS=100
80000
80000
60000
60000
Sem
nix
std
Time
Time
Sem
40000
nix
40000
std
20000
20000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 4 procs, NSS=1000
(d) 4 procs, NSS=10000
Figure 15: α graphs for 4 procs running in ACs.
17
80000
80000
60000
60000
Sem
Time
Time
Sem
nix
40000
std
20000
nix
40000
std
20000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 4 procs, NSS=10
(b) 4 procs, NSS=100
80000
80000
60000
60000
Sem
nix
std
Time
Time
Sem
40000
40000
nix
std
20000
20000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 4 procs, NSS=1000
(d) 4 procs, NSS=10000
Figure 16: α graphs for 4 procs running in ACs, non-blocking down()
18
80000
80000
60000
60000
Sem
Time
Time
Sem
nix
40000
std
20000
nix
40000
std
20000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 8 procs, NSS=10
(b) 8 procs, NSS=100
80000
80000
60000
60000
Sem
nix
std
Time
Time
Sem
40000
20000
nix
40000
std
20000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 8 procs, NSS=1000
(d) 8 procs, NSS=10000
Figure 17: α graphs for 8 procs running in ACs.
19
80000
80000
60000
60000
Sem
Time
Time
Sem
nix
40000
std
40000
nix
std
20000
20000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 8 procs, NSS=10
(b) 8 procs, NSS=100
80000
80000
60000
60000
Sem
nix
std
Time
Time
Sem
40000
40000
nix
std
20000
20000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 8 procs, NSS=1000
(d) 8 procs, NSS=10000
Figure 18: α graphs for 8 procs running in ACs, non-blocking down()
20
200000
200000
150000
150000
Sem
Time
Time
Sem
nix
100000
std
50000
nix
100000
std
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 16 procs, NSS=10
(b) 16 procs, NSS=100
250000
200000
200000
150000
150000
Sem
nix
std
Time
Time
Sem
nix
std
100000
100000
50000
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(c) 16 procs, NSS=1000
(d) 16 procs, NSS=10000
Figure 19: α graphs for 16 procs running in ACs.
21
50000
50000
40000
40000
30000
30000
Sem
Time
Time
Sem
nix
std
nix
std
20000
20000
10000
10000
0
0
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 16 procs, NSS=10
(b) 16 procs, NSS=100
50000
50000
40000
40000
30000
30000
nix
std
Sem
Time
Time
Sem
nix
std
20000
20000
10000
10000
0
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 16 procs, NSS=1000
(d) 16 procs, NSS=10000
Figure 20: α graphs for 16 procs running in ACs, non-blocking down()
22
6e+05
6e+05
4e+05
4e+05
Sem
Time
Time
Sem
nix
std
2e+05
nix
std
2e+05
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 24 procs, NSS=10
(b) 24 procs, NSS=100
6e+05
6e+05
4e+05
nix
std
Time
Time
Sem
2e+05
Sem
4e+05
nix
std
2e+05
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 24 procs, NSS=1000
(d) 24 procs, NSS=10000
Figure 21: α graphs for 24 procs running in ACs.
23
4.2.2
β graphs
80000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
80000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
60000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
60000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
Sem
Time
Time
Sem
nix
40000
std
●
●
●
●
nix
40000
std
●
●
●
●
●
●
●
●
●
●
20000
20000
●
●
●
●
●
0
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0
●
0.1
1
10
100
1000
10000
●
1e+05
0.1
Ratio % (Critical Section / Non−Critical Section)
1
10
(a) 4 procs
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
1000
10000
1e+05
(b) 8 procs
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
120000
●
●
●
●
●
●
●
●
●
●
●
100
Ratio % (Critical Section / Non−Critical Section)
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
80000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
100000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
60000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
80000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
nix
std
Time
Time
Sem
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
40000
Sem
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
60000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
nix
●
●
●
●
●
●
●
●
●
●
std
●
●
●
●
●
●
●
●
●
●
●
●
40000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
20000
20000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0
●
●
●
●
0.1
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0
1
10
100
1000
10000
1e+05
●
●
●
●
●
●
●
●
0.1
Ratio % (Critical Section / Non−Critical Section)
1
10
100
1000
10000
Ratio % (Critical Section / Non−Critical Section)
(c) 16 procs
(d) 24 procs
Figure 22: β graphs for procs running in ACs
24
1e+05
γ graphs
Ratio System Calls/Semaphore Operations (4 procs)
Ratio System Calls/Semaphore Operations (8 procs)
Call
Call
80
6000
4000
2000
0
0
2000
0
0
2000
4000
6000
8000
10000
0
0
2000
Critical Section
4000
(a) 4 procs
8000
10000
(b) 8 procs
Ratio System Calls/Semaphore Operations (16 procs)
Ratio System Calls/Semaphore Operations (24 procs)
Call
Call
80
Ratio %
40
60
20
4000
10000
8000
20
10000
8000
6000
Non−Critical Section
40
60
80
100
down
up
100
down
up
6000
4000
2000
0
2000
0
Ratio %
6000
Critical Section
0
0
2000
4000
6000
8000
10000
0
0
Critical Section
2000
4000
6000
8000
10000
Critical Section
(c) 16 procs
(d) 24 procs
Figure 23: γ graphs for procs running in ACs
25
Non−Critical Section
40
Ratio %
60
20
4000
10000
8000
20
10000
8000
6000
Non−Critical Section
40
Ratio %
60
80
100
down
up
100
down
up
Non−Critical Section
4.2.3
4.3
Experiment 2, 32 TC
4.3.1
δ graphs
4e+05
4e+05
3e+05
3e+05
Sem
Time
Time
Sem
nix
2e+05
std
1e+05
nix
2e+05
std
1e+05
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 10 procs, 2 semaphores, NSS=10
(b) 10 procs, 2 semaphores, NSS=100
4e+05
3e+05
3e+05
nix
std
Time
Time
Sem
2e+05
Sem
2e+05
nix
std
1e+05
1e+05
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 10 procs, 2 semaphores, NSS=1000
(d) 10 procs, 2 semaphores, NSS=10000
Figure 24: δ graphs for 10 procs running in TCs.
26
200000
200000
150000
150000
Sem
Time
Time
Sem
100000
nix
std
100000
nix
std
50000
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 10 procs, 5 semaphores, NSS=10
(b) 10 procs, 5 semaphores, NSS=100
1e+05
150000
8e+04
Sem
nix
std
Time
Time
6e+04
Sem
100000
nix
std
4e+04
50000
2e+04
0
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 10 procs, 5 semaphores, NSS=1000
(d) 10 procs, 5 semaphores, NSS=10000
Figure 25: δ graphs for 10 procs running in TCs.
27
1e+05
8e+04
8e+04
Sem
6e+04
Time
Time
1e+05
nix
std
nix
std
4e+04
4e+04
2e+04
2e+04
0e+00
Sem
6e+04
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 10 procs, 10 semaphores, NSS=10
(b) 10 procs, 10 semaphores, NSS=100
1e+05
80000
8e+04
60000
6e+04
Sem
nix
std
Time
Time
Sem
nix
std
40000
4e+04
20000
2e+04
0e+00
0
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 10 procs, 10 semaphores, NSS=1000
(d) 10 procs, 10 semaphores, NSS=10000
Figure 26: δ graphs for 10 procs running in TCs.
28
8e+05
8e+05
6e+05
6e+05
Sem
Time
Time
Sem
nix
4e+05
std
2e+05
nix
4e+05
std
2e+05
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 20 procs, 2 semaphores, NSS=10
(b) 20 procs, 2 semaphores, NSS=100
8e+05
8e+05
6e+05
6e+05
Sem
nix
std
Time
Time
Sem
4e+05
4e+05
nix
std
2e+05
2e+05
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 20 procs, 2 semaphores, NSS=1000
(d) 20 procs, 2 semaphores, NSS=10000
Figure 27: δ graphs for 20 procs running in TCs.
29
4e+05
4e+05
3e+05
3e+05
Sem
Time
Time
Sem
nix
2e+05
std
1e+05
nix
2e+05
std
1e+05
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 20 procs, 5 semaphores, NSS=10
(b) 20 procs, 5 semaphores, NSS=100
4e+05
4e+05
3e+05
3e+05
Sem
nix
std
2e+05
Time
Time
Sem
nix
2e+05
std
1e+05
1e+05
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 20 procs, 5 semaphores, NSS=1000
(d) 20 procs, 5 semaphores, NSS=10000
Figure 28: δ graphs for 20 procs running in TCs.
30
300000
300000
250000
250000
200000
200000
Sem
Time
Time
Sem
nix
150000
std
nix
150000
100000
100000
50000
50000
0
std
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 20 procs, 10 semaphores, NSS=10
(b) 20 procs, 10 semaphores, NSS=100
250000
300000
250000
200000
200000
150000
Sem
nix
150000
std
Time
Time
Sem
nix
std
100000
100000
50000
50000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(c) 20 procs, 10 semaphores, NSS=1000
(d) 20 procs, 10 semaphores, NSS=10000
Figure 29: δ graphs for 20 procs running in TCs.
31
2000000
2000000
1500000
1500000
Sem
Time
Time
Sem
nix
1000000
std
500000
nix
1000000
std
500000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 50 procs, 2 semaphores, NSS=10
(b) 50 procs, 2 semaphores, NSS=100
2000000
2000000
1500000
1500000
Sem
nix
std
Time
Time
Sem
1000000
500000
nix
1000000
std
500000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(c) 50 procs, 2 semaphores, NSS=1000
(d) 50 procs, 2 semaphores, NSS=10000
Figure 30: δ graphs for 50 procs running in TCs.
32
1200000
1200000
1000000
1000000
800000
800000
Sem
Time
Time
Sem
nix
600000
std
600000
nix
std
400000
400000
200000
200000
0
0
10
100
1000
10000
10
100
1000
10000
Critical Section
Critical Section
(a) 50 procs, 5 semaphores, NSS=10
(b) 50 procs, 5 semaphores, NSS=100
1200000
1000000
1e+06
800000
Sem
nix
std
Time
Time
Sem
600000
nix
std
5e+05
400000
200000
0
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 50 procs, 5 semaphores, NSS=1000
(d) 50 procs, 5 semaphores, NSS=10000
Figure 31: δ graphs for 50 procs running in TCs.
33
1e+06
1e+06
8e+05
8e+05
6e+05
6e+05
Sem
Time
Time
Sem
nix
std
nix
std
4e+05
4e+05
2e+05
2e+05
0e+00
0e+00
10
100
1000
10000
10
100
Critical Section
1000
10000
Critical Section
(a) 50 procs, 10 semaphores, NSS=10
(b) 50 procs, 10 semaphores, NSS=100
1e+06
1e+06
8e+05
8e+05
6e+05
6e+05
Sem
nix
std
Time
Time
Sem
nix
std
4e+05
4e+05
2e+05
2e+05
0e+00
0e+00
10
100
1000
10000
10
Critical Section
100
1000
10000
Critical Section
(c) 50 procs, 10 semaphores, NSS=1000
(d) 50 procs, 10 semaphores, NSS=10000
Figure 32: δ graphs for 50 procs running in TCs.
34
4.3.2
graphs
Nix
Std
Total
2000
0
0
1000
5000
Total
10000
3000
15000
4000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
Sem4
Sem6
Sem8
Semaphore
(a) 50 procs, 10 semaphores, CSS= 10, NSS=10
(b) 50 procs, 10 semaphores, CSS= 10, NSS=100
Nix
Std
3000
Total
0
0
1000
1000
2000
2000
Total
3000
4000
5000
4000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Semaphore
Sem2
Sem4
Sem6
Sem8
Semaphore
(c) 50 procs, 10 semaphores, CSS= 10 NSS=1000 (d) 50 procs, 10 semaphores, CSS= 10, NSS=10000
Figure 33: graphs for 50 procs, 10 semaphores and CSS=10, running in TCs.
35
7000
5000
6000
3000
Total
4000
5000
4000
0
0
1000
1000
2000
2000
3000
Total
Nix
Std
6000
7000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
Sem6
Sem8
Semaphore
(b) 50 procs, 10 semaphores, CSS= 100, NSS=100
8000
(a) 50 procs, 10 semaphores, CSS= 100, NSS=10
Nix
Std
Total
4000
4000
5000
6000
6000
7000
Nix
Std
0
0
1000
2000
2000
3000
Total
Sem4
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Semaphore
Sem2
Sem4
Sem6
Sem8
Semaphore
(c) 50 procs, 10 semaphores, CSS= 100, NSS=1000 (d) 50 procs, 10 semaphores, CSS= 100, NSS=10000
Figure 34: graphs for 50 procs, 10 semaphores and CSS=100, running in TCs.
36
15000
Nix
Std
Total
0
0
5000
5000
Total
10000
10000
15000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
Sem4
Sem6
Sem8
Semaphore
(a) 50 procs, 10 semaphores, CSS= 1000, NSS=10 (b) 50 procs, 10 semaphores, CSS= 1000, NSS=100
15000
Nix
Std
Total
0
0
5000
5000
Total
10000
10000
15000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
Sem4
Sem6
Sem8
Semaphore
(c) 50 procs, 10 semaphores, CSS= 1000, NSS=1000 (d) 50 procs,
NSS=10000
10
semaphores,
CSS=
1000,
Figure 35: graphs for 50 procs, 10 semaphores and CSS=1000, running in TCs.
37
8000
8000
4000
Total
6000
Nix
Std
0
0
2000
2000
4000
Total
6000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
Sem4
Sem6
Sem8
Semaphore
8000
8000
(a) 50 procs, 10 semaphores, CSS= 10000, NSS=10 (b) 50 procs, 10 semaphores, CSS= 10000, NSS=100
Total
6000
Nix
Std
0
0
2000
4000
4000
2000
Total
6000
Nix
Std
Sem0
Sem2
Sem4
Sem6
Sem8
Sem0
Sem2
Semaphore
(c) 50 procs,
NSS=1000
10
semaphores,
Sem4
Sem6
Sem8
Semaphore
CSS=
10000, (d) 50 procs,
NSS=10000
10
semaphores,
CSS=
10000,
Figure 36: graphs for 50 procs, 10 semaphores and CSS=10000, running in TCs.
38
4.4
Experiment 4, 32 TC
4.4.1
ζ graphs
50000
50000
●
●
●
●
●
●
●
●
●
●
●
40000
●
IPC
●
●
●
●
●
●
●
chan
●
pipe
●
tube
●
●
●
Time
Time
●
●
IPC
●
40000
●
●
●
●
chan
●
pipe
●
tube
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
30000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
30000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
32
64
512
4096
●
●
●
●
●
8
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
32
Message size (b)
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
8
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
64
512
4096
Message size (b)
(a) 1 ponger
(b) 8 pongers
55000
55000
50000
50000
●
●
45000
45000
●
●
●
●
●
●
●
●
●
●
40000
IPC
●
40000
●
●
●
IPC
●
●
●
chan
●
pipe
●
●
●
●
●
Time
Time
●
●
●
●
●
chan
●
pipe
●
tube
●
●
●
●
●
●
●
●
tube
●
●
●
●
●
●
●
●
●
●
●
●
●
35000
●
●
●
●
35000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
30000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
8
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
32
64
512
(d) 24 pongers
Figure 37: ζ graphs, running in TCs.
39
●
●
●
●
●
●
●
●
●
●
●
●
●
Message size (b)
(c) 16 pongers
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
4096
●
●
●
●
●
●
●
●
●
●
512
●
●
●
●
●
●
●
●
Message size (b)
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
64
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
32
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
8
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
25000
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
25000
30000
●
●
●
●
4096
4.5
Experiment 4, 28 AC
4.5.1
ζ graphs
8e+06
8e+06
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
6e+06
6e+06
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
IPC
●
●
●
●
IPC
Time
●
●
●
●
●
chan
●
pipe
●
●
●
Time
●
●
●
●
●
●
●
4e+06
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
chan
●
pipe
●
tube
4e+06
●
●
tube
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
2e+06
●
●
●
●
●
●
●
●
●
●
●
2e+06
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
0e+00
0e+00
8
32
64
512
4096
8
32
Message size (b)
64
512
4096
Message size (b)
(a) 1 ponger
(b) 8 pongers
8e+06
8e+06
6e+06
6e+06
●
●
●
●
●
●
●
●
●
chan
●
pipe
●
●
●
IPC
●
Time
Time
IPC
4e+06
●
●
●
tube
●
●
●
●
●
●
●
●
●
●
●
●
●
●
2e+06
2e+06
●
0e+00
0e+00
8
32
64
512
4096
8
Message size (b)
32
64
512
Message size (b)
(c) 16 pongers
(d) 24 pongers
Figure 38: ζ graphs, running in ACs.
40
●
chan
●
pipe
●
tube
4e+06
4096
●