DE4341877A1 - Coordination to access multiple processors to common resource - Google Patents

Abstract

A data processing system has a number of parallel processors (PRI-PRn) that are coupled via a network (VN) to a common resource in the form of a memory (SP). The processors have access to provide simultaneous reading of the memory contents, but have exclusive access for write operation using protocol. At the end of a reading operation the last processor to have access signals the conductor to enable write operators to proceed.

Description

If several processes want to access a common resource at the same time, a coordination or synchronization problem arises. This problem can e.g. B. be discussed with reference to FIG. 1, in which several processors PR1 to PRn can access a common memory SP in parallel via a connection network VN. The processors PR1 to PRn can, for. B. read common data from the memory SP or write to the memory SP. Accordingly, reader access and writer access can be distinguished in the game.

The reader / writer problem is a problem of coordination pa parallel or concurrent processes. It is known by it records that the processes involved have a common Res source, e.g. B. memory SP, want to use or change; before they also want common data, e.g. B. single variable, larger data structures or data areas, data records one Database or whole files, read or modify. In fol The coordination problem should be based on the example of Le water / writer accesses are described. The processes are to be coordinated so that any number of reader processes can read the data at the same time, but a writer process exclusive access to the data must be guaranteed. The To The principle of grip is therefore reading together, but exclusive Write.

For example, three reader processes L1, L2 and L3 of the Pro PR1, PR2, PR3 simultaneously the common data in the Use memory SP, a writer process S, z. B. from the process  sor PRn must not be simultaneous with other processes both Reader processes as well as writer processes towards the data to grab. A constellation in which about L2 and S at the same time Access rights to the shared data must therefore be excluded shut down.

This reader / writer problem can of course be in everyone Type of concurrent, parallel or distributed software So it is not limited to the example covered. It preferably plays in operating systems, file systems and Database systems a role, but also in concurrent, pa parallel or distributed application programs, it can occur men. An efficient and scalable solution to coordination problems increases the performance of the software in which the problem occurs. In the following explanation, however, we the coordination of writer access and readers reached for a memory discussed, but without a Restriction is said to be related to these types of problems.

Any process that accesses the shared data in memory wishes to go through a so-called entry protocol in which he announces the desired type of access. He is through that Entry log put on hold until it can be granted access. Then the entry leave the protocol. After access to the ge common data, each process must have a so-called exit protocol in which he announces the end of his access. We Due to the different access requirements, readers and Write different entry and exit protocols. A A method for solving the reader / writer problem is therefore practiced in the form of the entry and exit logs of the reader and formulated writing processes; the actual data access is embedded between the entry and exit protocol. These  Ratios are shown in Table 5 at the end poses.

For the maintenance of processes, one of the two following can be used Procedure used:

• - Active waiting (busy waiting).
  The waiting process remains active and reads and checks periodically control variables which, for. B. are also contained in the common memory SP, and via which access to the common data is regulated. He does this until he finds the control variables in a state that indicates that he now has access rights or may make a new attempt to acquire access rights. This method is known in the literature (Andrews 91).
• - Queuing.
  The waiting process is deactivated in the entry log and placed in a queue assigned to the data or the control variables protecting it. If in the exit log of another process the state is waiting that access can be granted to the processes, the leaving process takes them out of the queue and activates them. The processes thus have access rights or can make a new attempt to acquire access rights. This method is also known in the literature (Andrews 91).
  The following requirements can be placed on a process for reader and writer coordination:
• - correctness.
  Access rights must be correctly assigned to the processes and the procedure must e.g. B. be free of deadlocks and have other properties required by parallel or distributed algorithms (z. B. Andrews 91).
• - Efficiency and scalability (lack of serial bottlenecks).
  Entry and exit logs should be able to be executed as efficiently as possible. The property of the scalability of a process also plays an important role in parallel computers. For a method for reader / writer coordination, this means that with increasing number of processes the entry and exit protocols should be able to be carried out with constant efficiency, if possible.
• - fairness.
  The procedure should grant access rights to readers and writers as fairly as possible, ideally in the order in which the processes announce their access requests. It is to be prevented, for example, that a continuous stream of readers (who can join the currently active readers) blocked writers for a very long time (theoretically infinitely long: starvation of the writers). However, there may be applications in which a process type is treated with priority, ie in which variants with reader and writer priority must be used.

Solutions to the reader / writer problem can be found e.g. B. in two Classify classes:

1. Concurrent solutions

