Real-time multiprocessor locks with nesting: optimizing the common case

In prior work on multiprocessor real-time locking protocols, only protocols within the RNLP family support unrestricted lock nesting while guaranteeing asymptotically optimal priority-inversion blocking bounds. However, these protocols support nesting at the expense of increasing the cost of processing non-nested lock requests, which tend to be the common case in practice. To remedy this situation, a new fast-path mechanism is presented herein that extends prior RNLP variants by ensuring that non-nested requests are processed efficiently. This mechanism yields overhead and blocking costs for such requests that are nearly identical to those seen in the most efficient single-resource locking protocols. In experiments, the proposed fast-path mechanism enabled observed blocking times for non-nested requests that were up to 18 times lower than under an existing RNLP variant and improved schedulability over that variant and a simple group lock.

1. The terminology “fast-in-the-common-case RW-RNLP,” which is obviously too verbose, would be more technically precise.

2. A job can also be pi-blocked at release by lower-priority jobs executing non-preemptively. By our analysis assumptions, this release blocking is asymptotically upper bounded by the maximum spin blocking for any such jobs, so we focus on spin blocking.

3. Line 5 can be modified to handle overflow in and . In a spin-based implementation, at most m requests can be active at once, so and can be at most m apart. Therefore, the condition in Line 5 can be modified to to mitigate overflow.

4. The lock and unlock routines for the \(\text {R}^3\text {LP}\) or RW-RNLP* routines have been denoted in a slightly abbreviated way. For example, W_Lock\(^{{nn}}\) denotes the lock routine invoked by non-nested write requests under the chosen protocol.

5. More precisely, the bounds presented are \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) and \((m-1)(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}})\) for read and write requests, respectively.

6. Entitlement is a property of a request, and Definition 1 and Definition 2 give conditions upon which a request becomes entitled in terms of the entitlement of other requests. Therefore, while Definitions 1 and  2 reference each other parenthetically to aid the reader, they are not in fact circularly defined.

7. This extra phase erroneously combined Lines 3–6 into a single loop in the conference paper (Nemitz et al. 2017), given there as Listing 3, but the source code was correct. It has been corrected here.

8. See online appendix: http://www.cs.unc.edu/~anderson/papers.html.

Authors and Affiliations

1. Department of Computer Science, UNC-Chapel Hill, 201 S. Columbia St., Chapel Hill, NC, 27599, USA

   Catherine E. Nemitz, Tanya Amert & James H. Anderson

Corresponding author

Correspondence to Catherine E. Nemitz.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Work supported by NSF Grants CNS 1409175, CPS 1446631, CNS 1563845, and CNS 1717589, AFOSR Grant FA9550-14-1-0161, ARO Grant W911NF-14-1-0499, ARO Grant W911NF-17-1-0294, and funding from General Motors. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant No. DGS 1650116. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Additional details

This appendix provides additional details on several claims made in the body of the paper.

1.1 Tight blocking bounds for the RW-RNLP*

To show that each blocking bound proven for the RW-RNLP* is tight, we show that each worst-case bound can actually occur by means of examples. An example corresponding to each lemma and theorem about the RW-RNLP* is presented below in the order in which the lemmas and theorems appear in Sect. 4.4. In each example, requests are numbered in the order in which they were issued.

Lemma 5 bounds the acquisition delay that a write request can experience after becoming entitled to \(L ^r_{{\textit{max}}}\).

A simple example that shows worst-case acquisition delay for a read request and the acquisition delay a write may experience after becoming entitled

Full size image

Example 6

As shown in Fig. 16, write request \({\mathcal {R}}^w_2\), issued just after \({\mathcal {R}}^r_1\), is immediately entitled and can experience \(L ^r_{{\textit{max}}}\) acquisition delay. This is exactly the upper bound presented in Lemma 5.

Theorem 3 bounds the acquisition delay a read request can experience to \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\).

Example 7

