Math.Topology.CubeCmplx.DPTrace

Model directed process traces in a directed cubical framework.

Resource requests

type ResId = Int

Type for resource IDs.

data ReqType

Classical acquire/release notation.

Constructors

P

V

Instances

Eq ReqType

Show ReqType

type ResReq = (ReqType, ResId)

Resource request consists of acquiring/releasing a given resource.

Process Traces

type PID = Int

Type for process IDs.

data PTrace

Process trace is Process ID together with valid list of requests.

Instances

Eq PTrace

Show PTrace

pTrace :: PID -> [ResReq] -> Maybe PTrace

Attempt to build valid process trace from ID and list of requests.

pTraces :: [[ResReq]] -> Maybe [PTrace]

Attempt to build list of process traces with default process IDs from list of lists of requests.

Modeling contention problems

ptsAmbReg :: [PTrace] -> VertSpan

Given a list of process traces, determine a minimal vertex span suitable for modeling a resource contention problem.

ptsForbRegs :: [PTrace] -> [VertSpan]

Given a list of process traces, calculate associated list of forbidden regions which represent resource contention. These regions may overlap to form more complex regions.

ptsCmplx :: [PTrace] -> CubeCmplx

Given a list of process traces, represent the associated resource contention problem by a finite directed cubical complex. The ordering of the coordinates is the same as the ordering of the processes in the list.