8. Quick Review

8.1. Basic Operating System Concepts

The operating system is an example of system software. The primary role of an operating system is to manage the computer’s resources. This includes both physical (hardware) resources and abstract resources.

As a computer runs, it is either executing user level processes or the kernel of the operating system. Application programs run with the CPU in user mode, while the OS kernel runs with the CPU in supervisory mode. In user mode, the CPU is restricted in terms of what instructions will execute and what memory addresses may be referenced. No restrictions are placed on the CPU when it is in supervisory mode.

The mechanism that forces a context switch from running user code to running the operating system is an interrupt. Hardware interrupts invoke device handlers in the OS. Software interrupts are special assembly language instructions issued by application programs to invoke system calls. A trap interrupt is issued by the CPU in response to some error. Interrupts allow the operating system’s kernel to execute. The kernel itself, may be interrupted by another interrupt. The interrupted handler must be scheduled to finish later. This feature is called re-entrant interrupt handling.

The major components of an operating system are: process manager, memory manager, file system manager and I/O manager.

8.2. Process Management

The process is one of the fundamental concepts of operating systems. A process is an instance of a program in execution. A process consists of a set of memory addresses to hold data and instructions, the set of resources allocated to the process and a Process Control Block (PCB) to hold the properties of the process. Processes are created by another process (the parent) issuing a special system call to create a child process. When an operating system boots, the kernel starts one user process. All other user processes are descendants of this one process.

The operating system provides processes an abstract or virtual machine, which is the illusion that each process is the only process on the computer. Multiprogramming allows multiple programs to reside in memory at the same time and switches execution sequentially between the active processes.

Processes are said to have a state related to what is currently happening with the process. One process may be running on each CPU of the computer. While I/O operations are being performed, the requesting process is in a waiting state. Also in a waiting state are processes that are waiting for some resource to become available. Processes that are available to run are in the ready queue.

The task of selecting which process from the ready queue will run next is called CPU scheduling. The goal of CPU scheduling is to pick processes such that the computer appears to the users to be very fast. This requires that the scheduler be fair, efficient and also recognize the needs of different types of processes. An interactive process, such as using a text editor, is characterized by short service times and is said to be I/O bound because it spends most of it’s time waiting for I/O. These processes must have priority over background processes that are CPU bound because they need to execute a large number of calculations. Non-preemptive scheduling algorithms wait for processes to voluntarily leave the running state before scheduling another process while preemptive scheduling algorithms will sometimes stop a running process to allow other processes a chance to run.

First-come, first-served is a non-preemptive scheduling algorithm that is fair, but it does not recognize that small/interactive processes should have a higher priority than compute bound processes and thus it does not have very good performance. Shortest job next has better performance, but it has the pit fall of potentially causing starvation. Starvation occurs when a process is unfairly delayed because other, higher priority processes continually demand service. Round Robin is a preemptive scheduling algorithm that has good performance and is also fair. With round robin, each process is given a short time quantum before it is interrupted by the computer’s hardware clock. Thus round robin is fair but still gives interactive processes quick service. In practice, round robin with multiple priority queues are used by modern operating systems.

An important, recent extension of the classic process concept is the multi-threaded process. A process with multiple threads has a separate execution engine for each thread. The individual threads of a process share some data and resources. The shared data includes: the heap, global data and instructions. The stack data is unique (not shared) for each thread in the process. On most operating systems, threads require less overhead to create than a process and the shared data between threads makes communication and coordination between threads fairly easy.

8.3. Synchronization

Whenever processes or threads share data, there is a need to synchronize access to the data. The operating system itself is a heavy user of synchronization concepts and correct implementation of synchronization primitives, such as semaphores, requires supervisory CPU permission, thus it is necessary that the operating system implement and provide synchronization services to the processes.

For some problems, it is fairly difficult to correctly use synchronization such that the data is always protected and deadlock (failure to make progress) is avoided. Fortunately, there exists a large number of classic synchronization problems with known solutions. When developing a multi-threaded program requiring synchronization, it is best to relate the problem to one of the classic problems and use the known solution for that problem.

8.4. Memory Management

The memory addresses that each process uses to reference its memory is called the logical address, while the physical address refers to the actual memory of the computer. The CPU’s memory management unit does the address translation between logical or virtual memory addresses and physical addresses. The paged memory management scheme, where the physical memory is divided into relatively small frames, and a table is used to translate logical memory addresses to physical addresses, is used in modern operating systems. An extension to paged memory is demand paging with virtual memory. In this approach, a back-up copy of the memory is held on the hard drive. When memory is in short supply, some areas of memory may be removed from the RAM memory. If memory is requested that is presently not in physical memory, a trap interrupt known as a page fault occurs and the OS’s page fault handler is invoked. The operating system must find room for the missing page (frame), load it into memory and update the process’s page map table before the process may resume. Too many page faults to the point degraded performance is called thrashing.

The task of finding a location for the memory page is called page replacement. Pages which have been modified would need to be copied to the hard drive before they could be used, so those slots are less desired. Whether or not a page has been modified is tracked with a dirty bit. Ideally, the page which will not be used for the longest period would be replaced, but since we don’t know the future, we rely on statistics to help us estimate which page will likely not be needed again soon. From studying memory usage by processes, we have the principle of locality, which tells us that the memory most likely needed in the future is the same memory that was recently accessed. The least recently used (LRU) page replacement algorithm is the most commonly used algorithm. Here, we track when the last time a frame was accessed and use the one that was the longest time ago.

Page faults may be reduced by allocating an optimal number of memory slots to each process. If a process does not have enough memory slots, then it will incur a large number of page faults. If too many slots are allocated to a process, then memory is wasted, which would be better used by other processes. The working set algorithm dynamically adjusts the number of memory slots allocated to each process.

8.5. File Management

The concept of the file is one of the most widely used abstracts with computers. Physically, the hard drive is an ordered collection of blocks of data. However, the user of the computer sees a file system consisting of a directory tree and individual files. Modern file systems, such as Unix inode and Windows NTFS, contain a data structure for each file that lists its name, owner, modified times, access permissions, size and the ordered list of data blocks for the file. These file systems use an indexed approach to tracking the data blocks as opposed to the linked approach, which was used by older file systems, such as the DOS file allocation table (FAT) file system.

In most cases, the files are sequentially accessed. The alternative to sequential file access is direct or random access where files are viewed as set of records, rather than a sequential byte stream. Direct access file systems are often used with data base systems.

Since the time to move the head of a disk to the correct track on the disk is the slowest part of a computer, it is important that file systems use efficient disk scheduling algorithms. First come, first served is fair, but has horrible performance. Shortest seek time first can suffer from starvation because the head can linger in one region while requests in other regions are un-fairly delayed. The SCAN disk scheduling algorithm is the most commonly used. It works in a similar way as an elevator because the head move back and forth servicing read or write requests as it moves. The worst case delay with SCAN will not be longer than the time needed to move from one side of the disk to the other and back again.