How Operating Systems work

[Jadzia]

I've been thinking quite a bit about operating systems this past week, and how one might go about creating one.

Not that I'm likely to attempt this, but I would like a better understanding of how it can be done.

I began thinking about filesystems, designing my own, then reading in more detail about FAT32 and others, and making comparisons, and seeing what details I've overlooked.

Then I began thinking about threading, and how a processor might manage several applications held in memory, and allow them to run simultaneously.

Then I began thinking about graphical user interfaces, and this is something I'm struggling to figure out.

I've made a rudimentary gui before now, that resembles Windows, but it didn't do more than display widgets on forms, while the forms themselves could be dragged about the screen, and have their Z-Order changed when they gained focus.




What I was stuck with was this: Suppose we have a window. We can draw things on it's surface (eg, using GDI), so the window must have a bitmap associated with it to paint onto that surface.

But wouldn't that have to be a screen sized bitmap, as there's no reason why the window couldn't be resized fullscreen? So would that window's existence consume a megabyte or two of memory therefore, to hold such a large bitmap?

Win95 happily worked with 8MB of memory, but I never felt as though that memory was saturated from having a few windows open.

 

[Lindley]

I don't know how it's typically implemented on an OS level, but on the client level at least, the system keeps a record of which parts of the window are "valid". When you drag a window, the window's own content can just be moved around directly with no special processing; but when you cover part of it, that information becomes "invalid". Then when that portion of the window is exposed again, it must be redrawn, and it is the responsibility of the client program to handle the draw operation.

This is why, for instance, in gtk+ you should redraw your window by using the gdk_window_invalidate_rect() function to explicitly invalidate the entire thing, rather than forcing a redraw yourself.

However, these are all concerns of a GUI library, which is not of direct concern for OS development. At most, perhaps the OS could support a message-passing framework which a GUI library could be built on, but the OS should not interject itself too heavily into the GUI arena directly.

 

[Jadzia]

I don't know how it's typically implemented on an OS level, but on the client level at least, the system keeps a record of which parts of the window are "valid". When you drag a window, the window's own content can just be moved around directly with no special processing; but when you cover part of it, that information becomes "invalid". Then when that portion of the window is exposed again, it must be redrawn

Is that just dirty rectangles?

and it is the responsibility of the client program to handle the draw operation.

Does that mean there is no bitmap attached to the window unless the client program explicity creates one?

Does that mean that GDI cannot draw to all forms? Only ones with bitmaps attached to them?

 

[Lindley]

Is that just dirty rectangles?

That probably means the same thing, yes.

Does that mean that GDI cannot draw to all forms? Only ones with bitmaps attached to them?

