Operating System – CS 407
Spring 2014 (BE (CS))

Course contents
Overview of Operating System Objectives and functions of operating system A brief overview of computer architecture
Concept of process States of process; Process control block; Address space
Threads and processes Concept of threads; context of a thread Symmetric Multiprocessing (SMP) Microkernel architecture of Operating system
Concurrency, Mutual exclusion and Synchronization Principles of concurrency Hardware support for mutual exclusion Semaphores and monitors Synchronization through message passing
Deadlock and Starvation Deadlock prevention, avoidance and detection Algorithms for deadlock prevention, avoidance and detection
Memory management Requirements; Memory partitioning; paging and segmentation Virtual memory management and operating system support
Processor Scheduling Types of scheduling and scheduling algorithms Multiprocessor scheduling and real-time scheduling
I/O Management and Disk Scheduling Organization of I/O devices; Buffering Disk scheduling; Disk cache RAIDs
File management File organization and file directories File sharing and record blocking Secondary storage management
Protection and Security Computer security; Threats and attacks Viruses, Worms and Bots Authentication and access control Intrusion detection and malware defence
Distributed processing and Networks Communication architecture; Client/server computing Distributed message passing; Remote procedure calls

Text Book Operating Systems – Internals and Design Principles William Stallings – Sixth or Seventh Edition
Reference books 1. Operating System Concepts Silberscahtz and Galvin – 8th Edition 2. Modern Operating Systems Andrew S. Tanenbaum – 3rd Edition 3. Operating Systems Gary Nutt – 3rd Edition

Session Evaluation Marks Distribution (Total = 30) Test 10 marks Midterm 15 marks Quizzes, etc. 5 marks

Course Instructor Prof. Hasina Khatoon hkhatoon@neduet.edu.pk

Consultancy hours Monday and Thursday 14:00 to 16:00 hours

BASIC ELEMENTS OF A COMPUTER

Operating system exploits its resources to provide services to users Manages system including secondary storage and I/O devices
Basic elements of a computer include: Processor I/O modules Main memory System bus
Processor consists of a set of registers User-visible registers Data registers Address registers Index register Segment pointer Stack pointer Control and status registers Program counter (PC) Instruction register (IR) Condition code/ Flags register

Instruction execution goes through a cycle Instruction cycle Fetch and execute

A much simplified view of instruction format and the various steps of instruction execution cycle

Interrupts Mechanism to interrupt the normal sequencing of the processor
Classes of interrupts Interrupts from a program Timer I/O interrupts Hardware failure (not an exhaustive list)
Interrupts and execution cycle Suspend the program and handle the interrupts When? Interrupt step is added at the end of the steps of instruction execution

The process of interrupt handling – Intel 8086/8088

Multiple interrupts and their priorities Sequential order Priority-based interrupts Pre-emptive and non-preemptive interrupts

Multiprogramming Why is it required? Long I/O waits put the processor in idle state Program is context-switched

The memory hierarchy Parameters that describe the memory hierarchy Capacity Speed Cost
Build a memory hierarchy that gives high capacity at a fats speed and at a low cost

Behaviour of the hierarchy while moving from top to the lower levels Decreasing cost per bit Increasing capacity Increasing access time Decreasing frequency of access by the processor
Hierarchy is comprised of Registers Cache memory Main memory Secondary storage

For a two-level hierarchy T = H1 t1 + (1 – H1) t2 Speed is desired to be close to the speed of the 1st level. How? Due to principle of locality of reference Applicable to more than two levels of memory

Cache memory Working and Mapping schemes

Key elements of cache design Cache size Block size Mapping function Replacement algorithm Write policy

I/O communication techniques Programmed I/O Interrupt-driven I/O Direct memory Access (DMA) (estimate the level of understanding of the above topics)

OPERATING SYSTEM OVERVIEW

OBJECTIVES OF THE OPERATING SYSTEM An OS is a program that controls the execution of application programs and acts as an interface between applications and the computer hardware

Three main objectives Convenience Efficiency Ability to evolve

OS as an Interface between a User and a Computer
A user is not concerned with the details of the computer hardware A layered structure of the system Fig. 2.1 Collection of system programs form the OS to ease the task of application programmer

Utilities or library programs are a set of system programs that implement frequently used functions Program creation Management of files Control of I/O devices
Services provided by the OS • Program development e.g. editors and debuggers – application program development tools • Program execution: Load program into memory Initialize memory, I/O devices, files, etc. • Access to I/O devices OS provides a uniform interface for all types of I/O devices • Controlled access to files Controls access to files while providing a protection mechanism • System access OS controls access to system resources and resolves conflicts during resource contention • Error detection and response • Accounting OS collects usage statistics for various resources Future enhancements and tuning for improving system performance

Operating System as a Resource Manager All resources are controlled by a set of OS programs
Kernel or nucleus which is resident in the main memory contains the most frequently used functions of the OS Rest of the main memory is managed by the OS and allocated to user programs I/O devices and other resources are also managed by the OS
Ability of the OS to Evolve
The OS must evolve over the passage of time because of a number of reasons 1. Hardware upgrades and addition of new types of hardware 2. Addition of new services 3. Repair of faults as and when they occur
System should be modular with clearly defined interfaces to achieve the above objectives

THE EVOLUTION OF OS Earliest computer system has no OS – serial processing took place User interacted directly with the computer
Problems identified: Scheduling and Set-up time