These are preferably used to coordinate concurrent professionals processes that run on a single processor and the sen z. B. share in the time slice method. Such procedures are known, e.g. B. from Andrews 91.

A disadvantage of this method is that it is used for Paral Oil calculator correct, but not very efficient, above all are not scalable. The reason is that the inputs and Exit logs or access to the control variables, which in turn regulate access to the shared data, represent so-called critical regions, d. H. at any time only may be executed by a single process. In order to  incorrect changes in the control variables are output closed.

This places these critical regions in parallel computer in which many processes run in parallel, serial Eng passports. This means that even if e.g. B. readers only log in to access the shared data, only one ger reader his entry and exit protocol or an access allowed to execute on one control variable and all other was have to.

2. Parallel solutions

Other solutions are available for parallel computers with shared memory gene become known that mitigate the explained disadvantage or no longer have. These solutions are based on special len indivisible access operations to the common memory with which the control variables are checked or modified become. A common operation is fetch & add (see e.g. B. Almasi u. Gottlieb 89). Doing so is indivisible Operation a variable (the content of a memory word) read and returned and then one in the operation specified value added. Fetch & add is one with reasonable effort in hardware to be performed operation.

With the help of these storage operations, preferably fetch & add, can now create more efficient entry and exit protocols for Le This / writer coordination can be developed by accesses on the control variables with those operations who made the. Increased efficiency of entry and exit protocols results the hardware (the connection network VN and / or the shared memory SP) the indivisibility of Changes in control variables guaranteed and a series follow these changes; this no longer has to be in soft goods are made.  

In addition to increased efficiency, another advantage is this Reader / writer solutions their scalability when available appropriate hardware support. The connection network must be able to combine and decombine simultaneous fetch & add access to the same memory address. In the storage system is present of Combine only one combined access opera in the network tion instead of z. B. of four serial accesses in the absence of this property. The processes get returned correct values from any serial row order of these z. B. correspond to four memory accesses. The be Processes involved are only increased by the duration of a memory handles delayed because the memory accesses to the same variable be parallelized.

Such a combining connection network is e.g. B., in Al masi & Gottlieb 89.

In Gottlieb et al 83 there are two reader / writer methods the base of fetch & add, with busy waiting as Waiting discipline and reader resp. Writer priority. A disadvantage this procedure is that you can only do it with active waiting work and are not fair.

The problem underlying the invention is a Procedures for coordinating access to multiple processes specify a resource that meets the above requirements fulfilled, i.e. fair, scalable, efficient, correct and both active waiting and queuing can use as a waiting discipline.

This object is achieved in accordance with the features of patent claim 1 solved.  

In the method according to the invention, the processes are removed divided into classes according to their type, e.g. B. form the Le processes one class and the writer processes another Great. The process is carried out so that the processes of a class can access the resource in parallel Processes of a different class only have exclusive access to be right.

Further developments of the invention result from the dependent claims chen.

The method according to the invention solves the reader / writer problem in a fair way and in such a way that using fetch & add Storage operations efficiently and in the presence of station wagons ning or combining in the connection network is scalable. Above all, instead of busy waiting, queuing can also serve as a waiting disc plin can be used.

Process maintenance is accomplished through scalable semaphores (i.e. by scalable operations P () and V () on semaphores) works. The procedure is structured so that semaphores are busy waiting or queuing can be used as a waiting discipline can without changing the structure of the process. In order to the waiting discipline can be chosen without effort seems most suitable for the respective application.

The inventive method is fair in the sense that Le Server and writer processes mutually access the ge alternate common data. As long as readers are allowed access the data until a clerk logs on. Then the active readers end their accesses and the last of them activated the writer (s), one of whom finally gets access rights. A clerk gives in Termination of his access to the access control  reported readers; if no readers are registered, he will give one to one Continue writing.

To understand the method according to the invention, briefly Semaphores or semaphore operations P () and V () were received. Se maphore are a common synchronization tool and z. B. treated in Andrews 91.

A semaphore is an instance of an abstract data type, preferably a non-negative integer s, only by manipulates two special, indivisible operations P () and V () may be. Operation P () is used to execute a process delay until an event occurs. Operation V () indicates the occurrence of such an event. Is his non-negative integer, P (s) delays the calling pro press until s becomes positive, then s is decremented; V (s) on the other hand, increments s. P () is often called "happen" or "occupy" (pass), V () referred to as "release" (free). Has a semaphore has a positive value, it becomes "open" called, otherwise closed.

