Monitör yapısına dayalı paralel programlama ortamının tasarımı ve gerçeklenmesi

Abstract

Paralel programlama, özellikle birçok olayın dikkatle takip edilmesi gereken durumlarda kullanılan bir yöntemdir. Paralel programlarda, herbir işi yapmakla görevli birimlere görev adı verilir. Birçok durumda, bir görev başka bir görevle aynı veri bölgesini paylaşmak zorunda kalır. Bu ortak kullanım sırasında ortaya çıkabilecek tehlikeleri önlemek için semafor değişkenleri kullanılabilir. Semafor değişkenleri ortak veri kullanımını güvenli hale getirmekle birlikte, kullanıcı için programlama hatalarına elverişlidir. Bu yüzden, bu çalışmada da gerçekleştirilen monitör yapısını kullanmak daha uygundur.

Concurrent programming means writing programs that have several parts in execution at a given time. Concurrent programming has been used for many years in writing parts of operating systems. Concurrent programming makes it possible to use a computer where many things need attention at the same time which may be people at terminals or temperatures in an industrial plant. It is without doubt the most difficult form of programming. In a concurrent program, each task to be controlled can be represented by a process. A process consists of a private data structure and a sequential program that can operate on the data. One process can not operate on the private data of another process. Fig.l shows a process component. PRIVATE DATA SEQUENTIAL PROGRAM Fig.l Process component Although it is vital to make sure that some variables are private to processes, they must also be able to share data structures (such as buffer). Otherwise, concurrent processes can not exchange data and cooperate on common tasks. But shared data are the -vi- major pitfall of concurrent programming we must proceed with extreme care and define exactly what processes can do with such data structures. In fig. 2 we can see the state diagram showing the three states of a process may be in : 1. Running (actually using the CPU at that instant) 2. Blocked (unable to run until same external event happens) 3. Ready (runnable; temporarily stopped to let another process run) Fig. 2 State diagram of a process Four transitions are possible among these three states. Transition 1 occurs when a process discovers that it can not continue. Transition 2 and 3 are caused by the process scheduler, a part of the operating system. Transition 2 occurs when the scheduler decides that the running process has run long enough and it is time to let another process have some CPU time. Transition 3 occurs when all the other processes have had their share and it is time for the first process to run again. Transition 4 occurs when the external event for which a process was waiting happens. Ready and blocked states in the system are composed of double linked lists. Such a list consists of records each of which is called process descriptor as shown in fig 3. Each process is programmed using a procedure in Turbo Pascal. At the beginning of concurrent running, process scheduler allocates stacks to each process. Processes have private variables in their stacks. Process descriptor consists of current stack segment, stack pointer, priority and amount of CPU time slice used. Left and right variables are used in order to create double linked lists. Time_out variable is used to delay the processes. -vii- tasknode = record tss,tsp :word; t ime_out : 1 ongint ; left, right rtasknodep; priority :word; quant_used : 1 ongint ; end; Fig. 3 Process Descriptor 8253 which is a chip on the system board, automatically issues a type 8 interrupt 18 times per second. This interrupt signal transfers control from a process to another. After interrupt signal occurs, the running process will be transferred to ready state and one of the processes which are in ready state will be transferred to running state. While transition is done, current stack segment and stack pointer are stored in process descriptor of the process. The process scheduler loads the new running process's stack segment and stack pointer values into SS and SP registers in the system. At any instant, all the processes in the system can be in : 1- Running state 2- Ready queue 3- Queue of any semaphore 4- Queue of condition variable of any monitor. 5- Delay queue If there are more than one processes in ready queue, after timer interrupt comes, process scheduler begins to run a process which has used the least time slice of CPU. If there are more than one process which have used CPU time equally, the process descriptor decides to run a process which has the highest priority. Processes frequently need to communicate with other processes. Processes that are working together often share some common storage that each one can read and write. The shared storage may be in main memory or it may be a shared file. If two or more processes want to use the shared data at the same time, some problems will probably arise. Some processes may change a variable while others are using -viii- it. So, the processes may read wrong values. Where two or more processes are reading or writing some shared data and final result depends on who runs precisely when, are called race conditions. The key to avoid race conditions is to prohibit more than one processes from reading and writing the shared data at the same time. What we need is mutual exclusion. Some way of making sure that if one processes is using a shared variable or file, the other processes will be excluded from doing the same thing. Part of the time, a process is busy doing internal computations and other things that do not lead to race conditions. However, sometimes a process may be accessing shared memory files or doing other critical things that can lead to races. That part of the program where the shared memory is accessed is called the critical section. We need the following requirements for mutual exclusion : 1. No two processes may be simultaneously inside their critical sections. 2. No assumptions are made about relative process speeds or number of CPU's 3. No processes stopped outside its critical section should block other processes. 4. No processes should wait arbitrarily long to enter it's critical section. We can use semaphores for achieving mutual exclusion. The only valid operations on semaphores are WAIT and SIGNAL. The two semaphore operations allow a process to block itself to wait for a certain event, and then to be awakened by another processes when the event occurs. WAIT and SIGNAL have the following meanings : WAIT(s) : Wait until s > 0 and subtract 1 from s. SIGNAL(s) : Add 1 to s. Both WAIT and SIGNAL must be done indivisibly. The WAIT operation potentially blocks the executing process and SIGNAL potentially wakes up a blocked process. The process executing the SIGNAL operation is not blocked and continues execution. In this study, in order to attain indivisibility, interrupts are disabled before semaphore operations are called and enabled again after the semaphore operations are completed. While semaphores are created, an initial value is given to each semaphore. Semaphores are created by create_sem(init_val) system procedure. A data type shown in fig. 4 are allocated to every semaphore created. Qu_ptr variable is a pointer to tasknode type. When using semaphores, we must be careful to avoid deadlocks. Wrong use of semaphores can cause blocking of both processes. -ix- semelement = record sem_value qu_ptr end; ; shortint; ; tasknodep; Fig. 4. Data type of semaphores To make it easier to write correct programs, Hoare (1974) and Brinch Hansen (1975) proposed a higher level synchronization primitive called a monitor. A monitor is a collection of procedures, variables, and data structures that are all grouped in a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but they can not directly access the monitor's internal data structures from procedures declared outside monitor. Fig. 5 illustrates a monitor. monitor example integer i; condition c; procedure entryl(x); end; procedure entry2(x); end; begin end; endmonitor; Fig. 5. A monitor Monitors have an important property that makes them useful for achieving mutual exclusion: Only one pocess can be active in a monitor at any instant. Monitors are a programming language construct, so the compiler knows they are special and can handle -x- calls to monitor procedures differently from other procedure calls. When a process calls a monitor procedure, the first few instructions of the procedure will check to see if any other process is currently active within the monitor. If so, the calling process will be suspended until the other process has left the monitor. If no other process is using the monitor, the calling process may enter. In this study, a binary semaphore is used to achive mutual exclusion. The person writing the monitor doesn't have to be aware of how the compiler arranges for mutual exclusion. No two processes will ever execute their critical section at the same time. Although monitors provide an easy way to achive mutual exclusion, that is not enough. We also need a way for processes to block when they can not proceed. The solution is in the introduction of condition variables, along with two operations on them : WAIT and SIGNAL. When a monitor procedure discovers that it can not continue, it does a wait on some condition variable. This action causes the calling process to block. It also allows another process that had been previously prohibited from entering the monitor to enter now. When another process enters the monitor and finds the condition to be true, it executes a signal statement that removes a waiting process (if there is one) from the condition's queue and wakes it up. In this case, to avoid having two active processes in the monitor at the same time, we need a rule telling what happens after a signal. Hoare proposed to let the newly awakened process run, suspending the other one. Binch Hansen proposed finessing the problem by requiring that a process doing signal must exit the monitor immediately. In other words, a signal statement may appear only as the final statement in a monitor procedure. In this study, Hoare' s proposal is adopted. Monitor procedures, variables and data structures are found in a special unit in Turbo Pascal. Variables and data structures of monitor are written in implementation part of the unit. So, a program calling this unit can not reach the private data of the monitor. Monitor entries are written in interface part of the unit. For this reason, monitor entries can be called from a program using the monitor unit. Monitor entries are written by special monitor statements. A program converts them to concurrent pascal statements. Furthermore, this program does a WAIT operation at the beginning of each monitor entry and does a SIGNAL operation at the end of monitor entries in order to achieve mutual exclusion. Wait and signal operations on monitors must also be done indivisibly.