Chapter 1: Introduction to Operating Systems

CS330 - Operating Systems

Complete Edition with All Topics

1.1 What is an Operating System?

An Operating System (OS) is a program that acts as an intermediary between computer users and computer hardware. It provides an environment in which a user can execute programs conveniently and efficiently.

Key Components of a Computer System:

Users
(People, machines, other computers)
↓
Application Programs
(word processors, compilers, web browsers, database systems, video games)
↓
System Programs
(shells, editors, compilers)
↓
Operating System
(process, memory, I/O management)
↓
Computer Hardware
(CPU, memory, I/O devices)

The Kernel

The Kernel is "the one program running at all times on the computer"

  • Core part of the OS that runs in privileged mode
  • Manages system resources and hardware
  • Everything else is either:
    • A system program (ships with the operating system, but not part of the kernel)
    • An application program (all programs not associated with the operating system)

Operating System Goals

The operating system's goals depend on the point of view:

  • User View: Users want convenience, ease of use - don't care about resource utilization
  • System View: OS must allocate resources efficiently and fairly
    • Resource allocator - manages all resources
    • Control program - controls execution of programs to prevent errors
  • Shared computers (mainframe/minicomputer) must keep all users happy
  • Dedicated systems (workstations) have dedicated resources but use shared resources from servers
  • Handheld computers are resource poor, optimized for usability and battery life
  • Some computers have little or no user interface (embedded computers in devices and automobiles)

1.2 Operating System Operations

Dual-Mode Operation

Dual-mode operation allows OS to protect itself and other system components:

  • User mode - computer system is executing on behalf of a user app
  • Kernel mode (also kernel/system/supervisor mode) - protects the OS when it is running - execution done on behalf of operating system
  • Mode bit provided by hardware (kernel (0) or user (1))

Transition from User to Kernel Mode

User Process (mode bit = 1)

User process executing → calls system call → Return from system call
↓ trap (mode bit = 0) ↑ return (mode bit = 1)

Kernel (mode bit = 0)

Execute system call

Key Protection Mechanisms:

  • Provides ability to distinguish when system is running user code or kernel code
  • Some instructions whose execution can harm the system are designated as privileged, only executable in kernel mode
  • System call changes mode to kernel, return from call resets it to user

Timer Protection

The Operating System must protect the CPU from being taken over by a user program (e.g. in an infinite loop) using a Timer:

  • Set interrupt after specific period
  • Operating system decrements counter
  • When counter reaches zero, generate an interrupt
  • Set up before scheduling process to regain control or terminate program that exceeds allotted time

📝 Exam Question (CS330 Style):

Question: If the kernel is single threaded, then any user level thread performing a blocking system call will:

  • a) cause the entire process to run along with the other threads
  • b) cause the thread to block with the other threads running
  • c) cause the entire process to block even if the other threads are available to run
  • d) None of these

1.3 Computer System Architecture

Von Neumann Architecture

The Von Neumann architecture consists of:

INPUT
DEVICES
CENTRAL PROCESSING UNIT
(ALU + Control Unit)
MEMORY UNIT
(RAM + ROM)
OUTPUT
DEVICES
SYSTEM BUS

Key Characteristics:

  • Stored Program Concept: Both data and instructions are stored in the same memory
  • Sequential Execution: Instructions are executed one at a time
  • Binary System: All data and instructions are in binary form
  • CPU Components: ALU for arithmetic/logic operations, Control Unit for instruction interpretation

A general computer system consists of a group of modules (CPU, device controllers, memory & I/O devices) interconnected by a system bus.

Each device controller is in charge of a specific I/O device type

Component Function Examples
CPU Executes instructions Intel Core i7, AMD Ryzen
Memory Stores data and programs RAM, Cache, Registers
I/O Devices Interface with external world Keyboard, Monitor, Disk
System Bus Communication pathway Address, Data, Control buses
Device Controllers Manage specific device types USB controller, Disk controller

