Assignment 2 — Operating-System Simulator

01 Overview

This assignment is worth 20% 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 CLO3 (scheduling, synchronization, and deadlock analysis), CLO4 (memory and virtual-memory management), CLO5 (file systems, storage, and I/O), CLO6 (Linux systems programming and tools), and CLO8 (design and implementation of OS-related components).

03 Choose your option

You must choose exactly one of the three simulator options below. Each option is comparable in difficulty and scope; the choice is yours. Read all three before deciding, and record your choice in your design document.

04 Option A — CPU Scheduler Simulator

4.1 Functional requirements

1. A-F1 — Trace input. The simulator reads a trace of process arrivals. Each line specifies: arrival time, process ID, CPU burst length, priority, and an optional I/O burst pattern (a sequence of CPU bursts separated by I/O waits). The format is documented in the trace file's header.
2. A-F2 — Algorithm selection. The simulator supports at least the following algorithms, selectable by a command-line flag:
   • fcfs — First-Come, First-Served.
   • sjf — Shortest Job First (non-preemptive).
   • srtf — Shortest Remaining Time First (preemptive SJF).
   • rr <quantum> — Round Robin with a configurable quantum (in time units).
   • priority <mode> — Priority scheduling, with mode = preemptive or non-preemptive.
   • mlfq — Multilevel Feedback Queue with at least three levels, configurable quanta per level, and an aging policy that prevents starvation.
3. A-F3 — Multi-core simulation. The simulator supports N CPUs (selectable by a flag, default 1). Each CPU has its own ready queue or shares a global ready queue, depending on a configuration flag. The simulator implements a documented load-balancing policy (for example, work stealing or periodic migration) and reports the per-CPU utilisation.
4. A-F4 — Timeline output. The simulator produces a timeline (a Gantt-style textual representation) that shows which process runs on which CPU at each time step. The timeline is optional for large traces (a flag controls whether it is printed) but is always available for small traces.
5. A-F5 — Metrics. At the end of the run, the simulator computes and prints:
   • Average turnaround time, average waiting time, and average response time, per process and overall.
   • CPU utilisation (per CPU and overall), and throughput (processes completed per time unit).
   • Number of context switches, and the total context-switch overhead (a configurable cost per switch).
   • For priority and MLFQ: the number of processes that were starved (waited longer than a configurable threshold), and the maximum wait time.
   • For multi-core: the load imbalance (maximum per-CPU busy time minus minimum), and the number of migrations.
6. A-F6 — Parameters. A configuration file (or command-line flags) specifies the context-switch cost, the I/O model (fixed or random I/O durations), the number of CPUs, and the ready-queue policy. The parameters are recorded in the output so that a run can be reproduced exactly.
7. A-F7 — Reproducibility. The simulator's output is deterministic given the trace, the algorithm, and the parameters. If the I/O model uses randomness, the random seed is a parameter and is printed in the output.

4.2 Required analyses

In the report, you must include the following analyses:

1. Algorithm comparison. Run all six algorithms on the same set of traces (at least four: a batch trace with long bursts, an interactive trace with short bursts, a mixed trace, and a trace with a convoy). For each algorithm and trace, report all metrics. Identify the algorithm that minimises average waiting time, the one that minimises average response time, and the one that maximises throughput. Explain why the winners differ.
2. Quantum sweep. For Round Robin, sweep the quantum from 1 to 100 time units in steps of 1, and plot average turnaround time and context-switch overhead as functions of the quantum. Identify the quantum at which the turnaround time is minimised, and explain why the curve has the shape it does. Confirm the rule of thumb that the quantum should be slightly larger than the majority of CPU bursts.
3. Multi-core scaling. Fix the algorithm to Round Robin (or SRTF) and sweep the number of CPUs from 1 to 8. Report the throughput and the load imbalance. Compute the speedup relative to the single-CPU case, and compare it to the prediction of Amdahl's Law. Explain the sources of inefficiency as the CPU count grows.
4. Starvation analysis. Construct a trace that starves a low-priority process under non-preemptive priority scheduling. Measure the maximum wait time, then enable aging and measure it again. Report the trade-off: what happens to the average wait time of the high-priority processes when aging is enabled?
5. Convoy effect. Construct a trace in which a long CPU-bound process arrives first, followed by several short I/O-bound processes. Run FCFS and SJF. Report the difference in average response time and in CPU utilisation, and explain the convoy effect quantitatively.

