3420ICT Systems Programming 3420ICT_3171_NA Assessment Assignment 2 Assignment 2 Milestone 1 GIT Repository Before you start, make sure you create a new GIT repository for assignment 2 inside your (empty) working directory, e.g.: mkdir assignment2 cd assignment2 git init Don't forget to commit all changes you are making in the assignment (using git commit). To get marks for the repository, after all the steps in the following sub­sections, you need to create a milestone1 tag for your final milestone submission using the git tag command. Make sure you only perform the last step above after you have completed all the steps below but before you zip up and upload your assignment to be marked! First Steps in Synchronisation The objective of this part is to explore simple thread synchronisation using mutexes (simple locks) by implementing a program (in C, C++, or Swift) called sync 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 then wait for the user to hit return (or enter), then notify the child thread to exit. The parent thread should wait for the child to exit, then print "child thread is gone" and also exit. Implementation Steps 1. Create a new program sync.c (or the corresponding file extension if you are using one of the other languages above) and add it to the Makefile and the git repository. 2. Add a buffer (that holds at least 128 characters) to your parent thread. Pass the address of that buffer to the child thread. 3. In the parent thread, read one line of input into the buffer. Print the buffer to stdout from within the child thread (do not synchronise with the parent at this stage). Explain in your README what happens and why! 4. 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! 5. 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 and whether adding further mutexes (but no other synchronisation means such as busy waiting) would help. Uttam Thapa6. Make the parent notify the child once the user has hit the enter key. The child should then notify the parent that it is exiting, and then exit. The parent should wait for the notification, print "child thread is exiting", then wait for the child to actually exit (and print the "child thread is gone" afterwards) and then end the whole program (process). Do you need a third mutex for this notification? Will this be reliable under all circumstances? Explain why/why not! Your program needs to compile without warnings (if you use C, or C++, make sure you use the - Wall flag and the C11/C++11 language standard (gnu11/gnu++11 is fine))! Add your program to the repository using git add sync.c (or the corresponding file names for other programming languages) and commit it after every change using git commit -am "log message" (replace log message with a text that describes the changes you have made). Makefile Create a Makefile that compiles your program so that you can run it from the command line using ./bin/sync (followed by enter). Add your Makefile to the repository using git add Makefile and commit it after every change using git commit -am "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). Submission Don't forget to commit all steps to the repository individually. When you are done with the milestone, use the git tag command to tag everything as milestone1! Make sure you extend the clean and all targets of your Makefile for all the subsequent milestones in the coming weeks! Milestone 2 Semaphores 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 1. Create a new module sema with the corresponding file extension (e.g. sema.swift if you use Swift, sema.c with an accompanying sema.h for C, etc.) that implements the above algorithm, and add it to your existing git repository for assignment 2. Embed all the data needed to implement your Semaphore in a single struct or class. Don't use any existing POSIX or other Semaphore implementations 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 section on the top level assignment page!). 2. Add an initialiser function to your code that sets up a Semaphore and intialises it to a predefined (integer) value. 3. 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). 4. Test your code with a separate program sematest.c (or main.swift) that re­implements last week's synchronisation steps but this time uses semaphores. Use the smallest number of semaphores necessary (and make sure you don't use any other synchronisation constructs outside your semaphore implemetation (with the only exception being pthread_join()))! 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)! 5. Add a short test report to your documentation! Submission Don't forget to any add all new files to the Makefile and your repository as usual. When done with the milestone, use the git tag command to tag your files as milestone2 before zipping up your folder and submitting it! Milestone 3 16 Bit Random Number Generator The goal of this milestone is to solve the Producer/Consumer problem for a random number generator by using one of the algorithms discussed in the lecture, i.e., either by using your semaphores from last week, by implementing a monitor using condition variables and mutexes, or byusing sequencers and event counters. One thread acts as a random number generator that reads true random numbers from the reliable 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). Implementation Steps (Don't forget to also have a look at the hints section!) 1. Create a function that, in a loop, reads high quality 16 bit random numbers of type uint16_t for C/C++/Objective­C (as defined in ) or UInt16 for Swift from /dev/random as fast as it can. 2. 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. 3. 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. 4. 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. 5. Create your own synchronisation data types or use the operating system provided ones to implement your choice of synchronisation (i.e. monitor, semaphores, or message passing) 6. Modify your protection code to respect the maximum buffer fill level. Make sure that the producer waits if the maximum fill level is reached! 7. Modify your protection code to respect the minimum buffer fill level. Make sure that the consumer waits if the minimum fill level is reached! 8. Create a test program that uses threads or GCD to spawn the concurrent producer as a child thread. 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 lower­case hex number with a maximum of four (4) digits, prefixed by 0x (e.g. 0xfeed for the 16 bit decimal number 65261). 9. 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 5, and the minimum fill level should be 0 (zero). 10. 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). Ensure that the 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 (at the fastest pace possible, but make sure you synchronise with the producer if it cannot produce random numbers fast enough); then if the user types 3 another three integers should be read from the buffer and printed. 11. Add an exit command that cleans up any resources and exits the program. Don't forget to any add new files to the Makefile and your repository as usual. When done with the milestone, use the git tag command to tag your files as milestone3 before zipping up your folder and submitting it!