Quiz 2

Monday, October 23. 2006

Name: ______

  1. Describe the differences between a process and a thread in terms of
  2. how a programmer writes a program with multiple processes vs. multiple threads.
    (5) Threads are components of a single program (process). In writing a program with threads, the programmer has in mind a way that multiple, concurrent paths of execution(threads) through the program are going to provide a clearer or more efficient solution for the program [s]he is writing (e.g., the threads may be able to run in parallel on multiple processors if they are available). Threads are thus a feature of the high level programming language the programmer is using, either in terms of the syntax (as in Java) or as special library calls (e.g., the pthreads library used by C and its derivatives).
    Generally, processes are not used for solving a single problem as threads are (although they could be, but it is much more inconvenient than using built-in threads). That is, processes are generally autonomous and don’t cooperate with each other at all or as closely as threads. Furthermore, spawning new processes usually requires the programmer to use special operating system calls (such as through a fork() in Unix), and process synchronization among spawned processes requires even further special operating system calls to set up shared memory, inter-process communication, and so forth. So, processes are seldom used by the average programmer to solve problems that have concurrent aspects, but rather by systems programmers.
    (Another way to look at this to help one see the difference is that the programmer writing with threads needs to know only the high level programming language features for creating and synchronizing threads provided in the programming language and does not need to know anything about the OS on which the threaded program is to run. In programming with processes, the programmer would need to know not only the high level programming language, but a lot about spawning processes in the OS in use. Creating separate processes and making OS calls is different in different operating systems, so concurrent systems based on processes are not portable, whereas threaded programs using the high level language thread creation and synchronization sections are portable).
  3. how processes can communicate with each other vs. how threads can communicate with each other.
    (5) Since threads that are created as a program executes share the same code and global data as other threads, threads most easily communicate with each other through shared variables. No operating system calls are necessary for threads to communicate with each other.
    Processes, on the other hand, do not share data unless shared memory is specifically set up through a special operating system call. Thus, processes normally communicate through the use of signals, message passing mechanisms, and other means that must be set up through operating system calls.
  4. how an operating system views processes vs. threads.
    (5 ) A process corresponds to a program whose execution has been started by a user request or by another program. The operating system manages the execution of the program as a process, keeping track of the state of the process in a process control block.
    Threads, on the other hand, are components of processes. That is, threads are started by a process and execute in the same code space as the process that started them. An operating system may provide recognition and management of threads or it may not be aware of threads at all. In any case, if threads are handled by an operating system, the operating system manages the threads under the umbrella of the process control block of the process that started the threads.
  5. What is a critical section?
    (5) This is one of those definitions you were asked to memorize.
    A critical section is a section of code that requires mutual exclusion. That is, if one process (thread) is executing in a critical section of code, no other process (thread) can be executing in its corresponding critical section of code. For example, updating of a common, shared variable might be done in different processes (threads). The sections of code that update this shared variable in each of the processes (threads) would be corresponding critical sections. Only one of these processes can be executing in its corresponding critical section at a time to ensure the integrity of the variable being updated. It is important to note that a process (thread) can be interrupted while in its critical section, and if all corresponding critical sections are implemented properly, no other process (thread) will be able to get into its corresponding critical section until the interrupted process (thread) eventually gets to run again and leaves its critical section.
  6. Do all synchronization problems involve critical sections? Justify your answer.
    (5) No. The critical section (mutual exclusion) problem is just one of many synchroniation problems. For example, in the readers/writers problem, the corresponding code in each reader process or thread that reads a shared file or variable can be synchronized to allow as many readers as desire to execute in their corresponding reading code simultaneously (unlike the requirements for a critical section). On the other hand, only one writer (and no readers) can be allowed to be in the corresponding code that writes to the shared file or variable.
  7. Suppose the following:
  8. you are writing a program with N threads, where N >= 1 at any particular time
  9. there are 4 of the same resource (e.g., 4 of resource R) available for use by these threads
  10. each one of R must be used in a mutually exclusive fashion.
  11. the threads each execute the same code, which in pseudolanguage isgiven below
    Set up a semaphore shareResource and initialize it to 4 before any threads are spawned. Then start the N threads.
    loop
    some statements
    ...
    wait(shareResource)
    get the resource
    use the resource
    release the resource
    signal(shareResource)
    ….
    some statements
    endloop
  1. (5) Using semaphores, modify the above pseudolanguage code so that it solves the synchronization issue of ensuring that no thread tries to obtain a resource if there isn’t one available, but allowing a thread to gain a resource as long as at least one is available (don’t rewrite the entire program here; just modify the one above).
  2. Is your solution immune to deadlock? Justify your answer.
    (5) Yes. Since all processes need only one of resource R at a time, if a process gets one of the resources in R it will complete its execution of and release the resource. That is, since a process needs only one of R, it will never be involved in a “hold and wait.” Thus one of the necessary conditions for deadlock to occur does not hold in this instance.
  3. Is your solution immune to starvation? Justify your answer.
    (5) If we assume that the semaphore is implemented in a “fair” (e.g., first in first out) manner with respect to the processes that must wait in a queue when the semaphore is 0 or less at the entrance to the synchronized section, then starvation will not occur. However, if the situation is that some of the processes have higher priority than others and the higher priority processes are allowed to run first regardless of their position in the queue, starvation is a possibility. Finally, if the semaphore is managed in such a way that the entire queue of waiting processes is simply placed in the ready to run queue in arbitrary order when a signal call on the semaphore is made, starvation could also occur.
  1. Suppose that you have the same sort of scenario as in problem 4, but that at least four of the threads require two of the four resources simultaneously at some point in their execution. Of course, all threads will release their resources after using them (they may ask for them again later).
  2. Discuss any deadlock or starvation issues that might need to be addressed in solving this problem.
    (5) We now have the issue that some processes need more than one of the resource. This means that there might be the possibility for two or more processes to “hold and wait” (get one of the resources and hold onto it while awaiting another from the other process that is holding one and waiting for another to be released by the first process). There should be no particular issues with starvation assuming a fair semaphore or monitor solution.
  3. If there are deadlock issues to resolve, how (in general terms) could you design a solution that prevents deadlock (be specific about how you would do it)? Justify your answer.
    (5) To prevent deadlock in such a system, we must eliminate one of the three necessary conditions for deadlock. We cannot eliminate the first of the necessary conditions (mutual exclusion) because the resources must be used in mutually exclusive fashion. We could eliminate hold and wait by forcing the processes that need two resources to always ask for and be granted two of them at the same time (this could lead to starvation unless care is taken to be sure that a process that wants two will eventually get them).
  4. Look at the following allocation table that shows the number of resource R1 assigned to five running threads at this point. Assume that P1, P2, P3, and P4 all need two units of R1 simultaneously at some point during their execution and that P5 only needs 1 unit at any point in its execution. Consider the following questions with respect to deadlock avoidance.

R1
P1 / 1
P2 / 1
P3 / 1
P4 / 0
P5 / 0

Suppose that a resource request comes in from P5 for one of R1. Is it safe to assign one of R1 to P5? Justify your answer.

(5) Yes, it is safe, because process P5 will be able to finish with just one unit of the resource and release it. That would let P1 get one more resource for the 2 it needs and complete, releasing those two. Then there are enough for both P2 and P3 to continue until finished.

Suppose instead that a request for one unit of R1 comes in from P4. Is it safe to assign one of R1 to P4? Justify your answer.

(5) No, it is not safe. If P4 is granted its request for 1 unit of R1, all four units of R1 will be held by each of four processes that still need one resource…and there are none left. That is, we now have a circular wait going on as each process is blocked, waiting for one of the other three processes to release a resource that it has.

Suppose instead that a request for one more unit of R1 comes in from P2. Is it safe to assign one more unit of R1 to P2? Justify your answer.

(5) It is safe. There is just one resource left, but if we grant it to P2, P2 can now complete and release its two, which will be sufficient for P1 and P3 to complete.