Total 12 points
(version 1.0)

COMP3230A Principles of Operating Systems

Program project Two
Due date: Oct 24, 2018 (Wednesday) at 5:00 pm

Principles of Operating Systems案例Principles of Operating Systems案例


Programming Exercise – Timekeeper: A new system utility program


Objectives
An assessment task related to ILO4 [Practicability] – “demonstrate knowledge in applying system software and tools available in modern operating system for softwaredevelopment”.
A learning activity related to ILO
The goals of this programming projectare:
to have hands-on practice in designing and developing a system utility program, which involves the execution of multiple processes and collection of processstatistics;
to learn how to use various important Unix systemfunctions
to perform process creation and programexecution;
to interact between processes by using signals and pipes;and
to get the process’s running


Task
For this project, you are going to write a new system program – timekeeper, which is being used by end- users to obtain the execution statistics of a program or sequence of programs connected by pipes. This utility program will report the wall clock (real) time, user time, system time, number of context switches, and termination status of each program. For example, to obtain the execution statistics of the program firefox, we enter the following command under the command prompt:

./timekeeper firefox

After the firefox program terminated, timekeeper will display the firefox process’s running statistics:

The command “firefox” terminated with returned status code = 0 real: 37.21 s, user: 4.13 s, system: 0.44 s, context switch: 20292

To release the complexity of building this utility program, you are going to develop the program in 3 stages:

Stage 1 – Create the 1st version of the timekeeper program that:

parses input arguments to extract the command (and itsarguments),


creates a child process to execute the command,and
waits for the child process to terminate and then prints out child process’s terminationstatus
(without statistics).



Stage 2 – Modify stage 1 program to make the timekeeper process:

not being affected by the SIGINT signal while the child process may be affected by the SIGINT signal,
checks whether the child process was terminated because of interrupted by a signal,and
prints out the running statistics of the terminated child


Stage 3 – Modify stage 2 program to allow the timekeeper program to:

accept multiple commands (with arguments) that are interconnected by the special symbol“!”,
which acts as the pipe operator, and

print out the termination status and running statistics of each terminated child


Specification
Basic features of the timekeeper program



When invoking the timekeeper program without arguments, it will terminate successfully without any output.


When invoking the timekeeper program with input arguments, it will interpret the input and start the corresponding program(s) with necessary arguments. The timekeeper program should be able to execute any normal program (i.e. programs that are in binary format) that can be foundunder


absolute path (starting with /) specified in the command line,g.
./timekeeper /home/tmchan/a.out

relative path (starting with .) specified in the command line,g.
./timekeeper ./a.out abc 1000

directories listed in environment variable $PATH,g.
./timekeeper gedit readme.txt

where gedit is in the directory /usr/bin, and timekeeper should locate the target program by searching through all paths listed in the PATH environment variable, e.g.,

$PATH=/bin:/usr/bin:/usr/local/bin

After a new child process is created, timekeeper will print out a message that shows the child process id. For example:

Process with id: 11463 created for the command: cat

If the target program cannot be started/executed, timekeeper will print out a message to indicate the problem. For example:

timekeeper experienced an error in starting the command: xxxxxx



To reduce the complexity of this project, other special characters (e.g. ‘, “, >, >>, <, <<, |) will not be

appeared in the input arguments.

When the invoked program terminated, timekeeper will print out the wall clock (real) time, user time, and system time used by that process as well as the number of context switches experienced by that process. Here are the definitions of thosetimings:


Real time: the elapsed wall clock time (in seconds) between the start and end of the invoked program.


User time: the total number of CPU-seconds that the process spent in user
System time: the total number of CPU-seconds that the process spent in kernel
All timings are displayed in units of second and have the precision of 2 decimal places. For example,

real: 37.21 s, user: 4.13 s, system: 0.44 s, context switch: 20292

When the invoked program terminated successfully, timekeeper will print out thatprocess’s
termination status in addition to the running statistics as defined in item 3. For example,



The command “firefox” terminated with returned status code = 0 real: 37.21 s, user: 4.13 s, system: 0.44 s, context switch: 20292

The timekeeper process and its child process(es) are required to respond to the SIGINT signal (generated by pressing Ctrl-c or by the kill system command) as according to the followingguideline:


Upon receiving the SIGINT signal, the child process(es) will respond to the signal as according to the predefined behavior of the program in response to the SIGINT signal; while the timekeeper process should not be affected by SIGINT and continue until it detects that its child processes have terminated.


Instead of printing out a process’s termination status, timekeeper will output a message to indicate that the corresponding process is terminated by the SIGINT signal. Forexample,


