Assignment 1 — Parallel Log Analyzer

01 Overview

This assignment is worth 15% of the final grade. Late submission penalty: 10% per day up to three days; after three days, submission is accepted only with documented extenuating circumstances.

02 Learning outcomes assessed

This assignment assesses CLO2 (process and thread management), CLO3 (scheduling, synchronization, and deadlock), CLO6 (Linux systems programming and tools), and CLO8 (design and implementation of OS-related components).

03 The scenario

You are building the analysis engine for a small log-management service. The service receives a directory of log files produced by a fleet of application servers. Each log file is a line-oriented text file in the following format:

2024-03-15T14:22:07.412Z  INFO   api-server-03  GET /v1/orders 200 43ms
2024-03-15T14:22:07.418Z  WARN   api-server-01  slow query: orders_by_customer 812ms
2024-03-15T14:22:07.421Z  ERROR  api-server-03  connection reset by peer
2024-03-15T14:22:07.423Z  INFO   api-server-02  POST /v1/orders 201 91ms
...

Each line contains, in order: an ISO-8601 timestamp with milliseconds, a level (DEBUG, INFO, WARN, ERROR), a source identifier, and a free-form message. The analyzer must produce a summary report containing:

• Total number of lines processed, per level.
• Per-source line counts (a histogram of source identifiers).
• A per-minute time series: for each minute in the interval covered by the logs, the count of lines at each level.
• The top 10 most frequent error messages (normalised: digits replaced by # so that connection 192.168.1.5 and connection 192.168.1.7 are counted together).
• The 95th percentile of the latency field (the trailing <n>ms in the message, when present), per level.

The system must be concurrent: it must use multiple processes and multiple threads, and it must scale to tens of gigabytes of logs on a machine with a modest number of cores. It must also be robust: it must handle malformed lines, missing files, and an interrupt (Ctrl-C) without leaving orphaned processes, zombie processes, or partially written output.

04 Functional and non-functional requirements

4.1 Functional requirements

1. F1 — Command-line interface. The program is invoked as pla [options] <directory>. It supports at least the following options:
   • -p <n> — number of worker processes (default: number of CPU cores, capped at 8).
   • -t <n> — number of threads per worker process (default: 2).
   • -q <n> — capacity of the in-worker bounded buffer (default: 256 records).
   • -o <file> — write the report to a file instead of standard output.
   • -v — verbose; print per-file and per-worker progress to standard error.
   • -h — print usage and exit.
2. F2 — Discovery. The master process recursively scans the given directory for files whose name ends in .log and produces a work list. It prints the total number of files and the total byte size before processing begins.
3. F3 — Distribution. The master forks P worker processes. Each worker receives a share of the file list. Files are distributed dynamically: a worker that finishes its current file asks the master for another, so that a large file at the end does not leave other workers idle.
4. F4 — In-worker parallelism. Each worker reads its assigned file in chunks and sends parsed records to a bounded buffer consumed by T threads. The reader is a single producer; the T threads are consumers.
5. F5 — Per-worker statistics. Each worker maintains its own statistics structure (level counts, source histogram, per-minute time series, error message table, latency samples). Updates to this structure are made under a mutex, or via per-thread partial structures that are merged at the end (you choose; justify the choice in the report).
6. F6 — Aggregation. When a worker finishes, it sends its statistics to the master over a pipe (using a well-defined binary protocol) and exits with status 0. The master reads all statistics, merges them, and produces the final report.
7. F7 — Report. The master writes the report described in § 03 to standard output or to the file specified by -o. The report is deterministic: two runs on the same input produce byte-identical output (except for the elapsed-time line).
8. F8 — Error handling. Malformed lines are counted but not parsed; a summary line reports the number of malformed lines. Missing or unreadable files are reported to standard error and skipped; the run continues.
9. F9 — Signal handling. On SIGINT (Ctrl-C), the master sends SIGTERM to all workers, waits up to 5 seconds for them to exit, then sends SIGKILL to any stragglers. Workers handle SIGTERM by finishing the current record, flushing partial statistics to the master, and exiting cleanly. No zombie or orphan process is left behind.
10. F10 — Exit status. The program exits with 0 on success, 1 on a fatal error (for example, the directory does not exist), and 2 if the run was interrupted.

4.2 Non-functional requirements

1. N1 — Correctness. No line is lost, no line is counted twice, and the report is consistent with a single-threaded reference implementation on every test input.
2. N2 — No races, deadlocks, or leaks. Running under valgrind --tool=helgrind and valgrind --tool=drd produces no data-race reports (other than those explicitly caused by signal handlers, which must be documented). Running under valgrind --leak-check=full produces no leaks.
3. N3 — Scalability. With a large input (at least 1 GB of logs) and P × T = number of cores, the program achieves at least 70% of the theoretical speedup predicted by Amdahl's Law, where the serial fraction is the final aggregation step. Report the measured speedup for P ∈ {1, 2, 4, 8} with T = 2.
4. N4 — Portability. The program compiles with gcc -Wall -Wextra -Werror -pthread -O2 on Linux without warnings.
5. N5 — Documentation. Every source file begins with a header comment stating its purpose, its author, and the date. Every non-trivial function is documented with a short comment stating its contract. A README.md describes how to build, run, and test the program.

05 Suggested architecture

You are free to design the system as you see fit, but the following architecture is known to work and is offered as a starting point. Deviations are permitted and encouraged if you can justify them in the report.

5.1 Master process

The master performs four tasks: it discovers the input files, it forks workers and distributes work, it collects statistics from the workers, and it writes the final report. It also handles SIGINT and SIGCHLD.

• Work distribution uses a pipe pair per worker: the master writes a file path when the worker asks for one, or writes an end-of-stream marker when the list is exhausted. (An alternative is a shared-memory queue with a mutex and condition variables; either is acceptable.)
• Statistics collection uses a separate pipe pair per worker. The worker sends a fixed-size header followed by variable-length payload; the master reads the header, reads the payload, and merges the statistics into its own accumulators.
• The master reaps children with waitpid, either in a SIGCHLD handler (careful: waitpid is not async-signal-safe on all systems, so a self-pipe or sigwait is safer) or in a loop after all work has been distributed.

5.2 Worker process

Each worker runs a single reader thread (the main thread) and T consumer threads. The reader reads records from the current file and places them in the bounded buffer; the consumers pull records from the buffer and update the worker's statistics structure.

• The bounded buffer is a circular array protected by a mutex and two condition variables (not_full, not_empty), or by three semaphores (empty, full, mutex). Either is acceptable; justify your choice.
• Each consumer thread has a private partial statistics structure to minimise contention. At the end of the run, the worker's main thread merges the partial structures. (This is an optimisation; a single structure with a mutex is also acceptable if the lock is held only briefly.)
• The reader is the only producer. It must handle a partial last line, an empty file, and a file that grows while it is being read (the specification does not require handling the last case; state your assumption in the report).

5.3 Graceful shutdown

The master installs a handler for SIGINT. The handler sets a flag (declared volatile sig_atomic_t) and writes a byte to a self-pipe; the master's main loop watches the self-pipe. When the flag is set, the master:

1. Sends SIGTERM to each worker.
2. Waits up to 5 seconds, using waitpid with a loop and nanosleep, for the workers to exit.
3. Sends SIGKILL to any worker still alive.
4. Reaps all remaining children.
5. Prints a partial report to standard error (or writes it to the output file) and exits with status 2.

Each worker installs a handler for SIGTERM that sets a flag read by the reader and the consumers. The reader stops reading, closes the input, and signals the buffer's end-of-stream. The consumers drain the buffer, merge their statistics, send them to the master, and exit with status 0. The worker must not exit before its statistics are sent — otherwise the master loses that worker's contribution.

06 Milestones and suggested schedule

The assignment is designed to be completed over four weeks. The milestones below are not graded separately, but they are checked during office hours and are a strong predictor of the final grade. Submit each milestone's artefact (a short design note, a working prototype, or a test log) before the next milestone begins.

07 Required test cases

You must run the following tests and include the results in your report. Each test is described by its input, the command that runs it, and the property that must hold. You may add your own tests; the ones below are the minimum.

08 Submission instructions

Submit a single archive named a1-<lastname>-<studentnumber>.tar.gz containing the following files and directories:

• src/ — the C source files. Every source file must compile with gcc -Wall -Wextra -Werror -pthread -O2. Suggested files:
  • pla.c — the main entry point and option parsing.
  • master.c, master.h — the master process: discovery, forking, work distribution, aggregation, signals.
  • worker.c, worker.h — the worker process: reading, thread pool, buffer, statistics collection.
  • buffer.c, buffer.h — the bounded buffer.
  • stats.c, stats.h — the statistics structure, its update functions, and its merge function.
  • parser.c, parser.h — the line parser.
  • report.c, report.h — the report writer.
  • protocol.h — the wire format used between master and worker.
• Makefile — builds the executable pla and a make clean target. The default target must compile without warnings.
• tests/ — the test inputs and outputs. At minimum:
  • tests/input-small/ — a small directory of log files used for the correctness tests.
  • tests/expected-small.txt — the expected report for input-small.
  • tests/run-tests.sh — a script that runs the required tests and prints a pass/fail summary.
  • tests/generate.sh — a script that generates the larger inputs (100 MB) from a seed file, so that the archive remains small.
• logs/ — the outputs of the required tests. At minimum:
  • logs/helgrind.txt — the Helgrind output on the small input.
  • logs/drd.txt — the DRD output on the small input.
  • logs/valgrind-leak.txt — the leak-check output.
  • logs/perf.txt — the timing data for the scaling experiments (T13–T15).
  • logs/sigint.txt — the transcript of the SIGINT test, showing the exit status and the absence of zombies.
• README.md — build instructions, usage examples, and a short description of the architecture.
• report.pdf (or report.md) — the technical report described in § 09.
• design-notes.md — the design document produced at the Week 5 milestone.

09 Technical report

The technical report is worth 10% of the assignment grade and is the primary evidence of your understanding of the design trade-offs. It should be 8–10 pages (excluding code listings and raw logs) and must contain the following sections.

1. Introduction (½ page). The problem statement, the goals of the system, and a short summary of the architecture.
2. Architecture (1–2 pages). A diagram of the process and thread structure, with a clear description of the master, the workers, the reader, and the consumer threads. Describe the work-distribution protocol and the statistics-collection protocol at a level sufficient for a reader to re-implement them.
3. Synchronization design (2 pages). For each shared data structure, state which primitive protects it and why. For the bounded buffer, give the invariant that the buffer maintains and argue informally that your code preserves it. Explain how you avoid deadlock (lock ordering, try-lock with back-off, or a wait-for graph analysis), and how you avoid starvation (fair queues, aging, or a design argument).
4. Signal handling (1 page). The signal handlers you install, the async-signal-safe operations they perform, and how the shutdown sequence is coordinated between the master and the workers. Explain why printf, malloc, and pthread_mutex_lock must not be called from a signal handler, and show what you did instead.
5. Correctness evidence (2 pages). The results of the required tests T1–T12, presented as a table with the expected and observed results. Include the Helgrind, DRD, and leak-check summaries. For any deviation, give the diagnosis and the fix.
6. Performance analysis (2 pages). The results of tests T13–T15, presented as a table and as a plot of speedup versus number of worker processes × threads. Compute the serial fraction from your measurements and compare it to your prediction. Discuss the sources of overhead (process creation, context switching, lock contention, cache-line bouncing, pipe traffic) and how they affect the scaling curve. Identify the point at which adding more workers stops helping, and explain why.
7. Reflection (1 page). A discussion of what you would do differently if you were starting over. Which design decision proved most important? Which primitive or pattern was most error-prone, and how did you catch the bugs? What did you learn about concurrent programming that you did not know before?

10 Grading rubric

The assignment is marked out of 100 points. The criteria, their weights, and the associated CLOs are given below, followed by the five-level descriptors for each criterion.

10.1 Process implementation (15 points)

10.2 Thread implementation (20 points)

10.3 Synchronization design (25 points)

10.4 Correctness (20 points)

10.5 Code quality (10 points)

10.6 Technical report (10 points)

11 Academic integrity

This assignment is individual work. You may discuss the general approach with classmates, and you may consult textbooks, man pages, and online resources for specific technical questions (for example, the signature of pthread_cond_wait or the semantics of SIGCHLD). You must not copy code from another student, from a previous offering of the course, or from an online source without attribution, and you must not share your code with another student.

The following are specifically permitted:

• Using the course's lab code as a starting point for the individual components (for example, the bounded buffer from Lab 5), provided you understand it and can explain it.
• Using standard library functions and system calls.
• Using code-generation tools (for example, an AI assistant) for boilerplate (Makefile, argument parsing), provided you review the generated code, understand it, and take responsibility for it. You must disclose any such use in the report.

The following are prohibited:

• Copying code from another student or from a public repository without attribution.
• Having another person write any part of your code or your report.
• Submitting a report that misrepresents the performance of your code.

Suspected violations are handled according to the university's academic integrity policy. The penalty for a first offence is a grade of zero on the assignment; a second offence results in a grade of F in the course.

12 Resources

• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces. Chapters 4–7 (processes), 25–27 (threads and concurrency), 28–31 (locks, condition variables, semaphores), 32 (deadlock).
• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed. Chapters 3–4 (processes and threads), 6–8 (synchronization and deadlock).
• Stevens, W. R., & Rago, S. A. Advanced Programming in the UNIX Environment, 3rd ed. Chapters 8–10 (process control, signals), 15–16 (interprocess communication, network IPC).
• Kerrisk, M. The Linux Programming Interface. Chapters 24–28 (process creation, termination, monitoring), 29–33 (threads), 44–47 (pipes and FIFOs), 53–54 (POSIX semaphores, shared memory).
• Linux man-pages: man 2 fork, man 2 execve, man 2 wait, man 2 pipe, man 2 signal, man 7 signal, man 3 pthread_create, man 3 pthread_mutex_lock, man 3 pthread_cond_wait, man 3 sem_init, man 7 mq_overview, man 7 shm_overview.
• Valgrind documentation: Helgrind and DRD sections.
• Butenhof, D. R. Programming with POSIX Threads. Addison-Wesley, 1997.
• Drepper, U. How to Write Shared Libraries (for background on dynamic linking, not directly required).