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

The lack of comments to my two previous posts, despite the large number of likes, led me to the conclusion that the overwhelming majority did not understand anything. Just being a long time immersed in the topic, I showed inattention to my reader. My fault, I will be corrected. Let's talk about planning in an accessible language.

So what is a scheduler? 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 consistent nature, the processor cannot perform these tasks simultaneously - and it alternately switches from one task to another.

By the way of switching between tasks, planners are divided into cooperative and supplanting ones. In cooperative planning, the tasks themselves are responsible for switching tasks. Those. the task itself decides when it is possible to give place to the next. Unlike cooperative, displacing planners make their own decisions about changing tasks. It is easy to understand that the second planning method is generally preferable for the OS due to its predictability and reliability.
')
Further tasks will be called streams. Initially, tasks were single-threaded, and the thread of execution always corresponded to the task. Currently, this is no longer the case, so the task is logically divided into two related concepts: process, as a container of resources, and flow, as an independent sequence of code execution.

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

Depending on the priority, a time slice is assigned to the stream. For example, let the timer generate interrupts every millisecond. Then the stream to which quantum 50 is assigned can run for 50 milliseconds if it is not preempted by a stream with a higher priority.

How does the handler switch threads? In the first post I wrote that during an interrupt, the processor writes some registers of the task to the stack. In addition, the remaining registers were pushed further onto the stack. All registers together form the so-called flow context describing 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 write the previously saved context of another thread.

In toy, it 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. a logical processor can be either an old single-core chip, or a multi-core processor core (or even a kernel thread with multithreading).

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

There may be an erroneous impression that since each logical processor plans its own threads, there is no need for synchronization. In fact, the threads are not tied tightly to one processor, but can migrate (as when balancing the load, and obviously, at the initiative of another thread). For example, in a 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 an application programmer, such as a mutex, semaphore, or conditional variable. Such primitives imply blocking (drowsy) flow for the time when the requested resource is not available. But there is no one to block, so an active wait comes to the rescue. Those. The processor sequentially polls the state of the resource and exclusively captures it at the moment of release. Since an active idle is loading the processor, it should take as little time as possible to hold the resource.

The main primitive of synchronization, based on active waiting, 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 a memory cell. The implementation of the basic capture and release of the spinlock in 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.