The command “add” is interrupted by the signal number = 2 (SIGINT) real: 1.38 s, user: 1.26 s, system: 0.10s, context switch: 33

Like item 5, when the invoked program terminated involuntarily because of receiving signal (e.g. SIGSEGV), timekeeper will output a message to indicate that the corresponding process is terminated by a specific signal. Forexample,


The command “segfault” is interrupted by the signal number = 11 (SIGSEGV)

real: 0.45 s, user: 0.29 s, system: 0.02s, context switch: 27



The timekeeper program uses a special symbol “!” to act as the pipe Please note thatwe
are not using the tradition pipe symbol “|” as we don’t want the shell process to be confused if “|”



is used in this project. When the timekeeper process detects that its input arguments contain the special symbol “!”, it will identify the sequence of commands and will start the corresponding programs with necessary arguments. In addition, these programs will be linked up as according to the logical pipe defined by the input arguments. For example,



./timekeeper cat c3230a.txt ! grep kernel ! wc -w



In this example, the timekeeper program will create three child processes to execute the cat, grep, and wc programs. The standard output of the cat process is connected to the standard input of the grep process, and the standard output of the grep process is connected to the standard input of the wc process.

When detecting a child process has terminated, timekeeper will print out the termination status (or signal information) and running statistics of that terminated child process. Upon detecting all child processes have terminated, timekeeper will terminate too.



System Calls



You need the following system calls to build the timekeeper program.

fork() – The fork function is the main primitive for creating a child


exec family of functions – Use one of these functions to make a child process execute a new program.


waitpid() and waitid() – Wait for a child process to terminate or stop, and determine its


signal() and sigaction() – Specify how a signal should be handled by the


pipe() – This creates both the reading and writing ends of the pipe for interprocess communication. The returned reading and writing ends are represented as file


dup2() – This duplicates an open file descriptor onto another file descriptor; in other words, it allocates another file descriptor that refers to the same open file as the


Note: You are not allowed to use the system() or popen() functions to execute the target program.

Documentation
At the head of the submitted source code, state clearlythe
Filename
Student’sname
Student Number
Developmentplatform
Compilation – describe how to compile your program
Remark – describe how much you havecompleted
Inline comments (try to be detailed so that your code could be understood by otherseasily)


Computer platform to use
For this project, you are expected to develop and test your programs under Ubuntu 16.04. Your programs must be written in C and successfully compiled with gcc. It would be nice if you develop and

test your program on your own machine (with native Ubuntu (or Linux installation) or the course’s VM). After fully tested locally, upload the program to the department’s X2Go server for the final tests.

Submission
Submit your program to the project Two submission page at the course’s moodle web site. Name your program with this format: timekeeper_StudentNumber.c (replace StudentNumber with your HKU student number). As the Moodle site may not accept source code submission, please compress your program to the zip or tgz format.

Grading Criteria

Your submission will be primarily tested under Ubuntu 18.04. Make sure that your program can be compiled without any error or warning. Otherwise, we have no way to test your submission and thus you have to lose all the
As the tutor will check your source code, please write your program with good readability (i.e., with good code convention and sufficient comments) so that you will not lose marks due to possible confusions.


Documentation (0.5 points) · Include necessary documentation to clearly indicate the logic of the program
· Include required student’s info at the beginning of the program

Correctness of the program (11.5 points) Stage 1 – Process creation
(3.5 points)

· Given the filename of a standard Unix utility program, the system can locate and execute the corresponding program
· Can work with full path and relative path

· Can work with executing a program with any number of arguments

· Can handle error situation correctly, e.g., incorrect filename, incorrect path, not a binary file, etc.

· display a message to report the termination status of the child process

Stage 2 – Signal handling and report statistics (4 points) · timekeeper process should not be terminated by SIGINT signal
· child process can be terminated by SIGINT signal

· display a message to indicate that the child process is terminated by signal

· print out the wall clock time, user time, system time and the number of context switches experienced by the child process in the correct format



Stage 3 – Support pipeline
(4 points)

· Can execute two programs which are connected by the
logical pipe symbol “!”

· Can execute two programs with any number of arguments and are connected by the logical pipe

· Can execute any number of programs with any number of arguments and are connected by a sequence of pipes

· For each child process, display the running statistics and termination status (or signal information) of the process.



Plagiarism
Plagiarism is a very serious offence. Students should understand what constitutes plagiarism, the consequences of committing an offence of plagiarism, and how to avoid it. Please note that we may request you to explain to us how your program is functioning as well as we may also make use of software tools to detect software plagiarism.









Total 12 points
(version: 1.0)
COMP3230A Principles of Operating Systems

