SKEDSOFT

ASSUMPTIONS ON RESOURCES AND THEIR USAGE: We continue to focus on the case where the system contains only one processor. In addition, the system also contains ρ types of serially reusable resources named R1, R2, . . . , Rρ. There are νi indistinguishable units of resource (of type) Ri, for 1 ≤ i ≤ ρ. Serially reusable resources are typically granted (i.e., allocated) to jobs on a nonpreemptive basis and used in a mutually exclusive manner. In other words, when a unit of a resource Ri is granted to a job, this unit is no longer available to other jobs until the job frees the unit. Again, examples of such resources are mutexes, reader/writer locks, connection sockets, printers, and remote servers. A binary semaphore is a resource (type) that has only 1 unit while a counting semaphore has many units. A system containing five printers has 5 units of the printer resource. There is only 1 unit of an exclusive write-lock.

A resource that has an infinite number of units has no effect on the timing behavior of any job since every job can have the resource at any time; there is no need to include the resource in our model. Therefore, we lose no generality by assuming that every resource Ri has a finite number of units.

Some resources can be used by more than one job at the same time. We model such a resource as a resource type that has many units, each used in a mutually exclusive manner. For example, a file that can be read by at most ν users at the same time is modeled as a resource that has ν exclusive units. By modeling shared resources in this manner, we do not need to treat them differently.

Enforcement of Mutual Exclusion and Critical Sections: For the most part of this chapter, we assume that a lock-based concurrency control mechanism is used to enforce mutually exclusive accesses of jobs to resources. (We make this assumption for the sake of clarity. As you will see later, commonly used resource access control protocols can be implemented without locks.) When a job wants to use ηi units of resource Ri, it executes a lock to request them. We denote this lock request by L(Ri, ηi ). The job continues its execution when it is granted the requested resource. When the job no longer needs the resource, it releases the resource by executing an unlock, denoted by U(Ri, ηi ). When a resource Ri has only 1 unit, we use the simpler notations L(Ri ) and U(Ri ) for lock and unlock, respectively. When there are only a few resources and each has only 1 unit, we simply call them by capital letters, such as X, Y, and Z, or by names, such as Black, Shaded, and so on.

Following the usual convention, we call a segment of a job that begins at a lock and ends at a matching unlock a critical section. Furthermore, resources are released in the lastin- first-out order. Hence overlapping critical sections are properly nested.

As an example, Figure 8–1 shows three jobs, J1, J2, and J3, and the time instants when locks and unlocks are executed if each job executes alone starting from time 0. Resources R1, R2, and R3 have only 1 unit each, while resources R4 and R5 have many units. Job J3 has three overlapping critical sections that are properly nested. A critical section that is not included in other critical sections is an outermost critical section; the critical section delimited by L(R1) and U(R1) in J3 is an example. Other examples are the critical sections delimited by L(R2) and U(R2) in J2, the second pair of L(R3) and U(R3) in J2 and L(R3) and U(R3) in J1.

When the execution times of the critical sections and the way they are nested are relevant in our discussion, we denote each critical section by a square bracket [R, η; e]. The entries in the bracket give the name R and the number of units η of the resource used by the job when in the critical section and the (maximum) execution time e of the critical section. In the case where R has only 1 unit, we omit the value of η and use the simpler notation [R; e] instead. In the example in Figure 8–1, the critical section in J3 that begins at L(R5, 4) is [R5, 4; 3] because in this critical section, the job uses 4 units of R5 and the execution time of this critical section is 3. Concatenations and nestings of the brackets allow us to describe different com-

binations of critical sections. Specifically, we denote nested critical sections by nested square brackets. For example, the nested critical section in J3 is [R1; 14 [R4, 3; 9 [R5, 4; 3]]]. This notation indicates that the critical section beginning from L(R1) includes the one beginning from L(R4, 3), which in turn includes the one beginning from L(R5, 4). Similarly, critical sections in J2 are [R2; 7 [R3; 2]][R3; 3], indicating that there are two nonlapping critical sections in this job.

Resource Conflicts and Blocking
Two jobs conflict with one another, or have a resource conflict, if some of the resources they require are of the same type. The jobs contend for a resource when one job requests a resource that the other job already has. We use these terms interchangeably as the distinction between them is often not important. The scheduler always denies a request if there are not enough free units of the resource to satisfy the request. Sometimes, as we will see later, a scheduler may deny a request even when the requested resource units are free in order to prevent some undesirable execution behavior.

When the scheduler does not grant ηi units of resource Ri to the job requesting them, the lock request L(Ri, ηi ) of the job fails (or is denied). When its lock request fails, the job is blocked and loses the processor. A blocked job is removed from the ready job queue. It stays blocked until the scheduler grants it ηi units of Ri for which the job is waiting. At that time, the job becomes unblocked, is moved backed to the ready job queue, and executes when it is scheduled.