Operating System

• A program that controls the execution of application programs

• An interface between applications and hardware

• Responsible for managing resources

• Functions the same way as ordinary computer software

• It is a program that is executed

• The operating system relinquishes control of the processor

Operating System Objectives

1. Convenience

2. Efficiency

3. Ability to evolve

Layers and Views of a Computer System

• Application Programs (end-user)

• Utilities (programmer)

• Operating System (programmer)

• Computer Hardware (operating system designer)

Services Provided by the OS

1. Program development

   • Editors and debuggers

2. Program execution

3. Access I/O devices

4. Controlled access to files

5. System Access

6. Error detection and response

   • Internal and external hardware errors

   • Software errors

   • Operating system cannot grant the request of application

7. Accounting

   • Collect usage statistics

   • Monitor performance

   • Used to anticipate future enhancements

   • Used for billing purposes

OS as Resource Manager

Kernel

The kernel, also called the nucleus, is a portion of the operating system within the main memory. It contains the most frequently used functions.

Evolution of Operating Systems

• Hardware upgrades plus new types of hardware

• New services

• Fixes

• Serial processing

  • No operating system

  • Machines run from a console with display lights, toggle switches, input device, and printer

• Serial processing

  • Schedule time

  • Setup included loading the compiler, source program, saving compiled program, and loading and linking

• Simple batch system

  • Monitor

  • Software that controls the sequence of events

  • Batch jobs together

  • Program returns control to monitor when finished

Job Control Language

Job control is a special type of programming language that provides instruction to the monitor on:

• What compiler to use

• What data to use

Hardware Features

1. Memory protection

   • Does not allow the memory area containing the monitor to be altered

2. Timer

   • Prevents a job from monopolizing the system

3. Privileged instructions

   • Certain machine-level instructions can only be executed by the monitor

4. Interrupts

   • Early computer models did not have this capability

Memory Protection

• User program executes in user mode

  • Certain instructions may not be executed

• Monitor executes in system mode

  • Kernel mode

  • Privileged instructions are executed

  • Protected areas of memory may be accessed

Uniprogramming

• Processor must wait for I/O instructions to complete before proceeding

  

Multiprogramming

• When one job needs to wait for I/O, the processor can switch to another job

  

Utilization Histograms for both Uni- and Multiprogramming

Batch Multiprogramming

Match multiprogramming is the usage of multiprogramming to handle multiple interactive jobs. The processor’s time is shared among multiple users. Multiple users simultaneously access the system through terminals.

Batch Multiprogramming versus Time Sharing

CTSS Operation

Major Achievements

• Processes

• Memory management

• Information protection and security

• Scheduling and resource management

• System structure

Process

A process is a program in execution. It is an instance of a program running on a computer and the entity that can be assigned to and executed on a processor

A unit of activity characterized by:

• A single sequential thread of execution

• A current state

• An associated set of system resources

Consists of three components:

• An executable program

• Associated data needed by the program

• Execution context of the program

  • All the information the operating system needs to manage the process

    

Difficulties with Designing System Software

• Improper synchronization

• Failed mutual exclusion

• Nondeterminate program operation

• Deadlocks

Memory Management

• Process isolation

• Automatic allocation and management

• Support of modular programming

• Protection and access control

• Long-term storage

Virtual Memory

The virtual memory implements long-term storage. Within the virtual memory, information is stored in named objects called files which allows programmers to address memory from a logical point of view

Paging

• Allows a process to be comprised of a number of fixed-size blocks, called pages

• The virtual address is a page number and an offset within the page

• Each page may be located anywhere in the main memory

• Real address or physical address is the main memory address

Virtual Memory Concepts

• Main Memory

  • Main memory consists of a number of fixed-length frames, each equal to the size of a page. For a program to execute, some or all of its pages must be in the main memory.

• Disk

  • Secondary memory (disk) can hold many fixed-length pages. A user program consists of a number of pages. Pages for all programs plus the operating system are on disk, as are files.

Virtual Memory Addressing

Information Protection and Security

• Availability

  • Concerned with protecting the system against interruption

• Confidentiality

  • Assuring that users cannot read data for which access is unauthorized

• Data integrity

  • Give equal and fair access to resources

• Authenticity

  • Discriminate among different classes of jobs

Scheduling and Resource Management

• Efficiency

  • Maximize throughput, minimize response time, and accommodate as many uses as possible

Key Elements of an Operating System

System Structure

The system structure allows us to view the system as a series of levels. Each level performs a related subset of functions and relies on the next lower level to perform more primitive functions. This decomposes a problem into a number of more manageable subproblems

Levels

1. Level 1

   1. Electronic circuits

   2. Objects are registers, memory cells, and logic gates

   3. Operations are clearing a register or reading a memory location

2. Level 2

   1. Processor’s instruction set

   2. Operations such as add, subtract, load, and store

3. Level 3

   1. Adds the concept of a procedure or

      subroutine, plus call/return operations

4. Level 4

   1. Interrupts

   Concepts Related to Multiprogramming

5. Level 5

   1. Process as a program in execution

   2. Suspend and resume processes

6. Level 6

   1. Secondary storage devices

   2. Transfer of blocks of data

7. Level 7

   1. Creates logical address space for processes

   2. Organizes virtual address space into blocks

   Deal with External Objects

8. Level 8

   1. Communication of information and messages between processes

9. Level 9

   1. Supports long-term storage of named files

10. Level 10

    1. Provides access to external devices using standardized interfaces

11. Level 11

    1. Responsible for maintaining the association between the external and internal identifiers

12. Level 12

    1. Provides full-featured facility for the support of processes

13. Level 13

    1. Provides an interface to the OS for the user

Modern Operating Systems

Microkernel architecture

Assigns only a few essential functions to the kernel including:

• Address spaces

• Interprocess communication (IPC)

• Basic scheduling

Multithreading

The process is divided into threads that can run concurrently.

Thread

• Dispatchable unit of work that executes sequentially and is interruptable. A Process is a collection of one or more threads.

Symmetric multiprocessing (SMP)

• There are multiple processors

• These processors share the same main memory and I/O facilities

• All processors can perform the same functions

• 

• Distributed operating systems

  • Provides the illusion of a single main memory space and single secondary memory space

• Object-oriented design

  • Used for adding modular extensions to a small kernel

  • Enables programmers to customize an operating system without disrupting system integrity

Process Description Control

How are processes represented and controlled by the OS?

Requirements of an Operating System

An Operating System’s fundamental task is Process Management. It must:

1. Interleave the execution of multiple processes

2. Allocate resources to processes, and protect the resources of each process from other

   processes,

3. Enable processes to share and exchange

   information,

4. Enable synchronization among processes

Computer platforms consist of hardware resources. A computer’s applications are developed to perform some task but it’s inefficient for applications to be written directly for a given platform. As such, the OS is used since it provides an interface for applications to use and/or provides a representation of resources (data or hardware) that can be requested and accessed by an application.

The OS manages the execution of applications, which means it makes sure that:

1. resources are made available to multiple applications,

2. the processor is switched among multiple applications

3. the processor and I/O devices can be used efficiently

Process

Definitions

• A program in execution

• An instance of a program running on a computer

• The entity that can be assigned to and executed on a processor

• A unit of activity characterized by the execution of a sequence of instructions, a current state, and an associated set of system instructions

Elements of a Process

A process is comprised of:

1. Program code (possibly shared)

2. A set of data

3. A number of attributes describing the state of the process

While the process is running it has a number of elements including:

1. Identifier

2. State

3. Priority

4. Program counter

5. Memory pointers

6. Context data

7. I/O status information

8. Accounting information

A process control block contains the process elements. It is created and processed by the operating system and allows support for multiple processes.

Trace of the Process

The trace is a list of the sequence of instructions that are executed. It reflects the behavior of an individual process.

Dispatcher is a small program that switches the processor from one process to another.

Process Execution

Considering the execution of three processes and the dispatcher. All of which is in the memory, here’s a visual representation:

Trace from different points of view:

• Processor’s POV: each process runs to completion

  • 

• Processor’s POV:

  • 

Process states which characterize the behavior of processes

Two-state process model

• The state may be in two states: running and not-running

• State transition diagram:

  • 

• Queuing Diagram:

  • 

• Process’ Birth and Death

  • Creation

    • New batch job

    • Interactive Login

    • Created by OS to provide a service

    • Spawned by existing process

  • Termination

    • Normal Completion

    • Memory unavailable

    • Protection error

    • Operator or OS Intervention

• Process Creation

  • The OS builds a data structure to manage the process

  • Traditionally, the OS created all processes but it can be useful to let a running process create another. This action is called process spawning.

    • The Parent Process is the original and creating process

    • Child Process is the new process

• Process Termination

  • There must be some way that a process can indicate its completion

  • This indication may be:

    • A HALT instruction generating an interrupt alert to the OS.

    • A user action (e.g. log off, quitting an application)

    • A fault or error

    • Parent process terminating

Five-State Process Model

• The process has five states:

  • New

  • Ready

  • Running

  • Blocked

  • Exit

• Process Model

  • 

• Queueing Diagram using two queues

  • 

• Queueing Diagram for multiple blocked queues

  • 

• Suspended Processes

  • Processor is faster than I/O so all processes could be waiting for I/O

    • Swap these processes to disk to free up more memory and use the processor on more processes

  • The blocked state becomes a suspended state when swapped to disk

  • Two new states

    • Blocked/Suspend

    • Ready/Suspend

  • 

  • 

  • Reasons for Suspension

    • Swapping

      • The OS needs to release sufficient main memory to bring in a process that is ready to execute.

    • Other OS Reason

      • OS suspects the process of causing a problem

    • Interactive User Request

      • e.g. debugging or in connection with the use of a resource.

    • Timing

      • A process may be executed periodically (e.g., an accounting or system monitoring process) and may be suspended while waiting for the next time.

    • Parent Process Request

      • A parent process may wish to suspend the execution of a descendent to examine or modify the suspended process or coordinate the activity of various descendants.

Data structures used to manage processes

Operating System Control Structures

For the OS to manage processes and resources, it must have information about the current status of each process and resource. Tables are constructed for each entity the operating system manages

Memory Tables

Memory tables are used to keep track of both main and secondary memory. Memory Tables must include this information:

• Allocation of main memory to processes

• Allocation of secondary memory to processes

• Protection attributes for access to shared memory regions

• Information needed to manage virtual memory

I/O Tables

Used by the OS to manage the I/O devices and channels of the computer. The OS needs to know:

• Whether the I/O device is available or assigned

• The status of I/O operation

• The location in main memory being used as the source or destination of the I/O transfer

Files Table

These tables provide information about:

• Existence of files

• Location on secondary memory

• Current Status

• other attributes.

Sometimes this information is maintained by a file management system

Process Tables

To manage processes the OS needs to know the details of the processes:

• Current state

• Process ID

• Location in memory

• etc

Process control block

The most important data structure in an OS because it defines the state of the OS

Process Control Block requires protection

• A faulty routine could cause damage to the block destroying the OS’s ability to manage the process

• Any design change to the block could affect many modules of the OS

Process image: is the collection of program. Data, stack, and attributes.

Process Attributes

We can group the process control block information into three general categories:

• Process identification

• Processor state information

• Process control information

Process Identification

Each process is assigned a unique numeric identifier. Many of the other tables are controlled by the OS may use process identifiers to cross-reference process tables.

Processor State Information

This consists of the contents of processor registers.

• User-visible registers

• Control and status registers

• Stack pointers

Program status word (PSW): contains status information

• Example: the EFLAGS register on Pentium processors

Process Control Information

This is the additional information needed by the OS to control and coordinate the various active processes.

Summary:

OS Control Structures

1. Memory Tables

2. I/O Tables

3. File Tables

4. Process Tables

5. Process Control Block

   1. Process Attributes

      1. Process Identification

      2. Processor State Information

      3. Process Control Information

Ways in which the OS uses these data structures to control process execution

Modes of Execution

Most processors support at least two modes of execution

1. User mode

   1. Less-privileged mode

   2. User programs typically execute in this mode

2. System mode

   1. More-privileged mode

   2. Kernel of the operating system

Process Creation

Once the OS decides to create a new process it:

1. Assigns a unique process identifier

2. Allocates space for the process

3. Initializes process control block