Programming project Three
Due date: Nov 21, 2018 (Wednesday) at 5:00pm



Programming Exercise – An Implementation of Producer/Consumer Interaction


Objectives
An assessment task related to ILO4 [Practicability] – “demonstrate knowledge in applying system software and tools available in the modern operating system for softwaredevelopment”.
A learning activity related to ILO 2a and ILO
The goals of this programming exerciseare:
to have hands-on practice in designing and developing multithreadingprogram;
to learn how to use POSIX pthreads library to create, manage, and coordinate multiple threads in a shared memoryenvironment;
to design and implement a synchronization scheme for a multithreaded process using semaphores or locks and conditionvariables;
to consolidate your understanding of how to structure the multithreaded program in the bounded- buffer


Task
Counting word frequency – We want to count the frequencies of the selected keywords in a document, and your task is to write a multithreaded program to generate the resulting statistics after scanning through the document. We create multiple threads in the process; each thread is working as a worker to search and count the frequency of a keyword.



We are going to structure our solution in the form of producer/consumer interaction, such that the master (main) thread works as the producer that places keywords to a task pool, while the worker threads work as the consumers that obtain a keyword from the task pool and process it.



Specification
Step 1 – Download the sequential program – wordcnt0.c from the Course’s web site at moodle.hku.hk. The program accepts two arguments:

./wordcnt0 [target plaintext file] [keyword file]

“target plaintext file” gives the filename of the file to be searched by the program. We assume the contents of the file are just
“keyword file” gives the filename of a file which contains all the keywords need to be counted. Any characters other than the 26 letters will not be appeared in keywords to be


Assume both target plaintext file and keyword file are located under the same directory of the wordcnt0 program.
The keyword file consists of � + 1 lines of data. The first line consists of a number c, which gives the number of keywords to be counted. Then follows by c lines; each line contains a keyword to be counted. For example, below are the contents of a sample keyword file -txt:
4

child process string text

After getting input from the keyword file, the program searches target plaintext file and counts the frequency of each keyword in the plaintext file one at a time. In the end, the program output all results to the STDOUT. In the searching and counting, the program neglects about whether the word is capitalized or not, e.g., “WE”, “we” and “We”, it treats them as the same word, i.e., case insensitive.



Examine the sequential program and understand its execution logic before moving to the implementation.



Step 2 [Optional] – Create a simple multiple threads program with each thread executes on searching just one keyword in the plaintext file. After reading in the number of keywords to be counted (from the keyword file), the main program (in here we called it master thread) creates a new worker thread (using pthread_create()) and assigns a keyword to the worker thread to work on, i.e., one worker thread is given one task only. After distributing all the tasks, the master thread simply waits for all worker threads to complete (using pthread_join()) before it terminates.



For each worker thread, its task is to search the plaintext file and count the frequency of the assigned keyword. Then, it outputs the counting result to the STDOUT directly and exits. As each worker thread outputs its result independently, you may find that the results are displayed randomly in any order (in different runs) and may mix with each other. To test for concurrent execution, you can test your program in the academy servers, which has 48 cores.



The purpose of this step is to help you to get familiar with the use of ptherad_create() and pthread_join().



Step 3 – You are going to implement the control logic of the multithreaded program in the form of bounded- buffer interaction and use semaphores or (mutex locks and condition variables) to synchronize and coordinate between multiple threads.



To apply the bounded-buffer model to this application, we use the master thread to work as a producer and all worker threads act as the consumers. Unlike step 2, the multithreaded program only creates a fixed number (T) of worker threads regardless of the number of keywords. Producer communicates with all workers (consumers) via a task pool (the bounded-buffer), which is implemented as an array of C strings in this application. The array has N entries; each is for storing a keyword. The parameters T and N are runtime parameters obtained from the command line arguments. You can assume the number of worker threads is between 1 and 15 and the size of the bounded-buffer is between 1 to 10.



The master thread (producer) reads in keywords from the keyword file and places them one by one to the task pool. If the task pool becomes full, i.e., no empty entries, the producer should be blocked waiting for



empty entries in the task pool. This process would continue until all the keywords have been placed to the task pool.



The consumer would continuously check whether tasks (i.e., keywords) are available in the task pool. If the task pool is empty, consumers should be blocked waiting for new tasks to arrive. If there is a task in the task pool, one of the waiting consumers will obtain the task and remove it from the task pool.



To have better control on the output, we would like to ask all worker threads not to output the counting results directly to the screen (stdout); instead, they should return the keyword counts to master thread, and master thread will output all results only after it has waited for the termination of all worker threads.



