First of all, we'll begin importing some libraries that we will use:
Note
Instaparse (https://github.com/engelberg/instaparse) is a parser generator written in Clojure. To explain all of the mechanism behind Instaparse is beyond the scope of this book, but you should know that it handles context-free grammar (CFG) and generates parse trees of your input programs according to these grammar concepts.
To be able to pretty-print our output in the REPL, let's define an alias for clojure.pprint/pprint
, so that we can make it more conveniently:
As we'll be spawning processes with instructions of their own, let's define a minimal language that instaparse
will be able to interpret for us. Our language instructions for a single process are as follows:
The previous snippet is self-explanatory. Our language only contains three types of operations: heavy-op
, which are sorted according to the effort they need in order to be fully processed by the scheduler: heavy-op
, medium-op
, and finally light-op
. Besides, we are able to lock and unlock a portion of our programs with the lock
and unlock
instructions. Each one of these instructions needs you to specify an identifier, so that they can be recognized in the scheduler output.
The grammar for such a language is:
Note that identifiers between angle brackets will not be seen in the parse tree, so there's no use referring to the white-space
tags, for instance.
Let's see what would be the Instaparse output for the program we wrote in the preceding code. For this, just type the following in your REPL:
We need to transform these nested vectors in to instructions. First of all, we will make use of the very handy instaparse function transform
to eliminate the rules tags and get a more useful representation of our instructions. transform
function takes a tag and applies a function to the elements next to it in the vector that this tag refers to:
Here is the output of gen-program
. Input the following code in the REPL:
You'll get the following output:
To get rid of the nesting that we still see here, we are going to use a zipper, which is a Clojure facility to walk trees. Basically, we will loop all the nested vector elements and only take maps, so that we end up with a nice, flat program structure. As this will be our actual process, we'll also append a process-id
attribute and a priority
attribute to its output:
Here is a process spawned by our program named :process-1
that has the priority 10
. Input the following in your REPL:
You'll get the following output:
Now, we need to set effort for each of our instructions, that is, how many processor cycles each one of them takes to be executed:
Now we'll concern ourselves with locking. First of all, we need to find the indices of locking instructions in our instructions vector:
With our locks recognized, we can tell which lock every instruction depends on. This is basically done by finding out which locks have indices inferior to the instruction index:
We'll need a map that maintains the state of locks so the scheduler can track the locking and unlocking activities during the program execution with. We'll define lock
and un-lock
functions to do this:
The locker process information, manipulated in the previous step is important. As some process' instruction can only be denied access to a shared resource by locks set by other processes contains, we need to track which is locking what. The is-locked?
function relies on this mechanism to inform whether an instruction is locked at any point in time, so it cannot be fired by the scheduler:
Let's focus on the scheduler now. Imagine that some parts of a process have already been assigned some quanta of time. We need a map to maintain a state for all the processes regarding the parts that already have been processed so far. We'll call this map scheduled
. Let's say that this map should look like the following:
We'll prepare a helper function, scheduled-processes-parts
, that'll count the number of quanta already allocated, and this will be handy in knowing whether an instruction is complete:
We'll use this function to implement incomplete-instruction?
, incomplete-process?
, and more-incomplete-processes?
that we'll use later on:
Diving deeper into the implementation, let's now look at a single process and define a function that finds which instruction is to be fired if the scheduler decides to allocate a quantum to it. This translates to the first incomplete instruction if it is non-locked, that is, none of its locks have been set to locked
by another process:
Now, let's write progress-on-process!
, which considers one particular process, fires its fireable instruction — as found by the preceding function, and updates all locks
and scheduled
states. This is quite a long function, as it is the heart of the scheduler:
The following functions will help us prepare empty locks
and scheduled
maps, which are to be used by progress-on-process!
:
Equipped with all these functions, we must address the problem of process selection for the allocation of each quantum of time. We must give each process an opportunity to access the scheduler quanta according to its priority. For this purpose, we will construct an infinite sequence of holding repetitions of a process ID as many times as their priority values. In this, a process with higher priority will always come before another with lower priority. Suppose we have process p1
with priority 3, process p2
with priority 2, and process p3
with priority 1, then a sequence presenting the cycling that we described previously would be:
As the time quantums flow, the scheduler will have to pick at each step an element, cycling through the weighted cycling list, which we just saw, to be sure it is fair toward the process's priority.
The following functions create the priority-weighted cycling process IDs:
Locking programs may lead to infinite waiting. To tackle this problem, we will set a time-out for our scheduler, which will be twice the time needed by all the processes if they were to be executed sequentially, one after the other. This function does just that:
Finally, we can write our scheduler. While there are incomplete processes left to be scheduled and before the current quantum reaches time-out, the scheduler will cycle the weighted processes cycles, pick one process, and call progress-on-a-process!
on it. Note that we launch this on several programs as we are implementing time-sharing to do multithreading: