Clock Interrupts

All modern operating systems have one or more system clocks. These are I/O devices of sorts (at least according to your text). While they do not read data in or write it out, they periodically issue a clock tick, which causes an interrupt. The frequency of these clock ticks can vary widely from one system to another; a typical frequency is once every 10 to 20 msec.

Like other interrupts, whenever a clock tick occurs, the CPU stops whatever it was doing and jumps to an interrupt handler. We have already encountered some of the the things that the clock tick handler has to do

• Check whether the currently running process has exceeded its time quantum, and if so, call the dispatcher
• Set the referenced bits on some or all pages in memory back to zero.
• Update statistics on run time of the current process and update other statistics on accounting and usage.

There are other housekeeping chores that the clock tick interrupt handler has to do.

It has to maintain the time of day clock. Unix systems maintain this value as the number of seconds which have passed since Jan 1, 1970. Since this is stored in a 32 bit field, this field will overflow in the year 2106, and at that time all current Unix systems will cease to function (start planning for this now!). Systems need some way of maintaining this value, even when the power is off. This is done either by maintaining a separate low-power clock that runs on a battery, or by downloading the current time from the network when the system is booted up.

Most system have events which are scheduled to occur at a particular time. We have already seen the alarm system call, in which a process can set an alarm to go off in a certain number of seconds. Several of the sample programs have used the sleep system call, which causes a process to be blocked for a number of seconds (or milliseconds on Windows systems). Many Unix systems have a page daemon which is awakened periodically to check whether there are enough empty pages in memory for page faults to happen efficiently, and if there are not, it will mark pages to be overwritten. Most systems also allow a user to schedule an event to occur at a particular time. On Unix systems, the command to do this is cron. The clock interrupt handler has to check for all of these events and if necessary, call another interrupt handler to process an event which is scheduled.

There are benefits to having clock ticks more frequently or less frequently. The obvious advantage of more frequent clock ticks is a more accurate clock. Clearly the system cannot time any event more accurately than the clock tick rate. A common exercise in programming courses is to time programs. In theory, the user can report the time to the nearest millisecond, but in practice, the times are not nearly this accurate because they cannot be more accurate than the clock tick rate. Even that is not particularly accurate, because if there are other, higher priority, interrupts waiting to be processed, it might take the system a few milliseconds to process the clock tick.

The obvious advantage of less frequent clock ticks is less overhead. Processing a clock tick takes time away from application programs.

Graphical User Interfaces

Essentially all modern operating systems use a Graphical User Interface, or GUI. A GUI has a bit mapped monitor, in which each pixel of the monitor can be accessed by the operating system. This is in contrast to a character oriented monitor, which was the norm during the 1980s. Character oriented monitors could only display characters in fixed positions on the screen. These are of course much easier to program.

GUI interfaces typically have four features

• Windows (which can be moved, shrunk, enlarged, or iconified, and can contain child windows.)
• Icons
• Menus
• Pointer (that thing that moves around on the terminal when you move the mouse)

In general, each window is the front end of a process which is running or runnable. Typically, at any given time, one window has the focus, which means that when a keystroke is entered, the value is passed to the underlying process of that window.

The classical GUI interface was developed at Xerox PARC. The first commercial implementation was on the Apple Macintosh in 1984. This was an overwhelming commercial success and received a huge amount of favorable press because up until its release, almost all computing had been text based.

At the same time, Project Athena was launched at MIT (it actually started in 1983). Predominantly funded by IBM and DEC, it developed the prototype for the modern distributed computer network. One of the products of Project Athena was X Windows, which was a GUI for Unix workstations. Today, essentially all Unix workstations, regardless of the Operating system, run X Windows. It is now generally referred to as simply X, or X11 to refer to the current version, which is 11.