Single-Processor Systems

  • Most systems have special-purpose processors as well (device-specific processor, i.e. disk, KB) that run a limited instruction set & do not run user processes
  • Traditional computers with one general-purpose CPU
  • May contain special-purpose processors for specific tasks

Multiprocessor Systems

Multiprocessor systems (also known as parallel systems or tightly-coupled systems) are growing in use and importance.

Within the past several years, multiprocessor systems (also known as parallel systems or multicore systems) have begun to dominate the landscape of computing.

Advantages of Multiprocessor Systems:

  1. Increased throughput - more work done in less time
  2. Economy of scale - cost less than multiple single-processors as they share peripherals, power supplies, storage
  3. Increased reliability - graceful degradation or fault tolerance

Types of Multiprocessor Systems:

1. Asymmetric Multiprocessing

  • Master processor controls and allocates work to the slave processors
  • More common in extremely large systems
  • Each processor is assigned a specific task

2. Symmetric Multiprocessing (SMP)

  • Each processor performs all tasks within OS
  • No master-slave relationship exists between processors
  • All processors are peers

Symmetric Multiprocessing Architecture

CPU₀
registers
cache
CPU₁
registers
cache
CPU₂
registers
cache
Shared Memory

Clustered Systems

Like multiprocessor systems, but multiple systems working together

  • Usually sharing storage via a storage-area network (SAN) & closely linked via a LAN
  • Provides a high-availability service which survives failures

Asymmetric Clustering

Has one machine in hot-standby mode monitoring the active server while the other is running the applications

Symmetric Clustering

Has multiple nodes running applications, monitoring each other

Additional Clustering Features:

  • Some clusters are for high-performance computing (HPC)
  • Applications must be written to use parallelization (dividing a program into separate components that run in parallel on individual PCs)
  • Some have distributed lock manager (DLM) to avoid conflicting operations between shared accessed data

1.4 Computer System Operation

Bootstrap Process

The bootstrap program is loaded at power-up or reboot:

  1. Typically stored in ROM or EPROM (Erasable Programmable ROM), generally known as firmware
  2. Initializes all aspects of system: from CPU registers to device controllers to memory contents
  3. The bootstrap program must know how to load the operating system and how to start executing the system
  4. Loads the operating system kernel into memory
  5. Starts executing the operating system

Interrupt Mechanism

Key Points about Interrupts:

  • Interrupts are essential for the function of any OS
  • Interrupts from either HW or SW alert the OS when events occur
  • Current operating systems are interrupt driven - OS waits for an event
  • Events are signaled by the occurrence of an interrupt or a trap
1. Device sends interrupt signal
→
2. CPU stops current task
→
3. Saves state
→
4. Executes ISR
→
5. Restores state

Interrupt Handling Details:

  • Interrupts transfer control to the interrupt service routine (ISR) generally, through the interrupt vector, which contains the addresses of all the service routines
  • Interrupt architecture must save the address of the interrupted instruction
  • A trap or exception is a software-generated interrupt caused either by an error or a user request

📝 Exam Question (CS330 Final Exam):

Question: A table that points to routines that handle interrupts is called:

  • a) Interrupt handler
  • b) Interrupt indicator
  • c) Interrupt vector
  • d) Interrupt signal
// Simplified Interrupt Handler Example void interrupt_handler(int interrupt_number) { save_cpu_state(); switch(interrupt_number) { case KEYBOARD_INT: handle_keyboard(); break; case TIMER_INT: handle_timer(); break; case DISK_INT: handle_disk(); break; } restore_cpu_state(); return_from_interrupt(); }

Direct Memory Access (DMA)

Slow devices like keyboards will generate an interrupt to the main CPU after each byte is transferred. If a fast device such as a disk generated an interrupt for each byte, the operating system would spend most of its time handling these interrupts. So a typical computer uses direct memory access (DMA) hardware to reduce this overhead.

Direct Memory Access Structure

CPU
DMA Controller
Main Memory

Data Bus connects all components