4. Sets up appropriate linkages

5. Creates or expands other data structures

Switching Processes

Several design issues are raised regarding process switching

• What events trigger a process switch?

• We must distinguish between mode switching and process switching.

• What must the OS do to the various data structures under its control to achieve a process switch?

When to switch processes

A process switch may occur any time that the OS has gained control of the currently running process. Possible events giving OS control are:

1. Interrupt

   1. Cause: External to the execution of the current instruction

   2. Use: Reaction to an asynchronous external event

2. Trap

   1. Cause: Associated with the execution of the current instruction

   2. Use: Handling of an error or an exception condition

3. Supervisor call

   1. Cause: Explicit request

   2. Use: Call to an operating system function

Change of Process State

The steps in a process switch are:

1. Save the context of the processor including the program counter and other registers

2. Update the process control block of the process that is currently in the Running state

3. Move process control block to appropriate queue – ready; blocked; ready/suspend

4. Select another process for execution

5. Update the process control block of the process selected

6. Update memory-management data structures

7. Restore the context of the selected process

The OS as a Process — Execution of the Operating System

Non-process Kernel

Execute kernel outside of any process. The concept of process is considered to apply only to user programs. The operating system code is executed as a separate entity that operates in privileged mode.

Execution within User Processes

Operating system software within the context of a user process. No need for Process Switch to run the OS routine.

Process-based Operating System

Implement the OS as a collection of system process

Security Issues

An OS associates a set of privileges with each process. The highest level being administrator, supervisor, or root access.

A key security issue in the design of any OS is to prevent anything (user or process) from gaining unauthorized privileges on the system; especially gaining root access.

System Access Threats

• Intruders

  • Masquerader (outsider)

  • Misfeasor (insider)

  • Clandestine user (outside or insider)

• Malicious software (malware)

Countermeasures for

Intrusion Detection

Intrusion detection systems are typically designed to detect human intruders and malicious software behavior. These intrusions may be host or network-based

Intrusion detection systems (IDS) typically comprise of:

• Sensors

• Analyzers

• User Interface

Authentication

Two Stages:

1. Identification

2. Verification

Four Factors:

1. Something the individual knows

2. Something the individual possesses

3. Something the individual is (static biometrics)

4. Something the individual does (dynamic biometrics)

Access Control

• A policy governing access to resources

• A security administrator maintains an authorization database which the access control function consults to determine whether to grant access.

• An auditing function monitors and keeps a record of user access to system resources.

Firewalls

Traditionally, a firewall is a dedicated computer that:

• interfaces with computers outside a network

• has special security precautions built into it to protect sensitive files on computers within the network.

Threads, SMP, and Microkernels

Threads: Resource ownership and execution

Processes and Threads

Processes have two characteristics:

1. Resource ownership - process includes a virtual address space to hold process image.

2. Scheduling/execution - follows an execution path that may be interleaved with other processes.

These two characteristics are treated independently by the operating system.

The unit of dispatching is referred to as a thread or lightweight process. While the unit of resource ownership is referred to as a process or task.

Multithreading

Multithreading is the ability of an OS to support multiple, concurrent paths of execution within a single process.

• Java run-time environment is a single process with multiple threads.

• Multiple processes and threads are found in Windows, Solaris, and many modern versions of UNIX.

Single Thread Approaches

MS-DOS supports a single-user process and a single thread. On the other hand, some UNIX supports multiple user processes but only one thread per process.

Processes

There’s a virtual address space which holds the process image and with protected access to

• Processors,

• Other processes,

• Files,

• I/O resources

One or more Threads in Process

Each thread has the following:

1. An execution state (running, ready, etc.)

2. Saved thread context when not running

3. An execution stack

4. Some per-thread static storage for local variables

5. Access to the memory and resources of its process (all threads of a process share this).

One way to view a thread is as an independent program operating within a process.

Threads vs. Processes

Benefits of Threads

• It takes less time to create a new thread than a process.

• It takes less time to terminate a thread than a process.

• Switching between two threads takes less time than switching between processes.

• Threads can communicate with each other without invoking kernel.

Thread use in a Single-User System

• Foreground and background work

• Asynchronous processing

• Speed of execution