Microsoft was a latecomer to the GUI world. Their command driven DOS operating system was so dominant in the PC world that they did not feel that they needed to develop GUI capabilities. Microsoft's first two attempts at a GUI interface Windows 1.0 and Windows 2.0 were commercial failures (I bet you've never heard of them). Windows 3.1 released in 1991 was their first successful GUI product, although it was nothing more than a graphical front end for DOS. Windows 95, released in 1995, was a complete reworking of the operating system and was wildly successful.

GUIs, including X, Windows 95 and its successors are event driven. Event driven programming is somewhat different from the kinds of programs that you have written so far in all of your courses. The logic is very simple, although the implementation is often messy. An event driven program displays one or more windows, tells the operating system what kinds of events it will respond to, and then has code to handle each of the possible events. Here are some examples of events.

Mouse moves
Mouse button clicks
Pressing a key
Releasing a key
Exposing a window

Typically the main portion of the program simply enters an infinite loop which senses events and for each one, it calls the appropriate function. Here is some simple pseudocode for an event driven program.

main()
{
   DisplayWindow();
   SetUpEventMask(); /* tell the os what events the program
                        will respond to */
   while (true) {
       GetNextEvent();
       ProcessEvent();
   }
}

MouseMoveEventHandler() { ... }
KeyDownEventHandler() { ... }
etc.

It is important to remember that events are asynchronous; they can occur in any order, and in general, they are processed in the order that they are received.

A GUI system always has an extensive array of graphics calls, which allow the user to draw lines, text etc. in a window. Graphics on a GUI system is fairly complicated because in general, the programmer cannot make any assumptions about the size of the window. Usually the user can change the size of a window as well as the aspect ratio (the ratio of width to height), and it is up to the programmer to make sure that whatever is being displayed in the window looks reasonable no matter what the dimensions of the window.

Although there are some conceptual similarities between these two windowing systems in that they both use very similar concepts of event driven programming, there are also some major design differences.

One major difference between X and Microsoft Windows programming is the all of the X code runs in user space, completely independent of the operating system, while Microsoft Windows code is an integral part of the operating system. There are thousands of Win32 APIs, and less than 200 Unix system calls, and the reason for this is that all of the GUI calls are APIs in Windows, but not in Unix.

Another major difference between X and Microsoft Windows is that X is designed for a distributed system while Microsoft is not. With X, the window for an application can be running on a different computer than the process itself. To use terms that you will become more familiar with later, there is an X server on a particular machine, which displays windows; and clients, which are processes which may be running on different machines, which establish a connection to a particular X server.

X Windows is much more flexible than the Windows GUI. X allows a user to choose among various window manager programs. A window manager is a program which runs on the X server and is responsible for displaying the windows. There are a number of different window managers, each of which has a slightly different look and feel.

Here is a link to a web site which discusses the concept of a window manager and has links to many of the common ones. Read the introduction. It's short.

Students often ask me why we still use text based I/O in our lower division courses. The answer is the even the simplest hello world program in Windows or X is extremely complex. Although this course will not ask you to actually write a GUI program for either X or Window NT, we will discuss how this programming works and show some short samples.

Programming X Windows

It is possible to write an X Windows program at a number of different levels.

• Xlib The Xlib library contains functions for creating windows, and drawing text and graphics in them. Almost no one programs at this level, because the higher levels have library routines to handle this much more efficiently.
• Xintrinsics aka the XtToolkit This introduces the concept of a widget, which is a usually a window and the events to which it responds. Examples of widgets include labels, buttons, menus, scrollbars, and text entry areas. There are also manager widgets that control the layout of other widgets.

  Although the XtToolkit is written in C, it is object oriented. Widgets are classes; the implementation details are generally hidden from the user, and they often define fairly complex behaviors. There is even a class hierarchy in which widgets can inherit features from more elementary classes.

  Responses to events are called callbacks. It is possible to write a program using the the XtToolkit with no callbacks. It would display one or more windows, but it wouldn't do anything else. The programmer is responsible for writing callback routines which specify what the program should do in response to specific events.