The invention is further explained with the aid of tables attached at the end of the description and with reference to FIG. 2.

The process according to the invention is shown in Table 1 in Pseudocode notation, from Table 2 in pseudocode notation Operations P () and V () of a busy waiting semaphore with one Initialization procedure, from Table 3 a scalable Sema phore implementation with fetch & add and queuing as a waiting list tegie and from Table 4 an example of how the process coordinated according to Table 1 reader and writer processes. The key element of the method according to the invention is Use of a common control counter as a control variable. This control counter shows the state of conflict  the common data, d. H. the number of readers and cries who access the shared data or access waiting. Both sizes (number of active or waiting readers and Writers) can cnt darge in a single control counter are:

Readers increase or decrease the control counter cnt by a small count, e.g. B. 1, writer around a very large value, e.g. B. HUGE, which has to be larger than the number of readers logging on at the same time and should be selected as follows: If cnt is a memory word with the width n-bits, then HUGE: = 2 ^{n / 2 should be} set. The algorithm then works correctly up to a number of 2 ^{n / 2} -1 readers and writers active or waiting at the same time. In Table 1, n with n = 64 bits has been selected. The number of readers then active or waiting at a given time thus results in (cnt MOD HUGE), that of the writer (cnt DIV HUGE), where MOD denotes the modulo operation and DIV the integer division.

Any process that logs access to shared data or announces the end of his access, does so by one fetch & add access to the counter cnt; this is always the first operation in both entry and exit logs Process classes (see lines 10, 12, 18 and 23 of table 1). With Every pro reports this one fetch & add access to cnt cess to or from the access to the common data (by adding or subtracting one or HUGE) and receives at the same time the information about the current Kon back on the shared data. That state determines the further log activities that the process is made of leads.

No other activities are in a conflict-free state required. In such favorable situations, reduce yourself so that the entry and exit logs to a fetch &  add access to the common control counter cnt (plus weni local operations in the clerk protocols). In the In these cases, the process is optimally efficient.

