Gresham College Lectures

Operating Systems

June 01, 2022 Gresham College
Gresham College Lectures
Operating Systems
Show Notes Transcript

Early computers were either designed to do one thing or, if they were programmable, they would be loaded-up with the program, it would run, and then a new program would be run. But a modern computer gives the appearance of doing multiple things at once. 

This lecture shows that in reality it is a supreme juggling act and, like a plate-spinning act, should be accompanied by The Sabre Dance amazement and applause.

A lecture by Richard Harvey

The transcript and downloadable versions of the lecture are available from the Gresham College website:

Gresham College has been giving free public lectures since 1597. This tradition continues today with all of our five or so public lectures a week being made available for free download from our website. There are currently over 2,000 lectures free to access or download from the website.


- You're sitting at the keyboard ready to write your magnum opus, all is quiet. Just the calm of the blank page in front of you, your computer waits unobtrusively like a sort of electronic Jeeves, ready to leap into action should you command something. But underneath that impassive exterior lies a maelstrom of activity hidden from view, an intricate command and control structure, a sort of electronic court of Versailles, scurrying around making sure the computer can do its business and you, the user are treated like Louis XIV, all that hassle and bustle, the stuff that makes your computer work smoothly. That's what we call an operating system. If you prefer something a bit more prosaic, then I refer you to that radical magazine, "The Beano", in which the human brain is portrayed as having an interior full of little workers, beavering away and solving various cognitive problems. They're called the Numbskulls. And it's quite a good analogy I think of the operating system as we know it today, of course, early computers didn't have operating systems at all. And this picture, which shows Grace Hopper, one of most famous programmers of all time sitting at the terminal of UNIVAC, which was an early, early computer system. I talked about it in previous lectures actually. And what this illustrates very nicely is what is now known as the open shop system. So the idea really is that the computer designer, the programmer and the user in those days were pretty much the same person and programming computer sort of involves sitting in front of one of these complicated consoles and flicking switches. There wasn't a high level programming language, and there wasn't anything to make your job easy. You flick these switches and you ran the thing. And if the computer stayed up because they weren't the most reliable things, you got an answer at the end of it. You, the user had sole use of the machine, and this continued quite a way actually into the early life of computers. There's a paper by George Rick man talks about the IBM 701, which was an early computer that they'd had installed commercially where he worked and what they discovered that these computer thingies were really popular with a whole range of people. So there was a lot of people queuing up to use the system. Well, literally queuing up as it turned out. So the way they managed this demand was they split the open shop into 15 minute slots. So you, the programmer had 15 minutes to go on the computer and he sat there and made some notes on how people used the machine and discovered somewhat to his horror that roughly 10 minutes of the 15 minutes was spent faffing around, setting up the tapes and dealing with the output. So of your 15 minutes, you only got five minutes of run time, which was far from ideal, particularly as the IBM 701 had a meantime between failures of three and a half hours. So I assume it was highly likely that you would get into the open shop and discover that it wasn't open at all. So that was sort of pre-operating systems history. And the number of operating systems that could have gone on this timeline is wildly and crazily long. So I only given you a flavor of what you've got. I'll give you a link later to a full list of operating systems and their histories. But if we sort of slide along this timeline over on the left hand side, basically we've got systems which are trying to make available a single, very expensive resource, the computer, to as many people as possible. So that's the demand over there on the left, this commercial demand really, you've got a big, expensive capital asset and you want to work it as much as possible. And then as we slide over to the right to the present day, machines cost nothing. You know, the cost of the central processing unit, the CPU is negligible pence. So what we're really trying to do here apart from some rather modern issues to do with security and reliability and so on, what we're probably trying to do is more, the other way round, we're trying to give a single user access to as many machines as possible so that we can get their work done as quickly as possible. So it's a quite an interesting sort of swing across the, from many users one machine, to one user multiple machines, although in practice, of course it is multiple users and multiple machines. Now trying to put some sort of structure around operating systems history is not so easy because there've been a number of false starts and operating systems have come and gone as it happens, I'll show later quite a few have gone, but there've been a few big winners in the worlds of operating systems. In order to try and structure those ideas. I've just nicked a table from one of the operating systems experts, well, former expert pair, Per Brig Hansen, and he wrote this book sort of classic operating systems, which is a sort of collection of best papers in operating systems. Great read if you fancy it, sort of it's the of computer scientist version of "Pride and Prejudice" or "Barchester Chronicles" perhaps. And what he's trying to do here is pick out some phases in operating systems and some ideas that are of interest. So this table actually is pretty much chronological. So we start at the 1950s with the idea of this open shop. And in the sixties comes this idea of closed shop processing and the closed shop means the machine room isn't open to the likes of you and me. There's only a few high priests who are allowed into the machine room and we would write our programs on a remote terminal or dumb terminal. We might punch some tape or punch some cards. They would then be stacked up in a batch and run through in a batch and so that's the idea of tape batching, even when you got this batch of jobs to do, you've still got this interesting problem, which I'll come onto in a moment, which is which job should you run first then? Hmm. Should you run the longest job first or the shortest job first? Hmm. Interesting question, isn't it. And it needs a bit of thinking about, it's not quite so obvious. So that takes us through to the sort of early sixties. And then in the 1960s, there was a bit of a sort of buzz and we have moved to what you might think of as a sort of modern view of an operating system, which Per Brig Hansen has called multi programming here. But it's the idea here is that we're trying to give an impression of being able to run multiple jobs. So having a computer that can do more than one thing at once, maybe handle more than one person at once, which takes us through to time sharing. That's the 1970s, really. And then he's picked out concurrent programming. That was a big issue when I was a kid in the eighties and probably a lot of it was quite rarefied and didn't happen, but some of it has been picked up, and I'll talk a little bit about that later when I talk about the cloud. I'm not going to say too much about personal computing in this lecture. I've completely not talked about the graphical user interface, partly because there are other lectures talking about GUIs, partly because well, time is always the enemy in a Gresham lecture. So I'm just going to park graphical user interfaces, and then distributed systems. And what's not on here of course, 'cause this is quite an old table, is the cloud. And all that that brings. So we ought to talk about that. So there's a little plan, but let's sort of spool back and let's spool back to the sort of initial problem that sparked this, the multi programming initiative and the initial problem that caused quite a lot of hassle for people is quite a simple one to describe. And it's the peripherals, and for a lot of computers, a lot of the problems don't come from the computing. They come from the IO getting the input and the output right. And the usual problem is that the IO is far too slow. So the computer is sort of sitting there looking at its watch, waiting for things to happen. Now, for those of you who are, oh, I dunno how old you have to be to know this. But I thought just as a blast from the past, I thought I'd show you not a very old peripheral, but I'll show you one from the late 1970s, just looking at the physical audience. Yes. Quite a few people in the physical audience who might recognize this, online audience, this is what a printer used to look like. This is a printer from 1978 and somebody's having a go at rejuvenating it in this video. I'll just play it for you. (printer buzzing loudly) - [Man] Moving a bit crazy on the table, but it works. Yes. - Yes, a bit of a nightmare, isn't it? We used to have these things on our desks. They were unbelievably noisy and they had this absolutely rubbish print head. And this is quite a late one. You know, if you think about early peripherals, the problem was they're slow and they didn't have much memory in them. So the computer would send some small amount of information to the printer and then the printer would slowly print everything out and not, without the developments I'm talking about, there was nothing to do. So the computer would essentially sit there, running no ops through it, no operation. So it would just sit there. And it was pretty obvious early on that this was very inefficient. So a solution sort of presented itself quite early on and the solution was to have the computer do something else when it was in a wait state waiting for the IO. And this is an important concept in operating systems and it leads onto all sorts of other things. And the idea that was generated is called a context switch. So you can think of this a bit like this on the top line, let's imagine this is your user program running here. I've called it process one, and then we're going to get a signal. And the signal is usually called an interrupt, an interrupt is a signal to the computer to interrupt what you are doing. And then we're going to try and switch across to process two. And as we do that, we're going to save the state of process one into a program control block. Then we're going to load the state that is appropriate for process two, that's called a program control block. We're going to switch across, and then we'll switch back again when we're finished. So the program control block varies a lot from operating. Well, it can vary a lot. It varies from operating system to operating system. There is design decisions about what you need to save, but in essence, what you normally save is where am I in the program that's running and the state of the central processing unit as you were, as you have an interrupt. So that would be all of the registers, all of the local memory and so on. And then it comes to switch back. So all very simple. This time here down the bottom, which I've labeled Delta T is often called the process switch latency. And you obviously want that to be as fast as possible. So you try and design your computer so that you can save this PCB as quickly as possible. So there's lots of, sort of, what's the word, sort of maneuvering by hardware designers to make sure that this switch happens as quickly as it can be. And indeed software engineers, one of the maneuvering is to try and minimize the amount of stuff that we have to save in the PCB. So we could perhaps save a little bit less in which case, instead of a process, what we might refer to as a heavyweight process, which we're going to have to save a big context. We could use a lightweight process, often called a thread, which is often a sub process. And we don't have to save quite as much if we're doing this, but this operation bump, bump, bump, bump, is fundamental to the way your computer is working. Well, there's probably one in every pocket in this lecture room at the moment, if not two. And that's your mobile phone, it's fundamental to the way the operating system works. So now let me just talk you through how it works. So let's try and use an analogy. It's afternoon and we're doing some knitting okay. So I've got my knitting pattern out here and I dunno if you're experts on knitting, I'm not, but I presume you can read the pattern and know where you've got to. So that's the equivalent of my program counter. So I'm doing knit knit, knit, knit, knit, and I mark where that I've got to on the knitting pattern and I'm going to stop now 'cause I need to make supper, which is, I dunno, Shepherd's pie in our house. So what I'm going to do pick up my knitting and put it over here on this pile over here. And that's all the instructions. Now get the ingredients for shepherd's pie. Chop, chop, chop, chop, chop, chop, chop, chop, doing that. That's me on process two, right? Wow. Wow. Baby cries. Right? High priority interrupt. That is the baby has to be fed. So we pick up all the Shepherd's pie ingredients, stack them up on top of a knitting here over here, right? That's called the stack over here in computer language then comes the baby book, feed the baby, blah, blah, blah. Baby's finished. Put the baby back, get back this, pop the stack, as we would say, finish this. Oh, I've got a bit of time spare, do some knitting, pull up the knitting, put this back. So we got this memory area over here, which is getting longer and shorter. That's the side table and that's called the stack and the computer is popping the stack as it does these context switches, all happy with that? Now, I neatly segued there from a hardware driven interrupt, which is something like a hard disk saying I need to be serviced. That's what happens there as the printer or whatever it is, probably not a printer now, but let's pick a hard disc, says, I must have your attention. That's a high priority input interrupt. It goes to the interrupt processor, which says, hmm, Is your interrupt important enough to interrupt this high priority task that I'm doing at the moment? Yes, it is. Your high priority. I'll deal with you. Or it says, yes, you can wait. It's bit like a sort of someone in a school, the guardian to the head teacher's office who says yes, yes, fire, school's burning down. Yeah okay, that sounds important enough. Could I have tomorrow's detention? I think that can wait until we've dealt with the fire or the school burning down, so the interrupt processor does all of that and gets these priorities right. You can use the same idea to drive switches from the operating system if you wish. So what most operating system will do is split that timeline into chunks. And at each one of those chunks, something called a scheduler will run. I'll talk a little bit about that later. Decide what the priority tasks are at the moment, generate a software interrupt, switch everything round. And thus each one of the users shown here are getting this rather convincing impression that the computer is servicing their every little need in a continuous fashion. But it isn't. The computer is a master juggler. Unlike humans, humans are terrible at context switching, whatever people tell you, they're not good at it at all, but computers are absolute geniuses at it. And the reason is they store everything in the stack. We don't have a human equivalent of the stack. We don't what's in our brain. So we can't write it down. This diagram also shows another feature that is not quite so evident from what I've been saying so far. And it's not essential to have this, but most modern computers would have this, which is there's a clear distinction in a modern piece of hardware usually starts at hardware level, between what we would call the instructions that can be accessed by users and the instructions that are only for the part of the operating system that does the work. And they're called protected instructions. They're not absolutely essential. I remember some sadistic professor of mine setting a homework assignment, which was to write a multi-user operating system for a processor called the Z80. I mean, this was incredibly cruel 'cause the Z80 didn't have any protective mode instructions and was frankly, it wasn't even powerful enough to run a digital watch, let alone anything else. So you can do it, but you've got to have quite a lot of cooperation with the users. And the reason is of course you don't want a malign agent up here being able to affect what's happening to this user over here. So the only way you can do that is to stop these user processes accessing various bits of the hardware. And you certainly want to stop them task switching stuff that they don't own. So alongside, I was going to say every operating system, I hate using the word every 'cause there's always somebody online who says, oh no, RTS doesn't do this. But I suspect every operating system has the idea of privilege. So there are super users and users who have certain privileges. So there's a hierarchy of what people can do. And if you don't have that hierarchy, it's a free for all and you all have to incorporate. And as we know, computer scientists find cooperation somewhat difficult, particularly when a little bit of mis-cooperation can give you more access to the valuable CPU time. Which used to be when I was a graduate student, that was a favorite trick of ours, which was to log in and adjust the scheduling parameters on our workstations so that our jobs ran a hundred percent of the time over the weekend, it was a brilliant, a brilliant game. And it probably gave me enumerable results in my PhD that I didn't have a right to have, almost certainly at the expense of research group who owned the computers. But there you go, public confession time. Now there's one other feature that was developed in this sort of rather febrile period when we're talking about multi programming and I put this next to context switching, but it's not the same, they're often confused in people's minds. So context switching is the ability to run multiple tasks at once. Now I'm going to talk about virtual memory and virtual memory is it's a portmanteau term and could refer to quite a few things. And it's not very precisely defined as a lot of operating systems are cannot precisely defined, but I'll show you some of the concepts that sit within the idea of virtual memory. So if we are going to allow users to think that they have exclusive access to the computer, it's an illusion that we're going to create with our operating system. Then we presumably have to give them a programmers model of memory. So we've already acknowledged that parts of the memory are going to have the operating system in and parts of them are going to have bits of other users code and so on, but we don't want progress. But I don't want to know what you've put operating in the computer. I just want to get on with my life. So the programmers model is shown here on the left, which is just a sort of linear block of memory. And then over on the computer side, we've got a block reserved for the operating system. We've got user one jammed in here, we've got user two, maybe jammed in here. And then we've got some spare memory over here, but this isn't the full story because most computers will have some way of managing fast memory, different from slow memory. And in the old days, slow memory was a disc, a physical disc. You know, there was a, I dunno if you remember those days, but there used to be a large lump of spinning metal in your laptop or even on your mainframe, great big thing. And it could hold a lot of data by which I mean in the early days kilobytes, but it was very slow. So the trick was to persuade the physical computer, to use some of that memory as virtual memory. And if I just add these diagrams here, so the way this is usually done is to split your memory into blocks. These are usually called pages. Some people call them segments, but let's stick with pages here. I've labeled them A, B, C, D, E, F. Obviously the page size has to be chosen carefully to fit with the parameters of your system. And that's what systems engineers do. They fiddle around with the page size, get it wrong. And you've got some performance disaster on your hand I should add. And then through this thing here, which is usually called a page table, we're going to map these out to this backing store out here. So in this case, we just have two physical pages in our quick memory and the rest are out on disc. So if somebody asks, they say, well, I want page C, please. What happens is a page fault is generated here. And the paging system goes, ah, quick, quick, they want page C. Do we have it? Do we have it? No. Right. Get it in from disc. Get it in from disc. It's like one of those sort of French farces where something horrible is happening behind the doors. And somebody sort of says nothing to see here, nothing to see here. What's actually happening is the system is just saying, I'm not ready yet. I'm not ready yet. I'm not ready yet. Go off and do something else. Interrupt. Computer goes into something else. Are you ready yet? Yes, I'm ready now. I've got it in memory. Ah, right here it is, the process of shuffling these to and fro here is usually mediated through something called a cache. So if you hear the use of the word cache, that is a another bit of memory to make the access of these lumps of disc and pages faster still. Right, nowadays, we've got a lot of RAM. And so that's the quick memory. So this paging store backing store malarkey isn't used anywhere near as extensively as it used to be. I mean, when I was a kid, kid, I mean, when I was an undergraduate, we were programming on computers made by the Digital Equipment Corporation who made a wonderful range of computers, the first group were called PDP 11, which was very extensively used in research labs. And then they moved to a system called the VAX, which ran an operating system called the VMS, virtual memory system. You know, it was a big selling point then for Deck, the VMS, and because they were expensive, they were notorious for being supplied with not enough fast store. So you were always paging stuff in and out of memory. And that takes time. You can get to a point where the amount of time you spend shuffling pages in and out in off disk actually exceed the amount of time you spend doing anything else. And that's called thrashing. And this parody of, do you recall this poem? It was by Lewis Carroll, "The Duchess". She was sort of dangling her baby and had this peculiar poem, which probably wouldn't be allowed to get away with now, called speak roughly to your little boy and beat him when he displeases you I think. So this poem was pinned on every operator's door about the nightmare of VAX paging. So now we've sort of scooted up to what is basically the modern operating system. We've got something there that is handling some of the hardware issues and it's looking like a bit like the sort of operating systems that people are familiar with. So now it'll be a good time to look a little bit more detail at an operating system. And you might say, well, how do you choose what operating system to talk about? And that's actually quite easy because nowadays, as we'll see later, there are really only two operating systems of any significance. And I've picked one that is a sort of always a hero of academics, 'cause it's been widely used in, it's widely used in universities. That's for sure. And is now widely used in a wide range of places and that's Unix. So rather than explain Unix, I will play a little video of the two inventors of Unix, Dennis Richie and Ken Thompson, who were both based at Bell Labs AT&T Bell Labs. For those of you who've been following the series, you will notice that an awful lot of things were developed at Bell Labs. And if you've got a moment do visit AT&T Bell Labs to have a look at their history timeline, it is a very surprising record of achievement. Let's have a look at what they say. - Back in 1969, a couple of computer scientists here at Bell Labs started to develop some programs they needed for their own use. What Ken Thompson and Dennis Richie started developing then has evolved into the Unix operating system, which by now is widely used around the world. - We are trying to make computing as simple as possible, in the late 1960s Dennis Richie and I realized that the then current operating systems were much too complex. We attempted to reverse this trend by building a small, simple operating system on a mini computer. But what we wanted to preserve was not just a good programming environment in which to do programming, but a system around which a community could form. Fellowship. We knew from experience that the essence of communal computing as supplied by remote access time sharing systems is not just to type programs into a terminal instead of a key punch, but to encourage close communication. The Unix system started out as a two-man effort. And by now it's used all over Bell Labs. We have close to 20,000 computer terminals in this company, roughly one per employee. And most of them are used for communicating with Unix systems. One of the main reasons that the Unix system is popular around here is because it provides graceful facilities for decomposing complex computing tasks into simple subtasks. - The Unix operating system is basically made up of three parts. The kernel or operating system proper is the part that manages the control of the machine and supervises scheduling of the various user programs, the shell, or which is the name we give to the command interpreter looks after the communication between the user and the system itself. And the third part, which is actually the largest is the various utility programs, which perform specific tasks like editing a file or sorting a bunch of numbers or making a plot. In other words, all the other programs that are not provided directly as part of the operating system kernel. - Yeah. It's good to hear those guys talk. They're incredibly important innovators in the world of computer science. Also good to hear the word fellowship. You don't hear that word said very often in a operating systems lecture apart from of course the Worshipful Company of Information Technologists who sponsor these lectures and who believe in amongst other things fellowship. So shout out to them. You also heard the word kernel there, kernel as in inner part of a nut and the analogy that they were using there was that there was this sort of inner part of the operating system that does the work. And then there's this shell which you interact with. And in fact, the first Unix shell was imaginatively called SH, S-H, stands for shell. And then there's lots of utilities, which sit on the outside of that. And that was indeed in some contrast to operating system that preceded it, which had become very bulky. Nowadays, we don't normally draw it as a series of concentric circles. You'd normally draw an operating system with the hardware down at the bottom, and then the kernel sits here. This is the main part of the operating system up here. And then these are processes. They might be system processes, or they might be user processes, difference between a system process and user process is the amount of privilege it has when it's running. Now, this diagram looks simple, but it introduces a number of sort of common concepts that we're used to in operating systems. So the first one I suppose, is at the top of this, we have standard interfaces and this is really a programmer's convenience. It's a tremendous hassle writing programs at the best of times. And if you have to rewrite them every time a user has a slightly different bit of hardware, it's a nightmare, and this is what used to happen. So you thought, well, I've got a PDP 1140, I've written my program. And then your friend would say, can I have a copy of your program? And you'd say, yeah, here you go. And he said, I've got a different keyboard. Oh, sorry, it won't work. That doesn't happen now. And the reason is because we have defined interfaces between things, it's a straight copy from electrical engineering where you have standard parts and these standard or mechanical engineering now where these standard parts fit together. So that's an important part, important function of an operating system, which is to provide a coherent programmers interface between you, the user and hardware, that could be way, way different, really surprisingly different. The other feature here is that the kernel is split into blocks and there may be some difference between operating systems and these blocks, but pretty much you would expect if I put the diagram of Windows up here you would've seen pretty similar blocks. So it's a bit like a mechanic opening the sort of the hood or the bonnet of a car, they can spot, although the air conditioning compressor looks different on a Tesla from a VW Passat, it's fairly simple to identify it by its function. And it has similar inputs and outputs and does similar things. So that's an important concept of an operating system that common blocks are labeled in a common way, which makes systems design and systems tweaking a lot easier. And we can see this just by looking, I'm sorry about the complexity of this slide, but it does come straight from GitHub. These are a list of tools for interacting with various bits of the Linux operating system. It's a bit of an open question as to whether Linux is Unix or not Unix. Most people on the family tree of operating systems say, no, Linux is not the same as Unix. And that's because Linus Torvalds, when he was writing Linux, looked at the concepts that were present in Unix and decided to rewrite them all from scratch, same command names, same structure as Unix, but completely fresh and different code under the hood. So I'm not quite sure what you would call it, sort of Unix clone I suppose, the reason for that was partly because I think Torvalds likes writing code. And if you can write operating systems, then you you've probably reached the sort of, it's the Wimbledon of programming or Flushing Meadow of programming. It's the ultimate achievement doing so, but partly because AT&T, although they'd given away copies of Unix for free to universities, it got mired into all sorts of intellectual property disputes. And then there was another version that Berkeley had produced called BSD. And some people had used that and then someone had come along and done their own version. It was getting all very confused, so he said stuff that, I'm going to do my own version of Unix, which I'm going to call Linux. That was an aside. The important thing is to look at some of these blocks here and we can see that these will be fairly standard. Again, we've got hardware-y bits down the bottom. So these are called device drivers. These are the interfaces with bits of hardware. We've got stuff over here to do with file systems, virtual file system so on, we got stuff here to do with low level and medium level communication. That's networking, the internet protocol, and then the slightly higher TCP. These are things to do with the virtual memory, the scheduler. This is something to do with how the CPUs are being used. And then up here, we've got stuff to do with users. So an important feature of operating systems is the provision of these things called libraries. And the there's a bit of a debate. No, I think it's now settled, but there was a bit of a debate running pretty much when Torvalds wrote Linux actually as to how you would best configure an operating system. So far I've been talking about what are call monolithic operating systems, where all of these things here in pink are part of the protected mode and run in super user mode. So in a way you can think of it as a sort of a cabal of developers write all of this. They don't need to check whether the file server and the device driver are compatible with each other, 'cause they go together. They're always locked together. So you can do quite fast inter process communication, but it's a big old block of stuff to write. So there's a big sort of, there was a big debate, do we actually need all of this stuff running in protective mode, hence micro-kernel and the idea behind the micro-kernel is the principle of least privilege really. Which is you should not, what is the, how little stuff can I get away with running in protected mode or as a super user. And it's really a matter of philosophy of this and like a lot of operating systems wars, it doesn't really have a right or a wrong answer. I think there is a slight interest. One of the things that intrigues me about micro kernels isn't whether one is better than the other to write or any of those things, but the micro-kernel does hold out one interesting potential, which is if you could get it small enough, then you might be able to prove that it works. People are smiling when I say that, seems a bit of a weird thing. One of the problems with modern computer systems and I've alluded to this in other lectures, is how do you know that the thing you've got in front of you is doing what it says, and it's a sort of existence proof really. And that becomes particularly important when you've got embedded systems. So I'll give you an example. Let's say we we bought a router for 5G telephony in this country, United Kingdom. Well there's three or four people who could supply that router. It's a bit of a dumb terminal. What gives it life is the algorithm that gets downloaded into the router and does its business. And that algorithm gets updated. So then the router can go from completely functioning to not functioning at all, just like that. So if the person supplying the router was from a country that wasn't friendly towards the United Kingdom, then one press of the button and all of a sudden your telephony stops working. That's software-ization, that can happen with software-ization. So, and it's a common problem in the IT industry. We are never quite sure how the thing we've got in front of us really works as maybe only one person in the world who knows how it works, right? So micro-kernel, if we could get it small enough, we might be able to do a formal proof that it is doing what it says it can do. And indeed, that it's been done. There's a micro-kernel system called L4. And there's a version of L4, I think it's either SEL4 or CEL4, which is a high assurance version of L4 that has been formally verified. I think that's the first time ever. And so that's quite a sort of encouraging thought that there is an operating system out there that we can be mathematically confident is doing what it is meant to do. Doesn't say anything about the rest of the stuff of course. So it doesn't get you out of the woods, but it's a step in the right direction towards high assurance computing. Now I've alluded to this standardization several times and this block diagram is another version of Linux. It's one that you are probably quite familiar with. It's called Android. So if you have an Android phone, it's actually a Linux kernel in there, which is a version of Unix. So if you were thinking, if you were sitting here thinking, well, I've never heard of Unix, it sounds very rarefied. I you've probably heard of Android and you've probably been using it every day. Android is a rather interesting case and I picked it because it illustrates an interesting observation about the way code is put together, which is a function of the way operating systems work. So I remember the first program I wrote for a big Windows operating system. It was for a Sun workstation, wonderful computers. And the first program you always write is called hello world. And hello world only does one thing. It prints hello world on the output. But because it's a Windows program has to add various code and that code comes from libraries. So my one line program, hello world, or couple of lines, by the time I'd finished compiling it, I had added in 130,000 lines of code. So that extra, that was the stuff to do win loading system. So the library can be very significant and you can see the problem already can't you, which is, if you add every bit of the library to your code, as you compile it, as you build it, you're going to end up with great big bulky bloated bits of code. Well, that's called static library. So the alternative is to dynamically add in the code only when you call, it's called dynamic linking. So those of you who remember windows has this thing called a DLL or dynamic link library. And of course that leads to something called DLL hell, which is the version that I linked with. Doesn't have quite the same syntax as the one that's on the operating system. So one of the ways around this is to get away from this linking to libraries altogether, and to either interpret the code as you go. So you could do that on Android. You could have Java, which is an interpreted language as a native, or you can do a quick bit of compilation before you run it called just in time compilation. So JavaScript, that's the language that runs on web browsers is an example of that. So we talked a little bit about the operating system, what it does, a bit of virtual memory, all that sort of stuff. I skipped over a bit, which is scheduling and scheduling is a rather interesting problem. You know, you've got a number of processes in your computer system. How does the computer decide how much time to give to each one? Well, there's a multiplicity of algorithms. I've just picked one, which is quite a simple one. I've picked one from an operating system called Solaris, which was developed by the Sun operating system, the Sun Microsystems, but is now owned by Oracle. And what Solaris does is it defines things. It processes as one of multiple classes, most things are assigned to the time sharing class. And each one of these things is given a priority level and the lower the priority level, the more time it is allowed to run. So the shunting algorithm goes like this. Firstly, we we're going to slice the time. So I think Solaris by default has 20 millisecond time slots. We're going to assign a thread, a priority. There's a default designation, but in most of Unix and most things you, the user can fiddle around with that if you want to. The high priority threads are going to be dealt with first, once they have used up their exceeded time, then we decrease the priority. So it's the sort of greedy algorithm in the sense that your high priority, I'll deal with you, I'll deal with you. Oh, you've run out of time, right thanks, I've had enough of you, you're lower priority now, go to the back of a queue. Now I'll take you. So a lot of these algorithms out there, but that's quite a simple one. The reason I pick Solaris is because I just wanted to alert you to this interesting class of tasks here called real time. Real time is often misused in our field. It doesn't just mean speedy. It means I must have something done within a fixed time. So people often analyze, think of an operating system as the person spinning plates. I'm sure you've seen these people. Big wobbly sticks and the plates are spinning. The plates are spinning. This plate over here is going to fall over unless I get some twist in the stick. That is a real time problem. I don't have to do it now, but I have to do it within a fixed time. I have to do that. So that's a real time problem. And there are whole operating systems devoted to the challenge of real time. I feel I ought to say a little bit about inter process communication, but not too much. Here's a problem. Let's imagine I had this variable X, which I'm going to set to zero and I've got two functions on the left here. This one reads X and adds one to it. And this one reads X and adds one to it. And this is my code, sequential code. So you can what's going to happen. I'm going to read X equals zero. Well, X is zero. Then I'm going to read it in. That's why it's in blue. I'm going to add one to it. And then I set it to one. So X goes from zero to one, I'll read it again. And X ends up as two. No problem at all. Now then let's say we put that through an optimizing compiler and it thinks, wow, well, I can run these on separate processes, right? That will make it faster won't it? So I start with X equals zero. I read it in, and I do my computation and I just, oh, hang on. This one has started before this one has written it out. That's an example of a race condition, can happen a lot in our business. You've got these multiple tasks all going on. And either you can end up with very unexpected results like this. I mean the sum was executed twice. It should be two, it's only one. And that's because something was read at the wrong time, or worse, you can end up with task blocking. So the famous sort of undergraduate example is often given here is one of the Mars missions. And it didn't last very long this, but somebody very kindly wrote it up. So it gets mentioned a lot in undergraduate classes. What happened here was the Lunar vehicle had a high priority task that really needed to run. And it was running, running, running. And no, no, let's get this right, It's the other way round, a low priority task was run. And as that low priority task was running along the low priority task had some IO that it had to do or something that blocked it. So it said, well, I'll just wait for this IO. Then high priority task comes on. I'm in charge. High priority task comes in, high priority task also needs the same IO, it's blocked because the low priority task has locked the IO. Ah, so suddenly the computer thinks, oh, well, that's blocked. I can swap that out. So it swaps out the high priority task and brings in a medium priority task because the medium priority task is higher than the low priority task. And the whole thing falls in the heap. It's called priority inversion. As an example of deadlock or locking or race conditions. They're all examples of the same thing. And quite a lot of effort has to go through operating system design to try and stop those things hurting it. Few words about the cloud, which is all computer science talks given in industry always have a large fluffy picture of the cloud. I'd like a prize for not having put a picture of a fluffy cloud in my presentation. What's happening at the moment however, is the transition from physical machines in front of you to physical machines elsewhere. And this can have quite a lot of advantages, particularly for corporations. Obviously there's a huge capital advantage because you're not buy, well, you can buy them, but very often you'll be renting them. So that can be more convenient financially. You can site the machines in places where you can get free electricity. Like Iceland is a famous place to put a server site. You can also ensure tremendous physical security with remote machines, which might not be available to you. I mean, we're giving this lecture in the city of London. I have no idea how many servers are really based in the city of London, but not many I should think. You know, why would you base them here with very expensive real estate and all sorts of issues. You base them somewhere where it's possible to give them physical security. So a lot of interest in doing this, and the sort of buzzwords are, you could offer something that software as service, probably everyone has used that, that's something like Google Docs. That's a something that runs in the cloud or running on remote sheets here. And that's everything provided by the provider. And this of course is the history where you had operators in operating rooms and they had to do everything for you. This is called infrastructure of a service. And that's where you have virtual servers in the cloud. And just for completeness, I've got a platform of service. So that's an example of things like AWS, Amazon Web Services or Azure. So those are services that you can use and integrate into your own applications. So for example, I hope I'm getting right here, but I'm sure there is a Azure face detector. So you don't need to write your own face detector. You can just subscribe to Microsoft Azure and use their face detection service in your own software. Looks like you've got a library on your computer that does face detection. And of course the advantage of that is you can have this enormous library, which you can access your leisure, right? IAS is an interesting one because when we look at the way IAS is deployed, instead of having this diagram over here, which is what your machine might look like in front of you, what you've got in the service center is a block of hardware and multiple virtual machines running here. I'd just like a point for remembering to color the kernel boxes in mustard, just a little Cluedo joke there, but each one of these is a virtual machine. And this thing here, the virtual machine manager is an operating system of operating systems. It's a sometimes called hypervisor, and it in itself might be an operating system, especially configured to run processes that are themselves operating systems. The usual choice is Unix again, or Linux to be precise. But there are others. I want to end by looking at this market share graph, which looks ever so complicated and down here are in very small font are gazillions of bizarre operating systems that no longer exist, but let's look at it. And I should point out, this is not all computers. This is just personal devices. So I'm ignoring servers. And so on servers are dominated by Linux really. And various varieties of Unix. Let's look at today, right, we've really got two things going on, haven't we, we've got this green lump here. That's windows and that's based, Windows as we know today is nothing to do with DOS and old Windows. It's to do with an operating session called OS2, which was written some time ago. And over here, we've got varieties of Linux and this and Unix, this lump here is Android. So Linux has gone from this incredibly minor share of life to this incredibly huge share of the operating system and that's Linux. This is macOS. I think macOS is an interesting project is based on a micro-kernel actually called Mac, which was a version of Unix, especially rewritten, actually it's a hybrid. It has half of it's a micro-kernel half of it's a monolithic kernel, very interesting system. And then this is iOS, which is the operating system runs on your mobile phone, a version that runs on your watch, is all Unix, and down here, we've got Windows. So from this sort of many colored spectrum over here, we've gone to incredible homogeneity. I'm not sure I have a good explanation for the homogeneity and I suspect it's highly commercial, but I think it's quite interesting that when you track back these things here, the winners are probably the creation of a tiny, tiny handful of people of whom I have talked about. Just two of course. Ladies and gentlemen, that is the end of this lecture, it's also the end of the series for me. So thank you very much for having me. I should give a shout out to my successor, who is Professor Victoria Banes, who I think will give an excellent series of lectures. And in so many ways will be so much better than me. Thank you. (audience applauds) - Professor Harvey, thank you very much. We have just a tiny bit of time for some questions. I've got a couple the online audience, and then I'll ask the in person audience if there are any questions from you. Can you explain what exactly is a kernel panic? - Oh, kernel panic. Yeah. So the answer is no, I can't exactly explain it, but, there are some things that you never want to see in your life, right. You know, there are sort of, I'm applying CPR is one of the, you don't want to hear that if somebody's saying that, it's trouble, and kernel panic is when something has badly has gone wrong in the kernel. And it can't think what to do other than to print on your terminal, kernel panic. And it's going to shut down in as best and orderly way as it can. And in the old days, that usually meant the end of your hard disc. And the reason it meant the end of your hard disc was 'cause your kernel was controlling all that memory management that I was talking about. So you've got all these pages stacked up everywhere, and they can't do it anymore, end. And your disc is now a scramble and the stuff that was in your memory may or may not be on your disc. And so there was little you could do, but turn off usually your Linux system. 'Cause it was experimental, cautiously you would turn it off and on again was the only, but usually it wouldn't turn on again. - So that was a good question. And are Unix and Linux both written in C, could they be rewritten in another language? - Yes they could. So they are both written in C. There has been a long running debate about how you should write kernels. And, well actually we talked about Per Brig Hansen, and he was an advocate I think of writing as much of a kernel in high level language as possible, as indeed we're Richie and Thompson. The truth of the matter is you usually have to write a little bit of your kernel in machine code to get efficiency. So there is no reason in principle why you cannot write operating systems in a high level language and many people have, but in practice, usually in line as it's called a little bit of it, just to get the speed, operating systems are terribly. People get very cross if the operating system is slow doing things, I still get cross myself. It's something very disturbing about a very powerful computer sitting there going, it's not loved by users. - We are at the end of Professor Harvey's last series and our provost was sadly, he was not able to be here tonight, but he would like to say a few words. We're just going to put him on the screen to talk to Professor Harvey. - Oh thanks. - Well, ladies and gentlemen, sadly, this is Richard Harvey's final lecture as the Worshipful Company of Information Technologists, professor of information technology. And because of this, I just wanted Richard to say a few words of thanks. In addition to his work for Gresham, Richard is professor at the School of Computing Sciences at the University of East Anglia, and before joining UEA in 1993, Professor Harvey was a mathematician first at Plessy Naval Systems and then Marconi Underwater Systems. And throughout his career, he has acted as a consultant for a number of international companies and as executive and non-executive directors, his research now focuses on artificial intelligence and computer vision. And recently he's been working on the field of artificial lip reading, which fascinates him because of the scientific challenge. And it allows him to debunk false claims and misunderstandings. Well Richard, your 10 years Gresham professor began in 2018, and your first series was called The Science of Information. And Professor Harvey explored some of the modern advances in computer technology from speech and text processing to machine learning and creative computers. In his second series, which was entitled The Digital State, he examined the technological developments in a variety of services provided to the public such as digital healthcare, the digital economy, cashless society, digital education, and asked what could these mean for the future? His series in 2020 was called Great Ideas From Computer Science and this included lectures on the history of computers and the internet and an introduction to algorithms and programming. The series looked at how these concepts have gone on to influence and indeed pervade our lives and our thinking. And Richard, your last series, which you've wound up so brilliantly this evening was called Six Tech Inventions That Changed the World. And this gave us a wonderful rundown of some of the most significant inventions, such as cellular telephones, GPS, and various operating systems. Richard has shown us the computer science principles behind the everyday technologies that we've all become so dependent on. Through your time at Gresham College, Richard, you've brought your considerable knowledge and expertise to a wider audience, and we are extremely grateful to you for your work. You've helped us with our new website and other technical aspects of our provision. And we really hope that in the future we can welcome you back as a guest lecturer to the college. So thank you very much, Professor Harvey, for all you've done over the last four years as a Gresham professor. (audience applauds)