In Fig. 16, read request \({\mathcal {R}}^r_3\) experiences an acquisition delay of up to \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) time units. It was issued after the issuance of requests \({\mathcal {R}}^r_1\) and \({\mathcal {R}}^w_2\), all for the same resource. \({\mathcal {R}}^r_3\) cannot be satisfied initially, as \({\mathcal {R}}^w_2\) is entitled. Therefore it waits for up to \(L ^r_{{\textit{max}}}\) time units for \({\mathcal {R}}^r_1\) to complete. Once \({\mathcal {R}}^w_2\) is satisfied, \({\mathcal {R}}^r_3\) waits for up to \(L ^w_{{\textit{max}}}\) time units for \({\mathcal {R}}^w_2\) to complete before acquiring the resource.

According to Lemma 6, a write request \({\mathcal {R}}^w_i\) may experience up to \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) blocking after becoming the earliest-timestamped active write request for each resource in \(D_i\).

An issuance order which may cause the maximum blocking after a write request \({\mathcal {R}}^w_3\) becomes the earliest-timestamped active write request for each of its resources, here just \({\ell } _2\)

Full size image

Example 8

Similarly to the previous examples, in Fig. 17, write request \({\mathcal {R}}^w_3\) can experience the worst-case delay stated in Lemma 6. Because requests were issued in increasing index order, \({\mathcal {R}}^w_3\) can potentially block for the entire critical sections of \({\mathcal {R}}^w_1\) and \({\mathcal {R}}^r_2\), which can be as high as \(L ^w_{{\textit{max}}}\) and \(L ^r_{{\textit{max}}}\), respectively.

The earliest-timestamped non-nested write request with no nested requests present can experience blocking of \(L ^r_{{\textit{max}}}\). This upper-bound proven in Lemma 7 is shown to be tight in Example 6 with \({\mathcal {R}}^w_2\) as depicted in Fig. 16.

Lemma 8 bounds the time a nested write request must wait before becoming the earliest-timestamped write request for all of its resources to \(2L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\). The following example shows this bound is tight.

A series of read and write requests that illustrate the worst-case acquisition delay for nested and non-nested write requests

Full size image

Example 9

As shown in Fig. 18a, \({\mathcal {R}}^{w,n}_4\) is not the earliest-timestamped active write request for each of \(D_4=\{{\ell } _2,{\ell } _3\}\) when it is issued. In fact, it must wait until \({\mathcal {R}}^w_3\) has completed. Given that each of these requests could have been issued immediately after each other and that \({\mathcal {R}}^w_4\) will need to wait until \({\mathcal {R}}^w_1\), \({\mathcal {R}}^r_2\), and \({\mathcal {R}}^w_3\) complete, \({\mathcal {R}}^w_4\) may wait up to \(2L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) time units to become the earliest-timestamped active write request.

Lemma 9 has two cases for how soon a non-nested write request \({\mathcal {R}}^{w,nn}_i\) will become the earliest-timestamped request for each of its resources. Case (i) does not need an example: the worst-case delay for \({\mathcal {R}}^{w,nn}_i\) becoming the earliest-timestamped active write request in the RW-RNLP* for \(D_i\) is zero when no nested requests are active. Case (ii) bounds this time to \(4L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\) in the presence of nested requests.

Example 10

Consider \({\mathcal {R}}^w_5\) in Fig. 18. This non-nested write request may wait for up to \(4L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\) time units to become the earliest-timestamped request for \(D_5 = \{{\ell } _3\}\). To become the earliest-timestamped request for \(D_5\), \({\mathcal {R}}^w_5\) must wait for \({\mathcal {R}}^w_4\) to complete, which in turn must wait for \({\mathcal {R}}^w_3\) to complete. As shown in Fig. 18a, \({\mathcal {R}}^w_3\) may wait for up to \(L ^w_{{\textit{max}}}\) time units to become entitled (the time for \({\mathcal {R}}^w_1\) to complete, after which \({\mathcal {R}}^r_2\) is no longer entitled). After \({\mathcal {R}}^w_3\) becomes entitled, \({\mathcal {R}}^r_6\) is issued, as shown in (b). After up to \(L ^r_{{\textit{max}}}\) time units after \({\mathcal {R}}^w_3\) becomes entitled, \({\mathcal {R}}^r_2\) completes and \({\mathcal {R}}^w_3\) is satisfied. \({\mathcal {R}}^w_3\) may execute for just under \(L ^w_{{\textit{max}}}\) time units before \({\mathcal {R}}^w_7\) and \({\mathcal {R}}^r_8\) are issued, as shown in (c). Once \({\mathcal {R}}^w_3\) completes, \({\mathcal {R}}^w_4\) may still wait for up to \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) time units before becoming satisfied (for \({\mathcal {R}}^w_7\) and \({\mathcal {R}}^r_8\) to complete). After \({\mathcal {R}}^w_4\) is satisfied, it may execute for \(L ^w_{{\textit{max}}}\) time units, after which \({\mathcal {R}}^w_5\) is finally the earliest-timestamped request for \(D_5\) after waiting for up to \(4L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\) time units.

