Last Updated: 2021-04-11 Sun 22:17

CSCI 4061 Lab11: Job Runner with Semaphores

CODE DISTRIBUTION: lab11-code.zip

  • Download the code distribution
  • See further setup instructions below

CHANGELOG: Empty

1 Rationale

Semaphores are a classic means of coordinating multiple cooperating processes so that they access a shared resource without creating conflicts. This lab provides a small but nontrivial application which requires semaphores to be added to ensure no duplication / corruption occurs while processes compete to manipulate a data file.

Grading Policy

Credit for this Lab is earned by completing the exercises here and submitting a Zip of the work to Gradescope. Students are responsible to check that the results produced locally via make test are reflected on Gradescope after submitting their completed Zip. Successful completion earns 1 Engagement Point.

Lab Exercises are open resource/open collaboration and students are encouraged to coopearte on labs. Students may submit work as groups of up to 5 to Gradescope: one person submits then adds the names of their group members to the submission.

See the full policies in the course syllabus.

2 Codepack

The codepack for this lab is linked at the top of this document. Always download it and unzip/unpack it. It should contain the following files which are briefly described.

File Use Description
QUESTIONS.txt EDIT Questions to answer: fill in the multiple choice selections in this file.
runner.c EDIT C file to study and complete for the CODE portion. See instructions in QUESTIONS.txt
mmap_file.c Provided C file that memory maps a whole file; used in runner.c
runner.h Provided Header file with constants / includes for runner application.
QUESTIONS.txt.bk Backup Backup copy of the original file to help revert if needed
Makefile Build Enables make test and make zip
testy Testing Test running scripts
test_lab11.org Testing Tests for this lab
test_quiz_filter Testing Used to simplify quiz checksum

3 QUESTIONS.txt File Contents

Below are the contents of the QUESTIONS.txt file for the lab. Follow the instructions in it to complete the QUIZ and CODE questions for the lab.

                           __________________

                            LAB 11 QUESTIONS
                           __________________





Lab Instructions
================

  Follow the instructions below to experiment with topics related to
  this lab.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


QUIZ Semaphore Usage
====================

  Review use of POSIX semaphores from lecture examples and answer the
  following questions.

  Which of the following calls is used to open/create a semaphore?
  - ( ) sem_t *sem = sem_open(sem_name, O_CREAT, S_IRUSR | S_IWUSR);
  - ( ) sem_t *sem = open(sem_name, O_CREAT, S_IRUSR | S_IWUSR);
  - ( ) int fd = sem_open(sem_name, O_CREAT, S_IRUSR | S_IWUSR);
  - ( ) int fd = open(sem_name, O_CREAT, S_IRUSR | S_IWUSR);

  Which of the following calls will ensure that an opened semaphore is
  initialized to have value 1 (e.g. is unlocked)?
  - ( ) sem = 1;
  - ( ) init(&sem, 1);
  - ( ) sem_init(sem, 1, 1);
  - ( ) write(semfd, &vals, 1);

  Which pair of functions are used to "lock" and "unlock" a semaphore?
  - ( ) sem = 0; AND sem = 1;
  - ( ) sem_lock(sem); AND sem_unlock(sem);
  - ( ) sem.acquire(); AND sem.release();
  - ( ) sem_wait(sem); AND sem_post(sem);