When a newly arrived reader finds out that writer had logged in before him (i.e. if the return value of the fetch & add operation is greater than or equal to HUGE (line 10), he waits at the semaphore r intended for readers by P (r) executes (line 11). The behavior of a newly arrived Schreibers is similar. In the event of a conflict, he moves to the Semaphore w through P (w) to the waiting state (line 22).

When a writer process has finished accessing data in his exit log states that readers are waiting (i.e. if the return value of the fetch & add operation and there with its local variables oldcnt and nwr are greater than zero (Lines 23-25)), he shows the nwr waiting readers Share the shared data by writing nwr times V (r) executes (preferably in parallel) and thus the readers from their Waiting state wakes up (lines 28 and 29). Asks the clerk but firmly that no readers, but one or more writers wait (i.e. if nwr is zero and oldcnt is greater than HUGE (Lines 30, 31)), he activates the next waiting clerk using V (w) (line 32).

When reader processes release the common data and an or if several writers are on hold, the reader takes care with the exception of the last not the clerk; it is task of the last reader, the writer (s) by V (w) thereof in Notify that readers have ended their access (Lines 14, 15).

The rest of the somewhat more complex part deals with this situation of the procedure. The number of active readers must be in one Counters are kept so that readers can determine  which of them is the last one to have access to the ge shared data. As long as only readers use the data, this counter is not used, i.e. nar = 0.

The first arriving clerk must not count on the number of put active reader (line 21), which he from the return evaluates (oldcnt) his fetch & add access to the control counter cnt calculated (line 18). He recognizes from this return also worth being the first writer after a series of Le is (lines 19, 20). Only after the counter has stopped our clerk and has thus become positive the readers who enable data access do not use the counter use and decrement so that the last of them turns out to be can identify such. Until the counter is set, they must remain on hold (line 13). It is Note that no other readers are active in this situation will and can thus not change the counter; Readers who Arriving during these operations will be pending with P (r) lung offset (line 11).

There is a second situation where the counter is not must be set, namely when a writer closes the hands over control to waiting readers and already behind one or more clerks are waiting again. The counter nar must be set here to the number of readers to be activated (Line 27), so that the last of them as such recognizes and can activate the next recorder.

The course of the process is illustrated using an example according to Ta belle 4 explained. Table 4 shows how this is invented process according to Table 1 reader and writer pro processes coordinated, with different transitions between readers and writers and thus the different parts of the process be illustrated.  

The following should be said about the notation used in Table 4: The actions (execution of entry protocols E and exit protocols A and accesses Z to the common data) by readers L _i and writers S _j as well as the values of the variables and Waiting states which apply after the actions have been carried out in full. The time runs from top to bottom. Actions that run in series are separated by horizontal lines. In principle, a group of actions between two horizontal lines can overlap; the sequence of such actions shown corresponds to the assumed sequence of fetch & add accesses to the control counter cnt that the processes execute.

Both in Table 1 and Table 4 are the individual ones Processes commented so that they are understandable in themselves are. A further explanation is therefore not necessary.

As a waiting discipline for the method according to the invention by inserting appropriate semaphores or semaphore operas Both busy waiting and queuing can be selected. A scalable semaphore implementation with fetch & add and busy waiting as a waiting strategy is shown in Table 2. she is z. B. from Almasi & Gottlieb 89 known. Table 2 shows in Pseudocode notation the P () and V () operations of a busy wai ting semaphore together with an initialization procedure. Fetch & add is used in it to make the semaphores indivisible increment or decrement. Also in table 2 are commented on the individual processes, so that the procedure of Table 2 is understandable.

The method according to the invention can, however, also be carried out with the waiting disc ziplin queuing can be used, an example in pseudocode notation shows table 3.  

Table 3 is explained together with FIG. 2.

The queue (represented by Almasi & Gottlieb 89) is represented by a global circular field of process IDs pids (0: n-1) of size n, in which process IDs of the PID type can be stored in the waiting position (line 2). The global variables tail and head point to waiting positions (slots) into or from which the next process identifiers can be inserted or removed (lines 3 and 4). These variables are incremented with fetch & add memory accesses, so that each process receives a unique waiting position number, into which it can insert its process identifier P (e.g. P _i , P _j , P _k ) and from which it takes one can (e.g. P _l , P _m ). Initially the queue is empty and tail = head = 0.

The variables ublen and lblen (lines 5 and 6) have the following meanings known from Almasi and Gottlieb 89. The variable ublen denotes the number of waiting positions that are currently being filled or are currently being filled or emptied. In a sense, ublen is an "upper bound" of the currently valid queue length. The variable lblen denotes the number of waiting positions that are currently filled and not exactly filled or emptied; in a sense, lblen is a "lower bound" of the currently valid queue length. The difference between the two variables (ublen - lblen) denotes the number of process identifications that are inserted or removed at a time (see FIG. 2).

The two variables ublen and lblen are necessary because in ei A parallel queue of many enqueue and dequeue operas ions can run simultaneously (in parallel). Enqueue and de queue means inserting (enqueue) and removing (dequeue).  

They are in Almasi & Gottlieb 89, pp. 446-449) for administration described scalable parallel queues.

Both variables are incremented again using fetch & add or decremented (e.g. lines 25, 26, 46 and lines 39, 40, 33). Their values are used to determine whether the queue is full or empty. The queue is considered full if ublen is greater than or equal to n and as empty if lblen is less than or equal to zero.

Finally, there is a pair for each waiting position or slot needed by busy waiting semaphores to ensure that Enqueue and dequeue operations on each slot are correct alternate right. These are in Table 3 by the fields enqs (0: n-1) (enqueue - semaphore) and deqs (0: n-1) (Dequeue - Semaphore) represents (lines 7 and 8).

It can happen that an enqueue and a dequeue Operation want to fill and empty the same slot at the same time. These semaphores are initialized in this way and in the qP () and qV () operations are used so that each slot is always alternating is filled and emptied (lines 29, 32, 43, 45). Comparable Synchronization measures are from Almasi & Gott lieb 89 known.

The use of the queue server is essential in Table 3 administration in the semaphore operations qP () and qV (). A sema phore has this type of queuing as a waiting discipline via a semaphore counter qcnt, a parallel queue pids (0: n-1) and the described additional variables (Lines 9-11). The semaphore counter qcnt can be used here also become negative. If this is the case, his Abso The amount of the process IDs that are waiting in the lute amount snake were or will be inserted.  

If the semaphore counter qcnt is used in qP () (lines 20-33) as The process identifier is found to be non-positive (line 23) pid passed as a parameter to the queue classified. After the insert operation is successful, the process with identifier pid suspended (deactivated). Will in the course of Inserting pid based on ublen the queue as full recognized (line 25), the inserting process waits in a war loop until at least one slot is free again (line 27). So this queue (i.e. busy waiting) is a return Fall position in case the process queue is full is. The qP () operation is privileged in Table 3 Operation (system call) denotes, because in it a process one other process (namely pid) suspended. A process cannot even execute the qP () operation since it doesn't finish this could lead, but at deschedule (pid) de itself would activate. For the correct behavior of the semaphores but the qP () operation is complete; a qP () must be there from the calling process to another executing one Process to be transferred.

