Last Time Debugging It’s a science – use experiments to refine hypotheses about bugs It’s an art – creating effective hypotheses and experiments and trying them in the right order requires great intuitionLab 3 Questions?Today Advanced threads Thread example Implementation review Design issues Performance metricsThread variationsThread variations Example code from Ethernut RTOSWhat’s an RTOS? Real-Time Operating System Implication is that it can be used to build real-time systems Provides: Threads Real-time schedulerSynchronization primitivesSynchronization primitives Boot code Device drivers Might provide: Memory protection Virtual memory Is WinCE an RTOS? Embedded Linux?Thread Example We want code to do this:1. Turn on the wireless network at time t02. Wait until time is t0+ tawake3. If communication has not completed, wait until it has completed or else time is t0+ tawake+ twait_max4.Turn off radio4.Turn off radio5. Go back to step 1Threaded vs. Non-Threadedenum { ON, WAITING, OFF } state;void radio_wake_event_handler () {switch (state) {case ON:if (expired(&timer)) {set_timer (&timer, T_SLEEP);if (!communication_complete) {state = WAITING;set_timer (&wait_timer, void radio_wake_thread () {while (1) {radio_on();timer_set (&timer, T_AWAKE);wait_for_timer (&timer);T_MAX_WAIT);} else {turn_off_radio();state = OFF;}}break;case WAITING:if (communication_complete() ||timer_expired (&wait_timer)) {state = OFF;radio_off();}break; ...timer_set (&timer, T_SLEEP);if (!communication_complete()) {timer_set (&wait_timer, T_WAIT_MAX);wait_cond (communication_complete() ||timer_expired (&wait_timer));}radio_off();wait_for_timer (&timer);}}Blocking Blocking Ability for a thread to sleep awaiting some event• Like what? Fundamental service provided by an RTOSHow does blocking work? How does blocking work? 1. Thread calls a function provided by the RTOS2. RTOS decides to block the thread3. RTOS saves the thread’s context4. RTOS makes a scheduling decision5. RTOS loads the context of a different thread and runs it When does a blocked thread wake up?More Blocking When does a blocked thread wake up? When some predetermined condition becomes true Disk block available, network communication needed, timer expired, etc. Often interrupt handlers unblock threads Why is blocking good? Preserves the contents of the stack and registers Upon waking up, thread can just continue to execute Can you get by without blocking? Yes – but code tends to become very cluttered with state machinesPreemption When does the RTOS make scheduling decisions? Non-preemptive RTOS: Only when a thread blocks or exits Preemptive RTOS: every time a thread wakes up or changes priorityAdvantage of preemption: Threads can respond Advantage of preemption: Threads can respond more rapidly to events No need to wait for whatever thread is running to reach a blocking point Even preemptive threads sometimes have to wait For example when interrupts are disabled, preemption is disabled tooMore Preemption Preemption and blocking are orthogonal No blocking, no preemption – main loop style Blocking, no preemption – non-preemptive RTOS• Also MacOS < 10 No blocking, preemption – interrupt-driven systemBlocking, preemption –preemptive RTOSBlocking, preemption –preemptive RTOSThread Implementation TCB – thread control block One per thread A struct that stores:• Saved registers including PC and SP• Current thread state•All-threads link field•All-threads link field• Ready-list / block-list link field Stack Dedicated block of RAM per threadThread States Thread invariants At most one running thread• If there’s an idle thread then exactly one running thread Every thread is on the “all thread” list State-based:• Running thread → Not on any list• Blocked thread → On one blocked list• Active thread → On one ready listEthernut TCBstruct _NUTTHREADINFO {NUTTHREADINFO *volatile td_next; /* Linked list of all threads. */NUTTHREADINFO *td_qnxt; /* Linked list of all queued thread. */u_char td_name[9]; /* Name of this thread. */u_char td_state; /* Operating state. One of TDS_ */uptr_t td_sp; /* Stack pointer. */u_char td_priority; /* Priority level. 0 is highest priority. */u_char *td_memory; /* Pointer to heap memory used for stack. */u_char *td_memory; /* Pointer to heap memory used for stack. */HANDLE td_timer; /* Event timer. */HANDLE td_queue; /* Root entry of the waiting queue. */};#define TDS_TERM 0 /* Thread has exited. */#define TDS_RUNNING 1 /* Thread is running. */#define TDS_READY 2 /* Thread is ready to run. */#define TDS_SLEEP 3 /* Thread is sleeping. */Scheduler Makes a decision when: Thread blocks Thread wakes up (or is newly created) Time slice expires Thread priority changesHow does the scheduler make these decisions?How does the scheduler make these decisions? Typical RTOS: Priorities Typical GPOS: Complicated algorithm There are many other possibilitiesu_char NutThreadSetPriority(u_char level) {u_char last = runningThread->td_priority;/* Remove the thread from the run queue and re-insert it with a new* priority, if this new priority level is below 255. A priotity of* 255 will kill the thread. */NutThreadRemoveQueue(runningThread, &runQueue);runningThread->td_priority = level;if (level < 255) NutThreadAddPriQueue(runningThread, (NUTTHREADINFO **) & runQueue);else NutThreadKill();/* Are we still on top of the queue? If yes, then change our status* back to running, otherwise do a context switch. */if (runningThread == runQueue) {runningThread->td_state = TDS_RUNNING;} else {runningThread->td_state = TDS_READY;NutEnterCritical();NutThreadSwitch();NutExitCritical();}return last;}Dispatcher Low-level part of the RTOS Basic functionality: Save state of currently running thread• Important not to destroy register values in the process! Restore state of newly running thread What if there’s no new thread to run? Usually there’s an idle thread that is always ready to run In modern systems the idle thread probably just puts the processor to sleepEthernut ARM Contexttypedef struct {u_long csf_cpsr;u_long csf_r4;u_long csf_r5;u_long csf_r6;u_long csf_r7;u_long csf_r7;u_long csf_r8;u_long csf_r9;u_long