Implementation of the SSM runtime scheduler. More...

#include <ssm-internal.h>

Include dependency graph for ssm-scheduler.c:

Macros
#define	SSM_STATIC static
	A symbol is static unless `SSM_DEBUG` is defined. More...

#define	SSM_STATIC_INLINE static inline
	A symbol is static inline unless `SSM_DEBUG` is defined. More...

#define	SSM_EVENT_QUEUE_SIZE 2048
	Size of the event queue; override as necessary. More...

#define	SSM_ACT_QUEUE_SIZE 1024
	Size of the activation record queue; override as necessary. More...

#define	SSM_QUEUE_HEAD 1
	Extra entries at the start of a binary heap. More...

Typedefs
typedef uint16_t	q_idx_t
	Queue index type; index of 1 is the first element. More...

Functions
SSM_STATIC_INLINE void	act_queue_percolate_up (q_idx_t hole, ssm_act_t *act)
	Percolate act queue hole up, to find where to put a new entry. More...

SSM_STATIC_INLINE void	act_queue_percolate_down (q_idx_t hole, ssm_act_t *act)
	Percolate act queue hole down, to find where to put a new entry. More...

SSM_STATIC_INLINE void	event_queue_percolate_up (q_idx_t hole, ssm_sv_t *var)
	Percolate event queue hole up, to find where to put a new entry. More...

SSM_STATIC_INLINE void	event_queue_percolate_down (q_idx_t hole, ssm_sv_t *event)
	Percolate event queue hole down, to find where to put a new entry. More...

SSM_STATIC_INLINE q_idx_t	find_queued_event (ssm_sv_t *var)
	Determine the index of an already scheduled event. More...

ssm_time_t	ssm_now (void)
	The current model time. More...

bool	ssm_active (void)
	Whether there are still active processes in the activation queue. More...

ssm_act_t *	ssm_enter_int (size_t size, ssm_stepf_t step, ssm_act_t *parent, ssm_priority_t priority, ssm_depth_t depth)
	Allocate and initialize a routine activation record. More...

void	ssm_leave (ssm_act_t *act, size_t size)
	Destroy the activation record of a routine before leaving. More...

void	ssm_activate (ssm_act_t *act)
	Schedule a routine to run in the current instant. More...

void	ssm_sv_assign_unsafe (ssm_sv_t *var, ssm_priority_t prio, ssm_value_t val)
	ssm_assign() without automatic reference counting. More...

void	ssm_sv_later_unsafe (ssm_sv_t *var, ssm_time_t when, ssm_value_t val)
	ssm_later() without automatic reference counting. More...

void	ssm_sv_sensitize (ssm_sv_t var, ssm_trigger_t trig)
	Sensitize a variable to a trigger. More...

void	ssm_sv_desensitize (ssm_trigger_t *trig)
	Desensitize a variable from a trigger. More...

void	ssm_unschedule (ssm_sv_t *var)
	Unschedule any pending events on a variable. More...

ssm_time_t	ssm_next_event_time (void)
	The time of the next event in the event queue. More...

void	ssm_reset (void)
	Reset the scheduler. More...

void	ssm_set_now (ssm_time_t next)
	Advance the current model time. More...

void	ssm_update (ssm_sv_t *sv)
	Perform a (delayed) update on a variable. More...

void	ssm_tick (void)
	Run the system for the next scheduled instant. More...

Variables
SSM_STATIC ssm_sv_t *	event_queue [SSM_EVENT_QUEUE_SIZE+SSM_QUEUE_HEAD]
	Event queue, used to track and schedule events between instants. More...

SSM_STATIC q_idx_t	event_queue_len = 0
	The number of elements in event_queue. More...

SSM_STATIC ssm_act_t *	act_queue [SSM_ACT_QUEUE_SIZE+SSM_QUEUE_HEAD]
	Activation record queue, for scheduling at each instant. More...

SSM_STATIC q_idx_t	act_queue_len = 0
	the number of elements in act_queue. More...

SSM_STATIC ssm_time_t	now = 0L
	The current model time. More...

static size_t	num_processes = 0
	The program terminates when there are no more processes. More...

Detailed Description

Implementation of the SSM runtime scheduler.

Contains a priority queue implemented using a binary heap.

When SSM_DEBUG is defined, relevant symbols are exported for whitebox testing (see SSM_STATIC and SSM_STATIC_INLINE).

Author: Stephen Edwards (sedwards-lab); John Hui (j-hui)

Definition in file ssm-scheduler.c.

Macro Definition Documentation

◆ SSM_STATIC

#define SSM_STATIC static

A symbol is static unless SSM_DEBUG is defined.

Definition at line 24 of file ssm-scheduler.c.

◆ SSM_STATIC_INLINE

#define SSM_STATIC_INLINE static inline

A symbol is static inline unless SSM_DEBUG is defined.

Definition at line 25 of file ssm-scheduler.c.

◆ SSM_EVENT_QUEUE_SIZE

#define SSM_EVENT_QUEUE_SIZE 2048

Size of the event queue; override as necessary.

Definition at line 30 of file ssm-scheduler.c.

◆ SSM_ACT_QUEUE_SIZE

#define SSM_ACT_QUEUE_SIZE 1024

Size of the activation record queue; override as necessary.

