RTOS Scheduling Simulator

// RTOS core model: TCB, ready queue, PI inheritance, RMS/EDF
type TaskDef = {
  id:number; name:string;
  T:number; C:number; D:number;       // period, WCET, deadline ms
  basePrio:number;                     // RMS: 1/T, manual: 1..99 mapped
  mutex:string|null;
  csStart:number; // fraction 0..1 where lock attempted
  csDur:number;   // fraction held
  color:string;
};
type Job = {
  jobId:number; taskId:number;
  release:number; absDeadline:number;
  executed:number; remaining:number;
  state:'Ready'|'Running'|'Blocked'|'Done';
  blockedOn:string|null;
  holds:Set<string>;
  basePrio:number; effPrio:number;
  effDeadline:number;
  blockedTime:number;
  firstStart:number|null;
  completion:number|null;
  missed:boolean;
};

function basePriority(t:TaskDef, mode:'RMS'|'EDF'){
  if(t.basePrio>=100) return t.basePrio; // manual mapped 100..9900
  return mode==='RMS' ? (1_000_000 / t.T) : (1_000_000 / t.T); // rate monotonic base
}

function simulate(tasks:TaskDef[], horizon:number, mode:'RMS'|'EDF', isrPeriod:number, isrC:number){
  const mutexState = new Map<string,{holder:Job|null, queue:Job[]}>();
  let jobs:Job[]=[]; let jid=0;
  const log:number[] = new Array(horizon).fill(-1);
  const perTask: Record<number, Job['state'][]> = {};
  tasks.forEach(t=> perTask[t.id]= new Array(horizon).fill('Idle' as any));
  perTask[-1] = new Array(horizon).fill('Idle' as any); // the ISR's own row
  const events:{t:number, waiter:number, holder:number, mutex:string}[]=[];
  let totalMiss=0;

  for(let t=0; t<horizon; t++){
    // releases
    tasks.forEach(td=>{
      if(t % td.T===0){
        const j:Job={
          jobId:jid++, taskId:td.id, release:t, absDeadline:t+td.D,
          executed:0, remaining:td.C, state:'Ready',
          blockedOn:null, holds:new Set(), basePrio:basePriority(td,mode),
          effPrio:basePriority(td,mode), effDeadline:t+td.D,
          blockedTime:0, firstStart:null, completion:null, missed:false
        };
        jobs.push(j);
      }
    });
    if(isrPeriod>0 && t % isrPeriod===0){
      const ij:Job={
        jobId:jid++, taskId:-1, release:t, absDeadline:t+isrPeriod,
        executed:0, remaining:isrC, state:'Ready', blockedOn:null,
        holds:new Set(), basePrio:1e9, effPrio:1e9, effDeadline:t+isrPeriod,
        blockedTime:0, firstStart:null, completion:null, missed:false
      };
      jobs.push(ij);
    }

    // active jobs
    const active = jobs.filter(j=> j.release<=t && j.remaining>0);

    // try unblock / release expired CS
    active.forEach(j=>{
      if(j.taskId===-1) return;
      const td = tasks.find(x=>x.id===j.taskId);
      if(!td || !td.mutex) return;
      const m = td.mutex;
      // release check
      if(j.holds.has(m)){
        const endFrac = td.csStart+td.csDur;
        if(j.executed >= endFrac*td.C){
          j.holds.delete(m);
          const st = mutexState.get(m);
          if(st) st.holder=null;
        }
      }
    });

    // blocked jobs attempting acquisition after release
    active.filter(j=> j.state==='Blocked' && j.blockedOn).forEach(j=>{
      const st = mutexState.get(j.blockedOn!);
      if(st && !st.holder){
        // arbitration: highest effPrio waiter gets lock
        const candidates = st.queue.slice().sort((a,b)=> b.effPrio-a.effPrio);
        if(candidates[0]===j){
          st.holder=j; j.holds.add(j.blockedOn!); j.blockedOn=null; j.state='Ready';
          st.queue = st.queue.filter(x=>x!==j);
        }
      }
    });

    // new lock attempts
    active.filter(j=> j.state!=='Blocked' && j.remaining>0 && !j.blockedOn).forEach(j=>{
      if(j.taskId===-1) return;
      const td = tasks.find(x=>x.id===j.taskId);
      if(!td?.mutex) return;
      if(j.holds.has(td.mutex)) return;
      if(j.executed < td.csStart*td.C) return;
      if(j.executed >= (td.csStart+td.csDur)*td.C) return;
      let st = mutexState.get(td.mutex);
      if(!st){ st={holder:null, queue:[]}; mutexState.set(td.mutex,st); }
      if(!st.holder){
        st.holder=j; j.holds.add(td.mutex);
      }else if(st.holder!==j){
        if(!st.queue.includes(j)) st.queue.push(j);
        j.state='Blocked'; j.blockedOn=td.mutex;
        events.push({t, waiter:j.taskId, holder:st.holder.taskId, mutex:td.mutex});
      }
    });

    // priority / deadline inheritance fixpoint
    let changed=true;
    for(let iter=0; iter<10 && changed; iter++){
      changed=false;
      for(const [mname, st] of mutexState){
        if(!st.holder || st.queue.length===0) continue;
        if(mode==='RMS'){
          const maxWait = Math.max(...st.queue.map(q=> q.effPrio));
          if(maxWait > st.holder.effPrio){ st.holder.effPrio=maxWait; changed=true; }
        }else{
          const minDead = Math.min(...st.queue.map(q=> q.effDeadline));
          if(minDead < st.holder.effDeadline){ st.holder.effDeadline=minDead; changed=true; }
        }
      }
    }

    // deadline miss detection
    active.forEach(j=>{
      if(!j.missed && t >= j.absDeadline && j.remaining>0){
        j.missed=true; totalMiss++;
      }
      if(j.state==='Blocked') j.blockedTime++;
    });

    // scheduling selection
    const cand = active.filter(j=> j.state!=='Blocked');
    if(cand.length>0){
      cand.sort((a,b)=>{
        if(mode==='RMS') return b.effPrio - a.effPrio;
        const d = a.effDeadline - b.effDeadline;
        return d!==0? d : b.effPrio - a.effPrio;
      });
      const run = cand[0];
      run.state='Running';
      if(run.firstStart==null) run.firstStart=t;
      cand.slice(1).forEach(j=>{ if(j.state==='Running') j.state='Ready'; if(j.state!=='Blocked') j.state='Ready'; });
      run.executed++; run.remaining--;
      if(run.remaining<=0){
        run.remaining=0; run.state='Done'; run.completion=t+1;
        for(const m of [...run.holds]){ const st=mutexState.get(m); if(st?.holder===run) st.holder=null; }
        run.holds.clear();
      }
      log[t]=run.taskId;
    }else{
      log[t]=-1;
    }

    // per-task aggregate timeline for drawing
    tasks.forEach(td=>{
      const js = active.filter(j=> j.taskId===td.id);
      let st:'Idle'|'Ready'|'Running'|'Blocked' = 'Idle';
      if(js.some(j=> j.state==='Running')) st='Running';
      else if(js.some(j=> j.state==='Blocked')) st='Blocked';
      else if(js.some(j=> j.state==='Ready')) st='Ready';
      else if(js.length>0) st='Ready'; // a job that finished THIS tick is still occupying the row
      perTask[td.id][t]=st as any;
    });
    // ISR row
    {
      const isrActive = active.filter(j=> j.taskId===-1);
      let st:'Idle'|'Ready'|'Running'|'Blocked' = 'Idle';
      if(isrActive.some(j=> j.state==='Running')) st='Running';
      else if(isrActive.some(j=> j.state==='Blocked')) st='Blocked';
      else if(isrActive.some(j=> j.state==='Ready')) st='Ready';
      perTask[-1][t]=st as any;
    }
  }

  const U = tasks.reduce((s,t)=> s + t.C/t.T, 0);
  const bound = tasks.length * (Math.pow(2,1/tasks.length)-1);
  return {log, perTask, jobs, events, U, bound, totalMiss};
}

// Utilization: U = Σ C_i / T_i
// Liu & Layland: U ≤ n(2^{1/n}-1)
// Response time iteration: R_i^{k+1}= C_i + B_i + Σ ceil(R_i^k/T_j) C_j