Operating Systems Pre-midterms
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
Convenience
Efficiency
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
Program development
Editors and debuggers
Program execution
Access I/O devices
Controlled access to files
System Access
Error detection and response
Internal and external hardware errors
Software errors
Operating system cannot grant the request of application
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
Memory protection
Does not allow the memory area containing the monitor to be altered
Timer
Prevents a job from monopolizing the system
Privileged instructions
Certain machine-level instructions can only be executed by the monitor
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
Batch Multiprogramming | Time Sharing | |
|---|---|---|
Principal objective | Maximize processor use | Minimize processor use |
Source of directives to the operating system | Job control language commands are provided with the terminal job | Commands are entered at the terminal |
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
Level 1
Electronic circuits
Objects are registers, memory cells, and logic gates
Operations are clearing a register or reading a memory location
Level 2
Processor’s instruction set
Operations such as add, subtract, load, and store
Level 3
Adds the concept of a procedure or
subroutine, plus call/return operations
Level 4
Interrupts
Concepts Related to Multiprogramming
Level 5
Process as a program in execution
Suspend and resume processes
Level 6
Secondary storage devices
Transfer of blocks of data
Level 7
Creates logical address space for processes
Organizes virtual address space into blocks
Deal with External Objects
Level 8
Communication of information and messages between processes
Level 9
Supports long-term storage of named files
Level 10
Provides access to external devices using standardized interfaces
Level 11
Responsible for maintaining the association between the external and internal identifiers
Level 12
Provides full-featured facility for the support of processes
Level 13
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:
Interleave the execution of multiple processes
Allocate resources to processes, and protect the resources of each process from other
processes,
Enable processes to share and exchange
information,
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:
resources are made available to multiple applications,
the processor is switched among multiple applications
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:
Program code (possibly shared)
A set of data
A number of attributes describing the state of the process
While the process is running it has a number of elements including:
Identifier
State
Priority
Program counter
Memory pointers
Context data
I/O status information
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
Memory Tables
I/O Tables
File Tables
Process Tables
Process Control Block
Process Attributes
Process Identification
Processor State Information
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
User mode
Less-privileged mode
User programs typically execute in this mode
System mode
More-privileged mode
Kernel of the operating system
Process Creation
Once the OS decides to create a new process it:
Assigns a unique process identifier
Allocates space for the process
Initializes process control block
Sets up appropriate linkages
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:
Interrupt
Cause: External to the execution of the current instruction
Use: Reaction to an asynchronous external event
Trap
Cause: Associated with the execution of the current instruction
Use: Handling of an error or an exception condition
Supervisor call
Cause: Explicit request
Use: Call to an operating system function
Change of Process State
The steps in a process switch are:
Save the context of the processor including the program counter and other registers
Update the process control block of the process that is currently in the Running state
Move process control block to appropriate queue – ready; blocked; ready/suspend
Select another process for execution
Update the process control block of the process selected
Update memory-management data structures
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:
Identification
Verification
Four Factors:
Something the individual knows
Something the individual possesses
Something the individual is (static biometrics)
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:
Resource ownership - process includes a virtual address space to hold process image.
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:
An execution state (running, ready, etc.)
Saved thread context when not running
An execution stack
Some per-thread static storage for local variables
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:
Spawn (another thread)
Block - Issue: will blocking one thread block the others or all threads?
Unblock
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
User Level Thread (ULT)
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:
The kernel can simultaneously schedule multiple threads from the same process on multiple processors.
If one thread in a process is blocked, the kernel can schedule another thread of the same process.
Kernel routines themselves can be multithreaded.
Disadvantages of KTL:
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
Single Instruction Single Data (SISD) stream - a single processor executes a single instruction stream to operate on data stored in a single memory.
Single Instruction Multiple Data (SIMD) stream - each instruction is executed on a different set of data by the different processors.
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.
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:
Simultaneous concurrent processes or threads
Scheduling
Synchronization
Memory Management
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:
A header that identifies the sending and receiving process and
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
Uniform interfaces on requests made by a process
Extensibility
Flexibility
Portability
Reliability
Distributed system support
Object oriented operating systems