Systems Programming (Semester 1, 2012)

Assignment 2 for Systems Programming

This is your second assignment for Systems Programming, Semester 1, 2012

The purpose of this assignment is to look into the more intricate details of system level programming. The assignment consists of a programming task and a number of exercises that will be made available incrementally as milestones (so check this web page regularly to make sure you won't miss out on your next milestone!) Milestones are due every week and need to be submitted in or before the lab they are due in. You will only get marks for a milestone if you hand in the milestone before its deadline. See below below for the milestones and deadlines.

To submit a milestone, you need to commit everything that belongs to the solution into your Subversion repository on dwarf.ict.griffith.edu.au and tag it accordingly (i.e. milestone1 for the first milestone, milestone2 for the second milestone, etc.).

Please note that this is an individual assignment! Everything you hand in must be your original work (e.g. you cannot hand in any material created by anyone else, done as group work, or downloaded from the internet)!

Programming Task

The task for this assignment is to create (in stages), a number of small command line programs in C. For more details, see the milestones below.

All programs need to be tested and debugged before submission! Make sure that the final program behaves exactly as specified.

The overall program and all modules and functions need to be accompanied by source code documentation, a description of how to use the program, and a test report.

Milestones and Deadlines

Week 7, 17 April 2012 (15 marks)

Subversion Repository

Check out the (empty) working directory for assignment 2 on your workstation or on dwarf using, e.g.:

svn checkout file://$HOME/.spsvn-2012/ass2/trunk a2

This will create an a2 directory that you can create your assignment 2 files in. Don't forget to add each file that belongs to your assignment (e.g. using svn add file), then commit all changes (using svn commit).

To get marks for the repository, after all the steps in the following subsesctions, you need to create a milestone1 tag for your final milestone submission using (on one single line):

svn copy file://$HOME/.spsvn-2012/ass2/trunk file://$HOME/.spsvn-2010/ass2/tags/milestone1 -m "log message"

Make sure you only perform the last step above after you have completed all the steps below and want your assignment marked!

Multi-Threaded Hello World

Create a Hello World program hello.c that creates a child thread which prints Hello Child. After creating the child thread, the parent thread needs to print Hello Parent, then wait for the child thread to finish before itself exiting.

Your program needs to compile without warning when using

clang -std=gnu99 -Wall -o hello hello.c -lpthread

Add your program to the repository using svn add hello.c and commit it after every change using svn commit -m "log message" (replace log message with a text that descripts the changes you have made).

Makefile

Create a Makefile that compiles your program so that you can run it from the command line using ./hello (followed by enter).

Add your Makefile to the repository using svn add Makefile and commit it after every change using svn commit -m "log message" (again, replace log message with a descriptive log message).

Targets: `clean` and `all`

Add a clean target that removes all files that are generated when you run make (e.g. all .o files and the final executables).

Add an all target as the very first target in your Makefile to eventually compile all milestones in this assignment (of course, this only needs to compile the first milestone at this stage).

First Steps in Synchronisation

The objective of this part is to explore simple thread synchronisation using mutexes (simple locks) by implementing a program lock that creates a child thread, reads (in the parent thread) a line of input from the user, and sends that line to the child thread for printing (to stdout). The parent thread should wait for the user to hit return (or enter), then notify the child thread, and wait for the child to exit.

Implementation Steps

Create a new program lock.c and add it to the Makefile and the subversion repository. You can start from the hello.c code if you want, but make sure you copy the code over to the new lock.c file – don't change your hello.c.
Commit the previous step to the repository!
Add a buffer (that holds at least 256 characters) to your parent thread. Pass the address of that buffer to the child thread.
Commit the previous step to the repository!
In the parent thread, after starting the child thread, read one line of input into the buffer. Print the buffer to stdout from within the child thread (no need to wait for the parent at this stage). Explain in your README what happens.
Commit the previous step to the repository!
Use a mutex to make the child wait for the parent to have read a line before displaying the line. Hint: you will need to pass both the buffer and the mutex to the child. Don't ever use global variables; you can instead create a struct that contains all the variables you need to pass to the child thread!
Commit the previous step to the repository!
After the child thread has printed the output, make the parent thread prompt the user to hit Enter (and wait for the user to do so). Hint: You will need a second mutex for this. Explain in your README why this cannot be done reliably with a single mutex! How reliable is an approach that uses 2 mutexes? Explain if there is a scenario where even two mutexes might not be enough.
Commit the previous step to the repository!
Make the parent notify the child once the user has hit the enter key. The child needs to wait for that notification and then exit. The should wait for the child to exit and then end the whole program (process). Do you need a third mutex for this? Will this be reliable under all circumstances? Explain why/why not!
Commit the final step to the repository!

Don't forget to use the svn copy command to submit all your files as milestone1! Make sure you extend the clean and all targets of your Makefile for all the subsequent milestones in the coming weeks!

Week 8, 24 April 2012 (15 marks)

Creating a Semaphore

In the previous milestone, there was one race condition that would still remain. This problem cannot be avoided by using mutexes alone!

This can be prevented by using a Semaphore (since Semaphores can to be unlocked by a different thread than the one that originally locked it). The following pseudo-code implements a generic Semaphore that, unlike the traditional Semaphores discussed in the lecture, can be initialised with negative values:

procure(Semaphore *semaphore)
{
    begin_critical_section(semaphore);  // make the following concurrency-safe
    while (semaphore->value <= 0)
	wait_for_vacate(semaphore);     // wait for signal from vacate()
    semaphore->value--;                 // claim the Semaphore
    end_critical_section(semaphore);
}

vacate(Semaphore *semaphore)
{
    begin_critical_section(semaphore);  // make the following concurrency-safe
    semaphore->value++;                 // release the Semaphore
    signal_vacate(semaphore);           // signal anyone waiting on this
    end_critical_section(semaphore);
}

In the above code, the procure() function is similar to semWait() from the lecture, and vacate() is similar to semSignal().

Semaphore Implementation

Create a new module sema.c with an accompanying sema.h that implements the above algorithm in C (and add it to subversion repository). Embed all the data needed to implement your Semaphore in a single struct. Don't use an existing POSIX or other Semaphore implementation in your code! Hint: you can use a mutex to protect your critical section, and a condition variable to wait/signal that a Semaphore has been vacated (see also the hints below!).
Commit the previous step to the repository!
Add an initialiser function to your code that sets up a Semaphore and intialises it to a pre-defined (integer) value.
Commit the previous step to the repository!
Add a destructor function to your code that cleans up properly after the use of a Semaphore (e.g. destroys all mutexes, and condition variables, and releases all memory allocated for a Semaphore).
Commit the previous step to the repository!
Test your code with a separate program sematest.c. Your test needs to include a case that clearly shows the difference between using a mutex and a Semaphore! Hint: if you add a sleep at the beginning of the child thread in last week's code you should be able to demonstrate how your Semaphore implementation prevents the mutex problem discussed above! If you do use last week's code, make sure you copy the code into a new file first (don't modify last week's milestone directly)!
Commit the previous step to the repository!
Add a short test report to your documentation!
Commit the previous step to the repository!

Using GCD

Re-implement the problem using Grand Central Dispatch (GCD). Instead of creating monolithic parent and child threads, GCD allows using queues that automatically feed from a thread pool. Dispatching tasks to these queues (synchronously or asynchronously) can be done on the fly and can be interleaved (when using blocks) right where they are needed.

What you will need to implement, are two dispatch queues, parent and child. To wait for tasks in both queues to finish, you can use a dispatch_group that you can run the two groups under and that the main program can wait on.

For the milestone, implement this in C and explain how dispatch queues are different from threads and what a dispatch group does for synchronisation.

Don't forget to use the svn copy command to submit all your files as milestone2!

Week 9, 1 May 2012 (15 marks)

Event Counter

An Event Counter is another task synchronisation instrument that consists of an integer (with an initial value of 0) and atomic operations. The atomic operations are as follows:

read(Eventcounter): returns the current (integer) value of Eventcounter
advance(Eventcounter): increments the Eventcounter by one
await(Eventcounter, value): blocks the current thread until Eventcounter >= value

Sequencer

Sequencers are closely linked with event counters. A Sequencer is also an integer (initialised to 0) that is used to serialise the occurrence of events. A sequencer only has one atomic operation, ticket(), that returns the current value of the sequencer and then increments the sequencer by one.

8 Bit Random Number Generator

The goal of this milestone is to solve the Producer/Consumer problem for a random number generator using Sequencers and Event Counters. One thread acts as a random number generator that reads true random numbers from the kernel random number source device /dev/random and puts them into a buffer. Another thread consumes these random numbers as they come in and prints them on standard output.

It is important that the buffer does not overflow (i.e., the random number generator does not try to put more random numbers into the buffer than the buffer can hold). It is also imporant that the buffer does not underflow (i.e., a random number may only be taken out of the buffer if that does not take the total number that remains in the buffer below the minimum fill level).

Producer/Consumer Algorithm

The idea behind the algorithm is to use a sequencer each for the Producer and the Consumer to issue a unique ticket for each produce or consume operation. Putting an element into the buffer (in) or taking an element out of the buffer (out) are then protected by an event counter. What is important is that the producer does not try to add to a full buffer and the consumer does not try to remove from an empty buffer (or a buffer that would fall below a minimum fill level). For a buffer of capacity 1 with no minimum fill level, the algorithm would look somewhat like this:

u_int8_t buffer[1];                     // a very low capacity buffer
sequencer p_ticket, s_ticket;	        // producer and consumer tickets
eventcounter e_in, e_out;               // count/wait for in and out operations

producer()
{
  while (1)                             // forever
  {
    int v = produce();                  // produce an element
    int t = ticket(p_ticket);           // create a new ticket

    await(e_in, t);                     // one producer only!
    await(e_out, t);                    // wait for space in the buffer

    put(buffer, v);                     // put the value in the buffer

    advance(e_in);                      // next producer, please!
  }
}
   
consumer()
{
  while (1)                             // forever
  {
    int t = ticket(p_ticket);           // create a new ticket

    await(e_out, t);                    // one consumer only!
    await(e_in, t + 1);                 // wait for an element

    int v = get(buffer);                // get a value from the buffer

    advance(e_out);                     // next consumer, please!

    consume(v);                         // do something with v
  }
}

Implementation Steps

(Don't forget to also have a look at the hints below!)

Create a function that, in a loop, reads high quality 8 bit random numbers of type uint8_t (as defined in <stdint.h>) from /dev/random as fast as it can.
Commit the previous step to the repository!
Create a data type (e.g. a struct) for the buffer (queue) with an appropriate constructor (intialiser) and destructor (cleanup function). The constructor should take at least two (integer) parameters: a (maximum) buffer size, and a minimum fill level.
Create a put_buffer() function that puts a value into the buffer so that it can be read later. For the moment, you can ignore the maximum buffer size and concurrency.
Commit the previous step to the repository!
Create a get_buffer() function that reads the oldest value that was put into the buffer, removes that value from the buffer and returns it. For the moment, you can ignore the minimum fill level and concurrency.
Commit the previous step to the repository!
Create a Sequencer data type with an atomic ticket() operation as described above. Use the Semaphores you implemented in the previous milestone or locks to ensure atomicity.
Commit the previous step to the repository!
Create an EventCounter data type with atomic read(), advance(), and await() operations as described above. Use the Semaphores you implemented in the previous milestone or locks to ensure atomicity.
Commit the previous step to the repository!
Use the Sequencer and EventCounter for synchronisation (for the moment, a minimum fill level of zero and a maximum fill level of one is fine). I.e., add a construct to your put_buffer() function that waits for space to become available when the buffer is full. Also add a construct to your get_buffer() function that, if the minimum fill level would be compromised, waits for more data to arrive in the buffer before removing an integer from the buffer.
Commit the previous step to the repository!
Modify your protection code to respect the maximum buffer fill level.
Commit the previous step to the repository!
Modify your protection code to respect the minimum buffer fill level.
Commit the previous step to the repository!
Create a test program that uses dispatch_async() to spawn the concurrent producer. I.e. the task should use the function you created earlier to read values from /dev/random as fast as it can and immediately put each value into the buffer. A separate task should act as the consumer: it should read and remove one number from the buffer, and print it to stdout as a 2 digit lower-case hex numbers prefixed by 0x (e.g. 0xf0 for the decimal number 240).
Commit the previous step to the repository!
Add two command line parameters, a maximum buffer size, and a minimum fill level. These command line parameters should be optional to the user – by default, the maximum buffer size should be 2, and the minimum fill level should be 0 (zero).
Commit the previous step to the repository!
Add a loop to the main thread that reads user input from stdin, one line at a time. The user input should be interpreted as the number of integers that next should be read from the buffer and printed to stdout in one go (i.e. before the parent waits for the next input from the user). Use a child queue with the task from the earlier step to ensure thate integers are read and printed out in the order they were produced! Print each integer immediately after reading it from the buffer! E.g., if the user types 25 (followed by enter), 25 integers should be read from the buffer and printed to stdout; then if the user types 3 another three integers should be read from the buffer and printed.
Commit the previous step to the repository!
Add an exit command that cleans up any resources and exits the program.
Commit the previous step to the repository!

Don't forget to add new files to your repository and the Makefile as usual. When done with the milestone, use the svn copy command to submit all your files as milestone3!

Week 10, 8 May 2012 (15 marks)

Network Status Monitor

Solve the reader/writer problem by implementing a network status monitor that tracks network statistics on the system. The writer should monitor packet numbers once per second and update a status area containing the number of correctly transmitted and erroneous input and output packets as well as a time stamp of the update. The reader(s) should be able to read and display the latest status information at any time. A writer trying to update the status information needs to have priority over readers trying to read the information.

Implementation Steps

(Don't forget to also have a look at the hints below!)

Download and test NetStat.tar.bz2. This contains a function get_net_statistics() that retrieves network statistics. (You can use this function unchanged in your code by adding netstat.c and netstat.h to your own Makefile.)
Commit the previous step to the repository!
Create a write_net() function that writes the current network status (struct net_stat) into the status area.
Commit the previous step to the repository!
Create a read_net() function that returns the current information from the status area.
Commit the previous step to the repository!
Use semaphores for synchronisation and to protect your status area. I.e., you need to solve the reader/writer problem to make sure that the network statistics can be read and written atomically. Make sure that writers have priority over readers (see the lecture notes).
Commit the previous step to the repository!
Create a test program that spawns a child thread that acts as the writer. I.e. the child should use the get_net_statistics() function from the example code to retrieve network status information once a second and write that to the status area. The main (parent) thread should, for the moment, act as the reader (i.e. read the network statistics from the status area and print everything to stdout).
Commit the previous step to the repository!
Add a loop to the main thread that reads user input from stdin, one line at a time. The user input should be interpreted as the number of reader threads (additional child threads) that should read the the status information and print to stdout before the parent waits for the next input from the user. Print each statistic immediately after reading it from the buffer (from within these child threads), but make sure threads don't interfere with each other when displaying the information by adding mutual exclusion around your output to stdout! E.g., if the user types 10 (followed by enter), the status information should be read and printed 10 times, once by each reader thread; then if the user types 3 another three lines of output should be read and printed. Make sure every intermediate update from the writer is reflected in that output (testing writer priority). You can keep around reader threads for re-use or exit them immediately after having read and printed their status information.
Commit the previous step to the repository!
Add an exit command that tells the child thread to immediately exit. The parent thread should then wait for the child thread(s) to exit, clean up any resources and exit the program.

Don't forget to add new files to your repository and the Makefile as usual. When done with the milestone, use the svn copy command to submit all your files as milestone4!

Week 11, 15 May 2012 (10 marks)

Real-Time Scheduler

The task of this milestone is to specify, design, and implement a real time system scheduling library based on the discussed principles for task scheduling and real time systems. Initially, the library should just support static, non-preemptive, table-driven, periodic scheduling. The scheduling library should be usable from within an arbitrary real time computer program called the "client program". The library should support the following features:

Handling of periodic tasks
Specification of an activation period (in microseconds) for each task
Specification of a deadline (worst case execution time) for each task
Run-time checking of deadlines (and the proper generation of exceptions)

The library should be implemented in C and provide interfaces for C client programs. See also the hints below!

Write a test program that thouroughly test your library. In the test program, print when each task gets scheduled.

Dynamic Scheduling Algorithms

Extend your library to handle the following real-time scheduling algorithms:

dynamic scheduling with static priorities:
- Rate Monotonic (RM)
dynamic scheduling with dynamic priorities:
- Earliest Deadline First (EDF)
- Least Laxity (LL)

Extend your test program to test the above scheduling algorithms and to allow the following interactive commands:

exit ... clean up and exit the program.
add period deadline [runtime] ... add a new task and print its ID (e.g. a task number)
del task ... delete the given task.

By default, the add command should creat a task with a runtime that uses up half of its deadline time (e.g. if a deadline of 10 microseconds is specified, the task should actually be running for 5 microseconds). Make sure the system detects (after the fact) if a task misses its deadline.

Don't forget to add new files to your repository and the Makefile as usual. When done with the milestone, use the svn copy command to submit all your files as milestone5!

Bonus Marks

A maximum of 20 bonus marks may be awarded for features that significantly go beyond the requirements of this assignment (e.g. an advanced status monitor that measures throughput in packets per second, or creating an additional version of the final milestone that uses a monitor instead of semaphores). While these bonus marks cannot take you past the maximum 70 marks (35 %) for the assignment, they can make up for any marks you lost elsewhere in this assessment item.

If you want to go for bonus marks, please put documentation of what you did that you think deserves bonus points into a text file called BONUS

Some Hints

In addition to the hints below, also see assignment 1 for more hints!

Hints for Milestone 1 (and later milestones)

Creating and Exiting Threads: The pthread_create() function can be used to create a child thread. Unlike fork(), pthread_create() actually takes a function to invoke when the child thread gets started. The child thread ends when that function returns or pthread_exit() is called by the child. (Warning: never call exit() from within a child thread, as this will exit the whole process, not just the thread!)
Waiting for Threads: The pthread_join() function waits for a child thread to exit and collects its exit status. Simpilar to processes, by default, all exited children need to be joined (waited for) to prevent hitting the maximum number of allowed child threads within a process!
Creating and Destroying Mutexes: A mutex is a simple variable of type pthread_mutex_t. Before you can use a mutex, you will need to initialise it by passing its address to pthread_mutex_init(). If you no longer need a mutex, you need to call pthread_mutex_destroy() to free all resources allocated for that mutex.
Locking a Mutex: You can lock a mutex using pthread_mutex_lock() – this will wait for the mutex if it is currently locked. Note: by default, mutexes are not recursive, so you must not attempt to lock a locked mutex from within the same thread!
Unlocking a Mutex: To unlock (release) a mutex you have locked (and signal all threads waiting for that mutex), use pthread_mutex_unlock().

Hints for Milestone 2 (and later milestones)

Creating and Destroying Condition Variables: A condition variable is of type pthread_cond_t. Before you can use a condition variable, you will need to initialise it by passing its address to pthread_cond_init(). If you no longer need a condition variable, you need to call pthread_cond_destroy()
Waiting on a Condition Variable: You can wait on a condition variable using pthread_cond_wait(). Note that this function takes a mutex as a second parameter. That mutex must be locked at the time pthread_cond_wait() gets called and will get unlocked for the period of time (if any) the thread is actually waiting for the condition.
Signalling a Condition: You can signal any thread waiting on a condition variable using pthread_cond_signal(), which will wake up one thread waiting on the given condition variable.
Using GCD: See the course content page for example code on how to use GCD.; There you will also find a link to the Dispatch Queues chapter in the GCD Concurrency Programming Guide.

Hints for Milestone 3 (and later milestones)

Reading random numbers from /dev/random: /dev/random is a simple file that you can open() and read() from. The easiest way to read a (binary) integer, is to use the read() function (simply pass the address of a uint8_t variable as the buffer to read into, and sizeof(uint8_t) as the size (count)).
Creating a dynamic buffer: Just use a circular buffer as described in the synchronisation lecture notes. Since the buffer size is a command line parameter, you can use malloc() to allocate memory for your buffer (don't forget that malloc() requires the size of the buffer in bytes!).
Using GCD Semaphores: Instead of your own semaphores, you can use dispatch_semaphore_create() to create libdispatch semaphores and then use these

Hints for Milestone 4 (and later milestones)

Dispatching: A good way to implement dispatching is to use dispatch_sync_f(). Alternatively, you can use threads and semaphores.

Hints for Milestone 5

Real-Time Scheduling: Re-read the lecture notes and chapters 9 and 10 of the text book if you have troubles understanding some of the concepts. Use the lab and forum to get help with problems you might have!
Least Laxity: Laxity is the time between when the task will have finished and its deadline. This requires the run time to be known or estimated by the scheduler. In your test program implementation, you can use the (explicit or implied) runtime from the add command and the given deadline to calculate laxity.

Online Help

Latest Announcements

03/04/2012: Assignment 2 is now available!
27/02/2012: Assignment 1 is now available!
25/02/2012: Please note that labs start in week 1

Global links

Systems Programming (Semester 1, 2012)

Assignment 2 for Systems Programming

Programming Task

Milestones and Deadlines

Week 7, 17 April 2012 (15 marks)

Subversion Repository

Multi-Threaded Hello World

Makefile

Targets: `clean` and `all`

First Steps in Synchronisation

Implementation Steps

Week 8, 24 April 2012 (15 marks)

Creating a Semaphore

Semaphore Implementation

Using GCD

Week 9, 1 May 2012 (15 marks)

Event Counter

Sequencer

8 Bit Random Number Generator

Producer/Consumer Algorithm

Implementation Steps

Week 10, 8 May 2012 (15 marks)

Network Status Monitor

Implementation Steps

Week 11, 15 May 2012 (10 marks)

Real-Time Scheduler

Dynamic Scheduling Algorithms

Bonus Marks

Some Hints

Hints for Milestone 1 (and later milestones)

Hints for Milestone 2 (and later milestones)

Hints for Milestone 3 (and later milestones)

Hints for Milestone 4 (and later milestones)

Hints for Milestone 5

Online Help

Latest Announcements

Footer

Global links

Breadcrumb

Systems Programming (Semester 1, 2012)

Assignment 2 for Systems Programming

Subversion Repository

Multi-Threaded Hello World

Makefile

Targets: clean and all

First Steps in Synchronisation

Implementation Steps

Creating a Semaphore

Semaphore Implementation

Using GCD

Event Counter

Sequencer

8 Bit Random Number Generator

Producer/Consumer Algorithm

Implementation Steps

Network Status Monitor

Implementation Steps

Real-Time Scheduler

Dynamic Scheduling Algorithms

Bonus Marks

Online Help

Latest Announcements

Footer

Targets: `clean` and `all`