Theorem 4 presents four bounds for write requests. Non-nested write requests may experience up to \(L ^r_{{\textit{max}}}\) time units of acquisition delay if no nested requests are active (illustrated in Fig. 16 and described in Example 6). If nested read requests may be present but no nested write requests are active, non-nested write requests may experience up to \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) time units of acquisition delay, as illustrated in Fig. 17 and described in Example 8. The third bound presented in Theorem 4 is that non-nested write requests in the presence of nested requests may experience up \(5L ^w_{{\textit{max}}}+ 3L ^r_{{\textit{max}}}\) time units of acquisition delay (illustrated below). Finally, nested write requests may experience acquisition delay of up to \(3L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\) (also illustrated below).

Example 11

As illustrated by Fig. 18 and Example 10, \({\mathcal {R}}^w_5\) may wait for \(4L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\) time units to become the earliest-timestamped request for its resources. Suppose just before \({\mathcal {R}}^w_4\) completes, \({\mathcal {R}}^w_9\) and \({\mathcal {R}}^r_{10}\) are issued, as illustrated in Fig. 18d. (This is similar to the situation in Example 10 when \({\mathcal {R}}^w_7\) and \({\mathcal {R}}^r_8\) were issued just before the completion of \({\mathcal {R}}^w_3\).) \({\mathcal {R}}^w_5\) may indeed need to wait an additional \(L ^w_{{\textit{max}}}+ L ^r_{{\textit{max}}}\) time units before being satisfied, making its total acquisition delay \(5L ^w_{{\textit{max}}}+ 3L ^r_{{\textit{max}}}\) time units.

Figure 18 also illustrates that a nested write request, namely \({\mathcal {R}}^w_4\), may experience acquisition delay of \(3L ^w_{{\textit{max}}}+ 2L ^r_{{\textit{max}}}\). Indeed, \({\mathcal {R}}^w_4\) waits for the completion of three write requests (\({\mathcal {R}}^w_1\), \({\mathcal {R}}^w_3\), and \({\mathcal {R}}^w_7\)), which may only barely overlap, and two read phases (those of \({\mathcal {R}}^r_2\) and \({\mathcal {R}}^r_8\)) that do not overlap with any of the write requests.

1.2 Corner case for nested read requests

Illustrates the edge case in which a write request (\({\mathcal {R}}^w_4\)) would need to wait unnecessarily behind a nested read request (\({\mathcal {R}}^r_3\)) if the extra code step had not been added in Listing 5

Full size image

If the extra phase in Lines 3-6 of Listing 5 is not included for the \(\textsc {R*\_Lock}^\textit{n}\) routine, a potential edge case exists, as demonstrated in Fig. 19. In this edge case, write requests suffer unnecessary transitive blocking caused by read requests incorrectly marking themselves entitled.

In this scenario, read request \({\mathcal {R}}^{r,nn}_1\) is satisfied and write request \({\mathcal {R}}^{w,nn}_2\) is entitled when read request \({\mathcal {R}}^{r,n}_3\) is issued. At this point, \({\mathcal {R}}^{r,nn}_1\) has completed the \(\textsc {R*\_Lock}^\textit{nn}\) routine and \({\mathcal {R}}^{w,nn}_2\) is waiting at Line 13 for its requested resource to become available.

Without Lines 3-6, \({\mathcal {R}}^{r,n}_3\) immediately modifies \({\ell } _1\)’s rin variable, effectively marking itself entitled, and waits at Line 12 for \({\mathcal {R}}^{w,nn}_2\) to complete. When \({\mathcal {R}}^{w,nn}_4\) is released, it must wait at Line 13 (Listing 4) for \({\mathcal {R}}^{r,n}_3\) to complete, even though it should have been immediately satisfied following the rules of the fast RW-RNLP.