• Motif This is an example of a higher level toolkit with more sophisticated widgets, like pulldown menus, file selection boxes.etc. Motif defines a common ``look and feel'', although the developer is free to modify this. (much more so than MS-windows or MacOS).

Here is a short example of an X Windows program. It displays a window with two pushbuttons, labeled Hello and Quit. When the user pushes the Hello button, a popup window appears with the default appearance for a popup window (three buttons, labeled OK, Cancel, and Help). When the user presses the Quit button, the program terminates.

/* an X demo program.
   It creates a toplevel widget and four additional widgets.
   A RowColumn widget holds the two buttons.
   There are two PushButton widgets, "Hello" and "Quit".   
   Pushing the hello button causes the fourth widget, a
         PopupDialog to appear.
   Pushing the Quit button terminates the program.
   On Solaris, compile like this gcc prog1.c -lXm -lXt
*/
#include <Xm/PushB.h>
#include <Xm/RowColumn.h>
#include <Xm/MessageB.h>

void message_callback(), quit_callback();
int main(int argc, char *argv[])
{
    Widget       toplevel, manager, hello_button, quit_button;
    XtAppContext app;
    
    toplevel = XtVaAppInitialize(&app,"Demo1",NULL,0,
               &argc, argv, NULL, NULL);

    manager = XtVaCreateWidget("manager", xmRowColumnWidgetClass,
               toplevel,NULL); 

    hello_button = XtVaCreateWidget("Hello",
               xmPushButtonWidgetClass, manager,NULL);
    XtAddCallback(hello_button, XmNactivateCallback, message_callback,
               NULL);

    quit_button = XtVaCreateWidget("Quit",
               xmPushButtonWidgetClass, manager,NULL);
    XtAddCallback(quit_button, XmNactivateCallback, quit_callback, NULL);

    XtManageChild(hello_button);
    XtManageChild(quit_button);
    XtManageChild(manager);
    XtRealizeWidget(toplevel);
    XtAppMainLoop(app);
    return 0; /* we never get here */
}

void message_callback(Widget w, XtPointer client_data, XtPointer call_data)
{
    Widget message_box;
    Arg args[3];
    XmString xmsg;

    char *msg = "You have pushed the Hello Button";

    xmsg = XmStringCreateLocalized(msg);

    XtSetArg(args[0],XmNmessageString,xmsg);
    message_box = XmCreateInformationDialog(w, "info", args, 1);
    XmStringFree(xmsg);
    XtManageChild(message_box);
    XtPopup(XtParent(message_box), XtGrabNone);
}

void quit_callback(Widget w, XtPointer client_data, XtPointer call_data)
{
    exit(0);
}

The function XtAppMainLoop() is the library function which contains an infinite loop to respond to events. Each widget class has predefined the events to which it will respond. The function XtAddCallback adds a callback routine to a particular widget.

Windows GUI Programming

The Microsoft approach to software development is to tightly couple the programming with the operating system (Windows 95, Windows NT or whatever). The advantage of this approach is that the user can quickly develop fairly powerful applications which do very sophisticated things without much programming, but the disadvantage is that all portability is lost. Also, the learning curve to write even trivial applications is fairly steep.

Windows programming can be done at two levels: programming in C with the Windows Application Program Interface (API), and programming with the Microsoft Foundation Classes (MFC). The latter is a set of classes which build on the Windows API.

Code using either of these methods does not look much like the code that you have developed so far. For example, there is no concept of a controlling terminal, so you can't use the I/O library functions like printf, scanf (or cin and cout in C++). There is not even a function called main() (at least not in any code that the programmer writes; main is hidden in one of the API calls). The entry point for a windows program is a function named WinMain; this function creates a window and then enters an infinite loop. This loop receives events (called messages in Windows terminology) and acts on them. Events include such things as moving the mouse, hitting a key, depressing a mouse button, releasing a mouse button, or messages from the operating system to resize the window. The actions which are called in response to events are called callbacks. There are about 200 message types; here is a list of the ten most commonly used.

