FARMHANDS

[Functional Assets Required to Make Highly Available Nontrivial Distributed Systems]

Methodology, components & tools > Design patterns > Resources scheduler

In the standard guarded suspension pattern, if multiple threads are suspended, the pattern does not specify the order in which they shall be waken up again. In the proposed implementation, the last suspended request is the first to be awakened. The secheduler pattern (Lea, 1997) is suggested to deal with exclusive access to shared resources among multiple processes. Each process needs to wait until the resource is available and assigned to it, according to a specific policy.

This pattern is of applicability whenever

different calls to grant exclusive access to a shared resource must be synchronized, and
there is a particular policy to serialize access when several processes try to access the resource.

Figure 3 summarizes a typical interaction. Whenever a process needs a resource, it requests access by invoking an enter method from a scheduler. This call will not return until the scheduler decides to grant access to the process. The process will then have exclusive access to the resource until it requests a done service from the same scheduler; at that point the scheduler will choose, from the waiting processes, the next to get access to the resource.

Fig. 3. Using a scheduler to grant access to shared resources

The scheduler is implemented as a server with guarded suspension providing two services (enter and done). The server is configured with a policy function Policy: [(Client, Req)] -> ((Client, Req), [(Client, Req)]) to select the next process to be awakened. Besides, the scheduler state includes information about the resource lock status (busy or available).

-module(scheduler). -export([new/1, enter/2, done/1]). -export([handle/2, must_suspend/2, resume/2]). new(Policy) -> guardeds:start(fun handle/2, fun can_access/2, fun resume/2, {Policy, available}). enter(Scheduler, Data) -> server:call(Scheduler, {enter, Data}). done(Scheduler) -> server:call(Scheduler, done). handle({enter, Data}, {Policy, available}) -> {ok, {Policy,busy}}; handle(done, {Policy, busy}) -> {ok, {Policy,available}}. can_access({enter, Data}, {Policy, busy}) -> false; can_access(_,_) -> true. resume({Policy, available}, Suspended) -> {Request, MoreSuspended} = Policy(Suspended), {ok, Request, MoreSuspended}; resume(_, _) -> none.

Some policies or strategies can be defined as:

-module(policy). -export([fifo/1, lifo/1, priority/1]). lifo([X|Xs]) -> {X,Xs}. fifo(Suspended) -> {last(Suspended), firsts(Suspended)}.

Or if Data is an integer (such as the priority):

priority([ASuspended | MoreSuspended]) -> lists:foldl(fun (Req, {MaxReq, RestRequests}) -> case higher_prio(Req, MaxReq) of true -> {Req, [MaxReq|RestRequests]}; false -> {MaxReq, [Req|RestRequests]} end, end, {ASuspended, []}, MoreSuspended). higher_prio({_, {_, D1}}, {_, {_, D2}}) -> D1 > D2.

Once the scheduler has been defined, a convenient API to access the shared resource is as shown below:

-module(myresource). -export([start/1, doit/1]). start(Policy) -> Scheduler = scheduler:start(fun (X) -> policy:fifo(X) end), ResourceID = ... % some resource initialization {Scheduler, ResourceID}. doit({Scheduler, ResourceID}) -> scheduler:enter(Scheduler), ... work on ResourceID ... scheduler:done(Scheduler).

References

Lea, D. (1997). Concurrent programming in java: Design principles and patterns Reading, Mass.: Addison-Wesley