Concurrent Programming Ontology

AI SEARCH

FLOW ALGEBRA — CONCURRENT PROGRAMMING ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/programming/concurrent-programming-ontology.html

FLOW CONCURRENT_PROGRAMMING_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Programming"
    ONTOLOGY = "Concurrent Programming Ontology"
    PURPOSE = "Formalise concurrent programming concepts including processes, threads, tasks, shared state, message passing, synchronisation, ordering, races, deadlocks, scheduling and concurrent execution relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    CONCURRENT_PROGRAMMING
    CONCURRENCY
    PARALLELISM
    PROGRAM
    PROCESS
    THREAD
    TASK
    FIBER
    COROUTINE
    ACTOR
    WORKER
    EXECUTOR
    SCHEDULER
    EVENT_LOOP
    FUTURE
    PROMISE
    ASYNC_OPERATION
    AWAIT_OPERATION
    SHARED_STATE
    SHARED_MEMORY
    LOCAL_STATE
    IMMUTABLE_STATE
    MUTABLE_STATE
    RESOURCE
    SHARED_RESOURCE
    CRITICAL_SECTION
    SYNCHRONISATION
    LOCK
    MUTEX
    SPINLOCK
    READ_WRITE_LOCK
    SEMAPHORE
    BARRIER
    CONDITION_VARIABLE
    MONITOR
    ATOMIC_OPERATION
    ATOMIC_VARIABLE
    MEMORY_ORDER
    MEMORY_MODEL
    HAPPENS_BEFORE
    MESSAGE
    MESSAGE_QUEUE
    CHANNEL
    MAILBOX
    PIPE
    SOCKET
    MESSAGE_PASSING
    SEND_OPERATION
    RECEIVE_OPERATION
    EVENT
    SIGNAL
    WAIT
    WAKE
    BLOCKING_OPERATION
    NONBLOCKING_OPERATION
    DATA_RACE
    RACE_CONDITION
    DEADLOCK
    LIVELOCK
    STARVATION
    CONTENTION
    PRIORITY_INVERSION
    FAIRNESS
    INTERLEAVING
    EXECUTION_TRACE
    SCHEDULE
    STATE
    STATE_TRANSITION
    LINEARISATION_POINT
    CONSISTENCY_MODEL
    LANGUAGE_VERSION
    RUNTIME
    CONFIGURATION
    ERROR
    FAILURE
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    CONTAINS
    CREATES
    SPAWNS
    EXECUTES
    SCHEDULES
    INTERLEAVES_WITH
    RUNS_IN_PARALLEL_WITH
    SHARES
    READS
    WRITES
    MODIFIES
    LOCKS
    UNLOCKS
    WAITS_FOR
    WAKES
    SIGNALS
    SYNCHRONISES_WITH
    SENDS
    RECEIVES
    ENQUEUES
    DEQUEUES
    PRECEDES
    FOLLOWS
    HAPPENS_BEFORE_REL
    CONFLICTS_WITH
    CONTENDS_FOR
    BLOCKS_ON
    COMPLETES
    RESOLVES
    AWAITS
    HAS_STATE
    TRANSITIONS_TO
    HAS_MEMORY_ORDER
    HAS_MEMORY_MODEL
    HAS_SCHEDULE
    HAS_CONFIGURATION
    HAS_LANGUAGE_VERSION
    DEPENDS_ON
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    SOURCE_CODE
    LANGUAGE_SPECIFICATIONS
    LANGUAGE_VERSION_DATA
    PROCESS_AND_THREAD_DATA
    TASK_DATA
    SCHEDULER_TRACES
    EXECUTION_TRACES
    SHARED_MEMORY_TRACES
    READ_WRITE_TRACES
    LOCK_TRACES
    SYNCHRONISATION_TRACES
    MESSAGE_TRACES
    CHANNEL_DATA
    ATOMIC_OPERATION_DATA
    MEMORY_MODEL_DATA
    MEMORY_ORDER_DATA
    ASYNC_AWAIT_TRACES
    DEADLOCK_DATA
    RACE_DETECTION_DATA
    PERFORMANCE_METRICS
    RUNTIME_DATA
    CONFIGURATION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_CONCURRENT_ENTITY_IDENTIFIERS
    NORMALISE_LANGUAGE_NAMES
    NORMALISE_LANGUAGE_VERSIONS
    NORMALISE_PROCESS_THREAD_AND_TASK_IDENTIFIERS
    NORMALISE_SYNCHRONISATION_PRIMITIVES
    NORMALISE_MEMORY_ORDER_TERMS
    NORMALISE_MEMORY_MODEL_TERMS
    NORMALISE_MESSAGE_AND_CHANNEL_IDENTIFIERS
    NORMALISE_EVENT_TYPES
    NORMALISE_SCHEDULER_IDENTIFIERS
    NORMALISE_EXECUTION_TIMESTAMPS
    RESOLVE_CONCURRENT_ENTITY_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS CONCURRENCY_REASONING_PIPELINE {
    SOURCE_OR_RUNTIME_DATA
      -> CONCURRENT_ENTITY_RESOLUTION
      -> EXECUTION_CONTEXT_MAPPING
      -> SHARED_STATE_MAPPING
      -> SYNCHRONISATION_MAPPING
      -> MESSAGE_PASSING_MAPPING
      -> ORDERING_AND_MEMORY_MODEL_MAPPING
      -> RACE_AND_DEADLOCK_ANALYSIS
      -> VALIDATION
      -> OUTPUT
  }

  PROCESS CONCURRENT_EXECUTION_REASONING {
    CONCURRENT_ENTITIES
      -> SCHEDULER_OR_RUNTIME

    SCHEDULER_OR_RUNTIME
      -> EXECUTION_SCHEDULE

    EXECUTION_SCHEDULE
      -> INTERLEAVED_OR_PARALLEL_STEPS

    EXECUTION_STEPS
      -> STATE_TRANSITIONS

    STATE_TRANSITIONS
      -> EXECUTION_TRACE
  }

  PROCESS SHARED_MEMORY_REASONING {
    TASK_A + TASK_B + SHARED_LOCATION
      -> MEMORY_ACCESS_SET

    MEMORY_ACCESS_SET
      -> READ_WRITE_CONFLICT_ANALYSIS

    CONFLICTING_ACCESSES
      -> ORDERING_AND_SYNCHRONISATION_CHECK

    ORDERED_OR_SYNCHRONISED
      -> CONTROLLED_SHARED_ACCESS

    UNORDERED_CONFLICT
      -> DATA_RACE_CANDIDATE
  }

  PROCESS SYNCHRONISATION_REASONING {
    TASK + SYNCHRONISATION_PRIMITIVE
      -> ACQUIRE_WAIT_OR_SIGNAL

    ACQUIRE
      -> CRITICAL_SECTION_ENTRY

    CRITICAL_SECTION
      -> PROTECTED_RESOURCE_ACCESS

    RELEASE
      -> CRITICAL_SECTION_EXIT

    RELEASE_OR_SIGNAL
      -> WAKE_ELIGIBLE_WAITERS
  }

  PROCESS MESSAGE_PASSING_REASONING {
    SENDER
      -> MESSAGE_CREATION

    MESSAGE_CREATION
      -> SEND_OPERATION

    SEND_OPERATION
      -> CHANNEL_OR_MAILBOX

    CHANNEL_OR_MAILBOX
      -> RECEIVE_OPERATION

    RECEIVE_OPERATION
      -> RECEIVER_STATE_UPDATE
  }

  PROCESS ASYNC_REASONING {
    ASYNC_OPERATION
      -> FUTURE_OR_PROMISE

    FUTURE_OR_PROMISE
      -> PENDING_STATE

    OPERATION_COMPLETION
      -> RESOLVED_OR_REJECTED_STATE

    AWAIT_OPERATION
      -> SUSPEND_OR_REGISTER_CONTINUATION

    RESOLUTION
      -> RESUME_CONTINUATION
  }

  PROCESS HAPPENS_BEFORE_REASONING {
    PROGRAM_ORDER
      -> ORDERING_EDGE

    SYNCHRONISATION_EVENT
      -> SYNCHRONISATION_EDGE

    MESSAGE_SEND_RECEIVE
      -> COMMUNICATION_ORDER_EDGE

    ORDERING_EDGES
      -> TRANSITIVE_HAPPENS_BEFORE_RELATION

    HAPPENS_BEFORE_RELATION
      -> VISIBILITY_AND_RACE_ANALYSIS
  }

  PROCESS DATA_RACE_REASONING {
    ACCESS_A + ACCESS_B
      -> SAME_MEMORY_LOCATION_CHECK

    SAME_LOCATION
      + AT_LEAST_ONE_WRITE
      + CONCURRENT_OR_UNORDERED
      -> CONFLICTING_ACCESS_PAIR

    CONFLICTING_ACCESS_PAIR
      -> HAPPENS_BEFORE_AND_SYNCHRONISATION_CHECK

    NO_ORDERING_OR_SYNCHRONISATION
      -> DATA_RACE
  }

  PROCESS DEADLOCK_REASONING {
    TASKS + RESOURCE_WAIT_RELATIONS
      -> WAIT_FOR_GRAPH

    WAIT_FOR_GRAPH
      -> CYCLE_DETECTION

    CYCLE
      -> DEADLOCK_CANDIDATE

    DEADLOCK_CANDIDATE
      -> RESOURCE_AND_RUNTIME_STATE_VALIDATION
  }

  PROCESS LIVENESS_REASONING {
    EXECUTION_TRACE
      -> PROGRESS_ANALYSIS

    REPEATED_STATE_CHANGES_WITHOUT_PROGRESS
      -> LIVELOCK_CANDIDATE

    RUNNABLE_TASK_WITH_PERSISTENT_DENIAL
      -> STARVATION_CANDIDATE

    RESOURCE_CONTENTION
      -> FAIRNESS_ANALYSIS
  }

  RULES {
    IF TWO_TASKS_ACCESS_SAME_MUTABLE_LOCATION
    AND AT_LEAST_ONE_ACCESS_IS_WRITE
    THEN CHECK_ORDERING_AND_SYNCHRONISATION

    IF DATA_RACE_IS_ASSERTED
    THEN REQUIRE CONFLICTING_UNORDERED_ACCESSES

    IF WAIT_FOR_GRAPH_HAS_CYCLE
    THEN DO_NOT_ASSERT DEADLOCK_WITHOUT_RUNTIME_RESOURCE_VALIDATION

    IF TASKS_EXECUTE_CONCURRENTLY
    THEN DO_NOT_AUTOMATICALLY_ASSERT PHYSICAL_PARALLELISM

    IF TASKS_EXECUTE_IN_PARALLEL
    THEN CONCURRENCY_CONTEXT_IS_PRESENT

    IF MESSAGE_IS_SENT
    THEN PRESERVE SENDER_CHANNEL_MESSAGE_AND_RECEIVER_CONTEXT

    IF ATOMIC_OPERATION_IS_ASSERTED
    THEN PRESERVE MEMORY_ORDER_AND_LANGUAGE_RUNTIME_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND CONCURRENT_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        ENTITY_IDENTITY_CERTAINTY,
        EXECUTION_TRACE_COMPLETENESS,
        MEMORY_ACCESS_TRACE_COMPLETENESS,
        SYNCHRONISATION_TRACE_COMPLETENESS,
        MESSAGE_TRACE_COMPLETENESS,
        MEMORY_MODEL_CERTAINTY,
        SCHEDULER_CONTEXT_CERTAINTY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF EXECUTION_ORDER_IS_PARTIAL
    THEN REDUCE_RACE_AND_ORDERING_CONFIDENCE

    IF MEMORY_MODEL_IS_UNKNOWN
    THEN REDUCE_VISIBILITY_AND_ATOMICITY_INFERENCE_CONFIDENCE

    IF COMPLETE_REPRODUCIBLE_TRACE_CONFIRMS_BEHAVIOUR
    THEN INCREASE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        CANONICAL_IDENTIFIER,
        PROGRAM_OR_RUNTIME_INSTANCE,
        LANGUAGE_VERSION,
        THREAD_TASK_OR_RESOURCE_CONTEXT,
        EXECUTION_INTERVAL
      )

    IF EQUIVALENCE_KEY(A) == EQUIVALENCE_KEY(B)
    THEN A SEMANTICALLY_EQUIVALENT_TO B

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    CONCURRENCY != PARALLELISM
    PROCESS != THREAD
    THREAD != TASK_IN_ALL_RUNTIME_MODELS
    ASYNC != PARALLEL
    NONBLOCKING != ASYNCHRONOUS_IN_ALL_CONTEXTS
    RACE_CONDITION != DATA_RACE
    CONCURRENT_ACCESS != DATA_RACE
    CONTENTION != DEADLOCK
    DEADLOCK != LIVELOCK
    LIVELOCK != STARVATION
    ATOMICITY != MUTUAL_EXCLUSION
    MEMORY_ORDER != EXECUTION_TIME_ORDER_IN_ALL_MODELS
    HAPPENS_BEFORE != WALL_CLOCK_ORDER
    MESSAGE_SEND != MESSAGE_RECEIVE
    LOCK_ACQUISITION != GUARANTEED_FAIRNESS
    EXECUTION_SCHEDULE_MAY_BE_NONDETERMINISTIC
    LANGUAGE_RUNTIME_AND_MEMORY_MODEL_AFFECT_CONCURRENT_SEMANTICS
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_LANGUAGE_AND_VERSION
    CHECK_CONCURRENT_ENTITY_IDENTITIES
    CHECK_EXECUTION_SCHEDULE
    CHECK_SHARED_MEMORY_ACCESSES
    CHECK_SYNCHRONISATION_RELATIONS
    CHECK_MESSAGE_RELATIONS
    CHECK_ASYNC_AND_FUTURE_RELATIONS
    CHECK_MEMORY_MODEL
    CHECK_MEMORY_ORDER
    CHECK_HAPPENS_BEFORE_RELATIONS
    CHECK_DATA_RACE_RELATIONS
    CHECK_DEADLOCK_RELATIONS
    CHECK_LIVELOCK_AND_STARVATION
    CHECK_RUNTIME_CONTEXT
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_CONCURRENT_PROGRAMMING_ENTITIES
    PROCESS_THREAD_AND_TASK_RELATIONS
    EXECUTION_SCHEDULE_RELATIONS
    SHARED_MEMORY_RELATIONS
    SYNCHRONISATION_RELATIONS
    MESSAGE_PASSING_RELATIONS
    ASYNC_FUTURE_AND_PROMISE_RELATIONS
    MEMORY_ORDER_RELATIONS
    HAPPENS_BEFORE_RELATIONS
    DATA_RACE_RELATIONS
    RACE_CONDITION_HYPOTHESES
    DEADLOCK_HYPOTHESES
    LIVELOCK_HYPOTHESES
    STARVATION_HYPOTHESES
    FAIRNESS_RELATIONS
    EXECUTION_TRACES
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON CONCURRENT_EXECUTION_EVENT {
      NORMALISE
      RESOLVE_CONCURRENT_ENTITIES
      UPDATE_EXECUTION_SCHEDULE
      UPDATE_SHARED_MEMORY_RELATIONS
      UPDATE_SYNCHRONISATION_RELATIONS
      UPDATE_MESSAGE_RELATIONS
      UPDATE_HAPPENS_BEFORE_GRAPH
      RECOMPUTE_RACE_AND_LIVENESS_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON NEW_RUNTIME_OR_TRACE_DATA {
      LINK_EVIDENCE
      UPDATE_EXECUTION_TRACE
      UPDATE_MEMORY_ACCESS_GRAPH
      REASSESS_DATA_RACES
      REASSESS_DEADLOCK_LIVELOCK_AND_STARVATION
      UPDATE_CONFIDENCE
      RECORD_PROVENANCE
    }

    ON ONTOLOGY_REVISION {
      REMAP_TERMS
      CHECK_SEMANTIC_EQUIVALENCE
      IDENTIFY_DEPRECATED_TERMS
      MIGRATE_RELATIONSHIPS
      PRESERVE_PRIOR_VERSION_REFERENCES
    }
  }

  FLOW_HASH {
    HASH_INPUT =
      CANONICALISE(
        ENTITY_TYPES,
        RELATIONSHIPS,
        RULES,
        CONFIDENCE,
        SEMANTIC_EQUIVALENCE,
        REASONING_CONSTRAINTS,
        UPDATE_MODEL
      )

    FLOW_HASH = SHA256(HASH_INPUT)
  }

  AI_CONSUMPTION {
    INDEX {
      ONTOLOGY
      ENTITY_TYPES
      RELATIONSHIPS
      RULES
      OUTPUTS
    }

    RETRIEVE {
      BY_PROCESS
      BY_THREAD
      BY_TASK
      BY_SHARED_RESOURCE
      BY_LOCK
      BY_ATOMIC_OPERATION
      BY_MESSAGE
      BY_CHANNEL
      BY_FUTURE
      BY_MEMORY_ORDER
      BY_DATA_RACE
      BY_DEADLOCK
      BY_LIVELOCK
      BY_STARVATION
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_CONCURRENT_EXECUTION
      ANALYSE_SHARED_MEMORY
      ANALYSE_SYNCHRONISATION
      TRACE_MESSAGE_PASSING
      ANALYSE_ASYNC_OPERATIONS
      BUILD_HAPPENS_BEFORE_GRAPH
      ANALYSE_DATA_RACES
      ANALYSE_DEADLOCKS
      ANALYSE_LIVENESS_AND_FAIRNESS
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_CONCURRENCY_FROM_PARALLELISM
      DISTINGUISH_RACE_CONDITION_FROM_DATA_RACE
      DISTINGUISH_CONTENTION_DEADLOCK_LIVELOCK_AND_STARVATION
      PRESERVE_LANGUAGE_RUNTIME_MEMORY_MODEL_SCHEDULE_AND_TIME_CONTEXT
      DISTINGUISH_HAPPENS_BEFORE_FROM_WALL_CLOCK_ORDER
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_CONCURRENT_PROGRAMMING_INFERENCE
    }
  }

  TERMINAL {
    RESULT =
      VALIDATED(
        SEMANTICALLY_NORMALISED(
          EVIDENCE_LINKED(
            CONFIDENCE_AWARE(
              CONCURRENT_PROGRAMMING_KNOWLEDGE
            )
          )
        )
      )
  }
}

END FLOW