CSc360 Operating System Structure

II) Operating System Structure

An o/s is a large and complex piece of software => modularity in its internal organization and structure is crucial to its correct functioning and proper maintenance.
The o/s can be viewed as the manager of all hardware and software resources.
It can be roughly partitioned into the following components:

process management

A process is a program in execution.

process = program (code) + its local data (not input data)
A process is a unit of work in the o/s.
As a process executes, it changes states.

-----------------------------------------------------------------------

                         pre-empted/interrupted
                         +-----------<--------+
                         |                    |
                         |                    |
             create      |     dispatch       |       kill
      [new] --------> [ready] ----------> [running] -------> [dead]
                         |                    |
         request granted |                    | kernel request/
                         |                    | interrupted
                         +--<-- [blocked] <---+

Diagram 2.1 State transition of a process

-----------------------------------------------------------------------

The o/s is responsible for:

process creation and destruction,
process suspension and resumption,
process synchronization and communication, and
deadlock handling.

memory management

It manages the allocation and deallocation of memory space according to the need of each process.
The o/s is responsible for:

keeping track of memory usage,
process swapping, and
dynamic memory allocation.

disk management

It manages the disk storage allocation, scheduling, and free spaces.

i/o system management

It hides the peculiarities of specific hardware devices.
The i/o system usually consists of buffers and device drivers (which need to be written once and for all).

file management

It provides a uniform and logical view of the storage system.
The o/s is responsible for:

the creation and deletion of files and directories,
the support of primitives to manipulate files and directories,
mapping logical files to physical disk addresses, and
backing up.

protection system management

It provides sufficient protection to ensure system integrity without degrading performance.

networking

It provides the user with access to the various system resources distributed over a network.

command interpreters

A command interpreter makes available a repertoire of commands for the user to interact with the rest of the system.

* System structure

A) Monolithic approach

An o/s is basically a collection of modules which perform various functions, i.e., it is a single program!
The interaction between modules is by procedure calls.

-----------------------------------------------------------------------

Diagram 2.2: Structure of a monolithic o/s

-----------------------------------------------------------------------

B) Layered approach (kernel approach)

The o/s consists of many (conceptual) layers of software with the lowest layer being the "kernel" of the whole system and each layer is implemented using the primitives provided by the layers below.

------------------------------------------------------------------------

Diagram 2.3: Structure of an o/s kernel

------------------------------------------------------------------------

The main functions of the kernel are:

process creation and destruction,
cpu scheduling,
memory management,
process synchronization and communication, and
device management (may not be part of the kernel).

Basically, the kernel provides a fundamental abstraction: a virtual cpu for every active process.
It is crucial to decide which functions should be part of the kernel because it affects the overall performance.
Examples of the kernel approach:

process hierarchy (e.g., THE o/s)

            +------------------------------------------+
            |              User Programs               |
            | +--------------------------------------+ |
            | |         Virtual i/o devices          | |
            | | +----------------------------------+ | |
            | | |     Virtual operator console     | | |
            | | | +------------------------------+ | | |
            | | | |   Virtual segmented memory   | | | |
            | | | | +--------------------------+ | | | |
            | | | | |Cpu allocation, semaphores| | | | |
           -+-+-+-+-+--------------------------+-+-+-+-+-

functional hierarchy (e.g., Pilot o/s)

A process may perform more than one function.
Any given process may span several levels of the hierarchy.

object-oriented structure (e.g., iAPX-432 o/s)

The system is a collection of objects, including processes.
Objects communicate by messages.
A kernel is provided to enforce this abstract view of objects.
Objects are protected by capabilities (access rights).
The o/s is a network of objects interconnected by capabilities.

* Process management

An O/S can be viewed as a collection of processes, which cooperate by communicating with messages and synchronizing with signals, and compete for resources.
To support this abstract view, the kernel of an O/S is required to "virtualize" the cpu(s), i.e., every process has its own cpu.
In general, there are more processes than processors available on a particular system => we need to share the cpus among all processes.
To be able to start and stop a process at any time, we need to maintain the state of a process in a structure, called a process control block (PCB) or a process descriptor (PD).
A PCB typically contains the following information:

process id---a unique id of the process in the system.
process state---the current state of the process.
volatile environment---state of the processor which is logically independent but is physically shared. It includes the program counter, machine registers, ..., etc.
memory information---the memory allocated to this process. It includes bound registers, segment tables, ..., etc.
cpu scheduling information---the priority and the cpu time assigned to this process.
i/o status information---the state of all outstanding i/o requests.
accounting information---a record of all resource usage.

