• Primary goals of an operating system:
• To make the computer system convenient.
• To use the computer hardware in an efficient manner.
• Main components of a computer system:
• Hardware
• Operating system
• Application programs
• Users
• An operating system functions as a resource allocator on the computer system, as some form of control program or central government.
• There is no universally accepted definition of what is part of the operating system and what is not. It is generally accepted that it is the only program running at all times on the computer, while everything else is an application program.
• Short historical review of operating systems and types of computer architecture:
• Simple batch systems: there is no interaction between the user and the job while it is executing; jobs that are similar are batched together and run as a group; the CPU is often idle; and uses spooling as a mechanism to print out the information when the job has finished, therefore using the disk as a buffer for reading as far ahead as possible and storing the output until the moment when the output devices are able to accept them.
• Multiprogrammed batch systems: there is now a job pool that makes it possible to perform scheduling; multiprogramming increases the CPU utilization by organizing jobs in such a way that the CPU always has one to execute; the operating system now has to make decisions for the users for the first time ever; after selecting a job from the job pool, it is loaded into memory and run, which requires some form of memory management.
• Time-sharing systems: multiple jobs are executed by the CPU switching between them, although the switches happen so often that users may interact with each program while running; computer interactivity; an on-line filesystem must be available; the concept of a process is born, to refer to a program that is loaded into memory and is executing; virtual memory is used as a way to allow for the excution of a job that may not be completly in memory.
• Personal computers systems: hardware costs decreased in the 1970s; I/O devices changed from switches and card readers to display screens, mice and keyboards; personal workstations.
• Parallel systems: there is a trend toward multiprocessor systems, systems with more than one processor that share the computer bus, the system clock, and even the memory and peripheral devices quite often; there is an increase in throughput, although it is never equivalent to the amount of processors on the system (i.e., adding one more processor will not necesarily double the trhoughput); there is an increase in the overall reliability, with the systems becoming more fault-tolerant; distinguish between symmetric multiprocessing (each processor runs an identical copy of the OS) and asymmetric multiprocessing (each processor is assigned a specific task), which can be a consequence of either hardware or software design.
• Distributed systems: unlike in the case of tightly coupled systems (i.e., parallel systems), the processors do not share memory or a clock, each processor having its own memory instead, therefore being called loosely-coupled systems or distributed systems; they provide resource sharing between separate sites, some computation speedup, higher reliability and better communication between the programs so they can exchange data.
• Real-time systems: used when there are rigid time requirements on the operation of a processor or the flow of data (i.e., processing must be done within the defined constraints); divided in two main types (hard real-time systems, which guarantee that critical tasks complete on time by setting bounds to delays, and soft real-time systems, where a critical real-time task gets priority over other tasks, and retains that priority until it completes).

• The hardware must provide appropriate mechanisms to ensure correct behavior.
• The CPU and the device controllers can execute concurrently, therefore competing for memory cycles. To ensure orderly access to the shared memory, a memory controller may be present.

• The bootstrap program must locate and load into memory the operating system kernel, which then starts executing the first process (for example, init) and then waits for some event to occur.
• When an event occurs, there is an interrupt from either the hardware of the software: the hardware by sending a signal to the CPU via the system bus, usually; the software via a system call.
• Each interrupt has a service routine associated with it, which is responsible for dealing with it.
• Once the CPU is interrupted, it stops whatever it is doing at that time and it transfers execution to a given memory location, which is where the service routine is located.
• The particular design of the interrupt mechanism depends on the architecture itself.
• Since there is a limited amount of possible interrupts, a table of pointers to interrupt routines (which is stored in low memory) is generally used. This table contains the addresses of the service routines for the different types of interrupt that could occur.
• The interrupt architecture also saves the address of the interrupted instruction.
• Other interrupts are normally disabled while an interrupt is being processed, although some architectures allow for one interrupt to be processed while another is being taken care of.
• Modern operating systems are interrupt driven: the system will be sitting in idle until an interrupt (or a trap) occurs, at which point the hardware will transfer execution to the kernel.

