1.11.2004

Area to be studied: Andrews: luku 1 The Concurrent Computing Landscape.

The goal of these exercises is 1) to get an overall glance to the problem area of this course -- processes and their communication, 2) to learn to perceive the need for communication in the functionality of concurrent processes and 3) practice the notation for writing algorithms that is used in this course. in the

1 - BASIC TERMS

Explain the essentials of the following keywords (what is? differencies, needs? etc.)

• process - thread
• concurrent - parallel
• asynchronous - synchronous
• mutual exclusion - synchronization

2 - TWO PROCESSES (or THREADS) AS SEEN BY THE OS

a) Sketch a figure of the key structures that operating system maintains to manage two processes (or threads) that have shared memory areas (code, data) and own private areas (data, stack). Hint: PCB/TCB, See also Stallings' book.

b) What kind of requirements should be taken account when using a) shared code and b) shared data? Is it possible for the OS or hardware to guarantee any of those requirements? Are there something that the programmer is responsible for?

c) How concurrent / parallel the execution of these two processes (threads) can be? Assume that the programmer has ment that the communication is alternating (e.g. request - reply). What kind of situations must the programmer consider? What could go wrong (and how), if not done carefully?

3- ROUTER, PROCESSES AND A BUFFER

Router is a machine in the data communication network that receives packets from different routes, inspects their headers and forwards the packets to the right direction. One process is dedicated to receive packets and to put them into the memory buffer. Another process reads the packets from the buffer, inspects the header, and sends the packet to the intended outgoing route. Sketch a figure!

The basic algorithms for these processes are very easy, but since there is the other one, some additional things must be taken account. What problems emerge from the usage of a common buffer? Specify "exactly" the requirements for the behavior of the processes (i.e. who may do what and when, who is not allowed to do what and when etc.)

4 - A PRODUCER AND A CONSUMER AND A LIMITED BUFFER BETWEEN THEM

Between a producer and a consumer there is a buffer of size N. The buffer is used as a FIFO queue.

1. How is the buffer usage taken care of? What variables are needed for the buffer? Give the declarations for these variables.
2. How does the producer behave when he putting data into the buffer? When is it necessary for producer to wait and what is the reason for waiting?
3. How does the consumer behave when he taking data from the buffer? When is it necessary for consumer to wait and what is the reason for waiting?

5- STUDENTS IN THE LUNCH ROOM

Students come to the lunch room and queue for their turn to tell the person distibuting food what dish they want to eat. After getting their portions the students select their drinks and pick up the needed cutlery. To be able to eat a student needs both a knife and a fork. After a student has eaten he takes the dirty dishes to the stand for dirty dishes and leaves the lunch room.

1. Write, using the notation given in the course book (pp.26-31), the code (an algorithm) describing the behaviour of a student in the lunch room as a Student process.
2. In which situations the Student process has to synchronize its behaviour with other processes (= other Student processes or the FoodDistributor process)?
3. Very often there are not enough forks and knifes for the hungry students. How should the students behave to overcome this problem? Is it possible that somehow the situation becomes such that even when there are some knifes and some forks no student can start eating (cannot get both a knife and a fork)?

   SOME INSTRUCTIONS
   

   The exercises are worth 9 points.
   The exercices you have solved give you maximum 9 points. There will be 6 exercises each with 5 problems altogether 30 problems to be solved.

   Please, be well prepared to the sessions, and solve the problems beforehand. Students explain their own solutions in the small group sessions, and get feedback from other students and from the instructor. If needed, use news group hy.opiskelu.tktl.rio to ask hints to these exercises.

             Problems done              points given
   	            3                        1
   		    6                        2
   		    9                        3
   		   12                        4
   		   15                        5
   		   18                        6
   		   21                        7
   		   24                        8
   		   27                        9
   	  
    

   Two heads are better than one head.