An example of a multiprogrammed and multiprocessor system:

    CONST MAXPROCESS = N;
          MAXCPU = M;
          MAXPRIORITY = P;

    TYPE CpuState = (executing, idle);
          ProcessState = (ready, running, blocked, dead);
          ProcessPriority = [0..MAXPRIORITY];
          ProcessId = [0..MAXPROCESS];
          Context = (* for the Cpu and PD *)
            RECORD
              pc : Register; (* program counter *)
              sp : Register; (* stack pointer *)
              cs : Register; (* code segment pointer *)
              ds : Register; (* data segment pointer *)
              (* and many other registers *)
            END;

          Process = POINTER TO PD;
          PD = (* Process descriptor *)
            RECORD
              name     : ARRAY OF CHAR;
              pid      : ProcessId;
              state    : ProcessState;
              processor: Cpu;
              env      : Context;        (* the volatile environment *)
              priority : ProcessPriority;
              next     : Process;
              (* and other bookkeeping information *)
            END;

          Cpu = POINTER TO CpuDescriptor;
          CpuDescriptor =
            RECORD
              state : CpuState;
              env   : Context;        (* cpu's physical context *)
              active: Process;        (* the current running process *)
              next : Cpu;            (* to next cpu *)
            END;

VAR DeadPool : Process; (* set of unused PDs *)
IdleCpu : Cpu;

All processes waiting to be executed are kept in a "ready queue", which is a linked list of process descriptors.
A ready queue may have different structures when using different scheduling algorithms.

VAR ReadyQueue : Process;

In order to multiplex a cpu among several processes, we need a "dispatcher" to switch the context of a process on a cpu to another.
The dispatcher is the O/S routine that gives control of the cpu to the process executed next---it performs "context-switching".

      (* Dispatch the process 'p' to the processor 'c'. 'p' should be
         selected from the set of ready processes. *)
    PROCEDURE Dispatch( p : Process; c : Cpu );
    BEGIN
        IF c^.state = executing THEN
              (* preempt the running process *)
            Interrupt(c);   (* interrupt the processor c *)
              (* save the current active process's context *)
            c^.active^.env := c^.env;
            c^.active^.processor := NIL;
              (* put the current active process back into the ready queue *)
            QInsert(c^.active,ReadyQueue);
        END;
          (* processor c is now idle *)
        p^.state := running;
        p^.processor := c;
        c^.state := executing;
        c^.active := p;     (* p becomes the current running process *)
          (* load/restore the context of p *)
        c^.env := p^.env;
          (* resume the execution of processor c *)
        Start(c);
    END Dispatch;

To support the concept of process, the kernel must provide primitives to:

create a process:

          (* A process of name is created with priority n and its pid is
             returned. *)
        PROCEDURE Create( name   : ARRAY OF CHAR;
                          n      : ProcessPriority;
                          VAR id : ProcessId );
            VAR p : Process;
        BEGIN
            QDelete(p,DeadPool);
            p^.pid := NewPid();
            p^.name := name;
            id := p^.pid;
            p^.priority := n;
              (* Allocate enough memory for this new process,
                 load its code into the allocated memory, and
                 then initialize its stack and data areas.
                 Setup the process's new context pd(p).env.
                 Finally, put the new process into the ready queue *)
            QInsert( p, ReadyQueue );
        END Create;

destroy a process:

        PROCEDURE Destroy( id : ProcessId );
            VAR p : Process;
        BEGIN
            p := PDof(id);    (* locate its process descriptor *)
            Stop(p);
            p^.state := dead;
              (* Deallocate all resources held by this process and
                 then put its pd back to the deal pool *)
            QInsert(p,DeadPool)
        END Destroy;

        PROCEDURE Stop( p : Process );
        BEGIN
            IF p^.state = running THEN   (* stop it! *)
                Interrupt(p^.processor);
                p^.processor^.state := idle;
                QInsert(p^.processor,IdleCpu);
                  (* save the process's context *)
                p^.env := p^.processor^.env;
            END;
        END Stop;

suspend a process:

        PROCEDURE Suspend( id : ProcessId );
            VAR p : Process;
        BEGIN
            p := PdOf(id);
            Stop(p);
            p^.state := blocked;
        END Suspend;

resume a process:

        PROCEDURE Resume( id : ProcessId );
            VAR p : Process;
        BEGIN
            p := PDOf(id);
            IF p^.state = blocked THEN
                p^.state = ready;
                QInsert(p,ReadyQueue);
            END;
        END Resume;

Given a set of ready processes and a set of idle processors, our next step is allocating (or scheduling) the processors to the processes.