Computer Science 330
Operating Systems

Fall 2022, Siena College

Lab 4: Process Interleavings
Due: 9:20 AM, Friday, October 21, 2022

In this brief lab, you will think more about race conditions and how they can be problematic for concurrent access to a single shared variable.

You may work alone or in groups of size 2 or 3 on this lab.

Learning goals:

  1. To think more carefully about race conditions and atomic operations

Getting Set Up

In Canvas, you will find link to follow to set up your GitHub repository, which will be named interleavings-lab-yourgitname, for this lab. Only one member of the group should follow the link to set up the repository on GitHub, then others should request a link to be granted write access.

Process Interleavings

Write a C program that will list all possible orderings of the machine instructions generated for the critical sections of the Producer-Consumer example from class. Recall that the statements counter++ and counter-- actually generate machine code such as

Producer Consumer
P1 R0 = counter; C1 R1 = counter;
P2 R0 = R0 + 1; C2 R1 = R1 - 1;
P3 counter = R0; C3 counter = R1;

Your program should list all possible interleavings of the statements P1, P2, P3, C1, C2, and C3. Also have your program print which interleavings produce a correct result (that counter has the same value it started with).

Important: You are not writing a multithreaded program here! You are writing a program that generates the possible interleavings, computes the final value of counter for each interleaving, and prints the interleaving and the value of counter, along with an annotation that the answer is correct or incorrect.

Write your program in a file called interleaving.c.


Commit and push!


This assignment will be graded out of 15 points.


Value Score
Makefile 1
Correctness 10
Documentation 2
Efficiency and Elegance 2
Total 15