GDI (or whatever GUI framework you're using) has a responsibility to manage the drawing of all widgets. For some widgets, it may make sense to store a bitmap to be redisplayed when necessary; for others, it may make more sense to recompute every pixel on the fly. Still other widgets may have 'client areas' for which the GUI framework can do nothing except invoke a callback to the client program to draw that region----and again, the choice of drawing a stored image or creating it on the fly is passed on here.

I want to reiterate that while GUI frameworks are fascinating things, they should not be tightly coupled to the OS, but rather should run on top of it using a minimal but complete set of OS services as support.

 

[Robert Maxwell]

Operating systems begin with the kernel. What about the kernel?

A few points:

The rectangle for your window shouldn't be any larger than its size on the screen. If you're going to resize it, I think your best bet is to make a new surface of the desired size and blit to that, destroying the old surface at the same time. (This is assuming it is less expensive to destroy and redraw a surface than to actually resize the original surface.)

Most graphics toolkits seem to have an automatic paint loop that looks to see if any parts of the window need to be redrawn, based on Z-order and rectangle overlaps. It's obviously not an exact science, as I've seen many programs where the screen does not repaint after an overlap until you give the window focus again, or it doesn't repaint unless you move the window around--in short, you have to do something to trigger the repaint call if the program (or the toolkit it uses) is not good about doing it automatically.

This whole idea of storing separate bitmaps for each window is a (relatively) recent invention made possible by larger video memories. I think the old versions of Windows did everything by just directly blitting the rectangle of the current window, automatically covering up anything it overlapped. And I doubt it was ever storing the full bitmap of any window anywhere, beyond the full screen bitmap kept in the video memory itself.

ETA: I am not much of a GUI designer or tinkerer, this is just what I've gathered from screwing with GTK, Tkinter, pygame, and the like, and it may not be 100% right but I tried.

 

[YellowSubmarine]

Does that mean there is no bitmap attached to the window unless the client program explicity creates one?

Does that mean that GDI cannot draw to all forms? Only ones with bitmaps attached to them?

Drawing of windows can be implemented in many different ways. It depends on how the graphical toolkit communicates with the underlying graphical unit where the window is being drawn. It can be a library that allows you to draw to certain parts of the screen, it could be a socket where you can send drawing commands or it can be a shared memory where you write the image directly (or a combination of the three), but the graphical unit can limit you however it wants.

I believe the most common case would be this: Programs (i.e. graphical toolkits) can draw anywhere on the screen, but aren't supposed to, they are told where they can draw, and are also told when they need to redraw some part because something drew over them. A common extension to that approach would be to ask the toolkit to draw its windows on a off-screen buffer from where the graphical unit will redraw them back on the actual screen buffer thus removing the need for redrawing (and the associated flickering effects that this causes) when the window gets covered with something, and would allow things like window transparency implemented in the graphical unit.

 

[RobertVA]

Among the things you have to consider is that the Operating System handles the interaction between programs, the user and the hardware (screen, keyboard, mouse etc). Everything you type goes through the OS before the OS makes that data available to the program. Same for all your mouse/touch pad clicks and movements. Whenever a program wants to display something it tells the OS what it wants to display and the OS generates the bitmaps on the monitor.

Moving the mouse or typing something generates an "interupt" which is the computer equivalent of tapping the shoulder of a busy person. The OS keeps track of which program is displayed on which screen pixels and routes the input to the appropriate program. In many respects an element of the user interface (like a command button or text entry box) is treated the same as a program.

Sometimes the OS's display services extend to more complex functions like menus and dialog boxes. Ever notice how similar the "Save As..." dialogs are in Windows Paint and Windows Notepad? That's because they are the same dialog, generated by code that's part of the OS. The program merely calls the OS's function library and supplies a few simple facts like the the file types listed at the bottom of the dialog. Some programs, like Microsoft Office, substitute their own "Save As..." dialogs to supplement the generic functions in the OS's dialog. Even with the custom dialogs the OS supplies the code to generate and support user interface items like command buttons (OK, Cancel), text entry boxes, drop downs and check boxes. When the program requests a user interface element it needs to supply the code to be executed when the OS reports the user used the element.

Earlier OSs like Apple's ProDOS and MS DOS/IBM DOS lacked many of these complex services. They were primarily an interface for standardizing the use of storage devices like floppy and hard disks. Text input and display was handled by code in the computer's Read Only Memory and was primarily a scrolling format resembling an old paper output Teletype. The ROM function's few enhancements over the Teletype included the ability to move the insertion point around the screen, permitting a few simple text based imitations of the graphical interfaces appearing on the early Macs. All graphic mode functions had to be coded in the actual program or in a few common code libraries that had to be installed with the program (often a game) or the disks that came with a graphic card.

 

[JarodRussell]

Why would one want to program a OS from scratch?

 

[Lindley]

Sometimes the OS's display services extend to more complex functions like menus and dialog boxes. Ever notice how similar the "Save As..." dialogs are in Windows Paint and Windows Notepad? That's because they are the same dialog, generated by code that's part of the OS. The program merely calls the OS's function library and supplies a few simple facts like the the file types listed at the bottom of the dialog. Some programs, like Microsoft Office, substitute their own "Save As..." dialogs to supplement the generic functions in the OS's dialog. Even with the custom dialogs the OS supplies the code to generate and support user interface items like command buttons (OK, Cancel), text entry boxes, drop downs and check boxes. When the program requests a user interface element it needs to supply the code to be executed when the OS reports the user used the element.

Earlier OSs like Apple's ProDOS and MS DOS/IBM DOS lacked many of these complex services. They were primarily an interface for standardizing the use of storage devices like floppy and hard disks. Text input and display was handled by code in the computer's Read Only Memory and was primarily a scrolling format resembling an old paper output Teletype. The ROM function's few enhancements over the Teletype included the ability to move the insertion point around the screen, permitting a few simple text based imitations of the graphical interfaces appearing on the early Macs. All graphic mode functions had to be coded in the actual program or in a few common code libraries that had to be installed with the program (often a game) or the disks that came with a graphic card.

In my opinion, Windows makes a mistake by linking so much of the GUI interface directly to the OS. A GUI interface to an OS should be written on top of the OS, but should not be tightly coupled to it unless there is a performance reason to do so.

Now, it certainly does make sense to provide common libraries (possibly even at the kernel level) for programs to leverage OS features, and these are welcome to include things like Save As dialogs. Apple's "Core Image", "Core Audio", etc are good examples of how this can be done.

Why would one want to program a OS from scratch?

There's always value in understanding such things better. I didn't take it myself, but I know that if you take the Operating Systems class at Carnegie Mellon University, you will have programmed a simple OS before you pass.

 

[Jadzia]

This whole idea of storing separate bitmaps for each window is a (relatively) recent invention made possible by larger video memories. I think the old versions of Windows did everything by just directly blitting the rectangle of the current window, automatically covering up anything it overlapped. And I doubt it was ever storing the full bitmap of any window anywhere, beyond the full screen bitmap kept in the video memory itself.

Right, that would make sense. If there is a bitmap, GDI draws to the bitmap and is permanent. If there is no bitmap, it draws into the screen buffer, so that drawing will be lost if that part of the screen has something dragged over it.

In Visual Basic, all forms can be drawn on, and each form has a boolean property called AutoRedraw, which must determine if a bitmap is attached or not, and that must work something like I've written above.

Whether it's a screen sized or window sized bitmap may depend on whether the form is Fixed Size or Sizable.

GDI (or whatever GUI framework you're using) has a responsibility to manage the drawing of all widgets. For some widgets, it may make sense to store a bitmap to be redisplayed when necessary; for others, it may make more sense to recompute every pixel on the fly.

Okay. This was something I was also thinking about yesterday -- do widgets also have their own bitmaps, or are they redrawn on the fly? It makes sense that some things do and some things do not, weighing time taken vs memory used.

Font rendering seems like a difficult one -- it would be slow if done on the fly, or memory consuming if the label in every button/label/etc is stored as a bitmap.

I want to reiterate that while GUI frameworks are fascinating things, they should not be tightly coupled to the OS, but rather should run on top of it using a minimal but complete set of OS services as support.

Understood. When I say OS, I'm meaning something more complete.

A common extension to that approach would be to ask the toolkit to draw its windows on a off-screen buffer from where the graphical unit will redraw them back on the actual screen buffer...

So that would be a bitmap for the whole window complete with widgets, not just the form's drawing surface?

...would allow things like window transparency implemented in the graphical unit.

Yes, I can imagine how window transparency would complicate things, and create a need for these bitmaps.


It all seems very complicated! I doubt most really appreciate just how much brainwork has gone into operating system development (and GUIs).

 

[Robert Maxwell]

To be fair, one should not confuse a GUI with an operating system, as you can have a fully functional OS with no GUI at all.

As for the value of writing an OS: I think it's a useful and worthwhile learning experience. You quickly realize how much of operating system design is based on tradeoffs. Should it be fast or reliable? Should process handling favor giving all programs equal time or give more resource-intensive programs a wider berth? How do you efficiently manage memory without impacting system performance?

Personally, I'm far more interested in things like memory management, device drivers, interprocess communication, and the like. Those are the parts of operating systems that pique my interest.

 

[Jadzia]

Personally, I'm far more interested in things like memory management, device drivers, interprocess communication, and the like. Those are the parts of operating systems that pique my interest.

We can talk about these things if you like. This can be your thread as well

Would I be right in thinking that you prefer micro over monolithic kernel architectures?

I think I'd be more inclined to design a monolithic kernel. My reasoning is like I mentioned in my game thread: I started programming with procedureless imperative languages, and from that I've come to see high level languages as a slightly abstracted form of assembler. After all, the processor just sees an endless stream of code, so by keeping the kernel code in a single bundle, we maximise the control we have over it. The challenge is then to make it do everything we need it to do.

 

[Lindley]

I favor microkernels for a very simple reason: they only require one part of the kernel to do one thing, and limit interactions between kernel components to public interfaces. This greatly facilitates testing and debugging, by avoiding the possibility of "spaghetti dependencies" developing inside the kernel.

 

[Robert Maxwell]

Yeah, I'm also a fan of microkernel designs. I'm all about modularity.

There's also the whole kernel space/user space debate, as in what things should be in each and where do you draw the line between the two? Then you get into things like user-mode device drivers. How do you take something that must inherently touch the kernel--a device driver--and sandbox it so it can't break the rest of the OS, while allowing the hardware to be used for its intended purpose?

File systems are also kind of fascinating because they all make specific tradeoffs for disk efficiency, access performance, and write performance.

 

[Jadzia]

Then you get into things like user-mode device drivers. How do you take something that must inherently touch the kernel--a device driver--and sandbox it so it can't break the rest of the OS, while allowing the hardware to be used for its intended purpose?

I have this crazy idea that drivers should remain the same and that the hardware should adapt to the software.

File systems are also kind of fascinating because they all make specific tradeoffs for disk efficiency, access performance, and write performance.

When I was designing my filesystem, I had a side thought about blocksizes and how disk space is often wasted, either because blocks are too big (wasted sectors) for efficient storage of lots of small files, or blocks are too small (overhead waste) for efficient storage of a handful of large files.

We tend to have both extremes on our hard disks: a few movies and myriads of small program files.

What I thought about was a filesystem with split block sizes. It can begin with small 512byte blocks. Then at some later sector there is a merge point, where blocks are doubled up to 1024bytes, and so on. Being multiples of binary it should be not too hard to merge or bisect blocks when we need more or less of one size, and we move that merge point forward or backward.

Knowing the positions of these merge points, sector numbers could easily be calculated from the block address.

There's more details to work out for this however.

 

[Robert Maxwell]

There are some file systems that can intelligently use the "wasted" cluster space by storing small files. In fact, you could do this fairly efficiently by setting things up this way:

* Use a default cluster size, such as 2, 4, or 8KB.
* Your primary file table should list the clusters associated with each file. It will be assumed that the file takes up the entirety of each cluster, unless the cluster's table record says it only goes up to a certain number bytes in the cluster. Generally speaking, this should only be the case for the last cluster in a file.
* Have a secondary file table for all files smaller than the default cluster size. Keep an index of all the clusters that are only partially used, and store the smaller files in that "slack" space, tracking which cluster the file is in, what its offset is from the start of the cluster, and how many bytes long it is.

This should make storage and retrieval of small files very efficient, though you'd have to manage your tables and indexes carefully to avoid clobbering data on either side of it. I think there would be some performance sacrifices caused by all this, but you'd be able to eke more storage out of your disk.

 

[Bill Morris]

For making a new OS, I think the general feeling is that the world doesn't need a new filesystem, and making one should be your last priority. You will have to support at least one existing system anyway, and you have to be able to transfer files to be handled by your new system at an early stage. So just using existing code and supporting something early on seems reasonable, even though humanoid nature has a programmer all hot to make something original.

For the GUI, I read years ago that Microsoft's philosophy was to make the background responsible for refreshing itself as you moved a window, even though programmers prefer to grab a memory bitmap of the whole screen, blit a square just size of the window at its current location, use that to erase the window, then redraw your window or (better yet blit a saved memory bitmap of it to the new location).

Even if following the rule of placing the burden on the background, you wouldn't do that for things to move within the window. The particular application would do its own thing there. And supposedly so would drag and drop of an icon's ghost between windows.

Maybe Microsoft has changed that and starting using the smoother and more reliable double buffering we use with games, etc. I don't know.

I do know that for a jigsaw-puzzle app, you have to use a combination of the two. When a piece is being dragged, it's erasing by laying down a small square of the latest version of the background bitmap, but when the user picks up a piece, everything but the piece is redrawn and a new background bitmap is taken before the piece being picked up is drawn. And that piece may have to be rotated. If the application first strews the pieces at various angles then straightens a piece when it's first picked up. Either way, a small memory bitmap is taken of the piece when it's picked up, to be used to as the "masked-blit" source for dragging. The reason that the whole thing is redrawn at pickup is that the priority table for all the pieces changes, since the piece to pick up might have been partially covered and must move "through" any overlaid pieces. And only a complete refresh can accomplish that properly.

For the style of a GUI, I would first point out a problem with the existing desktop paradigm. If you have Microsoft Word open twice and want to copy some text from one to the other, the program wastes so much screen space there's hardly anything for the user to work with. You end up docking one window whether you want to or not before you can access the other. Top and bottom, each window has over 2 inches of frame that gets in your way.

So the windowing GUI I would suggest would look a lot like TrekBBS, with a thin frame at the top, bottom, and left of a window, with a vertical menu bar at right, where menus would only cover that bar when open. I would also eliminate the scroll bars and replace them with a scroll ball at bottom right of a window.

Then I would have window tile vertically rather than be resizable and moved around the screen. There would be a vertical program-selection bar at the left of the screen, and any open window would get the full width of the screen minus the width of the program bar, making the aforementioned thin frame possible, since don't need the part at the top used for dragging a window or the parts use for resizing.

That means you have more workspace per window, don't have windows being docked against your will when you work with more than one at a time, and don't have to carefully resize and arrange windows on the screen when you want to drag and drop or copy and paste between two or three windows.

And suppose you have two iterations of Notepad open on Windows with the same file and you are using one of them to write down information you get over the phone. You might at some point save and close it, forgetting and leaving the other open. Later, when you decide to close the other, you had better not save it, because you'll be destroying information you had recorded and saved. A new OS and GUI should rein in that booby trap. Programmers of some applications know about that problem and don't let it happen with their software.

 

[Lindley]

And suppose you have two iterations of Notepad open on Windows....

This is one reason why I don't like Windows' approach of treating two instances of the same executable as completely distinct. There are occasionally reasons why doing that would make sense, but it would be nice if they made it easier to detect that the same file was opened twice so you could warn the user.

 

[Jadzia]

I happen to like Windows' approach of treating two instances of the same executable as completely distinct.

I don't see this as a problem; the user just needs to think about what they're doing. The alternative is far worse in my opinion: where the software believes you don't know what you're doing, tries to force you to do something else, or does things behind your back without your knowledge.

This particular "problem" could be resolved by having the application remembering the datestamp of any file that is opened or saved.

LastKnownDateStamp := DateStamp(filename)

So if you later click "save", the application checks to see if the datestamp has changed since the file was last opened/saved by this instance of the application, and puts up a message box... something like this:

IF LastKnownDateStamp != DateStamp(filename) THEN
Result = MessageBox ("This file appears to have been updated by another application. Are you sure you want to overwrite it?", "Save (Overwrite)|SaveAs...|Cancel")
END IF

IF Result = 1 THEN filename = DisplaySaveAsDialog()
IF Result = 2 THEN filename=""
IF filename != "" THEN SaveTo(filename)

 

[Lindley]

The alternative is far worse in my opinion: where the software believes you don't know what you're doing

First rule of programming: Always assume the user doesn't know what they're doing. Or rather, always assume the user could be acting maliciously and defend against it.

Always validate user input and, when appropriate, user credentials. On the programming side, always practice data abstraction and hide implementation details behind minimal but complete interfaces, to minimize the number of ways things can go wrong and reduce complex operations to a set of simple, intuitive interactions.

tries to force you to do something else, or does things behind your back without your knowledge.

Certainly the primary goal is to provide a good user experience, so any "hidden" operations or decisions should be made in support of that goal, not against it.