Reading 03: Scheduling

Everyone:

Now that we have examined what a process is, we now need to explore how the operating system decides which process to run during a context switch. To do this, the operating system can employ a variety of scheduling algorithms that try to balance competing goals and metrics.

TL;DR¶

For this reading assignment, you are to read about scheduling with a focus on the FIFO, SJF, STCF, Round Robin, MLFQ, and Lottery algorithms, submit your responses to the Reading 03 Quiz, and modify your program to use fork to compute SHA1 digests concurrently.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces
1. Scheduling: Introduction
2. Scheduling: MLFQ
3. Scheduling: Lottery
4. Scheduling: MP (Optional)

Quiz¶

Once you have done the readings, answer the following Reading 03 Quiz questions:

Program¶

For this week's program, you are to modify the program.c from Reading 02 such that you use a separate child process to compute the SHA1 digest for each argument. In other words, for each file argument, you need to fork a child process that computes and displays the SHA1 digest of the contents of the file. The parent should collect the exit statuses of its children and return 0 if all children are successful. Otherwise, it should return the number of children that failed as its own exit status.

Example¶

The usage and output of your program should be the same as sha1sum:

$ ./program Makefile  # Compute SHA1 of Makefile
feb80a686dd776a787d6baf8cfbae7e9b2307602  Makefile

$ echo $?             # Check exit status
0

$ ./program asdf      # Handle invalid files

$ echo $?             # Check exit status
1

Requirements¶

Your code must compile cleanly with no warnings.
Your program may only use I/O system calls such as open, read, and close to access the contents of each file.
Your program must use stat to get the size of any files.
Your program must use the SHA1() function provided by OpenSSL.
Your program must not have any resource leaks or memory errors as detected by valgrind.
Your program must use fork and wait and WEXITSTATUS.
Each child process must run concurrently (ie. without waiting for another process).

Note: To link properly to the SHA1 functions, you will need to add -lcrypto to the LIBS variable in your Makefile.

Note: You will want to return 0 if all arguments were able to be processed successfully. Otherwise, return the number of files that failed as the exit status.

Hints¶

You should not need to modify your original sha1sum_file function from Reading 02. Instead, you should create an additional sha1sum_process function that computes the SHA1 digest using sha1sum_file and then displays the result:

void sha1sum_process(const char *path) {
    ...
    if (!sha1sum_file(path, cksum)) {
        ...   // Failure
    }
    ...       // Success
}

Once you have a sha1sum_process funciton, you will need to modify the main function as follows:

function main(arguments):
    For each argument:
        Create child process
        Call sha1sum_process with child process

    For each argument:
        Wait for each child
        Update the overall program status

Fork Bomb¶

Make sure you terminate the child process in sha1sum_process properly, otherwise you may end up in a situation where you create a fork bomb.

Submission¶

To submit your work, follow the same process outlined in Reading 01:

$ git switch master                   # Make sure we are in master branch

$ git pull --rebase                   # Make sure we are up-to-date with GitHub

$ git checkout -b reading03           # Create reading03 branch and check it out

$ cd reading03                        # Go into reading03 folder
$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/check.py                # Check reading03 quiz
Checking reading03 quiz ...
      Q1 0.60
      Q2 0.05
      Q3 0.05
      Q4 0.10
      Q5 0.50
      Q6 0.30
      Q7 0.25
      Q8 0.15
   Score 2.00 / 2.00
  Status Success

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 03: Quiz"    # Commit work

$ $EDITOR program.c                   # Edit your program.c file

$ make test-program                   # Check reading03 program
Testing reading03 program ...
 I/O System Calls                                             ... Success
 I/O Functions                                                ... Success
 Memory Functions                                             ... Success
 SHA1 Functions                                               ... Success
 Process System Calls                                         ... Success
 program                                                      ... Success
 program (valgrind)                                           ... Success
 program Makefile                                             ... Success
 program Makefile (valgrind)                                  ... Success
 program Makefile (strace)                                    ... Success
 program Makefile README.md                                   ... Success
 program Makefile README.md (valgrind)                        ... Success
 program Makefile README.md (strace)                          ... Success
 program Makefile README.md program.c                         ... Success
 program Makefile README.md program.c (valgrind)              ... Success
 program Makefile README.md program.c (strace)                ... Success
 program Makefile README.md program.c asdf                    ... Success
 program Makefile README.md program.c asdf (valgrind)         ... Success
 program Makefile README.md program.c asdf (strace)           ... Success
 program Makefile fdsa README.md program.c asdf               ... Success
 program Makefile fdsa README.md program.c asdf (valgrind)    ... Success
 program Makefile fdsa README.md program.c asdf (strace)      ... Success
 program Makefile README.md /bin/ls /bin/bash                 ... Success
 program Makefile README.md /bin/ls /bin/bash (valgrind)      ... Success
 program Makefile README.md /bin/ls /bin/bash (strace)        ... Success
   Score 2.00 / 2.00
  Status Success

$ git add program.c                   # Add program.c to staging area
$ git add Makefile                    # Add Makefile to staging area
$ git commit -m "Reading 03: Code"    # Commit work

$ git push -u origin reading03        # Push branch to GitHub

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 03 TA List.