Using the implementation given in Listing 5, however, \({\mathcal {R}}^{r,n}_3\) must wait at Line 6 due to \({\mathcal {R}}^{w,nn}_2\) having marked itself present in the bottom byte of \({\ell } _1\)’s rin variable. This prevents \({\mathcal {R}}^{r,n}_3\) from modifying \({\ell } _1\)’s rin variable before it becomes entitled. Therefore, when \({\mathcal {R}}^{w,nn}_4\) is released, the condition at Line 13 in Listing 4 is true for its single resource \({\ell } _2\), so it is immediately satisfied.

1.3 Linearizability

Herlihy and Wing presented linearizability as a correctness condition for concurrent objects that “provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point between its invocation and its response.” Linearizability is a local property; if the operations on each object can be linearized, the system as a whole is considered to be linearizable (Herlihy and Wing 1990). In the following discussion, we focus on the fast RW-RNLP with the RW-RNLP* as our example, but the fast RW-RNLP with the \(\text {R}^3\text {LP}\) is linearizable as well.

In the body of the paper, we claim that each routine we presented has a linearization point; this is the point at which the routine can be considered to take effect (atomically). For the non-nested routines, these points are clear. A read request enqueues atomically at Line 3 (Listing 4) and can be viewed as executing the lock function as a whole atomically at the end of the procedure. Similarly for \(\textsc {R*\_Unlock}^\textit{nn}\), the routine’s linearization point can be considered to be at its invocation. The non-nested write routines function similarly, with linearization points at the end of the lock routine’s execution and the beginning of the execution of the unlock routine.

The nested routines grant access to groups of resources at a time (Listing 5). Considering the routines themselves, each call of the lock routine can be said to linearize to the last point in its execution. That is, no access to any of the requested resources occurs before that point in time, and the order of request accesses to those resources is exactly the order of termination of the lock routines. (Recall that linearization is defined relative to a specific resource; there may be requests for other resources occurring concurrently. These requests are not granted access clearly before or after the non-conflicting request. Again, linearization is a local property and there may be multiple legal sequential histories (Herlihy and Wing 1990).) Just like non-nested requests, the invocation of each unlock routine can be considered to be the linearization point of the entire routine.

Illustration of a series of lock and unlock calls by requests \({\mathcal {R}}_1\) through \({\mathcal {R}}_5\) with the linearization point of each operation shown with a circle

Full size image

An example of the linearization of several objects is shown in Fig. 20. An operation invocation op on a set of shared resources \(D_i\) by request \({\mathcal {R}}_i\) is indicated by \(D_i~ \textit{op}~ {\mathcal {R}}_i\) above a line whose length corresponds to the duration of time each invocation takes. The linearization point of each operation’s execution is indicated with a circle at some point during its execution. As discussed above, this point can always be selected at the end of the execution of a lock operation and at the beginning of the execution of an unlock operation. In Fig. 20, time moves forward to the right.

Example 12

In Fig. 20, \({\mathcal {R}}^{w,n}_1\) is the first to begin executing the lock logic to gain mutually exclusive access to \(D_1 = \{{\ell } _1, {\ell } _2\}\). Then \({\mathcal {R}}^{w,nn}_2\) is issued for \(D_2 = \{{\ell } _2\}\). \({\mathcal {R}}^{w,nn}_2\) calls \(\textsc {W*\_Lock}^\textit{nn}\) for \({\ell } _2\). It is granted access to \({\ell } _2\) first (at the end of the lock routine), and then enters its critical section before calling \(\textsc {W*\_Unlock}^\textit{nn}\).

During \({\mathcal {R}}^{w,nn}_2\)’s execution of the lock operation, \({\mathcal {R}}^{r,n}_3\) invoked the lock call for \(D_3 = \{{\ell } _1, {\ell } _2\}\).

At some point \({\mathcal {R}}^{w,nn}_2\) completes its critical section and invokes the unlock routine. The unlock routine can be linearized to the point indicated in the Fig. 20, which clearly comes before the point at which \({\mathcal {R}}^{w,n}_1\) or \({\mathcal {R}}^{r,n}_3\) has linearized its respective lock call. Note that this properly reflects the mutually exclusive access for \({\mathcal {R}}^{w,nn}_2\) for \({\ell } _2\); a request is considered to access the resource between the linearization point for its call to the lock routine and the linearization point for its call to the unlock routine.

