Parallel Processing Analysis: Sequential vs. fork() vs. Pthreads

This project filters and aggregates 1,000,000 sales records spread across 20 CSV files in C, using three strategies: a sequential baseline, multiprocessing (fork() with results passed back through mmap shared memory), and multithreading (POSIX threads). Each strategy is benchmarked at 2 to 20 workers, and the results are checked against Amdahl's Law.

Headline: 4 threads give a 2.81× speedup (0.790 s → 0.282 s) on a 4-core VM. The fitted serial fraction is 22.4%, which caps any speedup at 4.46× no matter how many cores are added.

---

The task

The user picks a filter (Region, Country, Item Type or Sales Channel) and a value, for example Region = Europe. The program scans every record and reports:

• the number of matching orders
• total revenue
• total profit

All three implementations return identical results (259,402 orders, $345.9 B revenue, $101.9 B profit for Europe). The only differences are in the last few decimal places of the floating-point sums, because the addition order changes with parallel aggregation.

How each approach works

Approach	Mechanism	Work split	Result collection
Sequential (naive.c)	One loop over all 20 files	—	Local accumulators
Multiprocessing (mp.c)	fork() N children, parent wait()s	Each child gets a contiguous range of files	Per-child slots in mmap(MAP_SHARED | MAP_ANONYMOUS) arrays, summed by the parent
Multithreading (mth.c)	pthread_create() N threads, then pthread_join()	Same file-range split, passed in a ThreadData struct	Each thread writes its own struct field; no locks needed

Neither parallel version needs a mutex, because every worker writes only to its own slot. The only synchronisation is the final wait() / pthread_join() barrier.

Parsing uses a single fscanf format string with %*[^,] to skip the columns that aren't needed, so no per-line strtok pass is required.

---

Benchmark results

Setup: Intel i5-1135G7 (4C/8T) · Linux VM (VirtualBox, 4 vCPUs, 4 GB RAM) · GCC · timed with clock_gettime(CLOCK_MONOTONIC) · query Region = Europe

Approach	Workers	Time (s)	Speedup	Efficiency
Sequential	1	0.790	1.00×	100%
Multiprocessing	2	0.473	1.67×	83%
Multiprocessing	4	0.330	2.39×	60%
Multiprocessing	8	0.394	2.01×	25%
Multiprocessing	16	0.372	2.12×	13%
Multiprocessing	20	0.256	3.08×	15%
Multithreading	2	0.418	1.89×	94%
Multithreading	4	0.282	2.81×	70%
Multithreading	8	0.345	2.29×	29%
Multithreading	16	0.350	2.25×	14%
Multithreading	20	0.281	2.81×	14%

Speedup = T_sequential / T_parallel; efficiency = speedup / workers. Raw output is in osProject/files/results.txt.

Threads vs. processes, head to head: threads win at 2, 4, 8 and 16 workers (by 6 to 15%). Creating a thread is cheaper than fork(), and threads share an address space, so they avoid the page-table copy and the mmap setup.

---

Amdahl's Law analysis

$$S(n) = \frac{1}{f + \frac{1 - f}{n}}$$

where f is the serial (non-parallelisable) fraction of the runtime.

Fitting f: using the 4-process measurement, S(4) = 0.790 / 0.330 = 2.391:

$$\frac{1}{2.391} = f + \frac{1-f}{4} ;\Rightarrow; f = \frac{0.4182 - 0.25}{0.75} \approx \mathbf{0.224}$$

This means ~22.4% of the runtime is serial: input handling, spawning workers, the join barrier, aggregation and output. The remaining ~77.6% parallelises.

Workers n	Amdahl S(n)	Measured (processes)	Measured (threads)
2	1.63×	1.67×	1.89×
4	2.39×	2.39× (fit point)	2.81×
8	3.11×	2.01×	2.29×
16	3.67×	2.12×	2.25×
20	3.80×	3.08×	2.81×
∞	4.46×	—	—

Reading the table:

• Up to 4 workers the model fits well, and threads beat it. That's expected, since f was fitted on the more expensive fork() path and threads have less spawn overhead.
• Beyond 4 workers the VM has only 4 vCPUs, so the extra workers time-share the same cores. That adds scheduling and context-switch overhead with no extra parallelism, and Amdahl's model (which assumes n real processors) no longer applies.
• The ceiling: even with infinite cores, a 22.4% serial fraction limits speedup to 1 / 0.224 ≈ 4.46×.

Why 8 and 16 workers are slower than 4

The dip at 8 and 16 workers isn't only oversubscription. It's load imbalance built into the file split:

int FilesPerChild = NumOfFiles / NumOfChildren;   // integer division
...
if (j == NumOfChildren - 1) endFile = NumOfFiles; // last worker takes the remainder

Workers	Files per worker	Busiest worker (critical path)
4	5 each	5 files
8	2 each, last one gets 6	6 files
16	1 each, last one gets 5	5 files
20	1 each	1 file

Every run is only as fast as its busiest worker. With 8 workers the busiest one handles more files than with 4, so it's slower. With 20 workers the split is perfectly even, which is why both approaches recover there.

A round-robin or ceiling-division split (start = j*20/N, end = (j+1)*20/N) would fix this. It's the first item under Possible improvements.

---

Build & run

Requires Linux (or WSL) with GCC.

cd osProject
make            # builds main, naive, mp, mth
./main          # interactive menu → choose approach, filter, value, worker count

Or run a single approach directly: ./naive, ./mp or ./mth. Each run appends to files/results.txt.

osProject/
├── main.c      # menu driver
├── naive.c     # sequential baseline
├── mp.c        # fork() + mmap shared memory
├── mth.c       # POSIX threads
├── Makefile
└── files/
    ├── sales-data-1M/   # xaa.csv … xat.csv (20 × 50,000 rows)
    └── results.txt      # appended timing log

Possible improvements

• Balanced partitioning (start = j*N_FILES/N) to remove the 8- and 16-worker penalty.
• Repeated trials (median of k runs), to smooth out VM timing noise.
• Row-level work splitting, so the number of workers isn't limited by the number of files.
• mmap the input files and parse them in place, instead of going through stdio.

---

Operating Systems (ENCS3390), Birzeit University, Fall 2025.