Miou, a simple scheduler for unikernels

The first piece of our unikernel

Miou is a simple scheduler written in pure OCaml (whose priority queue has been proven via the VOCAL project) that allows tasks to be launched cooperatively: the aim is to have several tasks running at the same time so that, for example, our unikernel can handle several clients at the same time (in reality, these tasks do not run simultaneously as we only have a single vCPU available for our unikernel, but the scheduler seizes opportunities to execute some of our tasks whilst others are blocked).

In this chapter, we will first attempt to create our own scheduler from scratch in order to understand what a scheduler does. Next, we will introduce you to Miou with a few fairly simple examples.

A hand-written scheduler in OCaml

The idea behind a scheduler is to be able to have a task that runs in the background without blocking the execution of other tasks, such as our main task. In other words, we would like to be able to write the following:

let fn () = print_endline "World"

let () =
  do_it_in_background fn;
  print_endline "Hello"

We would like "Hello" to be displayed first, followed by the execution of our fn function, and then "World" to be displayed. Our scheduler would be responsible for executing fn. It is generally accepted that there should be some sort of witness (or promise) for the task that will execute fn. In this way, we will know whether fn has actually been executed and in what state the task ended.

let fn () = print_endline "World"

let () =
  let promise = do_it_in_background fn in
  print_endline "Hello";
  match await promise with
  | Ok () -> ()
  | Error exn -> raise exn

We now have what any OCaml scheduler should, in principle, provide. We will therefore set about implementing a scheduler that should provide the functions do_it_in_background and await. To do this, we will introduce you to a new concept in OCaml 5: effects.

Effects

One way of looking at effects in OCaml is probably to compare them with exceptions. The advantage of an exception is that it allows you to interrupt the execution of a function in order to jump to another part of the code:

let () =
  try print_endline "Hello" ;
      raise Break;
      print_endline "Unikernel"
  with Break ->
      print_endline "World"

Effects share the same feature of being able to interrupt execution and jump to another part of the code. However, they can also return to the point where the interruption occurred!

open Effect.Deep

type _ Effect.t += Break : unit Effect.t

let () =
  match print_endline "Hello";
        Effect.perform Break;
        print_endline "Unikernel"
  with
  | effect Break, k ->
    print_endline "World";
    continue k ()
  | () -> ()

This is the basic principle behind effects. As far as our scheduler is concerned, this will allow us to switch between application code and our scheduler's implementation (just as we can switch from user space to kernel space for a normal executable) and return to the breakpoint. We will therefore be able to manage and execute tasks behind our application.

A simple task

A task can be described as follows:

• it is a function representing a piece of code that we should execute
• it is a piece of code that has been paused at a certain point and which we can resume
• it is a result (what this piece of code produces) or an error

Its equivalent in OCaml is:

open Effect.Shallow

type 'a state =
  | Initial of (unit -> 'a)
  | Suspended : ('c, 'a) continuation * 'c Effect.t -> 'a state
  | Resolved of ('a, exn) result

Next, we’ll define a handler that will allow us to specify what to do when an effect occurs, an exception is thrown, or the function terminates:

let handler =
  let open Effect.Shallow in
  let retc v = Resolved (Ok v)
  and exnc exn = Resolved (Error exn)
  and effc : type c. c Effect.t -> ((c, 'a) continuation -> 'b) option
    = fun eff -> Some (fun k -> Suspended (k, eff)) in
  { retc; exnc; effc }

Finally, a task can simply be defined as the state of our piece of code:

type task = Task : 'a state -> task

A promise

Schedulers often provide a promise value. This acts as a witness for the task, showing whether or not it has been completed. It is called a promise because it represents a value that "should" appear in the future (once the task is complete). It is therefore a value that will change, which is why we define our promise as such for our scheduler:

type 'a promise = ('a, exn) result option ref

Next, we'll finally define our first two effects: one for running a task in the background, and one for waiting for a task to finish:

type _ Effect.t += Spawn : (unit -> 'a) -> 'a promise Effect.t
type _ Effect.t += Await : 'a promise -> ('a, exn) result Effect.t

Our basic scheduler

A scheduler is basically a program that maintains a list of tasks to be carried out. It simply tries to work through this list until there are no more tasks left. In this case, our Spawn effect adds a task to this list and our Await effect will watch our promise and either return the result or ask our scheduler to execute the other tasks (which may lead to the result being obtained).

let perform
  : type c. task list -> c Effect.t -> [ `Continue of c | `Yield ] * task list
  = fun todo -> function
  | Spawn fn ->
    let promise = ref None in
    let task = Initial (fun () -> value := Some (fn ())) in
    `Continue value, todo @ [ Task task ]
  | Await value -> begin match !value with
    | Some value -> `Continue value, todo
    | None -> `Yield, todo end
  | _ -> invalid_arg "Invalid effect"

The next step is to move a task forward so that part of it is executed and a new version of the task is created.

let step todo = function
  | Initial fn ->
    Effect.Shallow.(continue_with fn () handler), todo
  | Resolved _ as value -> value, todo
  | Suspended (k, effect) ->
    match perform todo effect with
    | `Continue v, todo -> Effect.Shallow.(continue_with k v handler), todo
    | `Yield, todo -> Suspended (k, effect), todo

Finally, the core of our scheduler consists of a loop that continues until there are no more tasks left. The aim is to advance our tasks (using the step function) until they have all been completed.

let run fn =

  let rec go = function
    | [] -> Option.get !result
    | Task task :: rest ->
      let state, todo = step todo task in
      match state with

      | Resolved _ -> go todo

      | (Initial _ | Suspended _) as task ->
        go (todo @ [ Task task ]) in

  let result = ref None in
  let task = Initial (fun () -> result := Some (fn ())) in
  go [ Task task ]; Option.get !result

A simple program with our scheduler

Do you remember our very first programme? We can now implement it as follows:

let fn () = print_endline "World"

let () = run @@ fun () ->
  let promise = Effect.perform (Spawn fn) in
  print_endline "Hello";
  match Effect.perform (Await promise) with
  | Ok () -> ()
  | Error exn -> raise exn

If we run this code, we do indeed see "Hello" and "World" displayed one after the other (even though we spawned fn before our print_endline). That's the principle behind schedulers! Now that you understand the principle, we can introduce Miou with a few examples.

Miou through examples

Miou is therefore simply a scheduler. Its sole purpose is only to manage tasks. We will look at I/O management in relation to unikernels using mkernel later on. We will therefore use fairly general examples to understand how Miou works. In this case, this scheduler has certain rules that developers must strictly adhere to, and we will describe them here.

Never forget your tasks

Miou has one fundamental rule: never forget your tasks. A task is considered to be a resource and, like all resources, it has a creation phase (using Miou.async or Miou.call - which corresponds to our Spawn) and a release phase (using Miou.await). So, as soon as you create a task, there should be a Miou.await on the promise not far away.

If this is not the case, Miou throws a Still_has_children exception:

# require "miou" ;;
# let () = Miou.run @@ fun () ->
    let _promise = Miou.async (Fun.const ()) in
    () ;;
Exception: Miou.Still_has_children

You must therefore either ensure that a task has completed successfully and retrieve its result using Miou.await, or cancel that task using Miou.cancel.

let () = Miou.run @@ fun () ->
  let promise0 = Miou.async (Fun.const ()) in
  let promise1 = Miou.async (Fun.const ()) in
  Miou.await_exn promise0;
  Miou.cancel promise1

Structured concurrency

Miou offers a form of task management known as structural: that is to say, there is a link between tasks, and in particular between tasks and their children. A child is a sub-task created from a task known as its parent.

let () = Miou.run @@ fun () ->
  let parent = Miou.async @@ fun () ->

    let child = Miou.async (Fun.const ()) in
    Miou.await_exn child in
  Miou.await_exn parent

Miou considers that a subtask can only be awaited (or cancelled) by its parent. The parent is said to ‘own’ its subtasks. If a task awaits another when there is no such parent-child relationship between the two, Miou raises the Not_a_child exception:

# let () = Miou.run @@ fun () ->
    let q = Queue.create () in
    let promise0 = Miou.async @@ fun () ->
      let sub = Miou.async (Fun.const ()) in
      Queue.push q sub;
      Miou.await_exn sub in
    let promise1 = Miou.async @@ fun () ->
      while Queue.is_empty q do Miou.yield () done;
      let sub = Queue.pop q in
      Miou.await_exn sub in
    Miou.await_exn promise0;
    Miou.await_exn promise1
  ;;
Exception: Miou.Not_a_child

This example is interesting because it illustrates why we might want a subtask to be shared between two tasks: to transfer information (in this case, we are attempting to do so via a shared queue).

In reality, Miou forces you to think about this issue using methods other than tasks: by means of a queue (possibly an atomic one), an array shared with a mutex, or a write-once variable.

This rule that one can only wait for one's own children also applies to cancellation; one can only cancel one's direct descendants.

Concurrency

One of the benefits of the scheduler is that it allows you to attempt to run several tasks at the same time and set a time limit on the execution of a task, rather than waiting indefinitely.

One of the best-known examples is attempting to connect to a service and cancelling the connection after a certain amount of time:

exception Timeout

let () = Miou_unix.run @@ fun () ->
  let socket = Miou_unix.tcpv4 () in
  (* localhost:80 *)
  let sockaddr = Unix.(ADDR_INET (inet_addr_loopback, 80)) in

  let promise0 = Miou.async @@ fun () ->
    Miou_unix.connect socket sockaddr in

  let promise1 = Miou.async @@ fun () ->
    Miou_unix.sleep 10.;
    raise Timeout in

  match Miou.await_first [ promise0; promise1 ] with
  | Ok () -> Miou_unix.close socket
  | Error Timeout -> prerr_endline "Timeout"
  | Error exn -> raise exn

Miou.await_first will wait for the first of the two tasks to complete, but it will also cancel the other task. It is said to cancel (Miou.cancel) all other tasks that have not yet completed. In this way, we comply with our first rule.

Background tasks

Miou offers a design pattern that is fairly straightforward to understand when it comes to setting up a service that needs to handle multiple clients. For this type of application, one usually ends up accepting clients and creating a "standalone" task for each client so that they can be managed simultaneously whilst new clients are being accepted.

These "standalone" tasks are known as background tasks; in other words, they continue to run (to manage clients) whilst our main task is to accept new clients.

To manage these tasks, using the same terminology as for children and parents, we refer to an orphanage to keep these tasks in the background. The idea is to keep track of these tasks and be able to check whether any of them have been completed (because, according to our first rule, we must not forget our tasks).

let rec clean_up orphans = match Miou.care orphans with
  | Some None | None -> ()
  | Some (Some promise) ->

    begin match Miou.await promise with
    | Ok () -> clean_up orphans
    | Error _exn -> () end

let () = Miou_unix.run @@ fun () ->
  let main = Miou_unix.tcpv4 () in
  (* localhost:8080 *)
  Miou_unix.bind_and_listen main
    Unix.(ADDR_INET (inet_addr_loopback, 8080));

  let rec go orphans =

    clean_up orphans;
    let socket, _ = Miou_unix.accept main in

    let _ = Miou.async ~orphans (fun () -> handle_client socket) in
    go orphans in
  go (Miou.orphans ())

Daemon

Another example, when developing an application, is having a background task to which we would like to send instructions on what actions to perform. This concept is generally referred to as a daemon.

This daemon exists and should terminate when our unikernel shuts down. We should then provide the ability to pass actions to this daemon.

type action =
  | Print of string

type state =
  { queue : action Queue.t
  ; mutex : Miou.Mutex.t
  ; condition : Miou.Condition.t }

let rec go t =
  let actions = Miou.Mutex.protect t.mutex @@ fun () ->
    while Queue.is_empty t.queue do

      Miou.Condition.wait t.condition t.mutex
    done;
    let actions = Queue.to_seq t.queue in
    let actions = List.of_seq actions in
    Queue.clean t.queue;
    actions in
  let fn = function
    | Print str -> print_endline str in

  List.iter fn actions;
  go t

let daemon () =
  let state =
    { queue= Queue.create ()
    ; mutex= Miou.Mutex.create ()
    ; condition= Miou.Condition.create () } in

  state, Miou.async (fun () -> go state)

let put elt t = Miou.Mutex.protect t.mutex @@ fun () ->
  Queue.push elt t.queue;
  Miou.Condition.signal t.condition 

let () = Miou.run @@ fun () ->
  let state, daemon = daemon () in

  Fun.protect ~finally:(fun () -> Miou.cancel daemon) @@ fun () ->
  put (Print "Hello") state;
  put (Print "World") state

This short example demonstrates a mechanism for transferring information (our actions) to another task. As far as our unikernel is concerned, we'll have quite a few daemons, just as you have plenty of daemons currently running on your system. This is simply an illustration in OCaml.

Ownership

Miou offers one final mechanism: ownership. This is a concept found in the Rust programming language. It involves assigning a resource to a specific task. If the task terminates abnormally or is cancelled, Miou will ensure that the resource in question is released.

Here is a very practical example:

let () = Miou_unix.run @@ fun () ->
  let finally () = print_endline "Released!" in
  let promise0 = Miou.async @@ fun () ->
    let resource = Miou.Ownership.create ~finally () in
    Miou.Ownership.own resource;

    raise Stdlib.Exit in
  let promise1 = Miou.async @@ fun () ->
    let resource = Miou.Ownership.create ~finally () in
    Miou.Ownership.own resource;
    Miou_unix.sleep 10. in

  ignore (Miou.await promise0);

  Miou.cancel promise1

Here is an example of a task that handles a client and repeats what the latter writes.

let handler socket =
  let tmp = Bytes.create 0x7ff in
  let finally = Miou_unix.close in
  let resource = Miou.Ownership.create ~finally socket in
  Miou.Ownership.own resource;
  let rec go () =
    let len = Miou_unix.read socket tmp 0 0x7ff in
    if len > 0 then begin
      let str = Bytes.sub_string tmp 0 len in
      Miou_unix.write socket str;
      go ()
    end in
  go ();
  Miou.Ownership.release resource

Check and transfer

It can also sometimes be useful to transfer ownership of a task to another. For example, we might first want to create a socket, acquire ownership of it, attempt a connection using the same model described here (and thus transfer ownership to the task attempting the connection), and finally transfer our socket back to the original task.

exception Timeout

let connect sockaddr =
  let socket = Miou_unix.tcpv4 () in
  let resource = Miou.Ownership.create ~finally:Miou_unix.close socket in
  Miou.Ownership.own resource;

  let promise0 = Miou.async ~give:[ resource ] @@ fun () ->
    Miou_unix.connect socket sockaddr;

    Miou.Ownership.transfer resource in
  let promise1 = Miou.async @@ fun () ->
    Miou_unix.select 10.; raise Timeout in
  match Miou.await_first [ promise0; promise1 ] with
  | Ok () -> socket
  | Error Timeout -> failwith "Timeout"
  | Error exn -> failwith "Unexpected exception"

The advantage of this approach is that it ensures that, in the event of a failure (if Miou_unix.connect fails) or cancellation (if promise0 is cancelled due to a timeout), a Unix.close is indeed called to release the resource correctly.

Conclusion

You know all about Miou now! In fact, Miou offers very few features and focuses solely on scheduling. We’ve introduced you here and there to a few features of Miou_unix (the version of Miou with the Unix module), but you’ve got the basics down:

• creating and managing tasks
• orphanage for managing background tasks
• mutexes and conditions
• the principle of ownership

Next, there are plenty of interactions similar to Miou_unix, which we'll explore bit by bit. This allows us to introduce you to a new layer: mkernel. It’s an extension of Miou, but specifically for Solo5.

There is a whole ecosystem surrounding Miou and Miou_unix if you wish to develop OCaml applications that are not unikernels. mtbox is a suite of tools for debugging applications with Miou. In particular, we can recommend vif, our OCaml web framework, or blaze, our Swiss Army knife for email.

Thanks to its simplicity, the mental model a developer needs to adopt when thinking about scheduling is fairly straightforward and ultimately requires knowledge of only around twenty functions. And that is precisely Miou’s aim: to provide an extremely simple scheduler.