Hello, so, we want to talk now about the details of real time scheduling, schedulers and the state machine used by the scheduler to determine what's executing at any point in time on a microprocessor that's managed by the operating system or RTOS and the scheduler. So let's review a few key terminology terms from our glossary. So first, we want to talk about AMP. And AMP is normally what we want its state of practice for real time systems. And so asymmetric multiprocessing, where you have multiple CPU cores, each with their own local memory and a message passing in a connection, perhaps, between them. Each processor running not only its own OS instance but its own application specific workload. So this is a very simple model. It's very close to a distributed system, but it might have low latency interconnection between the processor cores, each running an OS in a workload. And we can emulate this on an SMP system, which we'll talk about here in a moment. Like Linux, so Linux is by default, configured for symmetric multiprocessing. Where the OS there's one instance of the OS and it manages many cores or multiple cores. But what we do is we take that SMP system and we use thread affinity to essentially disable some of the SMP features. So that threads are assigned to cores and not allowed to migrate there by the disabling of load balancing through the use of thread affinity for those particular threads. So, we can have a true AMP architecture by design. Or we can emulate AMP on an SMP system by using thread affinity. So let's review what SMP is, SMP is symmetric multiprocessing. It's significantly different architecture than AMP. You have multiple CPU cores often with a common shared memory or message passing. But typically with just a common shared memory that has either uniform access or non uniform access. And I would suggest that you look at the glossary to understand UMA and NUMA. But most often all the cores share a memory and there's one operating system. And it maps, interrupts, and tasks to each of the cores under its management. The OS typically runs on one particular core like core zero, sometimes called the monarch core. And the interrupts and the tasks can be migrated or load balanced over time. And the migration, the movement, of tasks or threads between cores can make it difficult to model the behavior. So, in general, it's more difficult and therefore less deterministic because it's harder to model. Okay, so and use of SMP and architectures like virtual machines are more of a research topic in real time systems rather than state of practice. So AMP is a safe architecture that's well proven. So, it's what I would recommend, unless you have a very specific requirement that requires you to use something more complicated than the AMP. So, I would think about that very carefully because normally AMP can solve your problem and is widely used and widely proven, reduce to practice. Okay, so the final term that's important here in this discussion is priority preemptive run-to-completion scheduling. This is critical to rate monotonic policy, the rate monotonic theory, and rate monotonic analysis. So it simply states that the highest priority task or thread in a ready queue is dispatched. And it will preempt any running task that is lower priority than the one being dispatched. And otherwise, if there's no preemption a task simply runs to completion. There's no time slicing, there's no preemption otherwise, and that's an important concept. So with Linux, compared to say an RTOS, what best models this behavior is SCHED_FIFO. And as we see in the class SCHED_FIFO is priority preemptive run to completion, like RTOS tasks. It's unfair and it's deterministic and this is what we want in a real time system. So tasks or threads run at a priority until they complete and exit. So they just run to completion or until, within the code, they yield or request to sleep. Which will change their state to delayed. Or they activate a higher priority task or block on a secondary resource. Which would cause them to transition to pending or to get preempted. Or until an interrupt is raised that's going to change what's in the ready queue somehow. Perhaps by giving a semaphore or sending a message to a task that was previously blocked or waking up one that was delayed in the delayed state. Okay, so what are our other options? Well, the Linux real time extensions also include an option called SCHED_RR. This is fixed priority and preemptive. But it has time slicing. So it is fair. And it's higher overhead because of the time slicing. So you're going to take interrupts on a regular, periodic basis to adjust scheduling. And it may be deterministic because it's round robin as we'll see when we do scheduling analysis is fairly simple, but we really don't want fair. [LAUGH] So we want deterministic and unfair so that our highest priority tasks or threads complete and take precedence over anything that's lower priority. This gives us very deterministic failure modes as well as success. And so determinism is one of our primary goals. And we really also don't want fairness because we want very deterministic behavior in an overload scenario as well. Which we'll discuss near the end of this course. So, final option is just to use the default scheduling in Linux. It's known as SCHED_OTHER. And the current scheduler used in the Linux kernel as a default as a completely fair scheduler, as we said we don't want fair. The other problem with CFS is not only is it fair it's hard to model. So it has advanced features like nice levels and priority to decay to prevent CPU hogging. It's fantastic for scalable workloads and desktop computing. But it's not great for what we want to do. The analogy I like to make is with CFS. Everyone gets a slice of pie so nobody's going to starve and that can solve a lot of problems. So CFS is a valuable, best effort, scalable scheduler. If you have a higher priority through the use of nice, negative nice if you want higher priority. Some of the processes just get more slices of pie more often [LAUGH] than others is the easiest way to think about that. We have to have a time slice or quantum as it's sometimes called. Typically that's 10 milliseconds in Linux. And so there's an interrupt raised 100 times a second just to adjust scheduling, to maintain this fairness to prevent CPU hogs to implement nice levels, etc. And all tasks, a big advantage of it is to make progress. So it is fair. But this is not what we want. So it does not provide predictable response. So we want to use SCHED_FIFO is the final analysis for our options here in Linux. The one that I didn't mention that is a topic that comes up in course two is in this series of SCHED_DEADLINE. So SCHED_DEADLINE is a new feature of Linux. So you might not find in all versions of the kernel or all Linux distributions, which is the other reason we don't use it in this course. And it is because we want fixed-priority preemptive. So sched_deadline is adaptive and has dynamic priorities which is in a more advanced concept in real-time systems. Most often used for soft real-time but there is some debate about that. It's a dynamic priority alternative. If you refer to the Liu and Layland paper, it basically, implements deadline-driven scheduling dynamic priorities. So it's adaptive and it's harder to model, which is why we don't use it in this first course. Okay, so let's look at what we're using and why. So we, obviously, want to schedule execution and if we just have a single processor, we come down this tree and we go to preemptive fixed priority. And we use rate monotonic policy in theory for scheduling on one processor that works great with AMP. Now if we want multiple processors for scaling, then we have multiple cores, but what we do is instead of going down SMP we keep our workloads on each processor core static, that's the key. They're assigned once and for all. There's no migration, there's no load balancing. And we combine them and essentially we just have multiple instances of a single processor running priority preemptive workloads. Following rate monotonic policy, allowing us to do rate monotonic analysis on each processor core based on rate monotonic theory. And they may send messages between each other for specific data sharing or synchronization requirements but each one essentially has its own fixed workload and is managed by one and only one operating system. We emulate this in Linux with thread affinity. So we have emulated AMP but that works well for the course. So what are other alternatives? Well, another alternative would be a cyclic executive or multi-frequency executive. And that would be non-preemptive co-operative. The problem with this approach is that it's essentially hardcoded. So down here on this non-preemptive cooperative, it's the issue is hard coding. And we saw that we could make a schedule, and we could use just delays and make a hardcoded schedule that just executes over and over. And that meets requirements but it's difficult to maintain, it's difficult to scale. So it's not as flexible as an RTOS or Linux with real-time extensions. So over here, what we've circled is what's typically used for an RTOS or Linux plus RT extensions, the POSIX extensions. Namely SCHED_FIFO and other system calls that can be made. We can, therefore, use services implemented in userspace in Linux. We can also implement services in kernel space but that's a little more difficult to do, to debug, to learn in user-space so in this course, we stick with user-space. And so this just explains why so with Linux we want the default is SMP CFS Fair, but that's not what we want. We want HRT AMP rate monotonic. For soft real-time we might consider PDF, right? So this would be for soft real-time over here. That's generally accepted. For hard real-time, we want to use what we've circled up here. And so just an explanation as to why we've selected what we have. So now let's go into the details comparing an RTOS scheduler state machine to a Linux real-time extensions state machine. You can find information for Linux by just doing a man minus keyword P thread and POSIX for most of these system calls. I'm going to show you here, but let's start out with the RTOS. So in the RTOS normally, tasks exist most of the time if not all the time, in one of two states either ready to execute or executing. If the task is executing, it runs to completion unless something enters the ready queue that's higher priority than it and which case it would get preempted, right? If something enters the red queue that's higher priority, how would it enter the ready queue through something like an interrupt. The interrupt could give a semaphore to a task that was pending over here. And it could enter the ready queue and it could be higher priority than what's executing that would cause a preemption of what's executing, and then cause it to get dispatched. If in fact, it's higher priority. So that's really common scenario in RTOS and something that we need in Linux, so do we have the same thing? Well, if we create something SCHED_FIFO and it has a priority it will run until it gets preempted or yields. And if it is preempted it will go back to the ready queue. Just like VxWorks, right? And what would cause that? Well, something that could be pending. It could actually go from pending to ready, for example, acquiring a lock and transitioning. Similarly to what happened over here with the RTOS, it could also just be based on taking like a binary semaphore, as we'll see. And if it was higher priority, say it has our Tmax and what's currently running is less than our Tmax, then what would happen is that it would be dispatched in the place of what was running And we have this same basic state where, for the most part, SCHED_FIFO threads go between ready and executing and generally when they need some other resource they then go to pending, like when they try to acquire a lock or a binary semaphore. Which happens on both sides. So, what we're showing here is we have equivalent capability between VxWorks as documented by the Programmer's Guide, as documented by the manual pages for the real time extensions for Linux. And in both cases, I can be executing and I can delay myself by just calling task delay or calling something like asleep or a pause over in Linux. So we have parallel structure there. And in both cases if I say divide by zero I can go from executing over to a suspended state. And that can happen of course, because of division by zero over Linux as well. So what we're seeing is that these are in fact the same state machines. In the case of Linux, this is implemented with the native POSIX Threads library. Which maps user space threads onto kernel level tasks, which when they are SCHED_FIFO use this same scheduler state machine and take priority over all non-real time threads that are executing on the Linux system. So both can enter delayed through something like asleep or a pause, as we'll see in some of the example code. And we have parallel construction, you can look up these various system calls that I've pointed out here that cause these transitions in the manual pages over in Linux. If you want to look at documentation for the scheduling state machine for VxWorks for the wind kernel, refer to the VxWorks Programmer's Guide. Last time I looked at this, it was in chapter seven. So key things are that we have P thread create with SCHED FIFO. We can emulate amp with CPU core affinity. We have similar kind of capability to the task control of an RTOS with things like P thread join and other P thread operations. The user space threads are dispatched from a specific ready queue for SCHED FIFO in kernel space in Linux, like the scheduler works for the RTOS. The interesting thing about an RTOS is you can consider everything to be in kernel space for the RTOS. In Linux, we have the option of writing tasks that exist in kernel space or threads that exist in user space that are mapped on to kernel space tasks. With Linux, we dispatch the threads with rate-monotonic policies. So we can use the rate-monotonic policy in both cases between RT max and RT min. So we can achieve the same thing. And then we just reviewed system calls that can cause transitions over in Linux just like we have in the RTOS like VxWorks. The optional book for the course that I wrote covers both as well. So we have a parallel capability. There are differences of course between [LAUGH] Linux and RTOS and you have to be careful not to equate the two. This just shows we have similar scheduling capability and control. There are additional considerations. There are patches required for Linux to configure it for safe real-time use, for soft real-time and potentially hard real-time. But you have to think very carefully about using Linux for something like that and configure it very carefully. And so for example, the RT-Preempt patch and those will be discussed to some degree in this course but in further detail in the second course. And so, Vanilla Linux has to be carefully used, configured and essentially pared down to be more like an RTOS whereas the RTOS has to be built up. So the downside in the RTOS is you get a very minimal kernel. And you have to add code and libraries and modules to it to build it up to be like Linux. With Linux, what you really do is you get everything [LAUGH] and you only use a small subset so you have to pare it down. And use specific features and avoid using features that you don't need. So one's a build up and one's a pare down. But we can get, well, roughly equivalent results. Similar results is safe to say, from Linux certainly for soft real time and predictable response, if not deterministic. RTOS is more deterministic, and I would categorize Linux as predictable response. So the RTOS can also have predictable response. Getting deterministic behavior out of Linux is much harder, especially in user space. More possible in kernel space, but that's harder to code. And now, at that point, what I would always point out is if you're implementing all your services in kernel space in Linux, perhaps you should have just used an RTOS. And we'll [LAUGH] end on that note there, thank you very much. [SOUND]