Definition at line 35 of file ssm-scheduler.c.

◆ SSM_QUEUE_HEAD

#define SSM_QUEUE_HEAD 1

Extra entries at the start of a binary heap.

Definition at line 39 of file ssm-scheduler.c.

Typedef Documentation

◆ q_idx_t

typedef uint16_t q_idx_t

Queue index type; index of 1 is the first element.

Definition at line 42 of file ssm-scheduler.c.

Function Documentation

◆ act_queue_percolate_up()

SSM_STATIC_INLINE void act_queue_percolate_up	(	q_idx_t	hole,
		ssm_act_t *	act
	)

Percolate act queue hole up, to find where to put a new entry.

Starting at the hole, walk up toward the root of the tree, copying parent to child until we find where we can put the new activation record.

Parameters

hole	index of the hole that needs to be filled.
act	activation record that needs to be placed in the heap.

Definition at line 85 of file ssm-scheduler.c.

◆ act_queue_percolate_down()

SSM_STATIC_INLINE void act_queue_percolate_down	(	q_idx_t	hole,
		ssm_act_t *	act
	)

Percolate act queue hole down, to find where to put a new entry.

Starting at the hole, walk down towards the leaves of the tree, moving the earlier child to the parent and repeating the process on that child. This makes the parent earlier than both children. Stop when the activation record we're trying to place has a lower priority than either children.

Parameters

hole	where to place the given activation record.
act	activation record to be placed in the queue.

Definition at line 108 of file ssm-scheduler.c.

◆ event_queue_percolate_up()

SSM_STATIC_INLINE void event_queue_percolate_up	(	q_idx_t	hole,
		ssm_sv_t *	var
	)

Percolate event queue hole up, to find where to put a new entry.

Starting at the hole, walk up toward the root of the tree, copying parent to child until we find where we can put the new event.

The later_time field of var should already be set to the value it is sorted on.

Parameters

hole	index of the hole, from 1 to event_queue_len, inclusive.
var	event to place in the queue.

Definition at line 142 of file ssm-scheduler.c.

◆ event_queue_percolate_down()

SSM_STATIC_INLINE void event_queue_percolate_down	(	q_idx_t	hole,
		ssm_sv_t *	event
	)

Percolate event queue hole down, to find where to put a new entry.

Starting at the hole, walk down towards the leaves of the tree, moving the earlier child to the parent and repeating the process on that child. This makes the parent earlier than both children. Stop when the event we're trying to place is earlier than both of the children.

Parameters

hole	where to place event.
event	event to place in the queue.

Definition at line 164 of file ssm-scheduler.c.

◆ find_queued_event()

SSM_STATIC_INLINE q_idx_t find_queued_event ( ssm_sv_t * var )

Determine the index of an already scheduled event.

This is an inefficient linear search, so it's not meant to be used often. This is in preparation for either removing or rescheduling an event in the queue. The function should only be called on a variable that is in the queue.

Parameters

var	the variable being searched for.

Definition at line 197 of file ssm-scheduler.c.

Variable Documentation

◆ event_queue

SSM_STATIC ssm_sv_t* event_queue[SSM_EVENT_QUEUE_SIZE+SSM_QUEUE_HEAD]

Event queue, used to track and schedule events between instants.

Managed as a binary heap, sorted by later_time.

Since the first element (SSM_QUEUE_HEAD) is unusued, event_queue[event_queue_len] is the last element in the queue provided event_queue_len is non-zero.

Definition at line 52 of file ssm-scheduler.c.

◆ event_queue_len

SSM_STATIC q_idx_t event_queue_len = 0

The number of elements in event_queue.

Definition at line 55 of file ssm-scheduler.c.

◆ act_queue

SSM_STATIC ssm_act_t* act_queue[SSM_ACT_QUEUE_SIZE+SSM_QUEUE_HEAD]

Activation record queue, for scheduling at each instant.

Managed as a binary heap sorted by priority.

Definition at line 61 of file ssm-scheduler.c.

◆ act_queue_len

SSM_STATIC q_idx_t act_queue_len = 0

the number of elements in act_queue.

Definition at line 64 of file ssm-scheduler.c.

◆ now

SSM_STATIC ssm_time_t now = 0L

The current model time.

Read with ssm_now(); user programs should not manipuate this directly.

This starts out initialized to 0; can be reset by ssm_reset().

ssm_set_now() (and its caller ssm_tick()) advances now monotonically.

Definition at line 74 of file ssm-scheduler.c.

◆ num_processes

size_t num_processes = 0

static

The program terminates when there are no more processes.

Definition at line 265 of file ssm-scheduler.c.

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ SSM_STATIC

◆ SSM_STATIC_INLINE

◆ SSM_EVENT_QUEUE_SIZE

◆ SSM_ACT_QUEUE_SIZE

◆ SSM_QUEUE_HEAD

Typedef Documentation

◆ q_idx_t

Function Documentation

◆ act_queue_percolate_up()

◆ act_queue_percolate_down()

◆ event_queue_percolate_up()

◆ event_queue_percolate_down()

◆ find_queued_event()

Variable Documentation

◆ event_queue

◆ event_queue_len

◆ act_queue

◆ act_queue_len

◆ now

◆ num_processes