priority-sync: Task prioritization.

[ bsd3, concurrency, library, program ] [ Propose Tags ]

Implements cooperative task prioritization with room synchronization.

In the simplest usage, for an unprioritized FILO queue, only three operations are needed: simpleTaskPool, claim, and startQueue.

(pool :: TaskPool () ()) <- simpleTaskPool
forkIO $ claim Acquire pool $ putStrLn "Hello world!"
forkIO $ claim Acquire pool $ putStrLn "Goodbye world!"
startQueue pool

For a simple prioritized queue, the schedule operation introduces the priority. Prioritization is always least-first.

prio_pool <- simpleTaskPool
forkIO $ claim Acquire (schedule prio_pool 1) $ putStrLn "Hello world!"
forkIO $ claim Acquire (schedule prio_pool 2) $ putStrLn "Goodbye world!"
startQueue prio_pool

Note that if you run these programs with +RTS -N2 or greater, the claim operations may be processed in any order, since simpleTaskQueue detects the number of capabilities and schedules tasks on each.

TaskPools are not thread pools. The concept is similar to IO Completion Ports. There are no worker threads. If a number of threads are waiting, the thread that is most likely to be processed next is woken and temporarily serves as a working thread. TaskPools are backed by carefully written STM (software transactional memory) transactions.

A salient feature is that, because any thread can participate, a TaskPool supports both bound threads and threads created with forkOnIO.

For applications that have complex resource constraints, it is possible to create a Room to model each constraint. Rooms are fully reentrant, and an arbitrary number of threads can claim a Room according to arbitrary rules, or RoomConstraints. In the simple usage above, a single room represents the number of capabilities available to the GHC runtime.

Whenever a thread attempts to acquire a Room, a Claim is generated that represents that attempt. The Claim can be approved immediately, or it can be approved at the whim of another thread that has access to that Claim. This means that Rooms can be constructed in such a way that Claims are approved only when a third party thread sees that the resource constraint modeled by that Room has been satisfied.

The rules for generating and approving Claims are described by a RoomContext. By default, Claims are approved immediately if their associated RoomConstraints have been satisfied, but when a TaskPool is introduced approval is deferred for prioritization.

Room constraints are completely advisory: any task may claim any Room without restriction at any time by using the UnconstrainedRoomContext.

Queues are used to prioritize tasks. Even if you have no need for prioritization, a Queue ensures that only one thread is woken up when a Room becomes available. A Queue systematically examines to a configurable depth all waiting threads with their priorities and constraints and wakes the most eagerly prioritized thread whose constraints can be satisfied.

A TaskPool combines Rooms and Queues in an efficient, easy-to-use interface.

The git repository is available at http://www.downstairspeople.org/git/priority-sync.git.

Versions [faq] 0.1.0.0, 0.1.0.1, 0.2.1.0, 0.2.1.1
Dependencies base (>3), containers (>=0.1.0.1), heap, parallel (>=1.0.0.0), random, stm (>=2.1.1.2) [details]
License BSD-3-Clause
Author Christopher Lane Hinson
Maintainer Christopher Lane Hinson <lane@downstairspeople.org>
Category Concurrency
Uploaded by ChristopherLaneHinson at Wed Apr 29 17:18:38 UTC 2009
Distributions NixOS:0.2.1.1
Executables _Control_Concurrent_Priority_Tests
Downloads 1863 total (44 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees