Operating System Internals

Process

• A thread of execution
  • Program Counter
  • Register state
  • Local data, i.e. stack
• An address space
  • Could be a subset of a shared memory space
    • MicroOS-II
    • Pre Windows CE 6.0 kernels
  • Or virtual space
    • CE 6.0, NT (XP, Vista, 7), Linux

Simple System

Picture

+-Kernel----------------------------------+
|                                         |
|  +-Process-+  +-Process-+  +-Process-+  |
|  |         |  |         |  |         |  |
|  | Thread  |  | Thread  |  | Thread  |  |
|  | Thread  |  |         |  |         |  |
|  |         |  |         |  |         |  |
|  +---------+  +---------+  +---------+  |
|                                         |
+-----------------------------------------+

Process and Thread Control APIs

• Create
  • Creation of the thread or task
• Delete
  • Deletion of thread
• Set Priorities
  • Set the priority of a thread
• Suspend/Resume
  • Suspend and resume the execution of a thread

Scheduling

• One of the key features of an operating system is the scheduling of tasks or functions.
• Even systems without formal operating systems often use some form of simplistic scheduling.
• Non-OS approaches to scheduling.

Scheduler

• The dispatcher component of OS
• Schedules threads (tasks, processes)
• Implements preemption
• Implements scheduling algorithm(s)
• Should be fast, efficient, deterministic

Scheduling algorithms

• Priority scheduling algorithm
  • Highest priority runable task is the thread selected to execute
• Each thread is on one of two lists:
  • Ready list
  • Wait or suspended list

Task States

PENDED    <----> READY/EXEC. <-----> DELAYED
  ^                 ^                   |
  |                 |                   |
  v                 v                   v
PENDED &  -----> SUSPENDED   <------ DELAYED &
SUSPENDED                            SUSPENDED

Round Robin Scheduling

• Each runable task executes for a quantum of time.
• After the quantum expires the next thread begins (continues) executing.
• Sometimes referred to as time-sharing or time-slicing.

Dynamic Priority Scheduling

• The priority of a given thread is based on dynamic conditions.
• NT/XP/Vista
  • NT gives a normal priority thread a boost after it is restarted from an I/O suspend.
  • NT gives the foreground task on the GUI a priority boost.
• Multimedia
  • Earliest deadline algorithm

Real-time scheduling algorithms

• Priority scheduling
• Typical of Embedded and RTOS systems
• May add round-robin for equal priority tasks

Rate Monotonic Scheduling

• Highest rate periodic event == highest priority
• The higher the rate of a periodic task the higher its priority.
  • For example, if task A executes once every 50 msec and task B executes once every 100 msec, then task A will receive a higher priority than task B.
• Provably correct
  • This approach has been proven to be optimal (Liu and Layland)
• Unfortunately for Embedded developers, many of the tasks that we have to deal with are not periodic in nature.

Earliest deadline first

• With this algorithm the scheduler is looking at the time when a task must be complete.
• It then schedules the task that has the earliest deadline approaching.
• This algorithm has been used in real-time multimedia systems.
  • You could think of a set of tasks where one is decoding frames of video and the other decoding frames of audio.
• The task that has the earliest need to deliver their frame is the thread that is executed.

Least Laxity

• Thread with least laxity is executed
• Laxity is the amount of time a thread has to spare before its task must be completed.
  • If a thread has 10 msec of work to perform and must deliver the result in 300 msec then it has 290 msec of laxity.
  • The algorithm chooses the task with the least laxity to execute.

Simple Round-Robin

• Cooperative tasks
• No interrupts
• No priorities

PTASK pFunc[MAX_TASK];               // ptr to routine to run
UCHAR currentTask = -1;              // initialize list of tasks to run
pFunc[0] = MyFirstTask;
pFunc[1] = My2ndTask;
pFunc[2] = ...

while(TRUE) {                        // forever loop
  if (++currentTask >= MAX_TASK) {
    currentTask = 0;
  }

  if (pFunc[currentTask] != NULL) {  // call the next task
     pFunc[currentTask]();
  }
}

Simple Round-Robin with Interrupts

Background

PTASK pFunc[MAX_TASK];                // ptr to routine to run

while(TRUE) {    // forever
    if (++currentTask >= MAX_TASK) {
        currentTask = 0;
    }

    if (pFunc[currentTask] != NULL) { // call the next task
        pFunc[currentTask]();
    }
}

Foreground

PISR IDT[MAX_ISR];

InterruptA() {
    ...
}

InterruptB() {
    ...
}

With Function Queue Scheduling

Background

struct { PFUNC pFunc;                // function to run
    PTASK pNext;                     // ptr to next task
} TASK, *PTASK;

PTASK pHead = NULL;                  // start list
PTASK pNext = NULL;                  // next task

while(TRUE) {                        // forever
    if (pNext == NULL)
        pNext = pHead;               // call the next task
    if (pNext != NULL) {
        pNext->pFunc();
        pNext = pNext->pNext
    }
}

Foreground

PISR IDT[MAX_ISR];
InterruptA() {
    ...
    AddTask(pMytask)
}
InterruptB() {
    ...
}
AddTask(PTASK pFunc) {
    // walk list from head insert pFunc at position in list depending on priority
}