CSCI 4061 Lab11: Job Runner with Semaphores

                           __________________

                            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.