DMA Characteristics:

  • Used for high-speed I/O devices able to transmit information at close to memory speeds
  • Device controller transfers blocks of data from buffer storage directly to main memory without CPU intervention
  • Direct Memory Access (DMA) means CPU grants I/O module authority to read from or write to memory without involvement
  • DMA module itself controls exchange of data between main memory and the I/O device
  • CPU is only involved at the beginning and end of the transfer and interrupted only after entire block has been transferred
  • Only one interrupt is generated per block, rather than one interrupt per byte
I/O Type CPU Involvement Interrupts Best For
Programmed I/O High (continuous) None Very slow devices
Interrupt-driven I/O Medium One per byte Slow devices (keyboard)
DMA Low (start/end only) One per block Fast devices (disk, network)

1.5 Storage Structure and Hierarchy

Storage System Organization:

  • Storage systems organized in hierarchy based on:
    • Speed
    • Cost
    • Volatility
  • Caching - copying information into faster storage system; main memory can be viewed as a cache for secondary storage
  • Device Driver for each device controller to manage I/O - Provides uniform interface between controller and kernel

Primary Storage

  • Main memory - only large storage media that the CPU can access directly
    • Random access
    • Typically volatile

Secondary Storage

  • Secondary storage - extension of main memory that provides large nonvolatile storage capacity
  • Magnetic disks - rigid metal or glass platters covered with magnetic recording material
    • Disk surface is logically divided into tracks, which are subdivided into sectors
    • The disk controller determines the logical interaction between the device and the computer
  • Solid-state disks (SSD) - faster than magnetic disks, nonvolatile
    • Various technologies
    • Becoming more popular

Storage Hierarchy (Fastest to Slowest):

Registers (< 1 ns)
↓
Cache (L1, L2, L3) (1-10 ns)
↓
Main Memory (RAM) (10-100 ns)
↓
SSD (10-100 μs)
↓
Hard Disk (5-10 ms)
↓
Optical Disk/Tape (seconds)
Storage Type Capacity Access Time Cost/GB Volatile?
Registers < 1 KB < 1 ns Highest Yes
Cache 1-32 MB 1-10 ns Very High Yes
RAM 4-64 GB 10-100 ns High Yes
SSD 256 GB - 4 TB 10-100 μs Medium No
HDD 1-20 TB 5-10 ms Low No

Caching

  • Fetching instructions from RAM is time consuming - slows down the system
  • Important principle, performed at many levels in a computer (in hardware, operating system, software)
  • Idea of caching is to copy instructions and data into the cache for faster access
  • When a process needs data it first checks and tries to access the cache, otherwise it accesses data from the source
  • Cache smaller than storage being cached
  • Movement between levels of storage hierarchy can be explicit or implicit

1.6 Evolution and Types of Operating Systems

Different OSs vary greatly internally but have many common features. The evolution of operating systems shows progression from simple batch systems to complex modern systems.

Evolution of Operating Systems

1. Batch Systems

  • First computer systems were batch systems
  • Low CPU utilization
  • Jobs were prepared offline and batched together
  • No user interaction during execution

2. Multiprogramming

Multiprogramming needed for efficiency:

  • Single user cannot keep CPU and I/O devices busy at all times
  • Multiprogramming organizes jobs (code and data) so CPU always has one to execute
  • One job selected and run via job scheduling
  • When it has to wait (for I/O for example), OS switches to another job
  • Maximizes CPU utilization

3. Time-Sharing (Multitasking)

Timesharing (multitasking) is logical extension of multiprogramming:

  • CPU switches jobs so frequently that users can interact with each job while it is running
  • Creates interactive computing
  • Many users can share the computer simultaneously
  • Response time should be < 1 second
  • Minimizes response time for users

⚠️ Important for Exams:

Remember the key differences:

  • Multiprogramming: Maximizes CPU utilization
  • Time-sharing: Minimizes response time for users