At a later point in time, \({\mathcal {R}}^{w,n}_1\) finishes execution of the lock routine, enters its critical section, and then calls the unlock routine.

While \({\mathcal {R}}^{w,n}_1\) is executing the unlock routine for \(D_1=\{{\ell } _1,{\ell } _2\}\), \({\mathcal {R}}^{r,nn}_4\) and \({\mathcal {R}}^{w,nn}_5\) are issued for \(D_4=\{{\ell } _1\}\) and \(D_5=\{{\ell } _1\}\), respectively.

At some point in time after \({\mathcal {R}}^{w,n}_1\) has updated the writer bits of \({\ell } _1\)’s rin variable, \({\mathcal {R}}^{r,nn}_4\) becomes satisfied and completes its call to the lock routine. Similarly, after \({\mathcal {R}}^{w,n}_1\) has updated \({\ell } _2\)’s rin variable, \({\mathcal {R}}^{r,n}_3\) becomes satisfied and completes its call to the lock routine. Note that overlapping critical sections for \({\ell } _1\) is expected behavior for these requests; read requests may overlap.

Once the read requests finish accessing their respective resources, they both call the unlock routine. At a future point in time, \({\mathcal {R}}^{w,nn}_5\) completes its call to the lock routine and can begin its critical section. Note that the linearization points correctly reflect mutually exclusive access for this request for \({\ell } _1\).

1.4 Constraints used in schedulability study

As mentioned in the body of the paper, we tightened the calculated blocking from the the worst-case acquisition-delay bounds presented in Table 1 by applying several constraints. We illustrate these with an example using a ticket lock, and then discuss how these can be applied to more complex protocols.

Example 13

Suppose that we are working with an application with four tasks (\(n=4\)) and six processors (\(m=6\)) in which all tasks have the same period and access the same resource. The access of this resource is protected by a ticket lock. The requests issued by these tasks are \({\mathcal {R}}^w_1,...,{\mathcal {R}}^w_4\), with critical-section lengths \(L_1=50\mu \)s, \(L_2=60\mu \)s, \(L_3=30\mu \)s, and \(L_4=20\mu \)s. When calculating the worst-case blocking that the task issuing request \({\mathcal {R}}^w_1\) may experience, we can use the analytical bound for a ticket lock of \((m-1)L_{max} ^w\), where \(L_{max} ^w=60\mu \)s. Then the worst-case blocking for \({\mathcal {R}}^w_1\) is bounded by \(5 \cdot 60 = 300\mu \)s. However this blocking can never occur in practice.

1.4.1 Period-based constraints

Based on the period of each task in the system, we can compute how many jobs (and thus requests) of that task may be active while a given request is active. Then we can tighten our analysis to select only the highest instances of critical sections that may delay a given request.

Example 13 (cont’d)

As all tasks have the same period, at most two jobs of a given task can overlap with the job of interest. Thus, the job that issues \({\mathcal {R}}^w_2\) can only issue it twice while \({\mathcal {R}}^w_1\) is waiting or executing. We can tighten our analysis to select the top \(m-1\) instances of critical sections that may delay \({\mathcal {R}}^w_1\). Our new bound on the worst-case blocking after applying period-based constraints is \(60+60+30+30+20=200\mu \)s. Note that we do not count \({\mathcal {R}}^w_1\) as potentially increasing its own blocking.

1.4.2 FIFO constraints

The write requests handled by a ticket lock are enqueued in a FIFO queue. Thus, each request can only delay a given request once.

Example 13 (cont’d)

By imposing FIFO constraints, we can bound worst-case blocking to \(60+30+20=110\mu \)s.

Example 14

We now modify the task system presented in Example A.4 by adding a read request \({\mathcal {R}}^r_5\) with \(L_5=3\mu \)s. The task that issues \({\mathcal {R}}^r_5\) has a shorter period such that it could be issued six times while a given write request is active. We switch from using a ticket lock to using a PF-TL. When considering the blocking \({\mathcal {R}}^w_1\) may experience, the above analysis still holds for the write requests. Now we must account for the blocking \({\mathcal {R}}^w_1\) may experience due to read requests.

