Scheduler Ontology

AI SEARCH

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

FLOW SCHEDULER_ONTOLOGY {

  META {
    DOMAIN = "Computing Ontologies"
    SUBDOMAIN = "Operating Systems"
    ONTOLOGY = "Scheduler Ontology"
    PURPOSE = "Formalise operating-system scheduling entities, policies, runnable tasks, priorities, processor allocation, preemption, context switching, fairness and scheduling-performance relationships."
    LOCALE = "en-GB"
  }

  ENTITY_TYPES {
    SCHEDULER
    CPU_SCHEDULER
    PROCESS_SCHEDULER
    THREAD_SCHEDULER
    REAL_TIME_SCHEDULER
    SCHEDULING_POLICY
    FIRST_COME_FIRST_SERVED
    SHORTEST_JOB_FIRST
    SHORTEST_REMAINING_TIME
    ROUND_ROBIN
    PRIORITY_SCHEDULING
    MULTILEVEL_QUEUE
    MULTILEVEL_FEEDBACK_QUEUE
    FAIR_SCHEDULING
    DEADLINE_SCHEDULING
    RATE_MONOTONIC_SCHEDULING
    EARLIEST_DEADLINE_FIRST
    PROCESS
    THREAD
    TASK
    RUNNABLE_TASK
    BLOCKED_TASK
    CPU
    CORE
    PROCESSOR
    RUN_QUEUE
    READY_QUEUE
    PRIORITY
    NICE_VALUE
    DEADLINE
    PERIOD
    EXECUTION_TIME
    REMAINING_TIME
    TIME_SLICE
    QUANTUM
    CPU_BURST
    IO_BURST
    AFFINITY
    CPU_AFFINITY
    LOAD
    LOAD_BALANCE
    MIGRATION
    PREEMPTION
    DISPATCH
    CONTEXT_SWITCH
    WAIT_TIME
    RESPONSE_TIME
    TURNAROUND_TIME
    LATENCY
    THROUGHPUT
    FAIRNESS
    STARVATION
    PRIORITY_INVERSION
    PRIORITY_INHERITANCE
    UTILISATION
    SCHEDULER_STATE
    TASK_STATE
    EVENT
    TIMER_EVENT
    WAKE_EVENT
    BLOCK_EVENT
    CONFIGURATION
    OS_VERSION
    KERNEL_VERSION
    EVIDENCE
    CONFIDENCE_SCORE
    PROVENANCE_RECORD
  }

  RELATIONSHIPS {
    IS_A
    INSTANCE_OF
    PART_OF
    MANAGES
    SCHEDULES
    SELECTS
    DISPATCHES
    ASSIGNS_TO
    RUNS_ON
    PREEMPTS
    MIGRATES
    BALANCES
    ENQUEUES
    DEQUEUES
    BLOCKS
    WAKES
    YIELDS
    HAS_PRIORITY
    HAS_DEADLINE
    HAS_PERIOD
    HAS_TIME_SLICE
    HAS_AFFINITY
    HAS_LOAD
    HAS_STATE
    TRANSITIONS_TO
    HAS_WAIT_TIME
    HAS_RESPONSE_TIME
    HAS_TURNAROUND_TIME
    HAS_LATENCY
    HAS_THROUGHPUT
    HAS_FAIRNESS
    HAS_UTILISATION
    SUFFERS_STARVATION
    SUFFERS_PRIORITY_INVERSION
    INHERITS_PRIORITY
    HAS_CONFIGURATION
    DEPENDS_ON
    PRECEDES
    FOLLOWS
    DERIVED_FROM
    INFERRED_FROM
    HAS_EVIDENCE
    HAS_CONFIDENCE
    HAS_PROVENANCE
    SEMANTICALLY_EQUIVALENT_TO
  }

  INPUTS {
    SCHEDULER_SPECIFICATIONS
    SCHEDULING_POLICY_DATA
    PROCESS_AND_THREAD_DATA
    RUN_QUEUE_DATA
    TASK_STATE_TRACES
    CPU_AND_CORE_DATA
    PRIORITY_DATA
    DEADLINE_DATA
    TIME_SLICE_DATA
    CPU_BURST_DATA
    IO_BURST_DATA
    AFFINITY_DATA
    LOAD_DATA
    MIGRATION_TRACES
    PREEMPTION_TRACES
    CONTEXT_SWITCH_TRACES
    PERFORMANCE_METRICS
    CONFIGURATION_DATA
    OS_VERSION_DATA
    KERNEL_VERSION_DATA
    ONTOLOGY_TERMS
  }

  NORMALISE {
    STANDARDISE_SCHEDULER_IDENTIFIERS
    NORMALISE_POLICY_NAMES
    NORMALISE_TASK_IDENTIFIERS
    NORMALISE_CPU_AND_CORE_IDENTIFIERS
    NORMALISE_PRIORITY_VALUES
    NORMALISE_DEADLINE_UNITS
    NORMALISE_TIME_SLICE_UNITS
    NORMALISE_BURST_TIMES
    NORMALISE_AFFINITY_DATA
    NORMALISE_LOAD_METRICS
    NORMALISE_PERFORMANCE_METRICS
    NORMALISE_OS_AND_KERNEL_VERSIONS
    RESOLVE_TASK_IDENTITIES
    ALIGN_ONTOLOGY_TERMS
    REMOVE_DUPLICATES
    VALIDATE_METADATA
    PRESERVE_PROVENANCE
  }

  PROCESS SCHEDULING_PIPELINE {
    TASK_EVENT
      -> TASK_STATE_UPDATE
      -> RUN_QUEUE_UPDATE
      -> SCHEDULING_DECISION
      -> TASK_SELECTION
      -> CPU_OR_CORE_ASSIGNMENT
      -> DISPATCH
      -> EXECUTION
      -> PREEMPT_BLOCK_YIELD_OR_COMPLETE
      -> RESCHEDULE_IF_REQUIRED
  }

  PROCESS RUN_QUEUE_REASONING {
    RUNNABLE_TASK
      -> POLICY_SPECIFIC_QUEUE_POSITION

    POLICY_SPECIFIC_QUEUE_POSITION
      -> RUN_QUEUE

    TASK_BLOCK_OR_EXECUTION
      -> DEQUEUE

    TASK_WAKE_OR_CREATION
      -> ENQUEUE
  }

  PROCESS PRIORITY_REASONING {
    RUNNABLE_TASKS
      -> PRIORITY_COMPARISON

    PRIORITY_COMPARISON
      -> HIGHEST_EFFECTIVE_PRIORITY

    HIGHEST_EFFECTIVE_PRIORITY
      -> TASK_SELECTION

    EQUAL_PRIORITY
      -> POLICY_SPECIFIC_TIE_BREAKING
  }

  PROCESS ROUND_ROBIN_REASONING {
    READY_QUEUE
      -> HEAD_TASK

    HEAD_TASK
      -> DISPATCH

    DISPATCH
      -> EXECUTE_FOR_QUANTUM_OR_UNTIL_BLOCK_OR_EXIT

    QUANTUM_EXPIRES
      -> PREEMPT
      -> REQUEUE
  }

  PROCESS PREEMPTION_REASONING {
    RUNNING_TASK + SCHEDULING_EVENT
      -> PREEMPTION_CONDITION_CHECK

    HIGHER_PRIORITY_OR_POLICY_TRIGGER
      -> SAVE_CONTEXT

    SAVE_CONTEXT
      -> RUNNING_TASK_TO_READY

    SELECTED_TASK
      -> RESTORE_CONTEXT
      -> RUNNING
  }

  PROCESS MULTICORE_REASONING {
    RUNNABLE_TASKS + MULTIPLE_CORES
      -> PER_CORE_OR_GLOBAL_RUN_QUEUE

    LOAD_STATE
      -> LOAD_BALANCE_CHECK

    IMBALANCE
      -> MIGRATION_CANDIDATE_SELECTION

    MIGRATION_CANDIDATE_SELECTION
      -> AFFINITY_AND_COST_CHECK

    VALID_MIGRATION
      -> TARGET_CORE_ASSIGNMENT
  }

  PROCESS REAL_TIME_REASONING {
    REAL_TIME_TASK
      -> DEADLINE_AND_PERIOD_CONTEXT

    DEADLINE_AND_PERIOD_CONTEXT
      -> SCHEDULABILITY_ANALYSIS

    SCHEDULABILITY_ANALYSIS
      -> POLICY_SPECIFIC_PRIORITY_OR_DEADLINE_ORDER

    EXECUTION
      -> DEADLINE_CHECK

    COMPLETION_AFTER_DEADLINE
      -> DEADLINE_MISS
  }

  PROCESS PRIORITY_INVERSION_REASONING {
    HIGH_PRIORITY_TASK
      -> WAITS_FOR_RESOURCE

    RESOURCE_HELD_BY_LOWER_PRIORITY_TASK
      -> PRIORITY_INVERSION_CANDIDATE

    MEDIUM_PRIORITY_INTERFERENCE
      -> INVERSION_SEVERITY

    PRIORITY_INHERITANCE_IF_SUPPORTED
      -> TEMPORARY_PRIORITY_ADJUSTMENT
  }

  PROCESS PERFORMANCE_REASONING {
    SCHEDULER + WORKLOAD + CONFIGURATION
      -> SCHEDULING_PROFILE

    SCHEDULING_PROFILE
      -> WAIT_TIME
      -> RESPONSE_TIME
      -> TURNAROUND_TIME
      -> CONTEXT_SWITCH_OVERHEAD
      -> CPU_UTILISATION
      -> THROUGHPUT
      -> FAIRNESS
      -> MIGRATION_OVERHEAD

    SCHEDULING_PROFILE
      -> BOTTLENECK_OR_STARVATION_HYPOTHESIS
  }

  RULES {
    IF TASK_IS_RUNNING
    THEN LINK TASK TO CPU_OR_CORE_AND_TIME_CONTEXT

    IF TASK_IS_RUNNABLE
    THEN DO_NOT_ASSERT_RUNNING_STATE_WITHOUT_DISPATCH

    IF PREEMPTION_OCCURS
    THEN PRESERVE PREEMPTION_CAUSE_AND_CONTEXT_SWITCH

    IF TASK_HAS_AFFINITY
    THEN CHECK_AFFINITY_BEFORE_CPU_ASSIGNMENT_OR_MIGRATION

    IF HIGH_PRIORITY_TASK_WAITS_FOR_LOWER_PRIORITY_RESOURCE_HOLDER
    THEN CHECK_PRIORITY_INVERSION_CONTEXT

    IF TASK_WAITS_FOR_LONG_PERIOD
    THEN DO_NOT_ASSERT_STARVATION_WITHOUT_POLICY_AND_WORKLOAD_CONTEXT

    IF SCHEDULING_PERFORMANCE_IS_COMPARED
    THEN REQUIRE POLICY_WORKLOAD_HARDWARE_AND_CONFIGURATION_CONTEXT

    IF SEMANTIC_IDENTIFIERS_DIFFER
    AND SCHEDULER_REFERENT_IS_SAME
    THEN APPLY SEMANTIC_EQUIVALENCE
  }

  CONFIDENCE {
    CONFIDENCE_SCORE =
      WEIGHT(
        POLICY_CERTAINTY,
        TASK_IDENTITY_CERTAINTY,
        RUN_QUEUE_OBSERVABILITY,
        SCHEDULER_TRACE_COMPLETENESS,
        CPU_ASSIGNMENT_COMPLETENESS,
        PRIORITY_AND_AFFINITY_CONTEXT,
        PERFORMANCE_MEASUREMENT_QUALITY,
        PROVENANCE_COMPLETENESS
      )

    LEVELS {
      HIGH
      MODERATE
      LOW
      INSUFFICIENT
    }

    IF RUN_QUEUE_STATE_IS_PARTIAL
    THEN REDUCE_SCHEDULING_DECISION_INFERENCE_CONFIDENCE

    IF POLICY_OR_CONFIGURATION_IS_UNKNOWN
    THEN REDUCE_SCHEDULER_BEHAVIOUR_CONFIDENCE

    IF COMPLETE_TRACE_CONFIRMS_SCHEDULING_DECISION
    THEN INCREASE CONFIDENCE_SCORE
  }

  SEMANTIC_EQUIVALENCE {
    EQUIVALENCE_KEY =
      NORMALISE(
        ENTITY_TYPE,
        SCHEDULER_IDENTIFIER,
        POLICY,
        OS_VERSION,
        KERNEL_VERSION,
        CONFIGURATION
      )

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

    ELSE PRESERVE_DISTINCT_ENTITIES
  }

  REASONING_CONSTRAINTS {
    RUNNABLE != RUNNING
    PRIORITY != GUARANTEED_EXECUTION_ORDER_WITHOUT_POLICY_CONTEXT
    HIGH_PRIORITY != GUARANTEED_ZERO_WAIT
    TIME_SLICE != TOTAL_EXECUTION_TIME
    PREEMPTION != TERMINATION
    MIGRATION != CONTEXT_SWITCH_IN_ALL_CONTEXTS
    LOAD_BALANCE != EQUAL_TASK_COUNT
    FAIRNESS != EQUAL_CPU_TIME_IN_ALL_POLICIES
    LONG_WAIT != NECESSARILY_STARVATION
    PRIORITY_INVERSION != DEADLOCK
    DEADLINE != PRIORITY_IN_ALL_POLICIES
    SCHEDULING_PERFORMANCE_IS_WORKLOAD_DEPENDENT
    HARDWARE_TOPOLOGY_AFFECTS_MULTICORE_SCHEDULING
    OS_KERNEL_AND_CONFIGURATION_AFFECT_SCHEDULER_BEHAVIOUR
    PROVENANCE_MUST_BE_PRESERVED
    UNCERTAINTY_MUST_NOT_BE_DISCARDED
  }

  VALIDATION {
    CHECK_ENTITY_TYPES
    CHECK_RELATION_DOMAINS_AND_RANGES
    CHECK_SCHEDULER_IDENTIFIER
    CHECK_SCHEDULING_POLICY
    CHECK_TASK_IDENTITIES
    CHECK_TASK_STATES
    CHECK_RUN_QUEUE_STATE
    CHECK_PRIORITY
    CHECK_DEADLINE_AND_PERIOD
    CHECK_TIME_SLICE
    CHECK_CPU_ASSIGNMENT
    CHECK_AFFINITY
    CHECK_PREEMPTION
    CHECK_MIGRATION
    CHECK_LOAD_BALANCING
    CHECK_PRIORITY_INVERSION
    CHECK_PERFORMANCE_CONTEXT
    CHECK_OS_AND_KERNEL_CONTEXT
    CHECK_CONFIGURATION
    CHECK_PROVENANCE
    CHECK_CONFIDENCE
    CHECK_SEMANTIC_CONSISTENCY
  }

  OUTPUTS {
    NORMALISED_SCHEDULER_ENTITIES
    SCHEDULING_POLICY_RELATIONS
    RUN_QUEUE_RELATIONS
    TASK_SELECTION_RELATIONS
    CPU_AND_CORE_ASSIGNMENTS
    PREEMPTION_RELATIONS
    CONTEXT_SWITCH_RELATIONS
    AFFINITY_RELATIONS
    MIGRATION_RELATIONS
    LOAD_BALANCING_RELATIONS
    REAL_TIME_SCHEDULING_RELATIONS
    PRIORITY_INVERSION_RELATIONS
    STARVATION_HYPOTHESES
    SCHEDULING_PERFORMANCE_PROFILES
    CONFIDENCE_SCORES
    EVIDENCE_LINKS
    PROVENANCE_RECORDS
    EXPLANATION_PATHS
  }

  UPDATE_MODEL {
    ON SCHEDULER_EVENT {
      NORMALISE
      RESOLVE_TASK_IDENTITIES
      UPDATE_TASK_STATES
      UPDATE_RUN_QUEUES
      UPDATE_CPU_ASSIGNMENTS
      UPDATE_AFFINITY_AND_LOAD
      RECOMPUTE_SCHEDULING_RELATIONS
      UPDATE_CONFIDENCE
    }

    ON NEW_TRACE_OR_PERFORMANCE_DATA {
      LINK_EVIDENCE
      UPDATE_SCHEDULING_TRACE
      UPDATE_PERFORMANCE_PROFILE
      REASSESS_STARVATION_AND_PRIORITY_INVERSION
      REASSESS_LOAD_BALANCE
      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_SCHEDULER
      BY_POLICY
      BY_TASK
      BY_RUN_QUEUE
      BY_PRIORITY
      BY_DEADLINE
      BY_CPU
      BY_CORE
      BY_AFFINITY
      BY_PREEMPTION
      BY_MIGRATION
      BY_STARVATION
      BY_PRIORITY_INVERSION
      BY_PERFORMANCE
      BY_CONFIDENCE
    }

    REASON {
      APPLY_RELATIONSHIPS
      APPLY_RULES
      TRACE_SCHEDULING_PIPELINE
      TRACE_RUN_QUEUE_STATE
      ANALYSE_PRIORITY_SCHEDULING
      ANALYSE_ROUND_ROBIN
      ANALYSE_PREEMPTION
      ANALYSE_MULTICORE_SCHEDULING
      ANALYSE_REAL_TIME_SCHEDULING
      ANALYSE_PRIORITY_INVERSION
      ANALYSE_SCHEDULER_PERFORMANCE
      CHECK_SEMANTIC_EQUIVALENCE
      PRESERVE_UNCERTAINTY
      TRACE_EVIDENCE
      TRACE_PROVENANCE
      GENERATE_EXPLANATION_PATH
    }

    RESPONSE_POLICY {
      DISTINGUISH_RUNNABLE_FROM_RUNNING
      PRESERVE_POLICY_PRIORITY_AFFINITY_AND_TIME_CONTEXT
      DISTINGUISH_PREEMPTION_FROM_TERMINATION
      DISTINGUISH_PRIORITY_INVERSION_FROM_DEADLOCK
      PRESERVE_WORKLOAD_HARDWARE_OS_AND_KERNEL_CONTEXT
      RETURN_CONFIDENCE_WHEN_AVAILABLE
      RETURN_PROVENANCE_WHEN_AVAILABLE
      AVOID_UNSUPPORTED_SCHEDULER_INFERENCE
    }
  }

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

END FLOW