CODE Add Initialization + Coordination to runner.c
==================================================

  The provided runner.c code traverses a "job" file to execute each of
  the lines of it as though it were typed into a shell. It can be
  built/run using the following setup.

  ,----
  | > make                                   # build
  | gcc -Wall -Werror -g -Wno-format-truncation -c runner.c
  | gcc -Wall -Werror -g -Wno-format-truncation -c mmap_file.c
  | gcc -Wall -Werror -g -Wno-format-truncation -o runner runner.o mmap_file.o -lpthread
  | 
  | > cp test_jobs.1.txt test_jobs.tmp       # copy jobs file to a temporary file as runner will change it
  | 
  | > head test_jobs.tmp                     # lines that start with a '-' are incomplete jobs
  | - seq 10000
  | - gcc --version
  | - sleep 1.5
  | ...
  | 
  | > ./runner test_jobs.tmp                 # start the runner
  | 001: 232927 RUN 'seq 10000'              # each line reported is handled by the runner which reports
  | 002: 232927 RUN 'gcc --version'          # the line, its own PID, and the job being run. Output for 
  | 003: 232927 RUN 'sleep 1.5'              # each job is suppressed but in a real setting would be stored.
  | ...
  | 099: 232927 RUN 'wc jobs.txt'
  | 100: 232927 RUN 'seq 500'
  | 
  | > ./runner test_jobs.tmp                 # running second time returns immediately...
  | 
  | > head test_jobs.tmp                     # because all jobs are marked "D" for Done
  | D seq 10000
  | D gcc --version
  | D sleep 1.5
  | D ls
  | D ls -l
  | D sleep 2.0
  | D ls -li
  | D gcc --help
  | D sleep 2.0
  | D wc jobs.txt
  `----


  The `runner.c' program is mostly written so that multiple such runners
  can be started such as in the following where 2 such jobs get started.
  ,----
  | > ./runner test_jobs.tmp & ./runner test_jobs.tmp &      # start 2 runners
  | [1] 233292
  | [2] 233293
  | 001: 233292 RUN 'seq 10000'                              # first runner
  | 002: 233293 RUN 'gcc --version'                          # second runner
  | 003: 233292 RUN 'sleep 1.5'                              # first runner - takes a while to finish
  | 004: 233293 RUN 'ls'                                     # second runner
  | 005: 233293 RUN 'ls -l'                                  # second runner
  | 006: 233293 RUN 'sleep 2.0'                              # second runner
  | ...
  | 098: 233293 RUN 'sleep 2.0'
  | 099: 233292 RUN 'wc test_jobs.1.txt'
  | 100: 233292 RUN 'seq 500'
  `----

  Executing multiple runners can speed up the completion of all jobs BUT
  there is no coordination between processes. This can lead to
  duplication of effort between processes. To see this, use the provided
  "simulation" testing program which is run as follows.
  ,----
  | > ./test_runner.sh runner          # starts 10 runners working on the same jobs file
  | ITER  1: 10 unique pids did jobs   # reports that 10 processes cooperated on jobs BUT...
  | Duplicate Job Detected:            # at least one duplication ocurred due to lack of coordination
  | 019: 233594 RUN 'seq 100000'
  | 019: 233598 RUN 'seq 100000'
  | ITER  2: 10 unique pids did jobs   # The test is repeated but this time no duplicatation occurred
  | ITER  3: 10 unique pids did jobs   # On a further repeat, a different job was indadvertently duplicated
  | Duplicate Job Detected:
  | 001: 234031 RUN 'sleep 0.25'
  | 001: 234032 RUN 'sleep 0.25'
  | ITER  4: 10 unique pids did jobs
  | ...
  `----

  Modify the `runner.c' code so that any number of runners can be
  started which will cooperate to complete a jobs file. The program must
  satisfy several constraints.
  1. Make use of semaphores as a coordination mechanism including
     initialization a semaphore at the beginning of the program in a
     marked code block.
  2. Lock / Unlock the semaphore to protect the Critical Region where it
     would be dangerous for several processes to attempt "own" a job.
  3. Ensure that when several runners are started, all of them have fair
     access to cooperate. If a process locks the jobs file for over its
     entire processing of the file OR fails to release a lock after
     "owning" a job, the simulation will likely report a single runner
     process completed all jobs rather all 10 runners cooperating.

  Correct code for runner.c will be execute jobs files faster when
  multiple runners are started and will have the following output from
  the test_runner.sh script which is checked via `make test'.

  ,----
  | > ./test_runner.sh runner
  | ITER  1: 10 unique pids did jobs
  | ITER  2: 10 unique pids did jobs
  | ITER  3: 10 unique pids did jobs
  | ...
  | ITER 23: 10 unique pids did jobs
  | ITER 24: 10 unique pids did jobs
  | ITER 25: 10 unique pids did jobs
  `----

  NOTE: Several interesting techniques are demonstrated in runner.c /
  mmap_file.c including memory mapping a file to ease sharing its data
  between multiple processes and parsing that file using the `sscanf()'
  function. You do not need to understand all of this to complete the
  exercise but for those interested in learning some new coding tricks,
  this may provide some opportunities.

4 Submission

Follow the instructions at the end of Lab01 if you need a refresher on how to upload your completed lab zip to Gradescope.


Author: Chris Kauffman (kauffman@umn.edu)
Date: 2021-04-11 Sun 22:17