Real-Time OS Features

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

/* Tick-Based vs. Tickless Implementation Comparison */
 
/* ============================================
 * Tick-Based Timer Management
 * ============================================ */
 
#define TICK_RATE_HZ    1000    /* 1ms ticks */
static volatile uint32_t system_ticks = 0;
 
/* Periodic tick ISR - fires every 1ms */
void SysTick_Handler_TickBased(void) {
    system_ticks++;
    
    /* Check all delayed tasks - O(n) worst case */
    task_t *task = delayed_list_head;
    while (task != NULL) {
        task->delay_remaining--;
        if (task->delay_remaining == 0) {
            /* Move to ready list */
            move_to_ready_list(task);
        }
        task = task->next;
    }
    
    /* Check for preemption */
    scheduler_tick();
}
 
/* Delay function - resolution limited to tick period */
void delay_ticks_tickbased(uint32_t ticks) {
    current_task->delay_remaining = ticks;
    add_to_delayed_list(current_task);
    scheduler_yield();
}
 
/* ============================================
 * Tickless Timer Management
 * ============================================ */
 
static volatile uint64_t last_timer_time = 0;
 
/* Calculate time until next event */
uint64_t calculate_next_wakeup(void) {
    uint64_t min_wakeup = UINT64_MAX;
    
    /* Find earliest task wakeup time */
    task_t *task = delayed_list_head;
    while (task != NULL) {
        if (task->wakeup_time < min_wakeup) {
            min_wakeup = task->wakeup_time;
        }
        task = task->next;
    }
    
    return min_wakeup;
}
 
/* Called when scheduler has no ready tasks */
void tickless_idle(void) {
    uint64_t now = get_time_ns();
    uint64_t next_wakeup = calculate_next_wakeup();
    
    if (next_wakeup < UINT64_MAX) {
        /* Set timer for exact wakeup time */
        uint64_t sleep_duration = next_wakeup - now;
        set_oneshot_timer_ns(sleep_duration);
        
        /* Enter low-power sleep */
        enter_sleep_mode();
        
        /* Timer interrupt woke us - update time tracking */
        update_system_time();
    } else {
        /* No pending events - deep sleep until interrupt */
        enter_deep_sleep();
    }
}
 
/* One-shot timer ISR - fires only when needed */
void Timer_Handler_Tickless(void) {
    uint64_t now = get_time_ns();
    
    /* Wake tasks whose time has come */
    task_t *task = delayed_list_head;
    while (task != NULL && task->wakeup_time <= now) {
        task_t *next = task->next;
        move_to_ready_list(task);
        task = next;
    }
    
    /* If tasks became ready, reschedule */
    if (tasks_made_ready) {
        scheduler_preempt();
    }
}
 