• A device controller maintains some local buffer storage and a set of special-purpose registers. The device controller is responsible for moving the data between the peripheral devices that it controls and its local buffer storage.
• Two main types of responses to I/O interrupts:
  • Synchronous I/O: the I/O operation is started and, when completed, control is returned to the user process. This can be accomplished either via a special wait instruction that idles the CPU until the next interrupt, or by means of a wait loop if they do not have such instruction.
  • Asynchronous I/O: control is returned to the user process without waiting for the I/O operation to complete. In this case we need a specific system call to allow the user program to wait for I/O completion as well as a device-status table containing an entry for each I/O device together with information about its current status. Finally, since other processes may also issue requests to the same device that is being used, we also need a wait queue to be implemented.
• Direct memory access or DMA is used for high-speed I/O devices: once we set up buffers, pointers and counters for the devices, the device controller transfers an entire block of data directly to or from its own buffer storage to memory without any intervention whatsoever by the CPU.

• Main memory is the only large storage area that the processor can access directly. That is where the programs must be in order to be executed.
• The CPU uses a sequence of load and store instructions to specific memory addresses in order to interact with the memory.
• For a more convenient access to I/O devices, many architectures provide memory-mapped I/O, which are ranges of memory addresses set aside and mapped to the device registers.
• Since memory access can take several CPU cycles, modern architectures have added fast memory between the CPU and the main memory (i.e., a cache).
• Overall structure of magnetic disks:
  • They are form by disk platters with a circular shape similar to that of a CD, disposed one on top of the other around a spindle in the middle that allows for rotation.
  • A read-write head flies above each surface of every platter, and this head is attached to a disk arm which moves all the heads together.
  • The surface of a disk platter is divided into circular tracks subdivided into sectors. The set of tracks that are at one arm position forms a cylinder.
• Disk speed has two components:
  • The transfer rate is the rate at which data flows between the drive and the computer.
  • The positioning time (also called random access time) is the time to move the disk arm to the desired cylinder (i.e., the seek time) as well as the time it takes for the desired sector to rotate to the disk head (i.e., the rotational latency).
• A head crash happens when the head damages the magnetic surface of the disk.
• A disk drive is attached to the system by a set of wires called an I/O bus. The actual operation to transfer data, on the other hand, is carried out by the controllers:
  • The host controller is at the computer end of the bus.
  • The disk controller is built into each disk drive.
• Finally, magnetic tapes are used mainly for backup. They are kept in a spool that is wound or rewound past a read-write head, and provide very slow access times compared to the other storage devices mentioned here.

• Storage systems on a computer can be arranged in a hierarchy where the higher levels are expensive but fast and, as we move down, the cost decreases but so does the access time:
  • Registers.
  • Cache.
  • Main memory.
  • Electronic disk.
  • Magnetic disk.
  • Optical disk.
  • Magnetic tapes.
• Another issue to take into account is that of storage volatility: volatile storage loses its contents when the device is powered down.
• Cache is used to provide faster access to the information: as information is used, it is also copied into a faster storage system; the next time that we need a particular piece of information, we check the cache for it first. Due to its limited size, cache management becomes an important design problem.
• Since the same data may appear in different levels of the storage hierarchy, isues such as the coherency and consistency of the data become quite important, especially in a multiprocessor or a distributed environment.

• Since several programs may be in memory at the same time, a properly designed operating system must ensure that a program cannot cause other programs to execute incorrectly. Quite often, the hardware will trap the error and will transfer control to the operating system through an interrupt. Typically, an error message is given and the memory of the program is dumped.
• In order to provide the protection described above, we need two separate modes of operation: user mode and privileged mode (also called supervisor mode, system mode or monitor mode). Whenever a trap or interrupt occurs, the hardware switches from user mode to privileged mode.
  These days we tend to talk about user mode and kernel mode.
• The lack of a hardware-supported dual mode can cause serious shortcomings, as it was the case of MS-DOS on the Intel 8088 architecture.
• In order to avoid illegal I/O operations, all I/O instructions are usually privileged.
• When it comes to memory, the hardware provides protection for the interrupt vector itself, as well as the interrupt service routines. This is usually accomplished by determining the range of legal addresses that the program may access, which is done using a base and a limit. The operating system is the only one that can change and load these base and limit settings.
• Finally, we also need that the operating system always be in control, which means preventing an user program from taking over the CPU and running in a permanent loop. In order to accomplish this, a timer is set to interrupt the computer after a specified period and control is automatically transferred to the operating system at that point. The timer is also used to implement time sharing through the time slices as well as to compute the current time.

• Another instruction that is usually classified as privileged is the halt instruction.
• Since only the kernel is allowed to perform I/O operations, any user program will have to request it, which is done via a system call (also called a monitor call or an operating-system function call). It usually takes the form of a trap to a specific location in the interrupt vector, but it may differ from architecture to architecture. When a system call is executed, we have a software interrupt.

• All the pieces or subsystems that form an operating system have to be clearly designed with very well defined inputs, outputs and functionality in order to avoid problems. The main such components to be considered are:
  • Process management.
  • Main memory management.
  • File management.
  • I/O system management.
  • Secondary storage management.
  • Networking.
  • Protection system.
  • Command-line interpreter.
• A process is a program in execution, and will always have certain resources associated to it: CPU time, memory, files and I/O devices, among others. A process is the main unit of work in a system, and the operating system is responsible for all activities involved in process management:
  • Creation and deletion of user and system processes.
  • Suspension and resumption of processes.
  • Mechanisms for process synchronization.
  • Mechanisms for process communication.
  • Mechanisms for handling of deadlock situations.
• Main memory contains all the data that needs to be accessed quickly by the CPU and I/O devices. It is accessed by the CPU directly, unlike other storage devices. A process is executed after it is mapped to addresses and loaded into memory. Every operating system implements different memory management schemes which are usually highly dependent on the hardware design of the system they run on. Some of the most important elements of this scheme are:
  • Keeping track of which parts of the memory are currently in use and by which process.
  • Decide which processes are to be loaded into memory when memory space becomes available.
  • Allocate and deallocate memory space as needed by the processes.
• The operating system provides a logical or abstract view of the disk storage using the file as a storage unit. There are certain file management operations that any OS will have to handle:
  • Creation and deletion of files.
  • Creation and deletion of directories.
  • Support of primitives for manipulating files and directories.
  • Mapping of files onto secondary storage.
  • Backup of files on stable (nonvolatile) storage media.
• The I/O subsystem hides the peculiarities of each I/O device from the OS, leaving such knowledge only to the device drivers which are the ones that deal with the specific device. The main elements of the I/O subsystem are:
  • A memory management component to take care of things such as buffering, caching and spooling.
  • A general device-driver interface.
  • Drivers for specific hardware devices.
• While the running programs and the data they access must be in main memory during execution, they may also have additional data stored on disk. The main components of the disk management subsystem are:
  • Free-space management.
  • Storage allocation.
  • Disk scheduling.
• Network access is usually implemented as a form of file access, with all the details of the actual connection to the remote system encapsulated in the network interface's device driver.
• A modern OS with multiple users and concurrent execution of processes needs a protection system to control access to the system resources.
• Some operating systems include the command-line interpreter in the kernel, while others (MS-DOS, UNIX...) implement it as a special program.

• All operating systems provide certain services to programs and their users which make it more convenient for programmers and users to interact with the system:
  • Program execution: the system loads the program into memory and executes its instructions, then the program must be able to end its execution and exit.
  • I/O operations: in order to provide enough protection, users usually cannot access the devices. So, it is the OS itself that provides the means to perform I/O operations.
  • File-system manipulation: the OS assists programs in reading and writing files, as well as creating and deleting them.
  • Communications: sometimes a process may need to exchange information with another process running on the same or a different system. These communications can be implemented in two ways:
    • Shared memory.
    • Messag passing: packets of information are moved between processes by the operating system.
  • There is another set of operating system services that exist in order to ensure the efficient operation of the system itself:
    • Resource allocation: the operating system follows certain routines to allocate the different resources users and their processes can access: CPU, peripherals...
    • Accounting: the OS can sometimes keep track of which users use how much and what types of computer resources. This data can be used to bill the usrs or just to keep usage statistics for other purposes.
    • Protection: it should not be possible for a process to interfere with another, thererfore access to the system resources should also be controlled with security in mind.

• System calls provide the interface between a process and the operating system. They are generally availabe as assembly language instructions.
• Three general methods are generally used to pass paramters to the operating system:
  • In registers.
  • Stored in block or table in memory, and the address is then passed as a parameter in a register.
  • Pushed onto the stack of popped off it.
• System calls can be grouped into five major categories:
  • Process control: a running program needs to be able to halt its execution either normally (end) or abnormally (abort). Either way, a system call is made to terminate the currently running program. The running process may also need to load and execute a different one, in which case a system call needs to be made to save the memory image of the existing program, and then wait for the newly spawned process to end (wait time) with a signal event.
  • File manipulation: all operations to create and delete files, open, read, write, reposition or close files, as well as getting and setting the file attributes are performed via system calls.
  • Device management: when a process needs to access a device, a system call needs to be made in order to request exclusive access to it and then, when it is finished, the device needs to be released, so other processes can use it.
  • Information maintenance: many system calls just transfer information between the user program and the operating system (e.g., current time and date).
  • Communications: there are two main models to implement communication among processes:
    • Message-passing model: information is exchanged through an interprocess-communication facility provided by the operating system.
    • Shared-memory model: processes use map memory system calls to gain access to regions of memory owned by other processes.
    The message-passing model is useful when small amounts of data need to be exchanged, since there is little chance of conflicts arising. It is also easier to implement. On the other hand, shared-memory allows maximum speed and convenience, as it will function at memory speeds, but there are potential issues in the areas of protection and synchronization.

• System programs provide a more convenient environment for program development and execution. In some cases, they are just user interfaces to system calls.
• Categories of system programs:
  • File manipulation.
  • Status information.
  • File modification.
  • Programming language support.
  • Program loading and execution.
  • Communications.
• The command interpreter is perhaps the most important systems program in an operating system. It can be implemented in two main ways:
  • The command interpreter itself contains the code to execute the commands (e.g., DOS).
  • Commands are implemented as separate systems programs (e.g., UNIX).

• Due to the complexity of modern systems, it is quite normal to partition the task into small components. In this design, each module or component should have a well-defined portion of the system with clearly defined inputs, outputs and functions.
• There are two main forms to organize the system structure:
  • Simple structure (e.g., MS-DOS): where the interfaces and levels of functionality are not well separated. So, for example, the application programs are able to access the basic I/O routines to write directly to the display and disk drives.
  • Layered approach (e.g., UNIX): breaks the operating system into a number of layers, each built on top of other layers. The bottom layer (layer 0) is the hardware; the highest (layer N) is the user interface. Its main advantage is its modularity, which simplifies debugging. However, it requires very careful planning and it tends to be less efficient than other implementations.

• The hardware is the lowest level in all systems. The kernel running at the next level uses the hardware instructions to create a set of system calls for use by outer layers. Finally, the systems programs above the kernel use these system calls to access the hardware.
• Some systems also allow the systems programs to be called easily by the application programs. In this model, each process is provided with a (virtual) copy of the underlying computer. Disks, which are identical in all respects except size, are provided as virtual disks.
• The virtual machine software can run in monitor mode, since it is the operating system. The virtual machine itself can execute in only user mode. Just as the physical machine has two modes, however, so must the virtual machine. So, we end up with a virtual user mode and a virtual monitor mode, both of which run in a physical user mode.
• As a consequence of all this complexity, there is a time cost involved. However, on the other hand, there is also a complete protection of the system resources. Each virtual machine is isolated from the others.
• Java is a type of virtual machine design. It is implemented by a compiler that generates bytecode. These instructions run on a Java Virtual Machine (JVM).

• The first problem is to define the goals and specifications of the system. These can be divided in user goals and system goals.
• Mechanisms and policies should be separated: mechanisms determine how to do something, while policies decide what will be done. Policies are likely to change, so this separation will provide the required flexibility. Microkernel-based operating systems take this separation to an extreme by implementing a basic set of primitive building blocks which are almost policy-free.
• After the design, the system needs to be implemented. In old days, they were written in assembly language, but now they can also be written in higher-level languages. This means the code can be written faster, is more compact, and is easier to understand and debug, but it is also slower and it requires more storage.

• Operating systems are usually designed to run on any of a class of different machines. So, they need to be configured or generated for each specific architecture. This process is sometimes known as system generation (SYSGEN).
• Once the operating system has been generated, the hardware needs to know where to find the kernel. On most computers, there is a small piece of code, stored in ROM, known as the bootstrap program or bootstrap loader, which is able to locate the kernel, load it into memory, and start its execution.

• A process is a program in execution. A system, then, is a collection of processes: operating system processes executing system code, and user processes executing user code.
• The terms job and process are used almost interchangeably most of the time.
• The execution of a process must progress in a sequential fashion.
• Although two processes may be associated with the same program, they are nevertheless separate.
• A process usually has different components: text section (the actual program code), process counters, stack (subroutine parameters, return address, temporary variables), data section (global variables), etc.
• As a process executes, it changes state:
  • New: The process is being created.
  • Running: Instructions are being executed.
  • Waiting: The process is waiting for some event to occur (e.g., I/O).
  • Ready: The process is waiting to be assigned to a processor.
  • Terminated: It finished execution.
• Only one process can be running on any given processor at any given time.
• Each process is represented in the operating system by a process control block (PCB), also called sometimes a task control block, which contains the following components:
  • Process state: One of the states mentioned above.
  • Program counter: Indicates the address of the next instruction to be executed for this particular process.
  • CPU registers: These will vary from architecture to architecture. When the process is interrupted, this information needs to be saved, together with the program counter information, so that the process can be continued at a later stage.
  • CPU scheduling information: Information such as the process priority, scheduling parameters, etc.
  • Memory-management information: Information such as the value of the base and limit registers, page tables, etc.
  • Accounting information: Information such as the amount of CPU used, etc.
  • I/O status information: List of I/O devices allocated to the process, list of open files, etc.

• The objetive of multiprogramming is to have some processes running at all times, to maximize CPU utilization.
• As processes are started, they enter a process queue:
  • Ready queue: Processes that reside in main memory and are ready and waiting to execute.
  • Device queue: Processes that are waiting for a particular I/O device to become available.
• A process goes through the cycle until it terminates, at which point it is removed from all queues and has its PCB and resources completely deallocated.
• A piece of code within the operating system, called a scheduler, is in charge of selecting processes from these queues:
  • Short-term scheduler: Selects a new process for the CPU, doing so quite frequently (it must be very fast).
  • Long-term scheduler: Selects processes from the pool of processes that are ready to execute, and allocates the CPU to one of them (it runs much less frequently).
• In general, most processes are either I/O bound or CPU bound. The long-term scheduler should select a good process mix of both types of processes.
• The long-term scheduler may be missing in the case of certain operating systems.
• Some operating systems also have a medium-term scheduler, which removes processes from memory and from active contention for the CPU (i.e., swapping).
• Switching the CPU to another process implies saving the state of the old process and loading the saved information about the new process. This is called a context switch, which is highly dependent on the underlying hardware architecture.

• A process may spawn new processes, therefore creating a tree of process with a parent process and a child process.
• When a process creates a subprocess, the subprocess may be able to obtain its resources directly from the operating system, or it may be constrained to a subset of the resources of the parent process. This latter mechanism prevents any particular process from overloading the system by creating subprocesses out of control.
• When a process creates a subprocess, the execution could be handled in one of the two ways:
  • The parent continues to execute concurrently with its children.
  • The parent waits until some or all of its children have terminated.
• When it comes to the address space of the new subprocess, there are also two possibilities:
  • The child is a duplicate of the parent process.
  • The child has a different program loaded into it.
• In the case of UNIX systems, the fork system call creates a subprocess which is a copy of the address space of the original process. This allows the parent process to communicate easily with the child. After a fork, one of the two processes can use the execve system call to replace the process' memory space with a new program. This way, the two processes go separate ways but are still able to communicate.
• A process terminates when it finishes executing its last statement and asks the operating system to delete it by using the exit system call. At that point, the process may return data to its parent process (using the wait system call), and all of the resources that were being used by the process (virtual memory, open files, I/O buffers, etc.) are deallocated by the operating system.
• A process can cause the termination of another process via an abort call.
• In the case of UNIX, if a parent process is terminated, then all its children will be assigned to the init process as their new parent so they still have a parent to collect data when terminating.

• A process is considered to be a cooperating process when it can affected or be affected by other running processes.
• There could be several reasons why one may want to implement cooperating processes:
  • Information sharing: Allowing concurrent access to the same information.
  • Computation speedup: A task can run faster if we break it into several subtasks that, later, have to be coordinated.
  • Modularity: Dividing the system functions into separate processes to keep things better organized.
  • Convenience.
• Concurrent execution that requires cooperation among the processes requires mechanisms to allow processes to communicate with each other and synchronize their actions.

• A thread or lightweight process is a basic unit of CPU utilization, and consists of a program counter, a register set, and a stack space. It shares with other peer threads its code section, data section, and operating system resources (open files, signals, etc.). All of them are collectively known as a task.
• A heavyweight process is a task with one thread.
• A thread context switch still requires a register switch, but no additional memory-management work.
• Some operating systems implement user-level threads via user-level libraries, so that it is not necessary to make system calls.
• Threads can be in one of several states: ready, blocked, running, or terminated.
• Something to bear in mind when programming threads is that since all threads can access every address in the task, a thread can read or write over any other thread's stack.
• Without access to threads, a programmer would need to mimic the parallel structure of threads in heavyweight processes, which would end up generating an overly complex nonsequential program.
• User-level threads do not involve the kernel, so they are faster to switch among. However, any calls to the operating system can cause the entire process to wait. On the other hand, kernel-supported threads are more time-consuming, but each thread may be scheduled independently. Some systems use a hybrid approach.

• Inter-Process Communication (IPC) provides a mechanism to allow processes to communicate and to synchronize. It is implemented via a message system, which avoids the use of shared variables.
• An IPC facility provides, at the very least, a way to send and receive messages.
• Processes that want to communicate must have a way to refer to each other.
• The actual communication can be implemented in one of two ways:
  • Direct communication: Where each process must explictly name the recipient or sender of the message. A disadvantage of this method is that changing the name of a process also involves considering all these communications.
  • Indirect communication: Where the messages are sent to and received from mailboxes or ports that are shared by bother processes. It involves a way for the operating system to do some garbage collection if the processes ended and did not close the mailbox.
• There are basically three ways to implement a messaging queue (first one provides no buffering):
  • Zero capacity: The sender must wait until the recipient receives the message, so the two processes must be synchronized for the message transfer to take place.
  • Bonded capacity: The queue has a finite capacity and, when the link is full, the sender must wait until there is space available.
  • Unbounded capacity: The queue has an infinite length (at least potentially), so the sender is never delayed.
• A potential issue with the non-zero capacity mechanism is that a process does not know if the message that was sent was actually received at the other end. So, if knowing this fact is vital, the programmer has to include some form of message acknowledgment in the logic.
• A message system is particularly useful in a distributed environment, where messages are usually transferred by communication lines. In a single system environment, messages are usually implemented via shared memory.
• Regardless of whether the messaging system is functioning in a single system or a distributed environment, several exception conditions might occur:
  • Process terminates: When either the sender or the receiver terminates, there must be a way to let the other process know.
  • Lost messages: The messages being sent could get lost before making it to the other end. Using timeouts is a typical way to identify this problem.
  • Scrambled messsages: The message does arrive, but it is scrambled or corrupt. Usually, the operating system proceeds to retransmit the message. There are multiple error checking code mechanisms (checksums, parity, and CRC) that can be used to identify this problem.

• The objective of multitasking is to have some process running at all times, so that CPU utilization is maximized.
• Several processes are kept in memory at any given time.
• The actual process execution consists of a cycle of CPU execution and I/O wait. Processes alternate back and forth between these two states (they start with a CPU burst, followed by an I/O burst, then another CPU burst, etc.). Eventually, the last CPU burst will end with a request to terminate execution, rather than with yet another I/O burst. In this context, an I/O-bound program would have many short CPU bursts, while a CPU-bound program would have a few very long CPU bursts. This is important when making a decision on the scheduling algorithm to use.
• When the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is done by the short-term scheduler.
• CPU scheduling decisions happen under one of the following four situations:
  1. When a process switches from the running state to the waiting state (e.g., due to an I/O request).
  2. When a process switches from the running state to the ready state (e.g., when an interrupt occurs).
  3. When a process switches from the waiting state to the ready state (e.g., completion of I/O).
  4. When a process terminates.
• When scheduling takes place under conditions 1 and 4, it is called non-preemptive scheduling. On the other hand, when it happens under the other two, it is called preemptive scheduling.
• However, preemptive scheduling incurs a cost, since the process that was preempted may have left the data that it was working on in an inconsistent state and a second process may need to read it. So, the operating system needs to coordinate access to shared data to avoid problems. Some operating systems (e.g., most UNIX implementations) deal with this situation by waiting either for a system call to complete or for an I/O block to take place before doing a context switch, which in turn makes it difficult to support real-time computing.
• The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. Since it is invoked during every process switch, it should be really fast. Its work involves the following functions:
  • Switching context.
  • Switching to user mode.
  • Jumping to the proper location in the user program to restart that program.

• The following criteria are key when discussing different scheduling algorithms:
  • CPU utilization: We want to keep the CPU as busy as possible.
  • Throughput: The number of processes that are completed per time unit.
  • Turnaround time: How long it takes to execute a particular process.
  • Waiting time: The amount of time that a process spends waiting in the ready queue.
  • Response time: The time from the submission of a request until the first response is produced.
• The goal is to maximize CPU utilization and throughput, while minimizing turnaround time, waiting time, and response time.
• Sometimes, a system with reasonable and predictable response times may be preferable.

• Over time, a few basic scheduling algorithms have been defined:
  • First-Come, First-Served Scheduling: The process that requests the CPU first is allocated first. It is easily implemented with a simple FIFO queue. Average waiting times are quite long, and is prone to suffer from the convoy effect (when other processes are waiting for one big process to get off the CPU).
  • Shortest-Job-First Scheduling: The CPU is assigned to the process that has the smallest next CPU burst and, in case of a tie, it is broken using the First-Come, First-Served algorithm. In this type of scheduling, the average waiting time decreases, but it is quite difficult to know the length of the next CPU request.
  • Priority Scheduling: A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Process with equal priority are scheduled according to the First-Come, First-Served algorithm. The problem is that this scheduling algorithm can create starvation (i.e., a low-priority process can be waiting indefinitely for the CPU to become available). A possible solution to this problem is aging (i.e., gradually increasing the priority of processes that wait for a long time).
  • Round-Robin Scheduling: Similar to the First-Come, First-Served algorithm, it is especially designed for time-sharing systems. A small unit of time (a time quantum) or time slice is defined, and the CPU scheduler goes around the ready queue allocating the CPU to each process for a time interval up to 1 time quantum. The average waiting time is quite long, and its performance will depend on the size of the time quantum (the cost of the context switch should be taken into account when making a decision about this size).
  • Multilevel Queue Scheduling: It separates the ready queue into several separate queues, and permanently assigns processes to each one of them.
  • Multilevel Feedback Queue Scheduling: Processes are permanently assigned to a queue on entry to the system and, later, are moved between queues depending on their CPU-burst characteristics (i.e., depending on how much CPU time they use).

• The presence of multiple CPUs on the same system obviously makes the scheduling problem more complex too.
• A possible issue would be a system with an I/O device attached to the private bus of one processor. Processes that may use that device should be scheduled to run on that processor, otherwise the device would not be available.
• When several identical processors are available, it is possible to do load sharing. However, in that case we need to make sure that one CPU is not idle while the other is too busy. The common way to solve that problem is by implementing a common ready queue.
• In some cases, a master server processor is the one that makes all scheduling, I/O and other system decisions, while the other processors only execute code. This is called asymmetric multiprocessing.

• There are two types of real-time scheduling:
  • Hard real-time: Required to complete a critical task within a guaranteed amount of time. This requires that the scheduler know exactly how long each type of operating system function takes to perform.
  • Soft real-time: Requires that critical processes receive priority over other processes.
• Either way, we need to allow system calls to be preemptible. This can be done by inserting preemption points in system calls that take a long time which check to see whether a high-priority process needs to be run. Alternatively, the whole kernel can be made preemptible.

• Different criteria can be used to make a decision as to which CPU scheduling algorithm to use. We can use different evaluation methods to make an informed decision:
  • Deterministic modeling: It takes a particular predetermined workload and defines the performance of each algorithm for that workload. It is fast, but it requires too much knowledge to be truly useful (one must know the exact numbers for input, as well as the answers).
  • Queuing models: Since we can determine the distribution of CPU and I/O bursts, we could describe the computer system as a network of servers where each server has a queue of waiting processes and, knowing the arrival and service rates, we can compute the utilization, average queue length, average wait time, etc.
  • Simulations: They involve programming a model of the computer system in different software data structures, and then running a simulation. This a very complex and expensive task.
  • Implementation: Write the actual algorithm and test it. It is a very costly approach, and one must make sure that the environment is a realistic simulation.

• Running multiple cooperating processes (i.e., processes that share a logical address space and/or data) on the same system may lead to problems to coordinate them.
• When several processes access and manipulate the same data concurrently, and the outcome of the execution depends on the particular order in which the access takes place, we encounter what is called a race condition. To avoid its negative effect, we need to guarantee that only one process at a time can manipulate the variable counter. In turn, this requires a synchronization of the processes.

• A critical section of code is that which can only be executed by a single process at any given time. Each process must request permission to enter this section, which is implemented via an entry section.
• A solution to the critical section problem must satisfy the following three requirements:
  1. Mutual Exclusion: If a given process is executing this critical section, no other process is allowed to do so at that very same time.
  2. Progress: The selection of which process will be allowed to enter the critical section cannot be postponed indefinitely.
  3. Bounded Waiting: There must be a bound on the number of times that other processes are allowed to enter their critical sections after another process has requested to enter it too.
• There are two-process solutions to this problem, which involve only two processes and can be implemented via three main algorithms:
  • Allowing both processes to share a common integer variable turn initialized to 0 (or 1), so that if the value of that variable is one or the other the process is allowed to execute in its critical section or not. The problem with this approach is that it does not satisfy the progress requirement, since it requires strict alternation of processes.

• In the case of a single processor environment, we can solve the critical path problem by disallowing interrupts when a shared variable is being modified. However, this is not feasible in the case of multiprocessor environments. Several machine architectures provide special hardware instructions that allow us to modify or swap the content of a word atomically.
• The Test-andSet instruction is executed atomically (i.e., as one uninterruptible unit). So, if two Test-and-Set instructions are executed simultaneously (each on a different CPU), they will be run sequentially in some arbitrary order.

List of resources not associated with the book, but that may be useful to anyone who is interested in the topic of operating systems:

• Abraham Silberschatz, Peter B. Galvin, and Greg Gagne: Operating System Concepts.
• Andrew S. Tanenbaum: Modern Operating Systems.
• Andrew S. Tanenbaum and Albert S. Woodhull: Operating Systems Design and Implementation.
• William Stallings: Operating Systems: Internals and Design Principles.
• Thomas W. Doeppner: Operating Systems In Depth: Design and Programming.
• Ann McHoes and Ida M. Flynn: Understanding Operating Systems.
• Thomas Anderson and Michael Dahlin: Operating Systems: Principles and Practice.
• William S. Davies and T.M. Raijkumar: Operating Systems: A Systematic View.
• Rohit Khurana: Operating Systems.
• Maurice J. Bach: The design of the UNIX Operating System.

• Wikipedia: Operating system.
• Operating System Documentation Project.
• The OS Files.
• Bona Fide OS Developer.
• The Operating System Resource Center.
• OSDev.
• Slides to accompany Silberschatz & Galvin's Operating System Concepts.
• John Bell: Operating Systems. Course Notes (University of Illinois, Chicago).

• Neal Stephenson: In the Beginning was the Command Line.
• CS322: A Brief History of Computer Operating Systems (Gordon College).
• The Creation of the UNIX Operating System.
• Charles Severance: A Brief History of UNIX.

• Agnix Kernel.
• The OSKit Project.
• Yet Another Object Oriented Operating System.

• Greg Kroah-Hartman: Linux Kernel in a Nutshell.
• Linux Kernel Programming Tutorial.