Hello, one of the details that is important to clear up with Linux is methods and mechanisms for synchronization. And how they compare to, say for example, an RTOS, which is one of the three options as well as Linux and cyclic executive that is often used for real-time embedded systems. So I wanted to give you a quick comparison of the methods of synchronization and give you a few caveats about the Linux synchronization methods and mechanisms compared to RTOS. Okay, so you probably know this from an operating systems course, but maybe you haven't had one, or maybe it's been a long time. So I'm just going to give you a quick review, a brief history of methods of synchronization, and how they came about, and why they exist. So as you probably know, multiprogramming has been around for a long time. The idea of multiple processes running on one system, multiple applications being active at the same time, goes back, as far as the very early mainframes, many years, probably to the 1950s at least. And at that point in time the Edsger Dijkstra, who is an academic computer scientist, noticed that really there's an issue with fairness and potentials for race conditions and data corruption if you don't have a specific synchronization mechanism. And he wrote a paper, the original paper in Dutch, which I provided a link to, just for historical purposes, about two new operators, one called P and one called V. And there's some confusion as to what he meant by P and V, and in fact, I think over a couple different papers he changed the definition. But the basic idea was that P is Dutch prologue, for try to reduce or take, and V is verhogen for increase or give. Many RTOS's, like VxWorks, for example, still use semTake and semGive [LAUGH] as their operators. But he basically invented the semaphore with this P and V operation that he said was needed. And he suggested two different types. One is the binary semaphore, which has a value that can really just be 0 or 1. And this is critical, binary semaphore, for example, is available in the VxWorks RTOS. I just pick on VxWorks because I used that for this course prior to Linux. And it's limited to 0, 1, and if you make a call to the P function and it's currently 0, it causes the call in execution context, thread, task, whatever it is, to wait. And if you call it when P is 1, it does not, but it reduces the value of P to 0. So it either decrement S by 1, and blocks the caller if S is, really should probably say less than equal to 0, otherwise S equals S minus 1 and the caller continues. Well, I guess if you call it with 0, then S would be less than 0, right? So because you try to decrement it. And V is considered a signal or a give, and it increments S by 1. And the block callers are unblocked from S, and they wait on that semaphore in FIFO order. So in a queued order, and it's really that simple. This is still probably one of the most useful methods of synchronization, especially between interrupts and a scheduled context for tasks or threads. And you really want it to be binary, because if the semaphore is given repeatedly or multiple times, it stays at 1, it maxes out at 1. It's clamped at 1, lots of different ways to say that. It doesn't keep increasing, but there is also used for, as he noted, as Dijkstra noted, for another type of semaphore called a counting semaphore, that continues to increment if it's given over and over. And this would be more for fairness, for things like producer, consumer uses, for resources. Rather than just simple synchronization, say, between an interrupt and a task that's waiting for a request for service. Which is how we most often use a binary semaphore in real-time embedded systems. I won't say that counting semaphores aren't needed in real-time embedded systems, because certainly any place you have, Producer, consumer needs. It could definitely be useful, but generally it's not used as much in my experience. So this binary summary four is very important. The other thing that's very important is a mutex, and a mutex really is not a semaphore. A mutex is a lock, so it's best to call it a mutex lock. That's the most correct terminology. However, [LAUGH] many people call a mutex, a mutual exclusion. Feature a mutex semaphore, is that wrong? Well, that requires some explanation. So it turns out that historically, Dykstra also looked at the mutual exclusion problem, which is needed when you have multiple readers and writers. Executing code that needs to be put in what we call a critical section, which we talk about in this third course on a mission critical system design, and which we use in the first 2 courses in this series. Real time embedded concepts, and also in the real time embedded theory analysis, but so far critical sections, you need this mutual exclusion lock. And the reason it's best described as a lock is it's like a hotel key or a gas station bathroom key where you really want it keyed to that critical section, that resource. And you really only want one thread or by analogy, one person in there at a time. And so the reason it's more of a lock or a key as you may wish to look at it, is because, it is keyed to that critical section, right? There is one and only one mutex for the critical section that is used by all threads or tasks for it to be correct. Now, the reason some people will say that a mutex is a mutex, semaphore, an that is the case with VX works. They actually have Sam, B create. Sam M create. And Sam C create. As you'll see, coming up. Linux does not have it. This is VX works, as VX works just to give you a comparison. Is because, Dykstra himself and others showed that you could implement a mutex, making use of a binary semaphore, right, as a primitive to help construct it. So, and there's the confusion. [LAUGH] So as a result, sometimes a mutex is referred to as a semaphore, is that correct? Technically, no, it's really a lock because of the semantics of a mutex, and it can be implemented with test and set lock. In atomic testing, set lock, either instruction or assembly code sequence. It also causes typically any color that blocks on the mutex to block in Fifo order. Most often that's default, but VX works for example has scheduling priority order and priority inheritance order. It could use priority ceiling, but it has priority inheritance scheduling and Fifo order or VX works. Now, to add to the confusion, there's all sorts of other locks that you might have in addition to binary counting, semaphore, and mutex locks. Including Spinlocks, these are actually often used in embedded systems, so this is basically a busy wait, and it would consume all CPU if it's a true busy wait. But these also can be turned into what are called condition variables. Which busy wait but with some amount of yielding of the CPU, so condition variables I will say can be useful for embedded systems. When I've had to use them, I've created my own by essentially creating a spinlock with a delay inside it. But Linux does have condition variables, spinlocks, and then there's a final class called the monitor. This is probably mostly of academic interest, but it's a mutex combined with a condition variable. So that covers the history and gets you up to date and clears up maybe issues with terminology that we might otherwise have. So for us, just keep in mind that we really want to need a binary semaphore. You may need a counting semaphore, but not real likely in real time embedded systems, and you'll definitely want a mutex. Lock, so let's move forward down. Just give a comparison, since in this series of courses, our goal is to give you a practitioner's background in all three of these platforms, Cyclic Executives, RTOS and OS with real time extensions. But focusing on Linux as I've stated for convenience, logistics and because it is growing rapidly as an embedded system platform. So for VxWorks, you can see you have a large variety of semaphores and in fact as I stated the MUTEX is called a semaphore whether that's correct or not. So there's a little note down there. So you in the semaphore library you have semBCreate for Binary MCreate for MUTEX, Ccreate for counting and the basic operations are take and give. And I've got the links down here for the documentation, for example from windriver if you want to look at it in more detail, or perhaps you already use VxWorks. There's also a pthread library and in VxWorks 6.X and earlier, and I'm not completely up-to-date on the history on this, but our class last used VxWorks 6X. There's taskLock and intlock as well, so you can think of this as enabling, disabling interrupts and enabling and disabling the scheduler, right, and that would be used only in kernel space. So I haven't listed the equivalent on that in Linux because our assumptions that we're going to work in user space rather than kernel space tasks. And in for example, VxWorks, the SMP version of VxWorks, you have barriers, spin locks, message queues, and signals. You actually have message queues in all versions of VxWorks, so the amp as well. Message queues are quite handy and they're a way around MUTEX, which we discuss in more detail. And then of course, VxWorks has condition variables in the pthreadLib and things like that, so it's pretty fully featured. So RTOS is often really make sure you have what you need for synchronization and lots of options. Linux gives you a more generic semaphore, so the generic general semaphore that Linux provides, which is POSIX compliant by the way. You initialize it, you post and you wait and there's variations on it, like a timed wait where you can time out. And it's a counting semaphore, so this is really counting. So the interesting thing is, can you use it as a binary semaphore? Well, yes, but carefully [LAUGH] so it will count by nature, and so if it's given multiple times, it will increment above one. So what you'd have to do is likely wrap this inside something like a MUTEX and have logic to check that it doesn't go above one, or something creative like that. I'm not exactly sure why Linux doesn't just provide a binary semaphore option or POSIX for that matter. I actually have taken that as a note to myself to look into that more, but this is the case. This is what's generally available as a counting semaphore. For the most part, we use it in the series of courses as if it's a binary semaphore, and generally that's okay as long as you don't give it more than once. And so for any kind of real mission critical system you would want to wrap that and make sure it's a true binary semaphore that it can't exceed one. And for locks, we use the pthread MUTEX lock and unlock, and there's all sorts of variations on this, so look these up. What I suggest is if you do man minus K and you just do pthread and MUTEX and then just leave the rest off, you'll see all pthread MUTEX manual pages. You can do the same thing like sem underbar or something like that for semaphores. There's quite a few API calls in operations that you can do. There certainly are barriers in Linux, there are spinlocks. There's POSIX signals we actually use in this course, and we certainly use all of these pthread MUTEX operations and all of these semaphore operations as well in the class. Generally we don't use condition variables, but you could, so they're there and that gives you an overview of the two. If you're working in a cyclic executive, you really don't have a thread or tasking or process execution context here. Fusion context is limited to either your main loop or interrupt service routines, right. So if you're running say on the Texas Instruments MCU that I've given as examples, there is ARM assembly code to implement a semaphore. So you might be implementing your own simple executive or RTOS, right, writing your RTOS, [COUGH] or perhaps you're working with something like free RTOS. And essentially this sequence allows you to, this assembly code sequence that I reference here in number one, you can just go look at that on the ARM limited developer website, gives you the equivalent of a semaphore. And there also are on some microprocessors test and set lock instruction. I don't believe that's true on ARM, you have to write a small assembly code sequence, but some architectures actually have an instruction for that or there's going to be assembly code. And the question is how much you really need one because you don't have a task or thread execution contexts. So more likely you're going to use things like int, disable, and enable in a ACE masking and unmasking interrupts. You certainly use busy wait in a cyclic executive, right. And then you make use of interrupt vectors and enable disable masking, etc. And then if you want to support something higher level, like your own RTOS, then you would implement assembly code to create a semaphore that could be used in scheduling context. So hopefully that clears up any questions you might have about methods of synchronization with Linux using a Linux OS with real time extensions and comparing that to an RTOS and a cyclic executive. Thank you very much.
