I am writing a toy OS (more accessible about the scheduler)

  • Tutorial

The lack of comments on my two previous posts, despite the large number of likes, led me to the conclusion that the vast majority did not understand anything. It’s just that, having been immersed in the topic for a long time, I showed inattention to my reader. My fault, I will be corrected. Talk about planning in an accessible language. So what is a scheduler? The scheduler is a part of the OS that implements multitasking. The number of processors is usually much less than the number of tasks performed. Therefore, each processor has several tasks. Due to its sequential nature, the processor cannot perform these tasks at the same time - and it alternately switches from one task to another.



By the way of switching between tasks, the planners are divided into cooperative and preemptive. In cooperative planning, task switching is the responsibility of the tasks themselves. Those. the problem itself solves when it is possible to give way to the next. Unlike cooperative ones, crowding-out planners make their own decisions about changing tasks. It is easy to understand that the second planning method is generally more preferable for the OS due to its predictability and reliability.

Further tasks will be called flows. Initially, tasks were single-threaded, and the flow of execution always corresponded to the task. Currently, this is no longer the case, so the task was logically divided into two related concepts: a process, as a container of resources, and a thread, as an independent sequence of code execution.

Thread switching in the preemptive scheduler is triggered by a timer interrupt. Each specified period of time, the execution of the code is suspended, and control is transferred to the interrupt handler. This handler decides whether to continue working with the current thread until the next period, or transfer control to another thread.

Depending on the priority, a stream is assigned a certain quantum of time. For example, suppose a timer generates interrupts every millisecond. Then the flow to which the quantum 50 is assigned can work out 50 milliseconds if it is not replaced by the flow with high priority.

How does the handler switch threads? In the first postI wrote that during an interrupt, the processor writes some registers of the task to be performed on the stack. In addition, other registers were pushed further onto the stack. All registers together form the so-called context of the stream that describes its current state. To switch a task, you must first save its current context (so that it can be restored in the future), and in its place, record the previously saved context of another thread.

In toy, this is done like this:

DEFINE_ISR(timer, 0) {
  ...
  thrd->context = *stack_frame; // сохраняем текущий контекст в структуре thread_data
  update_priority_quantum(thrd); // вычисляем новый квант и приоритет потока
  ...
  prio = &cpud->priorities[cpud->current_priority = highest]; // работает с наивысшим текущим приоритетом
  struct thread_data *thrd2 = prio->active_tail; // берём из очереди наивысшего приоритета первый поток
  if (thrd2 != thrd) { // если старый и новый - не один и тот же поток
    *stack_frame = thrd2->context; // устанавливаем контекст из нового потока 
    wrmsr(MSR_FS_BASE, (uint64_t)thrd2);
  }
  ...
}


Before moving on to the multiprocessor scheduler ( SMP ), you should define the concept of a logical processor. By a logical processor we mean an entity that independently executes a sequence of instructions. Those. the logical processor can be either an old single-core chip or the core of a multi-core processor (or even a kernel thread in the presence of multithreading).

It is important to understand that the SMP scheduler code runs on each logical processor. Those. in each of them, timer interrupts are generated that switch the contexts of the flows. So, threads are distributed between existing logical processors (balancing their load is a separate non-trivial task). In modern x86 systems, along with the old programmable timer, the so-called local APICs are supportedtimers. Their main advantage is that each logical processor has its own independent local APIC timer. Therefore, it is these timers that are convenient to use for planning. The code for working with the APIC timer in toy can be found here .

There may be an erroneous impression that since each logical processor plans its own threads, there is no need for synchronization. In fact, threads are not attached rigidly to one processor, but can migrate (both when balancing the load, and explicitly, on the initiative of another thread). For example, in toy, one thread can pause the second, and run it on another processor. Accordingly, there is a need to protect shared data.

When writing a scheduler, we cannot use synchronization primitives familiar to the application programmer, such as a mutex, semaphore, or conditional variable. Such primitives assume blocking (sleep) of the flow for the duration of the inaccessibility of the requested resource. But there is no one to block, so active waiting comes to the rescue. Those. the processor sequentially polls the state of the resource and exclusively captures it at the time of release. Since active idle waiting loads the processor, holding the resource should take as little time as possible.

The main synchronization primitive based on active wait is spinlock. In modern systems, spinlocks are based on atomic instructions. For x86, this is xchg, lock cmpxchg, and others. The main task of such instructions is to atomically read and change the memory cell. Implementing the basic capture and release of a spinlock in a toy:

struct spinlock {
  volatile uint8_t busy;
};
static inline void create_spinlock(struct spinlock *lock) {
  lock->busy = false;
}
// zero tries means (practically) forever
static inline bool acquire_spinlock_int(struct spinlock *lock,
                                        uint64_t tries) {
  uint8_t al;
  do ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al));
  while (al && --tries);
  return !al;
}
static inline void release_spinlock_int(struct spinlock *lock) {
  ASMV("xorb %%al, %%al\nxchgb %%al, %0" : "+m"(lock->busy) : : "al");
}


That's all for today.

Only registered users can participate in the survey. Please come in.

Continue to write popularly?

  • 71.6% Yes, now at least it became clear what was being discussed. 225
  • 16.8% No, don’t need tithes, everything was clear before. 53
  • 11.4% Drop the garbage, not interesting. 36

Also popular now: