Intermediate Level Tasks : Below is a simple program. It creates 2 threads. The first thread keeps printing out X on the screen, and the second thread keeps printing out O on the screen. Except for the thread activity part, you do not have to pay much attention to the program language details. When executing the program, due to the time sharing nature between the 2 threads, we expect to see this pattern of execution: "XXXOOOXXXOOO...". Although not really accurate, we can regard the number of Xs or Os in the output as the indicator of the duration of the execution of the corresponding thread in its allocated time slice. In an ideal round-robin time sharing situation, we would see the same number of Xs, followed by the same number of Os, and then Xs, and then Os, and forever (until the program is terminated by an external force).
NOTE: Exactly what happened during the course of the execution is actually unknown. The best we can do is to take an informed guess, which is close enough. As already stated, it is not really accurate to regard the number of Xs or Os in the output as the indicator of the duration of the execution of the corresponding thread in its allocated time slice. Printing out Xs or Os is actually I/O operation. In this question, we do not take this nature into account. The fundamental point for this question is that the execution in a time sharing environment is very unpredictable. Many unknown and also unpredictable factors can change the time allocation to the threads and processes. However, each individual thread or process, effectively, executes as in isolation, thanks to the context preserving and restoring operation.
|
#include
#include
#include
// repeat the times (*) operation 100,000 times to slow down the
// execution of the instructions
#define RPT 100000
void* print_X() { inti; float x;
while (1) {
// consuming some CPU time to slow done the execution
// no logic meaning; can be safely ignored for(i=0; i
printf("X");
}
}
void* print_O() { inti; float x;
while (1) {
for(i=0; i
}
}
int main () {
pthread_t tid1, tid2;
pthread_create (&tid1, NULL, &print_X, NULL); pthread_create (&tid2, NULL, &print_O, NULL);
// Wait till threads complete. Not really related to this
// question in this assignment. Can be ignored.
pthread_join(tid1, NULL); pthread_join(tid2, NULL);
printf ("\n==========================\n");
}
|
One execution of the program produced the following output, next page. Newlines and line numbers were added manually after the output was captured to make it more readable. Please explain:
1. Suppose that Line 1 of the output indicates that the thread completed the full duration of its allocated time slice. Has the thread completed its execution yet? If yes, which thread produced the output in Line 3, and how? If not, why cannot the thread continue its exclusion anymore? Please explain what happened behind the scene, which we cannot see from the output, at the end of the line to the beginning of the next line.
2. Line 2 is shorter than Line 1. What could be the reason(s)?
3. What could be the possible reasons which caused the output from Line 08 to Line 15?
4. Will the effective execution output of the 2 threads be different, in this very program, when the computer is very busy and also with many interrupts in comparison with when the computer is almost idle with no other activities any all ?Why and why not?
Advanced Level Tasks
For the following tasks, you should write a proper report to explain the logic of your programs and also answer the questions from the tasks. Your report should read like a textbook on programming. You can use figures and pieces of program code in the report to help you to explain. The full programs and the program outputs should be included at the end of the report as an appendix. A submission with only the programs and without the report will not attract any mark; neither will a report without the programs.
Task 1: Below is a program which mimics the web page counter, counting how many visits to a web page. The counter increases by 1 for every visit. To mimic multiple concurrent visits, a new thread is created in response to a connection from a remote web browser. A real web server actually behaves like this. The variable cnt is the counter and is shared by all threads.
|
#include
#include
#include
// repeat 100 times to mimic 100 random visits to the page
#define RPT 100
//web page visit counter intcnt=0;
void* counter() {
intcntLocalCopy;
float r;
cntLocalCopy = cnt;
// mimicking the work of the sever in serving the page to
// the browser
r = rand() % 2000; usleep(r);
cnt = cntLocalCopy + 1;
} int main () { inti; float r;
pthread_ttid[RPT];
// seed the random number sequence srand(time(NULL));
for (i=0; i
// mimicking the random access to the web page r = rand() % 2000; usleep(r);
// a thread to respond to a connect from a browser pthread_create (&tid[i], NULL, &counter, NULL); }
// Wait till threads complete. for (i=0; i
pthread_join(tid[i], NULL);
}
// print out the counter value and the number of mimicked visits
// the 2 values should be the same if the program is written
// properly printf ("cnt=%d, repeat=%d\n", cnt, RPT);
}
|
The program was executed a number of times and the following are the output of each run.
cnt=63, repeat=100 cnt=59, repeat=100 cnt=58, repeat=100cnt=63, repeat=100 cnt=59, repeat=100
cnt=59, repeat=100
1. Explain why the counter value is smaller than the number of visits? From the list, the value of cnt is around 60. It is possible for the value be 50 or 70? Why or why not?
2. Please re-implement this program on the platform (Linux or Windows) of your choice with the programming language of your choice and then apply a proper fix. Report the outcome of your fixed program, and also explain your fix. This sample program has been tested on a Linux platform. General hint: please search the Internet on the synchronisation primitives (e.g., mutex, semaphore, or monitor) and their usages on your platform with your programming language, e.g., googling "synchronisation primitive C pthreadlinux". [; hint: please note that the difficult level of the task is not proportional to the mark, if measured by the scales of basic and intermediate level tasks]
Task 2: [hint: please note that the difficult level of the task is not proportional to the mark, if measured by the scales of basic and intermediate level tasks.]
Write a program on the platform (Linux or Windows) of your choice with the programming language of your choice. The program has two threads running concurrently. The 2 threads share a single buffer, which can be implemented as an array, with the capacity of storing maximum 8 characters.
Thread 1 endlessly performs the following actions in sequence.
- Read one alphabet character at a time from the keyboard. The character can be followed by an "Enter" if you don't know how to pick up a key stroke straightaway without waiting for the "Enter" key.
- Add the character into the buffer.
Thread 2 endlessly performs the following actions in sequence.
- Read one character from the buffer at a time.
- Remove the character from the buffer.
- Change the case (upper to lower or vice versa) of the character.
- Write the character, together with the number of the remaining characters in the buffer, to the console, e.g., [c:5].
- Sleep for a random period of time. The period of time should be decided by a random number, which is different in each round of this action sequence. The random number should be large enough so that the shared buffer will have some characters at some time.
You should properly synchronize the two threads to guard the data integrity in the buffer so that there will be no misbehaviors. When running the program, please input about 8 characters with a random delay after each input, and then wait for a long time, long enough for all characters being removed from the buffer by Thread 2.
1. What kind of display does the program produce? Explain the interaction, which is responsible for the display, between the 2 threads.
2. Explain how your program deals with the situation when the buffer is empty while Thread 2 is trying to read and remove a character from the buffer. Explain how your program deals with the situation when the buffer is full while Thread 1 is trying to add a character into the buffer.