Programming labs
Write the program yourself, then compare with the model solution. The problems follow the chapters, from the first programs to object-oriented design.
CPS 3250 · 84 labs
How many programs keep the CPU busy? (multiprogramming model)
Use the multiprogramming model utilization = 1 − pⁿ to size an EdgeCampus server. Input: lines p target maxN until the end of input, where p is the I/...
Amdahl's law: is renting more servers worth it?
A faculty member asks how many cloud servers to rent for a simulation. Help them with Amdahl's law. Input: first line P minEfficiency — the parallel f...
A tiny `top`: summarize a process snapshot
Linux tools such as ps and top read process information from the kernel. Write a small summary tool for an EdgeCampus edge server. Input: first line t...
Latency numbers on a human scale
Engineers remember approximate latencies ("an L1 cache hit is about a nanosecond, a round trip to a distant cloud about 100 ms"). They are easier to f...
Linux in practice: meet your operating system
Use a Linux machine (a lab PC, a virtual machine, WSL on Windows, or a free cloud shell). Run the commands below, copy the key lines of output into yo...
Research mini-project: who manages what in EdgeCampus?
EdgeCampus runs on three layers: students' phones, a GPU edge cluster in each building, and a public cloud region. Consider three workloads: - W1 — Ca...
Polling, interrupts or DMA? An I/O overhead calculator
For each device of an EdgeCampus server, compute the CPU overhead of the three I/O methods. Input: first line cpuHz (e.g. 1000000000). Then one device...
A mini kernel: dual mode and a system-call table
Simulate how a CPU with dual-mode operation executes a user program that uses system calls. The kernel has this system-call table (like Linux x86-64):...
Why buffering matters: counting system calls
An EdgeCampus sensor logger writes totalBytes bytes to a file. Each write system call costs syscallMicros microseconds, plus nanosPerByte nanoseconds...
Nested interrupts: a priority interrupt controller
Simulate an interrupt controller with priorities and nesting. Time advances in whole microseconds. Input: lines name arrival priority duration until t...
Linux in practice: watch system calls and interrupts
On a Linux machine (VM, WSL 2 or lab PC): 1. strace -c ls / — which system calls does ls use most? How many in total? 2. strace -e trace=openat,read,w...
Architecture decision: an OS for the EdgeCampus door controller
EdgeCampus will install smart door controllers on every lab. Each controller reads a student card, asks the edge server whether the student may enter,...
Process state machine with validation
Simulate the seven-state process model and reject invalid transitions. States: NEW, READY, RUNNING, BLOCKED, TERMINATED, SUSP_READY, SUSP_BLOCKED. Eve...
fork() explorer: build the process tree
Simulate a program made of fork and print statements executed by a process with PID 100. Input: one statement per line until the end of input: fork or...
Choosing the time slice: efficiency vs. response time
Help the EdgeCampus operations team choose a time slice for an interactive server. Input: first line n s maxWait — the number of processes taking turn...
Threads in practice: a parallel sum with a thread pool
Use real Java threads to sum a large array in parallel — the way an EdgeCampus analytics server splits work across cores. Input: first line n t (numbe...
Linux in practice: processes, threads and zombies
On a Linux machine: 1. ps -ef --forest head -40 and pstree -p head -20 — find PID 1 and your shell. Which process is the parent of your shell? 2. Run...
Research mini-project: how many workers for the GPU queue?
EdgeCampus runs a shared GPU server for student research jobs: 4 GPUs, 32 CPU cores, 256 GB RAM. Jobs arrive in a queue; each job needs 1 GPU, 4 CPU c...
CPU scheduling simulator (FCFS, SJF, SRTF, priority, RR)
Build the simulator every OS student wishes they had before the midterm. Input: first line: the algorithm — FCFS, SJF (non-preemptive), SRTF, PRIO-NP...
HRRN with the decision trace
Implement Highest Response Ratio Next (non-preemptive) and show the reasoning at every decision. Input: lines name arrival burst until the end of inpu...
Predicting CPU bursts with exponential averaging
SJF needs the length of the next CPU burst. Predict it with exponential averaging: τₙ₊₁ = α · tₙ + (1 − α) · τₙ Input: first line alpha tau0; second l...
Multilevel feedback queue simulator
Simulate an MLFQ with three queues: - Q0: quantum q0, Q1: quantum q1, Q2: FCFS (runs a job to completion). - New jobs enter the tail of Q0 (in input o...
Linux in practice: nice values and CPU shares
Linux's default scheduler gives each runnable task a CPU share proportional to a weight derived from its nice value (−20 … 19). Some weights: nice −5...
Midterm practice: one workload, five algorithms
Work by hand (then check with lab OS4.1). Workload (times in ms; priority 1 = highest): Process Arrival Burst Priority ------------ A 0 3 2 B 2 6 1 C...
Rate-monotonic analysis tool
Write a schedulability analyzer for periodic tasks under rate-monotonic scheduling (deadline = period, preemptive, one CPU). Input: lines name C T unt...
RM vs. EDF: simulate the hyperperiod
Simulate periodic tasks on one CPU over one hyperperiod (the least common multiple of the periods), in steps of 1 time unit. Input: first line RM or E...
Multicore load balancer with affinity
Balance tasks across cores, respecting pinned tasks (hard affinity). Input: first line: number of cores k. Then k lines, one per core (core 0 first),...
A mini CFS: virtual runtime and nice weights
Simulate the core idea of Linux's Completely Fair Scheduler on one CPU for CPU-bound tasks. Input: first line: total simulated time in ms. Then name n...
Linux in practice: affinity, real-time classes and migrations
On a Linux machine with at least 2 cores: 1. Start a CPU-bound process: yes /dev/null &. Run ps -o pid,psr,cls,ni,pri,comm -p <pid several times. The...
Research mini-project: energy-aware placement on a phone
CampusAR on a student's phone has four tasks for each second of operation. The phone has one big core (2.0 GHz, 2.0 W when busy) and one little core (...
Ranks and the critical path
Compute the ranks used by list-scheduling algorithms. Input format (used by all Chapter 6 labs): [code] Tasks are numbered 1…n. Compute: - average cos...
HEFT: reproduce a classic result
Implement HEFT and reproduce the makespan of 80 from the original paper's 10-task example. Input: the Chapter 6 format (see OS6.1). Algorithm: 1. Comp...
PEFT: look-ahead with the optimistic cost table
Implement PEFT (Arabnejad and Barbosa, 2014). Input: the Chapter 6 format. 1. Optimistic cost table: OCT(i, k) = 0 for exit tasks; otherwise OCT(i, k)...
Research tool: validate a schedule and compute its metrics
Every scheduling paper needs a validator: a bug that produces an impossible schedule makes all results meaningless. Write one. Input: the Chapter 6 fo...
Research reading: dissect the HEFT paper
Read the original HEFT paper: H. Topcuoglu, S. Hariri and M.-Y. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous comput...
Research mini-project: design an experiment for EdgeCampus workflows
EdgeCampus wants to choose a workflow scheduler for faculty workflows running on its heterogeneous platform: 2 edge GPUs, 4 edge CPUs and up to 4 clou...
Interleaving explorer: watch updates get lost
Two threads A and B each increment a shared counter (initially 0) k times. Each increment is three steps: load (r = counter), add (r = r + 1), store (...
Semaphore simulator with waiting queues
Simulate counting semaphores with FIFO waiting queues. Input lines until the end of input: - sem NAME value — declare a semaphore; - PROC wait NAME —...
Producer–consumer with a real BlockingQueue
Use real Java threads: one producer thread reads numbers from the input and puts them into an ArrayBlockingQueue<Integer of capacity cap; one consumer...
Concurrent bank transfers without deadlock
EdgeCampus keeps a "compute credit" account per research group. Transfers run concurrently on a thread pool; each transfer must lock both accounts, an...
Code review: a buggy bounded buffer
A teammate wrote this buffer for EdgeCampus frames. It "works in testing" but occasionally loses frames, occasionally hangs, and once threw an excepti...
Industry mini-project: double booking of GPU slots
Students book 2-hour slots on the EdgeCampus GPU server through a web app running on three application servers behind a load balancer, sharing one MyS...
The Banker's algorithm: safety and requests
Implement the Banker's algorithm. Input: n m; the Available vector; then n rows of Max; then n rows of Allocation; then zero or more lines request i r...
Deadlock detection with multiple instances
Implement the detection algorithm. Input: n m; Available; n rows of Allocation; n rows of Request (current outstanding requests). - Processes whose al...
Wait-for graph: find cycles and choose victims
Resources have a single instance. Input lines (any order) until the end of input: - holds P R — process P holds resource R; - waits P R — process P wa...
GPU cluster: pod-by-pod vs. gang scheduling
Simulate distributed training jobs on a GPU cluster. Input: policy (partial or gang), number of GPUs, number of jobs, then per job name workers durati...
Linux in practice: catch a real Java deadlock
Create, observe and fix a real deadlock on your own machine (Linux, macOS or Windows with a JDK). 1. Write Deadlock.java with two lock objects invento...
Research mini-project: deadlock-free GPU allocation for edge training
EdgeCampus wants to run federated/distributed training jobs on three edge sites (8, 8 and 4 GPUs) plus a cloud pool (32 GPUs, 40 ms away). Jobs need b...
Contiguous allocation: first, best, worst and next fit
Simulate a contiguous memory allocator. Input: the policy (first, best, worst or next), the memory size, then operations alloc NAME size and free NAME...
Paging calculator and address translation
Input: addressBits pageSize pteBytes (page size is a power of two), then the number of entries in a process's page table, the entries (frame number, o...
TLB simulator and effective access time
Simulate a fully associative TLB with LRU replacement. Input: entries pageSize tlbNs memNs levels, then logical addresses until the end of input. For...
The Linux buddy allocator
Simulate a buddy allocator. Input: total memory (a power of two) and the minimum block size (a power of two), then alloc NAME size / free NAME operati...
Linux in practice: where does the memory go?
On a Linux machine (a VM, WSL or a cloud instance), investigate memory management in a running system. Record the commands and outputs. 1. free -h and...
Research mini-project: memory-aware placement of AI inference
EdgeCampus runs three kinds of inference tasks: object detection (model 0.6 GB, 15 ms on edge GPU), speech recognition (model 1.5 GB, 40 ms), and a la...
Page-replacement simulator: FIFO, LRU, OPT and clock
Input: the algorithm (FIFO, LRU, OPT or CLOCK), the number of frames, then the reference string. Rules: - Free frames are filled from left to right. -...
Fault curves and Belady's anomaly
Input: maxFrames, then a reference string. For every number of frames f = 1 … maxFrames, count the faults of FIFO and LRU and print a table: [code] (f...
Working sets and thrashing detection
Input: delta frames nProc, then one line of page references per process (all lines have the same length; at each time step every process makes one ref...
Copy-on-write fork simulator
Simulate copy-on-write. Input: the number of pages of process P (frames 0 … n−1, one per page), then operations: - fork A B — process B becomes a chil...
Linux in practice: measuring page faults
On Linux (VM, WSL or cloud instance), measure virtual-memory behaviour. Record commands and outputs. 1. Write a small Java or C program that allocates...
Research reading: PagedAttention as virtual memory for AI
Read the abstract, introduction and design section of "Efficient Memory Management for Large Language Model Serving with PagedAttention" (Kwon et al.,...
Disk-scheduling simulator
Input: algorithm (FCFS, SSTF, SCAN, CSCAN, LOOK, CLOOK), the last cylinder max (cylinders 0 … max), the initial head position, the initial direction (...
Inode calculator: file sizes and disk reads
Input: block size (bytes), pointer size (bytes), number of direct pointers; then byte offsets until the end of input. The inode also has one single, o...
RAID planner
Input: number of disks n, disk size (TB), random IOPS per disk, read fraction; then RAID levels (RAID0, RAID1 as an n-way mirror, RAID5, RAID6, RAID10...
Write-back vs. write-through cache
Simulate a block cache with LRU replacement. Input: policy (through or back), capacity (blocks), then operations: read b, write b, sync, crash. - read...
Linux in practice: inodes, links, caches and fsync
On Linux, explore the file system and measure storage behaviour. Record commands and outputs. 1. Create a file, a hard link and a symbolic link. Use l...
Design mini-project: storage for EdgeCampus video analytics
EdgeCampus has 200 cameras (2 Mb/s each) streaming to three edge servers; detection runs at the edge; the university wants (a) 7 days of raw video on...
VM placement: FF, BF, FFD and BFD with a power model
Input: policy (FF, BF, FFD, BFD), host capacity cpu mem, then VMs name cpu mem until the end of input. Hosts are identical and opened on demand. - FF:...
Kubernetes Horizontal Pod Autoscaler
Input: replicas min max target podCapacity, then the load (requests/s) at each step. At each step: utilization = load / (replicas × podCapacity). If u...
CPU limits and CFS throttling
Simulate CFS bandwidth control in 1 ms ticks. Input: quota period threads work cores (quota and period in ms; each of threads threads needs work ms of...
Serverless cold starts and keep-alive
Simulate a serverless platform where each instance handles one request at a time. Input: keepAlive coldMs execMs, then request arrival times (ms, non-...
Linux in practice: build a container by hand
On a Linux VM (not a production machine), explore what a container really is. 1. Run docker run -d --name web -m 256m --cpus 0.5 nginx. Find its proce...
Research mini-project: energy-aware consolidation for the edge
EdgeCampus has 6 edge servers (16 cores each, 100 W idle, 250 W at full load). During the day, 40 services run with a total demand of 70 cores; at nig...
The offloading decision: local, edge or cloud?
Input: C D fLocal Pcompute Ptx alpha (C in gigacycles, D in KB with 1 KB = 1,000 bytes, fLocal in GHz, powers in W, alpha ∈ [0, 1]), then two lines na...
Multi-user offloading: best-response dynamics
Input: edgeGHz rttMs n, then n users name gigacycles fLocalGHz uploadMs. Local time = cycles / fLocal. If k users offload, the edge capacity is shared...
DNN partitioning: where to split?
A neural network is a chain of layers. Input: uplinkMbps rttMs inputKB n, then n layers name deviceMs edgeMs outputKB. Split k (0 ≤ k ≤ n) runs layers...
Deadline- and cost-aware placement across device, edge and cloud
Input: the number of resources, then per resource name speedGHz transferMsPerMB rttMs pricePerGcycle; then tasks name release deadline gigacycles MB (...
In practice: measure whether offloading pays off
Measure a real offloading decision with your own laptop/phone hotspot and a remote machine (a lab server, a campus VM, or a free-tier cloud VM). 1. Wr...
Research mini-project: reproduce and extend an offloading study
Choose one of the following and work in a team of 2–3. (A) Multi-user offloading. Extend Lab OS13.2: users also choose their transmit power or the edg...
Unix permission checker
Process commands until the end of input: - mode M — M is octal (754) or symbolic (rwxr-xr--, 9 characters). Print mode 754 = 754 = rwxr-xr-- (the inpu...
Access matrix: ACLs and capability lists
Maintain an access matrix (domains × objects; rights are single letters, o = owner). Commands: - create D O — domain D creates object O and gets right...
Password search spaces and hashing speed
Input: the number of hash functions h, then h lines name guessesPerSecond; then password policies label alphabetSize length until the end of input. Fo...
Multilevel security: Bell–LaPadula and Biba
Input: the model (BLP or BIBA), the number of levels and their names from lowest to highest, then lines subject NAME LEVEL, object NAME LEVEL, and req...
Linux in practice: harden a small server
On a Linux VM that you control (never on systems you do not own), apply and document basic hardening. Record commands, outputs and your reasoning. 1....
Design mini-project: security-aware task placement for EdgeCampus
Tasks at EdgeCampus have a sensitivity label: public (e.g., map rendering), internal (course analytics), personal (face recognition on campus video, h...