In qV () (lines 34-47) the semaphore counter qcnt is called ne found negative (line 37), the first process from the Queue removed and activated. In the course of the removal the queue can be considered "empty" (based on lblen) (line 39). If this happens, it is certain provides that at least one qP () operation in parallel Underway but not yet completed. The process, the qV () executes, enters a queue until at least one slot is filled (line 41). If the queue is actually empty, qcnt is found to be not negative, the attempt by Ent a process is not undertaken.

In Table 3, too, the individual lines are still do documented to explain their meaning.  

literature

[Almasi & Gottlieb 89]
GSAlmasi, A. Gottlieb, Highly Parallel Computing, Benja min / Cummings, 1989.
[Andrews 91]
GRAndrews, Concurrent Programming, Principles and Practice, Benjamin / Cummings, 1991.
[Gottlieb et al 83)
A. Gottlieb, BD bubachevsky, b. Rudolph, "Basic Techniques for the Efficient Coordination of Very barge Numbers of Cooperating Sequential Processors", ACM Trans. On Programming bangua ges and Systems, Vol. 5, No. April 2, 1983, pp. 164-189.

Table 1

Table 2

Table 3

Table 4

Table 5

Claims (14)

1. procedure for coordinating accesses of several processes to a common resource,

• - in which the processes are divided into classes according to their type,
• - where processes of a first class are allowed to access the resource until there is access by a process from another class,
• in which a process of a second class is activated after the access of the last process of the first class,
• - In which after the access of the process of the second class, if there are access requests from processes of other classes, these processes are activated, otherwise a process of the second class, if there is one.

2. The method according to claim 1, in which to synchronize the access of the processes semaphore be used. 3. The method according to claim 2, using processes from two classes. 4. The method according to claim 3, where the content of a control counter (cnt) as control va riable is used for coordination, whose counter status indicates how many processes access the resource or waiting for access. 5. The method according to claim 4, to distinguish the processes of different classes the count by which the control counter per accessing or Access requesting process is counted up or down, is so different for each class that the counter reading for  the case that all processes of a class approach the resource grab, is smaller than the meter reading, if at least At least one process of the other class accesses the resource. 6. The method according to claim 5, in which a process accesses the resource with an he fetch & add access to the control counter with which the Control counter changed in one direction by the count value and with a second fetch & add access to the control counter ends with which the counter in the other direction by the Count value is changed so that the meter reading is always a measure for the number of access requesting and waiting processes is. 7. The method according to any one of claims 2 to 6, in the case of an access request by a process of a class and simultaneous access by one process of the other Class the process of a class on one of these one class assigned semaphores and not accesses the resource. 8. The method according to any one of claims 2 to 7, in the case of an access request by a process of a class and simultaneous access by a process of the other class the process of the other class terminates its access and the releases the semaphores assigned to a class, so that the Process that a class can access the resource. 9. The method according to any one of the preceding claims, in which a second counter is used, in which the number of zu handles requesting processes of a class who saved those that are earlier than an access request from the others Class and in which one corresponds to the number of the second counter Adequate number of processes of the same class  accessed the resource before getting a process of another class allowed to access. 10. The method according to any one of the preceding claims, where the processes in the waiting state are regular inquire whether access to the resource is granted (busy-wai ting). 11. The method according to any one of claims 1 to 9, in which the waiting processes are in a war be queued and according to their position in access to the queue. 12. The method according to claim 11, where a queue with a specified number of Waiting positions are used in cyclical order be occupied and released, with the new one in the waiting state processes going over at the end of each other Processes assigned to waiting positions and deactivated in which depending on the termination of access to a process because the process at the beginning of the queue is removed and active fourth, in the event that the number of in the Processes waiting state is greater than the number of the unoccupied waiting positions that are not in the waiting room queuing processes in the busy waiting state be transferred and wait until a waiting position is released. 13. The method of claim 12, wherein several processes queued and deactivated at the same time can be removed from the queue and activated can be.   14. The method according to any one of the preceding claims, in which First class processes Read access, where processes of second class write access to a shared memory as a resource.