WM_CHAR	A character is input from the keyboard
WM_COMMAND	The user selects an item from a menu
WM_CREATE	A window is created
WM_DESTROY	A window is destroyed
WM_LBUTTONDOWN	The left mouse button is pressed
WM_LBUTTONUP	The left mouse button is released
WM_MOUSEMOVE	The mouse pointer is moved within the window
WM_PAINT	The window needs repainting (because it was resized
	or because part of it had been covered by another
	window and has become exposed
WM_QUIT	The application is about to terminate
WM_SIZE	A window is resized

The user writes callback code which is invoked by each of the various messages, and this is the essence of windows programming. As events occur, they are put in a queue, and the main loop of the the program retrieves these messages and acts on them according to these functions.

The Microsoft Foundation Classes (MFC)

The Microsoft Foundation Classes are a set of some 200 classes which place an object-oriented wrapper around the Windows APIs. Consistent with the OO philosophy, everything is a class. For example, there is an application class CWinApp and your application is a class derived from this. There are several window classes, such as CFrameWnd, and your windows are classes derived from these. MFC makes heavy use of inheritance, and all classes fit into a class hierarchy. The root of this hierarchy is the class CObject.

Here is a simple (Ha!) program which uses MFCs. Notice that there is no obvious entry point (i.e., no function called main or WinMain) and no obvious flow of control.

// When the user depresses the left mouse button, the
// program draws the coordinates of the pointer location
// on the screen.
// Unfortunately, the window is cleared whenever it
// is resized, covered, or minimized

#include <afxwin.h>
class CMyApp : public CWinApp
{
public:
    virtual BOOL InitInstance();
};

class CMyWindow : public CFrameWnd
{
public:
    CMyWindow();
protected:
    afx_msg void OnLButtonDown(int flags, CPoint point);
    DECLARE_MESSAGE_MAP();
};

CMyApp myApp;

BOOL CMyApp::InitInstance()
{
    m_pMainWnd = new CMyWindow;
    m_pMainWnd->ShowWindow(m_nCmdShow);
    m_pMainWnd->UpdateWindow();
    return TRUE;
}

BEGIN_MESSAGE_MAP (CMyWindow, CFrameWnd)
     ON_WM_LBUTTONDOWN()
END_MESSAGE_MAP()

CMyWindow::CMyWindow()
{
    Create(NULL, "My First Window Application");
}

void CMyWindow::OnLButtonDown(int flags, CPoint point)
{
       CClientDC dc(this);
	   char s[32];
	   sprintf(s,"[%d %d]",point.x, point.y);
	   dc.TextOut(point.x, point.y, s);    
}

I/O in Windows and Unix

Windows

A key component device management in Windows systems is the Plug and Play manager. Plug and Play (PnP) is a combination of hardware and software support that enables the operating system to recognize and adapt to hardware configuration changes with little or no intervention by a human. New devices can be added (or devices removed) without the awkward configuration changes required by earlier systems. For example, a user can dock a portable computer and use the docking station keyboard, mouse and monitor without making manual configuration changes.

We can contrast this with earlier PC operating systems in which the process of adding a new device was a little tricky. After installing the device driver, it was usually necessary to reboot the system, and sometimes set some dip switches. Occasionally two different devices would attempt to use the same interrupt request line, with disastrous results.

With PnP, when a change in devices occurs, the operating system will automatically determine the resources needed by the device (i.e. I/O Ports, IRQs (Interrupt Request Lines), DMA channel, and memory allocation) and make the appropriate assignments. It can even dynamically load the appropriate device driver. If two devices request the same IRQ, The PnP manager will automatically resolve the conflict.

This leads to another feature of modern device management. The old model of a computer with a single bus has been replaced by a much more complex, multiple bus system. Compare Figure 1.6 on page 19 of your text with Figure 1.12 on page 31 of your text. An operating system with PnP will build a device tree at boot time, and update this as needed. Here is an example (copied from the Microsoft Device Driver Development Kit Help pages).

For example, many systems now have a SCSI (Small Computer System Interface) Adapter. This is technically a bus rather than just an adapter, since several different peripheral devices can be attached to this at the same time. The transmission rate is faster than the standard serial or parallel ports.

SCSI has been around for a while. A newer I/O external bus standard is the Universal Serial Bus (USB). Like the SCSI, this allows numerous (up to 127) peripherals to be connected through one port.

I/O in Unix

In most Unix systems, devices are made to look like files. They are opened with the same system calls and read and written with the same system calls. All of the information about devices is in a directory named /dev. Here are some of the files in a typical linux directory along with a description.

/dev/fd0	Floppy disk
/dev/hda	First IDE disk
/dev/hda2	Second partition of first IDE disk
/dev/hdb	Second IDE disk
/dev/ttyp0	Terminal
/dev/console	Console
/dev/lp1	Parallel printer

It is possible to open a particular device directly and read from it using our standard system calls.

The following snippet of code opens the floppy drive on my linux box and reads the first sector (sectors are 512 bytes). Subsequent calls to read would read subsequent sectors.

fd = open("/dev/fd0",O_RDONLY);

n = read(fd,buffer,512);

Linux allows users to install a device driver on the fly, without rebooting the system. Deadlock

Recall that one definition of an operating system is a resource allocator. There are many resources that can be allocated to only one process at a time, and we have seen several operating system features that allow this, such as mutexes, semaphores or file locks.

Sometimes a process has to reserve more than one resource. For example, a process which copies files from one tape to another generally requires two tape drives. A process which deals with databases may need to lock multiple records in a database.

In general, resources allocated to a process are not preemptable; this means that once a resource has been allocated to a process, there is no simple mechanism by which the system can take the resource back from the process unless the process voluntarily gives it up or the system administrator kills the process. This can lead to a situation called deadlock. A set of processes or threads is deadlocked when each process or thread is waiting for a resource to be freed which is controlled by another process. Here is an example of a situation where deadlock can occur.

Mutex M1, M2;

/* Thread 1 */
while (1) {
   NonCriticalSection()
   Mutex_lock(&M1);
   Mutex_lock(&M2);
   CriticalSection();
   Mutex_unlock(&M2);
   Mutex_unlock(&M1);
}

/* Thread 2 */
while (1) {
   NonCriticalSection()
   Mutex_lock(&M2);
   Mutex_lock(&M1);
   CriticalSection();
   Mutex_unlock(&M1);
   Mutex_unlock(&M2);
}

Traffic gridlock is an everyday example of a deadlock situation.

In order for deadlock to occur, four conditions must be true.

• Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available. (Two processes cannot simultaneously control the same resource or be in their critical section).
• Hold and Wait - processes currently holding resources can request new resources
• No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.
• Circular wait - Each process is waiting to obtain a resource which is held by another process.

The dining philosophers problem discussed in an earlier section is a classic example of deadlock. Each philosopher picks up his or her left fork and waits for the right fork to become available, but it never does.

Deadlock can be modeled with a directed graph. In a deadlock graph, vertices represent either processes (circles) or resources (squares). A process which has acquired a resource is shown with an arrow (edge) from the resource to the process. A process which has requested a resource which has not yet been assigned to it is modeled with an arrow from the process to the resource. If these create a cycle, there is deadlock.

The deadlock situation in the above code can be modeled like this.

This graph shows an extremely simple deadlock situation, but it is also possible for a more complex situation to create deadlock. Here is an example of deadlock with four processes and four resources.

There are a number of ways that deadlock can occur in an operating situation. We have seen some examples, here are two more.

• Two processes need to lock two files, the first process locks one file the second process locks the other, and each waits for the other to free up the locked file.
• Two processes want to write a file to a print spool area at the same time and both start writing. However, the print spool area is of fixed size, and it fills up before either process finishes writing its file, so both wait for more space to become available.

Return to the course home page