• Modular program structure

Threads

Several actions can affect all of the threads in a process. Therefore, the OS must manage these at the process level.

Examples:

• Suspending a process involves suspending all threads of the process

• Termination of a process terminated all of the threads within the process.

Activities similar to Processes

Threads - they have execution states and may synchronize with one another, similar to a process.

Here are the two aspects of thread functionality:

• States

• Synchronization

Thread Execution States

States associated with a change in thread state:

1. Spawn (another thread)

2. Block - Issue: will blocking one thread block the others or all threads?

3. Unblock

4. Finish thread - deallocate register context and stacks.

Remote Procedure Call (RPC)

As an example, consider a program that performs two remote procedure calls (RPCs) to two different hosts in order to obtain a combined result.

• Using Single Thread

• Using One Thread Per Server

• Multithreading on a Uniprocessor

  

Adobe PageMaker

Categories of Thread Implementation

1. User Level Thread (ULT)

2. Kernel Level Thread (KLT) - also called kernel-supported threads, lightweight processes

User-Level Threads

In this implementation, all thread management is done by the application. The kernel is not aware of the existence of threads.

Relationship between ULT Thread and Process States

Kernel-Level Threads

The kernel maintains context information for the process and the threads. With this, no thread management is done by the application. Scheduling is done on a thread basis. Windows is an example of this approach.

Advantages of KTL:

1. The kernel can simultaneously schedule multiple threads from the same process on multiple processors.

2. If one thread in a process is blocked, the kernel can schedule another thread of the same process.

3. Kernel routines themselves can be multithreaded.

Disadvantages of KTL:

1. The transfer of protocol from one thread to another within the same process requires a mode switch to the kernel.

Combined Approaches

Thread creation can be done in user space. The bulk of scheduling and synchronization of threads can be done by the application. An example of this approach is Solaris.

Relationship Between Thread and Processes

Symmetric Multiprocessing (SMP)

Traditional View

Traditionally, the computer has been viewed as a sequential machine. A processor executes instructions one at a time in sequence and each instruction is a sequence of operations.

Two popular approaches providing parallelism are:

• Symmetric Multiprocessors (SMPs)

• Clusters (ch 16)

Categories of Computer Systems

1. Single Instruction Single Data (SISD) stream - a single processor executes a single instruction stream to operate on data stored in a single memory.

2. Single Instruction Multiple Data (SIMD) stream - each instruction is executed on a different set of data by the different processors.

3. Multiple Instruction Single Data (MISD) stream - a sequence of data is transmitted to a set of processors, and each of the processors executes a different instruction sequence.

4. Multiple Instruction Multiple Data (MIMD) stream - a set of processors execute different instruction sequences on different data sets.

Parallel Processor Architectures

Symmetric Multiprocessing

The kernel can execute on any processor, thereby allowing portions of the kernel to execute in parallel. Typically, each processor does self-scheduling from the pool of available processes or threads.

Typical SMP Organization

Multiprocessor OS Design Considerations

The key design issues include:

1. Simultaneous concurrent processes or threads

2. Scheduling

3. Synchronization

4. Memory Management

5. Reliability and Fault Tolerance

Microkernel

A microkernel is a small OS core that provides the foundation for modular extensions. The big question is, how small must a kernel be to qualify as a microkernel; Must drivers be in user space?

In theory, this approach provides a high degree of flexibility and modularity.

Kernel Architecture

Microkernel Design: Memory Management

Low-level memory management - this requires mapping each virtual page to a physical page frame. Most memory management tasks occur in user space.

Microkernel Design: Interprocess Communication

Communication between processes or threads in a microkernel OS is via messages. A message includes:

1. A header that identifies the sending and receiving process and

2. A body that contains data, a pointer to a block of data, or some control information about the process.

Microkernel Design: I/O and Interrupt management

Within a microkernel, it is possible to handle hardware interrupts as messages and to include I/O ports in address spaces. A particular user-level process is assigned to the interrupt and the kernel maintains the mapping.

Benefits of a Microkernel Organization

1. Uniform interfaces on requests made by a process

2. Extensibility

3. Flexibility

4. Portability

5. Reliability

6. Distributed system support

7. Object oriented operating systems