Simple Batch systems were designed with monitor program to control the sequential processing of application programs User program interacted with the monitor
Resident monitor had features of interrupt processing, device drivers, job sequencing and Command Line Interpreter (CLI)

Monitor point of view
Processor point of view Processor executes both monitor and application program instructions
A Job Control Language (JCL) is used by the application to interface with the monitor

In addition to monitor program, other hardware features were also desirable 1. Features for memory protection 2. Timer for job timing 3. Privileged instructions to be executed only by the monitor 4. Interrupt mechanism to relinquish and regain control from user programs

User mode and kernel mode of operation Overhead of monitor is also incurred
A high CPU idle time was still there because of long I/O waits
Multiprogramming or multitasking were used to avoid this large idle time

Multiprogramming batch system Memory management features were required Several programs are in memory at the same time An algorithm for scheduling is required Select one of several jobs for execution

Time sharing systems Multiple interactive jobs need time sharing when run in multiprogrammed mode
Key differences between batch multiprogramming and time sharing systems Objective and source of directives to the OS

Major Advances in the Development of Operating system • Processes • Memory management • Information protection and security • Scheduling and resource management • System structure

The process 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 a single sequential thread of execution, a current state and an associated set of system resources The concept of a process developed due to Multiprogramming batch operation Time sharing Real-time transaction systems
A number of errors occurred while synchronizing between various events, which were difficult to handle
There were four main causes of errors 1. Improper design of synchronization mechanism 2. Failed mutual exclusion More than one user/program attempted to use a shared resource at the same time A mutual exclusion mechanism was required 3. Non-determinate program operation The order in which programs are scheduled may affect the outcome of the program Due to sharing of memory and other resources 5. Deadlocks Two or more programs may be waiting on each other and do not progress

The process concept provides the foundation to deal with the above problems

Components of a process An executable program The associated data needed by the program The execution context of the program Process state Contents of processor registers – PC and data registers OS related information e.g. present state and the priority Process management requires a process list Process context including base and limit registers

Memory Management OS performs five storage management functions 1. Process isolation The OS must prevent processes from interfering with each other’s memory 2. Automatic allocation and management Memory allocation should be done dynamically across the memory hierarchy Should be transparent to the user 3. Support for modular programming Programmers should be able to create, destroy and alter the size of modules dynamically 4. Protection and access control Sharing of memory at any level should be controlled under user requirements 5. Long-term storage Information needs to be stored even after the system is powered-off

Virtual memory and file system facilities help the OS to deal with the above functions
File-system implements the long-term storage File is a useful unit of access control and protection for the OS

Virtual memory allows programs to address memory from a logical point of view without considering the amount of physical memory available VM allows viewing programs comprising of blocks called pages
Virtual address – Page number and offset within the page

Dynamic mapping between virtual address and real or physical address is performed by the paging system
All pages of a process may not be in memory at the same time VM management module loads a required page in memory if it is not in memory

Address translation hardware and address translation mechanism

Information Protection and Security Problem of controlling access to the computer system and protect the information stored in them
The characteristics can be categorized into four categories 1. Availability: protecting the system against interruption 2. Confidentiality: User should not data for which the access is unauthorized 3. Data integrity: Protection of data against unauthorized modification 4. Authenticity: Proper identification and verification of users and validity of messages or data

Scheduling and Resource Management Manage resources and schedule their use by various active processes
A resource allocation and scheduling policy should consider the following three factors:
1. Fairness: Fair access to resources should be given to all competing processes
2. Differential responsiveness: OS needs to discriminate among different classes of jobs with different service requirements
3. Efficiency: The OS should maximize throughput, minimize response time and accommodate as many users as possible

All the conflicting requirements must be balanced
OS maintains a number of queues that contain a list of processes waiting for each of the resources Short-term queue: Round-robin technique is generally used Long-term queue I/O queue: A unique I/O queue is maintained for each device

System Structure Size and complexity of OS have grown over time
Four problems have emerged due to the above 1. OS are late in being delivered, especially the updates 2. System has bugs that can be fixed in the field 3. Performance is often not what was expected 4. OS is vulnerable to a variety of security attacks, including viruses and worms

A modular structure of the OS has been proposed to overcome the above problems Layered architecture is preferred with levels of OS layers

Hierarchical model of modern OS
Level 1: Electronic circuits – Registers, memory cells, etc. Operations are – clearing a register or read a memory location
Level 2: The processor’s instruction set Allowed machine language instructions
Level 3: Adds the concept of a procedure or a subroutine
Level 4: Interrupts that cause the processor to save current context and invoke an ISR

The above are not actually a part of OS, but the OS begins to appear at level 4
Level 5: The notion of a process Cooperation between processes, synchronization, etc.
Level 6: Secondary storage devices of the computer Scheduling, etc.
Level 7: Creates a logical address space for processes Organizes the virtual address space Fixed-size pages, variable-size segments, both pages and segments
Level 8: Communication of information and messages between processes
Level 9: Supports the long-term storage of named files
Level 10: Provides access to external devices using standardized interfaces
Level 11: Maintains the association between the external and internal identifiers of the system’s resources and objects
Level 12: Full-featured facility for support of processes
Level 13: Provides and interface to the OS for the user – shell

The Concept of Virtual Machines