Note that when we consider locking protocols with both read and write requests, FIFO constraints may apply to the write requests but will not apply to read requests; all reader/writer protocols we have discussed handle read requests separately from write requests to yield constant-time blocking. Because of this, a given read request may execute multiple times before a write request of interest. However, we can constrain the total number of read requests that must be included by period-based constraints and a new constraint.

1.4.3 Read-write constraints

Each protocol examined in this paper functions by alternative write and read phases in some manner. Thus, the number of read phases by which a request is blocked is constrained by the number of write phases possible, which may be limited by the above constraints.

Example 14 (cont’d)

In this scenario, only three write requests could contribute to the blocking \({\mathcal {R}}^w_1\) experiences. In the worst case, before each of these write requests (including \({\mathcal {R}}^w_1\)), a read phase could occur. Thus, we are limited to the four highest read critical-section instances. Because our read request could occur six times, its critical section can be counted for all four instances. Thus the blocking \({\mathcal {R}}^w_1\) experiences due to read requests is at most \(4 \cdot 3 = 12\mu \)s and the total blocking is at most \(110 + 12=122\mu \)s.

While we have focused on the blocking a write request may experience in the above examples, the same constraints may be applied when calculating the write and read critical sections that may block a read request.

1.4.4 Contention constraints

For both fast RW-RNLP variants, the blocking bound for non-nested write requests depends on contention. Recall that in Theorem 1 the contending requests that contributed to blocking were only other non-nested write requests for the same resource. Therefore, for each task system and each request, we use the number of contending non-nested write requests for the value of contention.

1.4.5 Constraints applied to protocols

Recall that we evaluated four protocols: the PF-TL, the RW-RNLP, the fast RW-RNLP with the \(\text {R}^3\text {LP}\), and the fast RW-RNLP with the RW-RNLP*. The PF-TL was applied as group lock for a static group of all resources.

When the period-based, FIFO, and read-write constraints are applied to the group PF-TL, the blocking computed for read and write requests may be tightened. The same analysis holds for the RW-RNLP. While the RW-RNLP is a fine-grained locking protocol, its worst-case blocking for write requests is still \((m-1)(L_{max} ^w + L_{max} ^r)\) due to potential transitive blocking chains between nested write requests. Computing these transitive blocking chains is an expensive process, and in a system with randomly requested resources, write expansion and potential chains imply that it is likely that each write request could delay any other write request. However, the FIFO manner in which the RW-RNLP functions allows us to use the FIFO constraint to limit the contribution of each write request to blocking others only once. Without expensive tighter analysis that considers possible transitive blocking chains, the tightened blocking bounds of the RW-RNLP are identical to those of the group PF-TL.

FIFO constraints can also be applied to the fast RW-RNLP, but the modular structure means that FIFO constraints cannot be applied to write requests of the opposite type. For example, a given nested write request may enter the RNLP and then be allowed to execute by the global arbitration mechanism multiple times while a non-nested write request waits behind other non-nested write requests in its ticket lock. The same scenario can occur for nested write requests. Thus the FIFO constraints can only be applied to nested write requests which share at least one resource or non-nested write requests for the same resource. For any write requests to which FIFO constraints cannot be applied, the period-based constraints can still be applied. Due to the way in which requests are grouped by the \(\text {R}^3\text {LP}\), when we account for blocking in the fast RW-RNLP with the \(\text {R}^3\text {LP}\), we add the highest critical-section length instances of non-nested write requests and nested write requests separately to get a tighter bound.

Based on the number of requests being generated in each scenario, we expect that in some scenarios, the manner in which the FIFO constraints can be applied in the context of the group PF-TL may greatly reduce the number of critical sections that may be counted toward blocking. (Because it is a group lock, each write can only effect the request of interest once by the FIFO constraint.) The FIFO constraint cannot be applied as broadly to the fine-grained nesting protocols, as some requests may delay the request of interest multiple times. This argues for tighter blocking analysis, though getting exact blocking analysis for nested resource accesses is NP-hard (Wieder and Brandenburg 2014).

Reprints and permissions