Thread Ontology

AI SEARCH

FLOW ALGEBRA — THREAD ONTOLOGY
Semantic Library
Version: 4.0
Canonical Page:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/operating-systems/thread-ontology.html

FLOW THREAD_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Operating Systems"
    ONTOLOGY = "Thread Ontology"
    PURPOSE = "Formalise operating-system threads, execution states, scheduling, processor contexts, shared process resources, synchronisation, communication and lifecycle relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    THREAD
    USER_THREAD
    KERNEL_THREAD
    MAIN_THREAD
    WORKER_THREAD
    HARDWARE_THREAD
    PROCESS
    PROGRAM
    THREAD_IDENTIFIER
    PROCESS_IDENTIFIER
    THREAD_CONTROL_BLOCK
    EXECUTION_CONTEXT
    CPU_CONTEXT
    REGISTER_STATE
    PROGRAM_COUNTER
    STACK_POINTER
    THREAD_STACK
    THREAD_LOCAL_STORAGE
    THREAD_STATE
    NEW_STATE
    READY_STATE
    RUNNING_STATE
    BLOCKED_STATE
    WAITING_STATE
    SLEEPING_STATE
    SUSPENDED_STATE
    TERMINATED_STATE
    SCHEDULER
    SCHEDULING_POLICY
    CPU
    CORE
    TIME_SLICE
    PRIORITY
    AFFINITY
    CONTEXT_SWITCH
    SHARED_ADDRESS_SPACE
    PROCESS_HEAP
    SHARED_FILE_DESCRIPTOR
    RESOURCE
    SHARED_RESOURCE
    LOCK
    MUTEX
    SPINLOCK
    SEMAPHORE
    CONDITION_VARIABLE
    BARRIER
    ATOMIC_OPERATION
    SIGNAL
    EVENT
    MESSAGE
    IPC_CHANNEL
    SYSTEM_CALL
    IO_REQUEST
    RACE_CONDITION
    DATA_RACE
    DEADLOCK
    STARVATION
    CANCELLATION
    JOIN_OPERATION
    DETACH_OPERATION
    EXIT_STATUS
    CONFIGURATION
    OS_VERSION
    KERNEL_VERSION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    BELONGS_TO
    HAS_THREAD
    HAS_MAIN_THREAD
    HAS_CONTROL_BLOCK
    HAS_CONTEXT
    HAS_STACK
    HAS_THREAD_LOCAL_STORAGE
    HAS_STATE
    TRANSITIONS_TO
    EXECUTES
    SCHEDULED_BY
    ASSIGNED_TO
    RUNS_ON
    HAS_PRIORITY
    HAS_AFFINITY
    BLOCKS_ON
    WAITS_FOR
    WAKES_ON
    SLEEPS
    SUSPENDS
    RESUMES
    YIELDS
    TERMINATES
    CANCELS
    JOINS
    DETACHES
    SHARES_ADDRESS_SPACE_WITH
    SHARES_RESOURCE_WITH
    LOCKS
    UNLOCKS
    SYNCHRONISES_WITH
    SIGNALS
    RECEIVES_SIGNAL
    COMMUNICATES_WITH
    INVOKES
    REQUESTS_IO
    HAS_EXIT_STATUS
    HAS_CONFIGURATION
    DEPENDS_ON
    PRECEDES
    FOLLOWS
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    THREAD_TABLES
    THREAD_IDENTIFIERS
    PROCESS_THREAD_DATA
    THREAD_CONTROL_BLOCK_DATA
    THREAD_STATE_TRACES
    SCHEDULER_TRACES
    CPU_ASSIGNMENT_DATA
    AFFINITY_DATA
    CONTEXT_SWITCH_TRACES
    STACK_DATA
    THREAD_LOCAL_STORAGE_DATA
    SYNCHRONISATION_TRACES
    LOCK_TRACES
    SIGNAL_TRACES
    SYSTEM_CALL_TRACES
    IO_TRACES
    JOIN_AND_CANCELLATION_DATA
    SYSTEM_LOGS
    OS_VERSION_DATA
    KERNEL_VERSION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_THREAD_IDENTIFIERS
    NORMALISE_PROCESS_IDENTIFIERS
    NORMALISE_THREAD_STATES
    NORMALISE_PRIORITY_VALUES
    NORMALISE_CPU_AND_CORE_IDENTIFIERS
    NORMALISE_AFFINITY_DATA
    NORMALISE_SYNCHRONISATION_PRIMITIVES
    NORMALISE_SIGNAL_TYPES
    NORMALISE_EXIT_STATUSES
    NORMALISE_OS_AND_KERNEL_VERSIONS
    RESOLVE_THREAD_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS THREAD_LIFECYCLE {
    THREAD_CREATION
      -> NEW_STATE
      -> READY_STATE

    READY_STATE
      -> SCHEDULER_SELECTION

    SCHEDULER_SELECTION
      -> RUNNING_STATE

    RUNNING_STATE
      -> PREEMPT_OR_BLOCK_OR_SLEEP_OR_YIELD_OR_EXIT

    PREEMPT_OR_YIELD
      -> READY_STATE

    BLOCK_OR_SLEEP
      -> BLOCKED_OR_SLEEPING_STATE

    WAKE_EVENT
      -> READY_STATE

    EXIT
      -> TERMINATED_STATE
  }

  PROCESS THREAD_CREATION_REASONING {
    PROCESS_OR_THREAD_CREATOR
      -> THREAD_CREATION_REQUEST

    THREAD_CREATION_REQUEST
      -> THREAD_IDENTIFIER_ALLOCATION

    THREAD_IDENTIFIER_ALLOCATION
      -> STACK_AND_TLS_SETUP

    STACK_AND_TLS_SETUP
      -> EXECUTION_CONTEXT_INITIALISATION

    EXECUTION_CONTEXT_INITIALISATION
      -> INITIAL_THREAD_STATE
  }

  PROCESS SCHEDULING_REASONING {
    RUNNABLE_THREADS
      -> SCHEDULING_POLICY

    SCHEDULING_POLICY
      -> THREAD_SELECTION

    THREAD_SELECTION
      -> CPU_OR_CORE_ASSIGNMENT

    CPU_OR_CORE_ASSIGNMENT
      -> CONTEXT_RESTORE

    CONTEXT_RESTORE
      -> RUNNING_STATE
  }

  PROCESS CONTEXT_SWITCH_REASONING {
    RUNNING_THREAD_A
      -> SAVE_THREAD_CONTEXT

    SAVE_THREAD_CONTEXT
      -> THREAD_A_CONTROL_BLOCK

    SCHEDULER_SELECTION
      -> THREAD_B_CONTROL_BLOCK

    THREAD_B_CONTROL_BLOCK
      -> RESTORE_THREAD_CONTEXT

    RESTORE_THREAD_CONTEXT
      -> RUNNING_THREAD_B
  }

  PROCESS SHARED_RESOURCE_REASONING {
    THREAD_A + THREAD_B + SHARED_RESOURCE
      -> CONCURRENT_ACCESS

    CONCURRENT_ACCESS
      -> READ_WRITE_CONFLICT_CHECK

    CONFLICTING_ACCESS
      -> SYNCHRONISATION_CHECK

    SYNCHRONISED_ACCESS
      -> ORDERED_RESOURCE_USE

    UNSYNCHRONISED_CONFLICT
      -> DATA_RACE_CANDIDATE
  }

  PROCESS SYNCHRONISATION_REASONING {
    THREAD + SYNCHRONISATION_PRIMITIVE
      -> ACQUIRE_OR_WAIT

    ACQUIRE
      -> CRITICAL_SECTION

    CRITICAL_SECTION
      -> RELEASE

    RELEASE
      -> WAKE_OR_SIGNAL_WAITERS
  }

  PROCESS DEADLOCK_REASONING {
    THREADS + LOCK_WAIT_RELATIONS
      -> WAIT_FOR_GRAPH

    WAIT_FOR_GRAPH
      -> CYCLE_DETECTION

    CYCLE
      -> DEADLOCK_CANDIDATE

    DEADLOCK_CANDIDATE
      -> RESOURCE_AND_RUNTIME_STATE_VALIDATION
  }

  PROCESS JOIN_REASONING {
    THREAD_A
      -> JOIN_REQUEST(THREAD_B)

    IF THREAD_B_RUNNING
      -> THREAD_A_WAIT

    THREAD_B_TERMINATES
      -> WAKE_THREAD_A

    WAKE_THREAD_A
      -> JOIN_COMPLETION
  }

  PROCESS TERMINATION_REASONING {
    THREAD_EXIT_OR_CANCELLATION
      -> EXIT_STATUS_OR_TERMINATION_REASON

    TERMINATION_REASON
      -> THREAD_RESOURCE_CLEANUP

    THREAD_RESOURCE_CLEANUP
      -> TERMINATED_STATE

    JOINABLE_THREAD
      -> RETAIN_REQUIRED_TERMINATION_METADATA
  }

  RULES {
    IF THREAD_EXISTS
    THEN REQUIRE {
      THREAD_IDENTIFIER
      PARENT_PROCESS
      THREAD_STATE
      EXECUTION_CONTEXT
    }

    IF THREAD_IS_RUNNING
    THEN LINK THREAD TO CPU_OR_CORE_AND_TIME_CONTEXT

    IF THREAD_BLOCKS
    THEN PRESERVE BLOCKING_RESOURCE_OR_EVENT

    IF THREAD_STATE_CHANGES
    THEN LINK PRIOR_STATE_EVENT_AND_RESULTING_STATE

    IF THREADS_SHARE_PROCESS
    THEN DO_NOT_ASSUME_ALL_RESOURCES_ARE_THREAD_LOCAL

    IF THREADS_ACCESS_SHARED_MUTABLE_DATA
    THEN CHECK_SYNCHRONISATION_AND_ORDERING

    IF WAIT_FOR_GRAPH_HAS_CYCLE
    THEN DO_NOT_ASSERT_DEADLOCK_WITHOUT_RUNTIME_STATE_VALIDATION

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND THREAD_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        THREAD_IDENTITY_CERTAINTY,
        THREAD_STATE_OBSERVABILITY,
        SCHEDULER_TRACE_COMPLETENESS,
        CPU_ASSIGNMENT_COMPLETENESS,
        CONTEXT_SWITCH_TRACE_QUALITY,
        SYNCHRONISATION_TRACE_COMPLETENESS,
        SYSTEM_LOG_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF THREAD_IDENTIFIER_IS_REUSED_ACROSS_TIME
    THEN REQUIRE_TIME_CONTEXT_FOR_IDENTITY

    IF RUNTIME_STATE_IS_PARTIAL
    THEN REDUCE_THREAD_STATE_INFERENCE_CONFIDENCE

    IF COMPLETE_TRACE_CONFIRMS_THREAD_TRANSITION
    THEN INCREASE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        THREAD_IDENTIFIER,
        THREAD_START_TIME,
        PARENT_PROCESS_IDENTITY,
        OS_INSTANCE,
        KERNEL_CONTEXT
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    THREAD != PROCESS
    THREAD != HARDWARE_THREAD
    THREAD_IDENTIFIER != THREAD_IDENTITY_WITHOUT_TIME_CONTEXT
    READY != RUNNING
    BLOCKED != TERMINATED
    THREAD_STACK != PROCESS_HEAP
    THREAD_LOCAL_STORAGE != SHARED_PROCESS_MEMORY
    SHARED_ADDRESS_SPACE != IDENTICAL_EXECUTION_CONTEXT
    CONCURRENT_ACCESS != DATA_RACE
    RESOURCE_CONTENTION != DEADLOCK
    THREAD_EXIT != PROCESS_EXIT_UNLESS_PROCESS_SEMANTICS_REQUIRE_IT
    SCHEDULING_AFFECTS_OBSERVED_EXECUTION
    RUNTIME_STATE_MAY_CHANGE_RAPIDLY
    OS_AND_KERNEL_CONTEXT_AFFECT_THREAD_BEHAVIOUR
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_THREAD_IDENTITY
    CHECK_PARENT_PROCESS
    CHECK_THREAD_STATE
    CHECK_STATE_TRANSITIONS
    CHECK_CPU_ASSIGNMENT
    CHECK_AFFINITY
    CHECK_CONTEXT_SWITCHES
    CHECK_STACK_AND_TLS
    CHECK_SHARED_RESOURCE_RELATIONS
    CHECK_SYNCHRONISATION
    CHECK_DATA_RACE_RELATIONS
    CHECK_DEADLOCK_RELATIONS
    CHECK_JOIN_AND_CANCELLATION
    CHECK_EXIT_STATUS
    CHECK_OS_AND_KERNEL_CONTEXT
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_THREAD_ENTITIES
    PROCESS_THREAD_RELATIONS
    THREAD_STATE_TRANSITIONS
    SCHEDULING_RELATIONS
    CPU_AND_CORE_ASSIGNMENTS
    CONTEXT_SWITCH_RELATIONS
    STACK_AND_TLS_RELATIONS
    SHARED_RESOURCE_RELATIONS
    SYNCHRONISATION_RELATIONS
    DATA_RACE_HYPOTHESES
    DEADLOCK_HYPOTHESES
    JOIN_RELATIONS
    CANCELLATION_RELATIONS
    TERMINATION_RELATIONS
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON THREAD_EVENT {
      NORMALISE
      RESOLVE_THREAD_IDENTITY
      UPDATE_THREAD_STATE
      UPDATE_CPU_ASSIGNMENT
      UPDATE_CONTEXT
      UPDATE_SYNCHRONISATION_RELATIONS
      UPDATE_SHARED_RESOURCE_RELATIONS
      RECOMPUTE_DEPENDENT_INFERENCES
      UPDATE_CONFIDENCE
    }

    ON NEW_RUNTIME_OR_LOG_DATA {
      LINK_EVIDENCE
      UPDATE_THREAD_TRACE
      REASSESS_STATE_TRANSITIONS
      REASSESS_RACE_AND_DEADLOCK_HYPOTHESES
      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_THREAD
      BY_THREAD_IDENTIFIER
      BY_PROCESS
      BY_STATE
      BY_SCHEDULER
      BY_CPU
      BY_CORE
      BY_AFFINITY
      BY_LOCK
      BY_SHARED_RESOURCE
      BY_JOIN
      BY_CANCELLATION
      BY_EXIT_STATUS
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_THREAD_LIFECYCLE
      TRACE_THREAD_CREATION
      TRACE_SCHEDULING
      TRACE_CONTEXT_SWITCHES
      ANALYSE_SHARED_RESOURCE_ACCESS
      ANALYSE_SYNCHRONISATION
      ANALYSE_DATA_RACES
      ANALYSE_DEADLOCKS
      TRACE_JOIN_AND_TERMINATION
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_THREAD_FROM_PROCESS
      DISTINGUISH_SOFTWARE_THREAD_FROM_HARDWARE_THREAD
      PRESERVE_THREAD_IDENTITY_AND_TIME_CONTEXT
      PRESERVE_PROCESS_OS_KERNEL_AND_RUNTIME_CONTEXT
      DISTINGUISH_CONCURRENT_ACCESS_FROM_DATA_RACE
      DISTINGUISH_CONTENTION_FROM_DEADLOCK
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_THREAD_INFERENCE
    }
  }

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

END FLOW