05 Option B — Virtual Memory Simulator

5.1 Functional requirements

1. B-F1 — Reference-string input. The simulator reads a reference string: a sequence of virtual page numbers, optionally annotated with an access type (R for read, W for write) and a process ID (for multi-programming experiments). The format is documented.
2. B-F2 — Replacement algorithms. The simulator supports at least the following algorithms, selectable by a command-line flag:
   • fifo — First-In, First-Out.
   • lru — Least Recently Used (exact, implemented with a timestamp or a stack).
   • clock — Clock (Second-Chance), with a configurable reference-bit clear policy.
   • esc — Enhanced Second-Chance, which uses both the reference bit and the dirty bit.
   • lfu — Least Frequently Used, with a configurable reset policy.
   • opt — Optimal (Belady's algorithm), used as a benchmark.
3. B-F3 — Frames and page size. The number of physical frames and the page size are configurable. The simulator reports the memory footprint of its own data structures (page table, TLB simulation if applicable) so that the student can analyse the overhead of the management structures themselves.
4. B-F4 — TLB simulation. Optionally, the simulator includes a TLB of configurable size and associativity. When the TLB is enabled, the simulator distinguishes TLB hits from TLB misses and reports the TLB hit rate and the effective access time (using a configurable TLB hit cost, TLB miss cost, and page-fault cost).
5. B-F5 — Metrics. At the end of the run, the simulator computes and prints:
   • Total references, page faults, and page-fault rate.
   • For each frame: the number of pages that occupied it, the total time it was occupied, and the number of evictions.
   • Write-back count: the number of dirty pages that were evicted (requiring a disk write).
   • For the reference string: the working-set size over time (with a configurable window Δ), and the maximum working-set size.
   • If the TLB is enabled: TLB hit rate, TLB miss count, effective access time.
6. B-F6 — Reproducibility. The output is deterministic given the reference string, the algorithm, the number of frames, and the parameters. If the reference string is generated randomly, the seed is a parameter and is printed in the output.

5.2 Required analyses

1. Algorithm comparison on a fixed reference string. Use a reference string of at least 10,000 references. Run all six algorithms with the same number of frames (for example, 16). Report the fault count and the write-back count for each. Verify that OPT produces the minimum fault count and quantify the gap between OPT and each of the others.
2. Frame sweep. For each algorithm, sweep the number of frames from 1 to 64 in steps of 1 and plot the fault count as a function of the number of frames. Confirm that the curves are monotone for LRU, OPT, and Clock, and identify the anomaly for FIFO: find a reference string and a pair of frame counts (n, n+1) for which FIFO produces more faults with n+1 frames than with n. Report the string and the two fault counts.
3. Locality and workload type. Generate four reference strings with different locality characteristics: (a) sequential, (b) looping over a small working set, (c) uniformly random, (d) strong locality with occasional jumps. For each, report the fault count for each algorithm and identify which algorithm performs best and why. Compute the working-set size over time for each and relate it to the performance of the algorithms.
4. Thrashing. Construct a multi-programmed workload in which the sum of the working sets exceeds the number of frames. Measure the fault rate as the number of concurrent processes increases. Show the characteristic thrashing curve: a rapid increase in the fault rate above a threshold number of processes. Then implement a simple working-set policy that suspends processes whose working sets do not fit, and show that the fault rate recovers.
5. TLB and effective access time. With the TLB enabled, sweep the TLB size from 4 to 256 entries and plot the effective access time. Explain the shape of the curve in terms of TLB coverage and the working-set size.

06 Option C — File-System Simulator

6.1 Functional requirements

1. C-F1 — Operation trace. The simulator reads a trace of file-system operations. Each line is one of: create <name> <size>, read <name> <offset> <len>, write <name> <offset> <len>, append <name> <size>, truncate <name> <size>, unlink <name>, mkdir <name>, readdir <name>, stat <name>. The format is documented.
2. C-F2 — Inode structure. The simulator models an inode with the following fields: mode, owner, group, size, atime, mtime, ctime, link count, and block pointers. The block pointers follow the classical scheme: 12 direct pointers, one single-indirect pointer, one double-indirect pointer, and one triple-indirect pointer. The block size is configurable.
3. C-F3 — Free-block management. The simulator supports at least two free-block management strategies, selectable by a flag:
   • bitmap — a bitmap with first-fit allocation.
   • extents — an extent-based allocator with best-fit allocation.
4. C-F4 — Directory organisation. The simulator supports at least two directory organisations, selectable by a flag:
   • linear — a linear list of name-to-inode entries.
   • htree — a hash-based directory index (simulated), which allows O(1) lookup.
5. C-F5 — Crash simulation. The simulator supports an optional "crash" command in the trace. On a crash, the simulator records the state of the file system and then, optionally, applies a recovery procedure. Two recovery models are supported:
   • fsck — a full consistency check and repair, which scans the entire disk.
   • journal — replay of a simulated journal, which is faster but may lose data that was not yet committed.
6. C-F6 — Metrics. At the end of the run, the simulator computes and prints:
   • Disk utilisation: allocated blocks / total blocks.
   • Internal fragmentation: total bytes allocated minus total bytes requested, and the ratio.
   • External fragmentation: the number and size distribution of free runs.
   • Metadata overhead: blocks used for inodes, indirect blocks, and directory entries, as a fraction of total blocks.
   • For each operation type: the average number of disk blocks read, the average number written, and the average number of inode reads.
   • For directory operations: the average number of directory entries examined per lookup.
   • For the recovery experiments: the recovery time (in simulated disk operations) for each recovery model.
7. C-F7 — Reproducibility. The output is deterministic given the trace and the configuration. If the trace is generated randomly, the seed is a parameter and is printed in the output.

6.2 Required analyses

1. Allocation comparison. Run a workload of at least 100,000 operations under each allocator (bitmap + first-fit, extents + best-fit). Report the metrics above for each. Identify the workload patterns under which each allocator performs best. Construct one workload that produces significant external fragmentation under the bitmap allocator and show that the extent allocator handles it better.
2. Large-file analysis. Construct a workload that creates files of increasing size (up to at least 1 GB). Show how the number of indirect blocks grows as the file size crosses the boundaries of the direct, single-indirect, double-indirect, and triple-indirect regions. Verify the maximum file size against the theoretical value computed from the block size and the pointer size.
3. Directory performance. Create a directory with 1,000, 10,000, and 100,000 entries. Measure the average number of directory entries examined per lookup under the linear and htree organisations. Plot the result and confirm that linear lookup is O(n) and htree is O(1).
4. Fragmentation. Construct a workload that creates and deletes files in a pattern designed to fragment the disk. Measure the internal and external fragmentation over time. Then run a "defragmentation" pass that consolidates free space, and measure the improvement. Explain why defragmentation is rarely performed on modern file systems.
5. Crash and recovery. Construct a workload that crashes in the middle of a multi-step operation (for example, between allocating a data block and updating the inode). Run the workload with both recovery models and report: the recovery time, the amount of data lost, and the consistency of the file system afterwards. Explain the trade-off between the two models in terms of the classic performance-versus-consistency trade-off.

07 Common requirements for all options

The following requirements apply to all three options. They are the non-functional requirements that distinguish a working simulator from a well-engineered one.

7.1 Interface and configuration

1. Command-line interface. The simulator is invoked as sim [options] <trace-file>. It supports at least: -a <algorithm> (or --algorithm), -c <config-file>, -o <output>, -v (verbose), -h (help). The help output lists every option, its default, and a one-line description.
2. Configuration file. Every parameter that can be set by a flag can also be set in a configuration file. The file is documented in the report and a sample is provided in configs/.
3. Output format. The simulator produces at least two output files:
   • A human-readable summary, printed to standard output or to the file specified by -o.
   • A machine-readable summary (CSV), which is used to produce the plots in the report. The CSV has a stable header line so that a script can parse it.

7.2 Workload generation

1. Synthetic traces. The simulator includes a trace generator (a separate program or a mode of the simulator) that produces workloads with configurable characteristics: the arrival rate or reference distribution, the locality, the size distribution, the read/write mix, and the seed. The generator is documented and the generated traces are included in the submission as compressed files.
2. Reference traces. For each option, the assignment specifies the characteristics of at least four reference traces that the simulator must handle. The traces are generated by the student and are included in the submission.
3. Scaling. The simulator must process a trace with at least 1,000,000 events in under 30 seconds on the virtual machine, with the default configuration. (This is not a strict performance requirement; it is a usability requirement. A simulator that takes an hour per run cannot be used for the analyses in § 4.2, § 5.2, or § 6.2.)

7.3 Correctness and validation

1. Hand-computed reference cases. For each algorithm, the student constructs a small trace (10–20 events) and computes the expected output by hand. The simulator's output is checked against the hand-computed result. The trace, the hand-computed result, and the simulator's output are all included in the report.
2. Reference implementation. The student writes a second, independent implementation of the simplest algorithm (FCFS, FIFO, or bitmap allocation) — a naive, single-function version — and verifies that the full simulator produces the same results on the small traces. The reference implementation is included in the submission as tests/reference/.
3. Invariant checks. The simulator includes, under a compile-time flag, a set of invariant checks that are executed after every event. Examples: for the scheduler, the sum of the CPU busy times plus the idle time equals the elapsed time; for the memory simulator, the total number of pages in memory plus the number of free frames equals the total number of frames; for the file system, the sum of allocated blocks plus the number of free blocks equals the total number of blocks. The invariants are documented and the flag is enabled for the test runs.
4. Valgrind. The simulator runs cleanly under valgrind --leak-check=full on a small trace. The output is included in the submission.

7.4 Code quality

1. The code compiles with gcc -Wall -Wextra -Werror -O2 without warnings.
2. The code is modular: each major subsystem (trace reader, algorithm, statistics, output) is in its own file with a header file that declares its public interface.
3. The algorithm is selected at run time by a function pointer, so that adding a new algorithm requires adding a new implementation and registering it, without modifying the existing code. This is an application of the open-closed principle.
4. Every system call's return value is checked, and every error is reported with context (what was being done, which file, which argument).
5. The code has no global mutable state other than the simulator's own state structure, which is passed explicitly to the functions that need it.

08 Milestones and suggested schedule

The assignment is designed to be completed over five weeks. The milestones below are not graded separately, but they are checked during office hours and are a strong predictor of the final grade.

09 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.

10 Submission instructions

Submit a single archive named a2-<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 -O2. Suggested files (adapt to your option):
  • sim.c — the main entry point and option parsing.
  • trace.c, trace.h — the trace reader and the trace generator.
  • state.c, state.h — the simulator's state structure and its initialisation, reset, and cleanup functions.
  • algorithm.c, algorithm.h — the algorithm registry (a table of function pointers) and the common algorithm interface.
  • algo_*.c — one file per algorithm (for example, algo_fcfs.c, algo_rr.c for Option A; algo_fifo.c, algo_lru.c for Option B; algo_bitmap.c, algo_extent.c for Option C).
  • metrics.c, metrics.h — the metric accumulators and their computation.
  • output.c, output.h — the human-readable and CSV output writers.
  • invariants.c, invariants.h — the invariant checks, compiled in only when the flag is set.
• Makefile — builds the executable sim and a make clean target. The default target must compile without warnings. A separate target builds the version with invariant checks enabled.
• tests/ — the test inputs, outputs, and scripts:
  • tests/traces/ — the small and medium traces used for the correctness tests, and the hand-computed expected results.
  • tests/reference/ — the naive reference implementation and its Makefile.
  • tests/run-tests.sh — a script that runs the required tests T1–T12 and prints a pass/fail summary.
  • tests/generate-traces.sh — a script that generates the large traces (1,000,000 events) from a seed, so that the archive remains small.
• configs/ — the configuration files used for the required analyses. Each file is documented with comments.
• logs/ — the outputs of the required tests. At minimum:
  • logs/valgrind.txt — the leak-check output on a small trace.
  • logs/invariants.txt — the invariant-check output on a small trace.
  • logs/timing.txt — the timings for T11.
  • logs/reproducibility.txt — the diff output from T10.
• analysis/ — the data and scripts for the required analyses:
  • analysis/data/ — the CSV files produced by the simulator for each analysis.
  • analysis/plots/ — the plots (PNG or PDF) referenced in the report.
  • analysis/plot.py (or a similar script) — the script that generates the plots from the CSV data.
• README.md — build instructions, usage examples, and a short description of the architecture and the chosen option.
• report.pdf (or report.md) — the technical report described in § 11.
• design-notes.md — the design document produced at the Week 9 milestone.

11 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 and the algorithms. It should be 12–15 pages (excluding code listings and raw logs) and must contain the following sections.

1. Introduction (1 page). The subsystem you chose to simulate, the algorithms you implemented, and a summary of the findings.
2. Design (3–4 pages). The state, the events, and the event loop. A class diagram or a module diagram showing the interfaces between the components. The algorithm registry and the interface that every algorithm implements. The metric accumulators and where they are updated. The data structures and their complexity. The design decisions you made and the alternatives you rejected, with reasons.
3. Algorithms (2–3 pages). For each algorithm, a precise description: the state it maintains, the decision rule, the update rule, and the complexity of each operation. A worked example on a small trace, with the intermediate state shown.
4. Correctness evidence (2 pages). The hand-computed reference cases and the simulator's output for each. The comparison with the naive reference implementation. The invariant checks and their results. The Valgrind output. Any deviation and its diagnosis.
5. Analyses (4–5 pages). The five required analyses for your option. Present the data as tables and plots. For each analysis, state the question, the method, the result, and the interpretation. The interpretation must be quantitative wherever possible — for example, "the fault rate under FIFO is 12% higher than under LRU on the locality trace, because FIFO evicts the loop's working set while LRU retains it."
6. Reflection (1–2 pages). A discussion of what you learned about the subsystem, about simulator design, and about the relationship between the model and the real system. What assumptions does your simulator make, and how would they affect the conclusions if the simulator were used to make decisions about a real operating system? What would you simulate next if you had another two weeks?

12 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.

12.1 Requirements coverage (20 points)

12.2 Algorithm correctness (25 points)

12.3 System design (20 points)

12.4 Testing and validation (15 points)

12.5 Documentation (10 points)

12.6 Code quality (10 points)

13 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. 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 scheduling simulator from Lab 4, the page-replacement simulator from Lab 8, or the file-allocation simulator from Lab 9), provided you understand it and can explain it. Extending your own lab work is expected and encouraged.
• Using standard library functions and system calls.
• Using plotting libraries (gnuplot, matplotlib, or a similar tool) for the analyses.
• Using code-generation tools (for example, an AI assistant) for boilerplate (Makefile, argument parsing, CSV output), 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 simulator or the results of the analyses.

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.

14 Resources

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed. Chapters 5 (CPU scheduling), 9–10 (memory management), 13–15 (file systems).
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces. Chapters 7–10 (scheduling), 18–23 (virtual memory), 39–43 (file systems).
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed. Chapters 2 (processes and threads), 3 (memory management), 4 (file systems).
• Jain, R. The Art of Computer Systems Performance Analysis. Wiley, 1991 (for the methodology of the performance analyses: warm-up, repetitions, confidence intervals).
• Law, A. M., & Kelton, W. D. Simulation Modeling and Analysis. McGraw-Hill, 5th ed., 2014 (for discrete-event simulation methodology).
• Denning, P. J. The Working Set Model for Program Behavior. Communications of the ACM, 1968.
• Belady, L. A., Nelson, R. A., & Shedler, G. S. An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine. Communications of the ACM, 1969.
• McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984.
• Rosenblum, M., & Ousterhout, J. K. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, 1992.
• Linux man-pages: man 3 pthread_create, man 2 mmap, man 2 open, man 3 printf, man 3 getline.