/* Precise delay - resolution limited only by timer hardware */
void delay_ns_tickless(uint64_t nanoseconds) {
    uint64_t now = get_time_ns();
    current_task->wakeup_time = now + nanoseconds;
    add_to_delayed_list_sorted(current_task);
    scheduler_yield();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

/* High-Resolution Timer System Implementation */
 
#include <stdint.h>
#include <stdbool.h>
 
/* ============================================
 * Timer Wheel for Efficient Timer Management
 * O(1) insert, O(1) expiration processing
 * ============================================ */
 
#define WHEEL_BITS      8
#define WHEEL_SIZE      (1 << WHEEL_BITS)
#define WHEEL_MASK      (WHEEL_SIZE - 1)
#define NUM_WHEELS      4   /* 4 wheels = 32-bit range */
 
typedef struct timer {
    struct timer *next;
    struct timer *prev;
    uint64_t expires;           /* Absolute expiration time */
    void (*callback)(void *);   /* Expiration callback */
    void *data;                 /* Callback argument */
} timer_t;
 
typedef struct {
    timer_t *slots[WHEEL_SIZE];
    uint32_t current_slot;
} timer_wheel_t;
 
static timer_wheel_t wheels[NUM_WHEELS];
static uint64_t current_time_ns;
 
/* Insert timer - O(1) */
void timer_add(timer_t *timer) {
    uint64_t delta = timer->expires - current_time_ns;
    
    /* Find appropriate wheel based on delay magnitude */
    int wheel;
    uint32_t slot;
    
    if (delta < (1ULL << (WHEEL_BITS * 1))) {
        wheel = 0;
        slot = (timer->expires >> 0) & WHEEL_MASK;
    } else if (delta < (1ULL << (WHEEL_BITS * 2))) {
        wheel = 1;
        slot = (timer->expires >> WHEEL_BITS) & WHEEL_MASK;
    } else if (delta < (1ULL << (WHEEL_BITS * 3))) {
        wheel = 2;
        slot = (timer->expires >> (WHEEL_BITS * 2)) & WHEEL_MASK;
    } else {
        wheel = 3;
        slot = (timer->expires >> (WHEEL_BITS * 3)) & WHEEL_MASK;
    }
    
    /* Add to slot's list */
    timer->next = wheels[wheel].slots[slot];
    timer->prev = NULL;
    if (wheels[wheel].slots[slot]) {
        wheels[wheel].slots[slot]->prev = timer;
    }
    wheels[wheel].slots[slot] = timer;
}
 
/* Process expired timers - called periodically */
void timer_tick(void) {
    current_time_ns = get_hardware_time_ns();
    
    /* Process wheel 0 (finest granularity) */
    uint32_t slot = (current_time_ns >> 0) & WHEEL_MASK;
    
    timer_t *timer = wheels[0].slots[slot];
    while (timer != NULL) {
        timer_t *next = timer->next;
        
        if (timer->expires <= current_time_ns) {
            /* Remove from wheel */
            if (timer->prev) timer->prev->next = timer->next;
            if (timer->next) timer->next->prev = timer->prev;
            if (wheels[0].slots[slot] == timer) {
                wheels[0].slots[slot] = timer->next;
            }
            
            /* Fire callback */
            timer->callback(timer->data);
        }
        
        timer = next;
    }
    
    /* Cascade from higher wheels when wrapping */
    if (slot == 0) {
        cascade_wheel(1);
    }
}
 
/* ============================================
 * POSIX-like High-Resolution Timer API
 * ============================================ */
 
typedef struct {
    uint64_t tv_sec;
    uint64_t tv_nsec;
} timespec_t;
 
/* Clock types */
#define CLOCK_REALTIME      0   /* Wall clock, may jump */
#define CLOCK_MONOTONIC     1   /* Never decreases, may slew */
#define CLOCK_MONOTONIC_RAW 2   /* Never decreases, never slewed */
 
static uint64_t monotonic_offset = 0;
 
int clock_gettime(int clk_id, timespec_t *tp) {
    uint64_t ns;
    
    switch (clk_id) {
        case CLOCK_REALTIME:
            ns = get_realtime_ns();
            break;
            
        case CLOCK_MONOTONIC:
            ns = get_hardware_time_ns() + monotonic_offset;
            break;
            
        case CLOCK_MONOTONIC_RAW:
            ns = get_hardware_time_ns();
            break;
            
        default:
            return -1;
    }
    
    tp->tv_sec = ns / 1000000000ULL;
    tp->tv_nsec = ns % 1000000000ULL;
    return 0;
}
 
/* Sleep until absolute time - key for deterministic scheduling */
int clock_nanosleep(int clk_id, int flags, 
                    const timespec_t *request, timespec_t *remain) {
    uint64_t target_ns;
    
    if (flags & TIMER_ABSTIME) {
        /* Absolute time - directly use specified time */
        target_ns = request->tv_sec * 1000000000ULL + request->tv_nsec;
    } else {
        /* Relative - add to current time */
        uint64_t now = get_hardware_time_ns();
        target_ns = now + request->tv_sec * 1000000000ULL + request->tv_nsec;
    }
    
    /* Program hardware timer for wakeup */
    current_task->wakeup_time = target_ns;
    suspend_task(current_task);
    
    /* When we wake, calculate remaining if interrupted */
    if (remain != NULL) {
        uint64_t now = get_hardware_time_ns();
        if (now < target_ns) {
            uint64_t left = target_ns - now;
            remain->tv_sec = left / 1000000000ULL;
            remain->tv_nsec = left % 1000000000ULL;
        } else {
            remain->tv_sec = 0;
            remain->tv_nsec = 0;
        }
    }
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

/* Timer Resolution in Schedulability Analysis */
 
#include <stdint.h>
#include <stdbool.h>
#include <math.h>
 
typedef struct {
    uint32_t period_us;      /* Task period in microseconds */
    uint32_t wcet_us;        /* Worst-case execution time */
    uint32_t deadline_us;    /* Relative deadline */
    uint32_t priority;       /* RMS priority (lower period = higher) */
} rt_task_t;
 
/* System configuration */
#define TICK_PERIOD_US      1000    /* 1ms tick period */
#define SCHEDULER_OVERHEAD_US 10    /* Scheduler execution time */
#define ISR_OVERHEAD_US     2       /* Tick ISR overhead */
 
/* Calculate effective WCET including timer effects */
uint32_t effective_wcet(rt_task_t *task) {
    /* Actual WCET includes:
     * 1. Task's own execution time
     * 2. Tick ISR overhead (task may be interrupted by tick)
     * 3. Timer-induced wakeup jitter
     * 4. Scheduler overhead
     */
    uint32_t ticks_during_execution = 
        (task->wcet_us / TICK_PERIOD_US) + 1;
    
    uint32_t timer_overhead = 
        ticks_during_execution * (ISR_OVERHEAD_US + SCHEDULER_OVERHEAD_US);
    
    /* Wakeup jitter: worst case is we wake just after a tick */
    uint32_t wakeup_jitter = TICK_PERIOD_US;
    
    return task->wcet_us + timer_overhead + wakeup_jitter;
}
 
/* Response Time Analysis with timer effects */
uint32_t response_time_analysis(rt_task_t *tasks, int num_tasks, int task_idx) {
    rt_task_t *task = &tasks[task_idx];
    uint32_t wcet = effective_wcet(task);
    uint32_t R = wcet;  /* Initial estimate */
    
    /* Iterate until convergence */
    uint32_t R_prev;
    do {
        R_prev = R;
        R = wcet;
        
        /* Add interference from higher-priority tasks */
        for (int i = 0; i < task_idx; i++) {
            uint32_t hp_wcet = effective_wcet(&tasks[i]);
            uint32_t hp_period = tasks[i].period_us;
            
            /* Number of times HP task runs during R */
            uint32_t hp_runs = ((R + hp_period - 1) / hp_period);
            R += hp_runs * hp_wcet;
        }
        
        /* Check for deadline miss */
        if (R > task->deadline_us) {
            return UINT32_MAX;  /* Task not schedulable */
        }
        
    } while (R != R_prev);
    
    return R;
}
 
/* Check if task set is schedulable */
bool is_schedulable(rt_task_t *tasks, int num_tasks) {
    /* Sort by period (RMS priority assignment) */
    sort_by_period(tasks, num_tasks);
    
    for (int i = 0; i < num_tasks; i++) {
        uint32_t R = response_time_analysis(tasks, num_tasks, i);
        
        if (R > tasks[i].deadline_us) {
            printf("Task %d: R=%u > D=%u - NOT SCHEDULABLE\n",
                   i, R, tasks[i].deadline_us);
            return false;
        }
        
        printf("Task %d: R=%u, D=%u, margin=%d us\n",
               i, R, tasks[i].deadline_us, tasks[i].deadline_us - R);
    }
    
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

/* Clock Drift Compensation Techniques */
 
#include <stdint.h>
#include <stdbool.h>
 
/* ============================================
 * Software Clock Discipline
 * ============================================ */
 
typedef struct {
    int64_t offset_ns;      /* Current offset from reference */
    int32_t freq_adj_ppb;   /* Frequency adjustment in ppb */
    uint64_t last_update;   /* Time of last adjustment */
} clock_discipline_t;
 
static clock_discipline_t clock_state;
 
/* Called periodically with reference time from NTP, GPS, or PTP */
void clock_discipline_update(uint64_t local_time_ns, 
                             uint64_t reference_time_ns) {
    int64_t offset = reference_time_ns - local_time_ns;
    
    /* PI controller for clock discipline */
    const int32_t Kp = 100;    /* Proportional gain (ppb per ns offset) */
    const int32_t Ki = 1;      /* Integral gain */
    
    /* Calculate frequency adjustment */
    int64_t time_since_update = local_time_ns - clock_state.last_update;
    int32_t drift_rate = (offset - clock_state.offset_ns) * 1000000000LL 
                         / time_since_update;  /* ppb */
    
    /* Update frequency adjustment */
    clock_state.freq_adj_ppb += Ki * drift_rate;
    
    /* Apply proportional correction (phase adjustment) */
    clock_state.offset_ns = offset;
    
    /* Apply to hardware timer if supported */
    apply_frequency_adjustment(clock_state.freq_adj_ppb);
    
    clock_state.last_update = local_time_ns;
}
 
/* Get disciplined time */
uint64_t get_disciplined_time_ns(void) {
    uint64_t raw_time = get_hardware_time_ns();
    
    /* Apply offset correction */
    raw_time += clock_state.offset_ns;
    
    /* Apply frequency correction (scaled by time since last update) */
    uint64_t elapsed = raw_time - clock_state.last_update;
    int64_t freq_correction = (elapsed * clock_state.freq_adj_ppb) 
                              / 1000000000LL;
    
    return raw_time + freq_correction;
}
 
/* ============================================
 * Precision Time Protocol (PTP/IEEE 1588)
 * For sub-microsecond synchronization
 * ============================================ */
 
typedef struct {
    uint64_t t1;    /* Master sends Sync */
    uint64_t t2;    /* Slave receives Sync */
    uint64_t t3;    /* Slave sends Delay_Req */
    uint64_t t4;    /* Master receives Delay_Req */
} ptp_timestamps_t;
 
/* Calculate offset and delay from PTP exchange */
void ptp_calculate_offset(ptp_timestamps_t *ts, 
                          int64_t *offset, 
                          uint64_t *delay) {
    /* 
     * offset = ((t2 - t1) - (t4 - t3)) / 2
     * delay = ((t2 - t1) + (t4 - t3)) / 2
     * 
     * Assumes symmetric network delay
     */
    int64_t diff_ms = (int64_t)(ts->t2 - ts->t1);  /* Master to Slave */
    int64_t diff_sm = (int64_t)(ts->t4 - ts->t3);  /* Slave to Master */
    
    *offset = (diff_ms - diff_sm) / 2;
    *delay = ((uint64_t)diff_ms + diff_sm) / 2;
}
 
/* Apply PTP synchronization */
void ptp_sync_clock(ptp_timestamps_t *ts) {
    int64_t offset;
    uint64_t delay;
    
    ptp_calculate_offset(ts, &offset, &delay);
    
    /* Filter outliers (network jitter) */
    if (abs(offset) < MAX_ALLOWED_OFFSET) {
        /* Apply servo algorithm for smooth adjustment */
        clock_discipline_update(get_hardware_time_ns(),
                                get_hardware_time_ns() + offset);
    }
    
    /* Log synchronization quality */
    log_ptp_stats(offset, delay);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

/* Timer Best Practices and Common Pitfalls */
 
/* ✗ BAD: Relative sleep accumulates drift */
void periodic_task_bad(uint32_t period_ms) {
    while (1) {
        do_work();
        delay_ms(period_ms);  /* Execution time adds to period! */
    }
    /* After 1000 iterations with 1ms execution time:
     * Intended: 1000 × period_ms
     * Actual: 1000 × (period_ms + 1ms) = 1000ms drift! */
}
 
/* ✓ GOOD: Absolute time maintains accuracy */
void periodic_task_good(uint32_t period_ms) {
    timespec_t next_wakeup;
    clock_gettime(CLOCK_MONOTONIC, &next_wakeup);
    
    while (1) {
        /* Advance to next period */
        next_wakeup.tv_nsec += period_ms * 1000000ULL;
        if (next_wakeup.tv_nsec >= 1000000000) {
            next_wakeup.tv_sec++;
            next_wakeup.tv_nsec -= 1000000000;
        }
        
        do_work();
        
        /* Sleep until absolute time - no drift! */
        clock_nanosleep(CLOCK_MONOTONIC, TIMER_ABSTIME, 
                        &next_wakeup, NULL);
    }
}
 
/* ✗ BAD: Timer wraparound bug */
bool timeout_expired_bad(uint32_t start, uint32_t timeout) {
    uint32_t now = get_timer_counter();
    return (now - start) > timeout;  /* Fails at wraparound! */
}
 
/* ✓ GOOD: Wraparound-safe comparison */
bool timeout_expired_good(uint32_t start, uint32_t timeout) {
    uint32_t now = get_timer_counter();
    /* Works correctly even if 'now' has wrapped and 'start' hasn't */
    return ((int32_t)(now - start)) >= (int32_t)timeout;
}
 
/* ✗ BAD: Using wall clock for computation */
void measure_duration_bad(void) {
    timespec_t start, end;
    clock_gettime(CLOCK_REALTIME, &start);  /* BAD: Can jump! */
    
    do_operation();
    
    clock_gettime(CLOCK_REALTIME, &end);
    /* If NTP adjusts clock during operation, result is garbage! */
}
 
/* ✓ GOOD: Using monotonic clock for duration */
void measure_duration_good(void) {
    timespec_t start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);  /* Never jumps */
    
    do_operation();
    
    clock_gettime(CLOCK_MONOTONIC, &end);
    uint64_t duration_ns = timespec_diff_ns(&end, &start);
    /* Always correct, even across NTP/DST adjustments */
}