Type Characteristics Examples Use Cases
Batch OS Groups similar jobs, No user interaction IBM OS/360 Payroll, Bank statements
Time-Sharing OS Multiple users, Quick response time Unix, Linux General computing
Real-Time OS Fixed time constraints, Predictable VxWorks, RTLinux Medical devices, Robotics
Distributed OS Multiple CPUs, Resource sharing Google's OS, Amoeba Cloud computing
Mobile OS Power efficient, Touch interface Android, iOS Smartphones, Tablets

📝 Practice Question (CS330 Style):

Question: A process cannot keep both CPU and I/O busy all time. The technique which is used to efficiently use CPU is:

  • a) Multithreading
  • b) Time-sharing
  • c) Multiprogramming
  • d) Preemptive scheduling

1.7 Computing Environments

Computing environments have evolved from traditional stand-alone systems to complex distributed and cloud-based systems.

Traditional Computing

  • Stand-alone general-purpose machines
  • Network computers (thin clients)
  • Blurred line between traditional and mobile computing

Mobile Computing

  • Smartphones and tablets
  • Resource poor - optimized for usability and battery life
  • Touch interface
  • Limited memory and processing power

Client-Server Computing

  • Dumb terminals replaced by smart PCs
  • Servers respond to requests generated by clients
  • Compute-server system
  • File-server system

Peer-to-Peer Computing

  • No centralized server
  • Each peer acts as both client and server
  • Examples: BitTorrent, Blockchain

Cloud Computing

  • Computing as a utility
  • Types: Public, Private, Hybrid clouds
  • Services: SaaS, PaaS, IaaS
  • Elastic resources

Real-Time Embedded Systems

  • Embedded computers in devices and automobiles
  • Little or no user interface
  • Real-time constraints
  • Examples: IoT devices, car systems

1.8 Operating System Services

Process Management
Creating and deleting processes, suspending and resuming processes, providing mechanisms for process synchronization and communication
Memory Management
Keeping track of which parts of memory are being used, deciding which processes to load when memory space becomes available, allocating and deallocating memory space
File System Management
Creating and deleting files and directories, supporting primitives for manipulating files and directories, mapping files onto secondary storage
I/O System Management
Memory management of I/O including buffering, caching, and spooling, general device-driver interface, drivers for specific hardware devices
Protection and Security
Protection involves ensuring that all access to system resources is controlled. Security defends the system from external and internal attacks

📝 Practice Question (CS330 Style):

Question: The controller uses _____ to help with the transfers when handling network interfaces.

  • a) Input Buffer storage
  • b) Signal enhancers
  • c) Bridge circuits
  • d) All of the mentioned

1.9 System Calls

System calls provide an interface between running program and the operating system. They are generally available as assembly language instructions.

Types of System Calls:

1. Process Control

  • end, abort
  • load, execute
  • create process, terminate process
  • get process attributes, set process attributes
  • wait for time
  • wait event, signal event

2. File Management

  • create file, delete file
  • open, close
  • read, write, reposition
  • get file attributes, set file attributes

3. Device Management

  • request device, release device
  • read, write, reposition
  • get device attributes, set device attributes

4. Information Maintenance

  • get time or date, set time or date
  • get system data, set system data
  • get process, file, or device attributes
  • set process, file, or device attributes

5. Communications

  • create, delete communication connection
  • send, receive messages
  • transfer status information
  • attach or detach remote devices

6. Protection

  • get/set permissions
  • allow/deny user access
// Example: System call in C (Linux) #include <unistd.h> #include <sys/types.h> #include <stdio.h> #include <sys/wait.h> int main() { pid_t pid; // Fork system call creates a new process pid = fork(); if (pid == 0) { // Child process printf("Child Process: PID = %d\n", getpid()); exit(0); // Exit system call } else if (pid > 0) { // Parent process printf("Parent Process: PID = %d\n", getpid()); wait(NULL); // Wait system call } else { // Fork failed perror("fork failed"); exit(1); } return 0; }

1.10 Comprehensive Exam Practice

Multiple Choice Questions (From Previous CS330 Exams)