We make use of the logic defined in Figure 30.12 of our E-textbook as the base for our implementation of this producer/consumer interaction. Here is the pseudocode that reflects the logic of producer/consumer interaction:



Producer



while still havekeywords
mutex_lock(pool_lock)
while task pool isfull
cond_wait(task pool becomes notfull)
endwhile
put a keyword in the next unused buffer of the taskpool
update the free pointer to point to next unusedbuffer
cond_signal(any waiting consumers that there is a newtask)
mutex_unlock(pool_lock)
endwhile
inform all worker threads that no more tasks will be assigned, and they should terminate after finished all pendingtasks
wait for all worker threads toterminate
print theresults


Consumer



while not yetterminated
mutex_lock(pool_lock)
while task pool isempty
cond_wait(task pool becomes notempty)
endwhile
copy a keyword from the next available task from the taskpool
clear the keyword from the taskbuffer
update the next pointer to point to next availabletask
cond_signal(the producer on this newly availablebuffer)
mutex_unlock(pool_lock)
perform the searching and counting of thistask
return the countingresult


is it time toterminate?
endWhile
exit


With this logic, the producer can pass all keywords via the task pool to worker threads to work on the computation. However, we still have to solve two issues: (i) how can worker threads pass the results to the master thread? (ii) how can worker threads know that it is time to terminate, i.e., no more new tasks?



You can have many methods to tackle these issues. Here are two possible mechanisms for your reference:

The master thread creates an extra array (like the struct output in wordcnt0.c) for worker threads to place their counting results. To coordinate between all worker threads, we need to have a mutex lock to guard against concurrent
After placing all keywords to the task pool, master thread places some extra sentinel keywords (e.g., “ xx ”) to the task pool to inform all worker threads to terminate. If there are k worker threads, the master thread should place k sentinel keywords to alert each worker
As implementing a solution to the bounded-buffer problem is one of the goals of this project, you are required to use the producer/consumer logic as defined in the above pseudocode. However, you have the flexibility to select your own mechanisms in handling the (i) collection of results and (ii) signaling the termination condition.

In order to show that a worker thread has successfully terminated, the going to terminated worker thread should pass the total number of tasks it has performed to the master thread.

Submission
Name the program to thrwordcnt_StudentNumber.c (replace StudentNumber with your HKU student number) and submit the program to the Course’s web site at moodle.hku.hk. To control the number (T) of worker threads and the size of the task pool (N), this program needs to accept two additional input arguments. Therefore, the program interface is changed to:

./thrwordcnt [number of workers] [number of buffers] [target plaintext file] [keyword file]



As the Moodle site may not accept source code submission, please compress your program to the zip or tgz format.

Sample Output

Please refer to the document “ass3-sample-output.pdf” for more information.



Documentation
At the head of the submitted source code, state clearlythe
Filename
Student’sname
Student Number
Developmentplatform
Compilation – describe how to compile your program
Remark – describe how much you havecompleted
Inline comments (try to be detailed so that your code could be understood by otherseasily)


Computer platform to use
For this project, you are expected to develop and test your programs under Ubuntu 16.04 / 18.04. Your programs must be written in C and successfully compiled with gcc. It would be nice if you develop and test your program on your own machine (with native Ubuntu (or Linux installation) or the course’s VM). After fully tested locally, upload the program to the department’s X2Go server for the final tests.



Grading Criteria
Your submission will be primarily tested under Ubuntu 18.04. Make sure that your program can be compiled without any error or warning. Otherwise, we have no way to test your submission and thus you may lose all the
As the tutor will check your source code, please write your program with good readability (i.e., with good code convention and sufficient comments) so that you will not lose marks due to possible


Documentation (0.5 points) · Include necessary documentation to clearly indicate the logic of the program
· Include required student’s info at the beginning of the program

Correctness of the program (11.5 points) · The program should be compiled and executed successfully, and the total no. of threads created in this program should be equaled to the no. of workers (input parameter).
· Worker threads must be executed in parallel.
· Must use the producer/consumer model to coordinate the threads.
· Can work with different numbers of worker threads, sizes of task pool, and numbers of keywords, and return “correct” results as compared to the sequential program. (Note: counting results could be displayed in any order; should not have duplication.)
· Worker threads must pass the counting results to the master thread.
· Worker threads can detect the termination condition and terminate successfully.
· Master thread should wait for all worker threads to terminate before displaying all counting results


Plagiarism
Plagiarism is a very serious offence. Students should understand what constitutes plagiarism, the consequences of committing an offence of plagiarism, and how to avoid it. Please note that we may request you to explain to us how your program is functioning as well as we may also make use of software tools to detect software plagiarism.