Assignment - System Software
Task 1
Below is a multithreaded program with two threads. The first thread displays the letter ‘X' on the screen and the second thread displays the letter ‘O' on the screen. The threads are executed on a busy (with several active processes) computer on a time-sharing manner where the execution path of the threads is completely unpredictable.
#include #include #include
// repeat the times (*) operation 100,000 times to slow down the
// execution of the instructions #define RPT 100000
void* print_X() { int i;
float x;
while (1) {
// the multiplication operation below is for consuming some CPU
//time to slow down the execution
for(i=0; i
printf("X");
}
}
void* print_O() { int i;
float x;
while (1) {
// the multiplication operation below is for consuming some CPU
//time to slow down the execution
for(i=0; i
printf("O");
}
}
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");
}
An instance of the execution of the program produced the output below. Newlines and line numbers were added manually after the output was captured to make it more readable. Based on the information and assumption given above, please answer the following questions:
A. Suppose that Line 1 of the output indicates the corresponding thread completed the full duration of its allocated time slice. Has the thread completed its execution after Line 1?
B. Line 2 is shorter than Line 1. What could be the reason(s)?
C. What could be the possible reasons that caused the output from Line 08 to Line 15?
D. Assuming the program is executed to completion, will the effective execution output of each of the 2 threads (that is the number of Xs and Os printed) be different if the process executing this program is the only active process in the computer? Why and why not?
E. Is it possible to produce exactly the same output (sequence of Xs and Os) with multiple execution instances of the program? Why or why not? Is it possible to have Os printed out before Xs? Why or why not?
01: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
02: OOOOOOOOOOOOOO
03: XXXXXXXXXXXXXXXXXXX
04: OOOOOOOOOOOOOOOOOOO
05: XXXXXXXXXXXXXXXXXX
06: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
07: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
08: XXX
09: O
10: X
11: O
12: X
13: O
14: X
15: O
16: XXXXXXXXXXXXXXXXXXXXXXXXX
17: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
18: XXXXXXXXXXXXXXXXXXXXXXX
19: OOOOOOOOOOOOOOOOOOOOOOOO
Task 2
Below is a program that mimics a webpage counter - the counter increases by one for every visit. To count multiple concurrent visits, a new thread is created per every request for a connection from a remote web browser. The variable cnt stores the counter value 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 int cnt=0;
void* counter() {
int cntLocalCopy; 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 () { int i; float r;
pthread_t tid[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 connection request 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 produced the following output for the corresponding instances of executions.
A. 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?
B. Modify this program on a platform (Linux or Windows) and programming language of your choice to produce accurate and consistent results.
C. Write a multithreaded program (with two threads - one for writing to a buffer and another for reading from the buffer) on a platform (Linux or Windows) and programming language of your choice. The two threads run concurrently and share the buffer which can be implemented as an array with a maximum capacity of 10 characters. Below is a description of the actions performed by each thread. This can be achieved with a minor modification of the program (avoidance.c on Canvas) from Week 7 lab task.
Thread 1 (writer):
o Reads one character at a time from keyboard.
o Adds the character to the buffer. Thread 2 (reader):
o Reads one character at a time from the buffer.
o Removes the character from the buffer.
o Write the character, together with the number of the remaining characters in the buffer, to the console, e.g., [c:5].
Ensure the threads are properly synchronized so that the reader thread does not attempt to read from an empty buffer and the writer thread does not write into a full buffer. You also need to ensure the buffer is accessed by one of the threads at any given time to maintain the consistency and integrity of data in the buffer.
Task 3
Based on the principles of paging memory management systems, answer the following questions.
A. Briefly explain how a paging memory management system works. Please include the following in your explanation:
- What logical memory addresses are, what physical memory addresses are, and also the relation between the two?
- What level of memory, logical or physical, does the process image of an application occupy?
- What type of memory addresses, logical or physical, does the physical processor (or CPU) operate on?
B. Does a paging memory management system have fragmentation problem at the physical memory (RAM) level? Why or why not? Does a paging memory management system have fragmentation problem at process image level? Why or why not?
C. Can an application running on a computer with a paging memory management system directly access the physical memory? Why or why not?
D. Write down your conclusion about the effectiveness and usefulness of memory defragmentation applications. Your conclusion should be based on the arguments in your answers to the previous questions.
Task 4
Write a program (with the programming language and on the platform of your choice) to demonstrate the memory leak problem. The full program and the program outputs should be included at the end of the report as an appendix.
If you write the program on a platform which has built-in garbage collection mechanism, special care has to be taken to introduce the memory leak problem.
Execute the program until it cannot proceed anymore. You may have to allocate big chunks of memory iteratively to reach to this point quickly. This is even more so if you are running the program on a 64-bit operating system. Based on your observation and your understanding of the principles of a paging memory management system, answer the following questions:
A. How much memory has the program used when reaching the point where it cannot proceed anymore? What is the physical (32-bit or 64-bit) and logical address space of the computer you run this application on? What is the size of the physical memory (RAM) of the computer you run this application on?
B. What type of memory, virtual or physical, is exhausted when there is a memory leak problem with a process?
C. When a process that has a memory leak problem cannot proceed anymore, does it prevent any other program from starting/running due to lack of memory? Does it slow down the whole system?
D. On a platform which has built-in garbage collection mechanism, e.g., .NET and JVM, to a large extent, the memory leak problem can be avoided. Why?