Q1. Because of virtual memory, the memory can be shared among:

  • a) Processes
  • b) Threads
  • c) Instructions
  • d) None of the mentioned

Q2. The bootstrap program is stored in:

  • a) RAM
  • b) ROM/EPROM
  • c) Hard Disk
  • d) Cache

Q3. Which of the following is NOT a goal of an operating system?

  • a) Execute user programs
  • b) Make the computer convenient to use
  • c) Use hardware efficiently
  • d) Compile source code

Q4. In symmetric multiprocessing:

  • a) Each processor performs all tasks within the OS
  • b) One processor acts as master
  • c) Processors are arranged in a hierarchy
  • d) Only one processor can access memory at a time

Short Answer Questions

Q5. Explain the difference between a program and a process. (5 marks)

Answer Key:

  • Program: A passive entity stored on disk (executable file)
  • Process: An active entity with a program counter specifying the next instruction to execute
  • A process includes: program code, current activity, stack, data section, heap
  • One program can have multiple processes
  • Process has state (new, ready, running, waiting, terminated)

Q6. List and briefly describe the four main components of Von Neumann architecture. (8 marks)

Answer Key:

  • Central Processing Unit (CPU):
    • Control Unit: Fetches and decodes instructions
    • ALU: Performs arithmetic and logical operations
  • Memory Unit: Stores both data and instructions (stored program concept)
  • Input Devices: Allow data entry into the system (keyboard, mouse)
  • Output Devices: Display results (monitor, printer)

Q7. What are the advantages of multiprocessor systems? List at least three. (6 marks)

Answer Key:

  1. Increased throughput: By increasing the number of processors, we expect to get more work done in less time
  2. Economy of scale: Multiprocessor systems can cost less than equivalent multiple single-processor systems as they share peripherals, power supplies, and storage
  3. Increased reliability: If functions can be distributed properly among several processors, then the failure of one processor will not halt the system, only slow it down (graceful degradation/fault tolerance)

Q8. Explain the difference between symmetric and asymmetric multiprocessing. (6 marks)

Answer Key:

  • Asymmetric Multiprocessing:
    • Master processor controls and allocates work to slave processors
    • Each processor is assigned a specific task
    • More common in extremely large systems
  • Symmetric Multiprocessing:
    • Each processor performs all tasks within OS
    • No master-slave relationship exists between processors
    • All processors are peers

Calculation Problem

Q9. A paging system with 32-bit logical addresses, 1 GB (2^30) main memory, and a 1 megabyte (20-bit) page size will have a page table that contains how many entries?

Solution:

Page size = 2^20 bytes

Logical address space = 2^32 bytes

Number of pages = 2^32 / 2^20 = 2^12 = 4096 entries

Answer: 4,096 entries

1.11 Key Terms and Definitions

Term Definition
Kernel The one program running at all times on the computer; core part of the OS that runs in privileged mode and manages system resources
Shell User interface to the operating system (can be CLI or GUI)
System Call Programming interface to the services provided by the OS
Interrupt Signal to the processor that an event needs immediate attention
Trap/Exception Software-generated interrupt caused either by an error or a user request
Context Switch Storing and restoring the state of a process so execution can resume later
Bootstrap Loader Initial program stored in ROM/EPROM that loads the OS kernel into memory
Firmware Software stored in ROM or EPROM, includes bootstrap program
Device Controller Hardware that manages a specific type of device
Device Driver Software that provides interface between OS and device controller
DMA Direct Memory Access - allows devices to transfer data directly to memory without CPU intervention
Dual-mode Operation Hardware support for differentiating between user mode and kernel mode execution
Mode Bit Hardware bit that indicates current mode: kernel (0) or user (1)
Privileged Instructions Instructions that can only be executed in kernel mode
Multiprogramming Technique to maximize CPU utilization by keeping multiple programs in memory
Time-sharing Logical extension of multiprogramming where CPU switches rapidly between users
SMP Symmetric Multiprocessing - all processors are peers and perform all OS tasks
Clustered System Multiple systems working together, usually sharing storage via SAN