Kathir College of Arts and Science

(Affiliated to Bharathiar University)

"Wisdom Tree", Neelambur, Coimbatore – 641 062

COMPLETE TOPIC INDEX

System Software and Operating

Systems

Subject Code: 43A

Semester: IV | Class: II [Link] IT | Academic Year: 2025–2026

Faculty: Prof. M. Mathiyalagan

Department of Information Technology

 UNIT I — Introduction to System Software

◆ 1. Introduction
• System Software – Definition and overview
• System Software vs Application Software
• Machine Dependency in System Software
• Machine-Independent Features

◆ 2. Types of System Software

1. Operating System
2. Language Translators
– Compilers
– Interpreters
– Assemblers
– Pre-processors
3. Loaders
4. Linkers
5. Macro Processors

◆ 3. Language Translators
• Definition and role of Language Translators
• Source Program → Language Translator → Object Program

◆ 4. Compilers
• Definition of Compiler
• Two aspects of compilation
– Generate code to represent meaning of source program
– Provide diagnostics for language specification violations
• High Level Language → Compiler → Machine Language Program

◆ 5. Interpreters
• Definition of Interpreter
• How interpretation works
• Program Counter (PC) role in interpretation
• Interpretation Cycle
– Fetch the statement
– Analyze the statement and determine its meaning
– Execute the meaning of the statement
• Characteristics of Interpretation
– Source program retained in source form; no target program
– Each statement is analyzed during interpretation

◆ 6. Assemblers
 • Definition of Assembler
• Assembly Language concept (mnemonic symbols)
• Fundamental functions of an Assembler
– Translating mnemonic operation codes to machine language equivalents
– Assigning machine addresses to symbolic labels used by programmers

◆ 7. The Simplified Instructional Computer (SIC)

• Overview – similar to a typical microcomputer
• Two versions: Standard model and XE version

■ 7.1 SIC Machine Structure – Memory

• Bytes (8 bits) and Words (24 bits = 3 consecutive bytes)
• Addressed by location of lowest-numbered byte
• Total memory: 32,768 bytes

■ 7.2 SIC Machine Structure – Registers

• 5 Registers:
– Accumulator (A) – used for arithmetic operations
– Index Register (X) – used for addressing
– Linkage Register (L) – stores return address for JSUB
– Program Counter (PC) – address of current instruction
– Status Word (SW) – contains condition code and other info

■ 7.3 SIC Machine Structure – Data Formats

• Integers stored as 24-bit binary numbers
• 2's complement representation for negative values
• Characters stored using 8-bit ASCII codes
• Floating-point data items NOT supported

■ 7.4 SIC Machine Structure – Instruction Formats

• All machine instructions are 24-bits wide
• X-flag bit indicates indexed-addressing mode
• Two addressing types:
– Direct addressing mode
– Indexed addressing mode / Indirect addressing mode

■ 7.5 SIC Machine Structure – Instruction Set

• Data movement instructions – LDA, LDX, STA, STX
• Arithmetic operation instructions – ADD, SUB, MUL, DIV
• Branching instructions – JLT, JEQ, JGT
• Subroutine linkage instructions – JSUB, RSUB

■ 7.6 SIC Machine Structure – Input and Output

• I/O performed by transferring one byte at a time
• Each device assigned a unique 8-bit code
• Three I/O instructions:
– Test Device (TD) – tests if device is ready
– Read Data (RD) – reads data from device
 – Write Data (WD) – writes data to device

◆ 8. SIC/XE Architecture & System Specification

■ 8.1 Memory
• 1 word = 24 bits (3 bytes of 8 bits each)
• Total memory: 2^20 = 1,048,576 bytes (1 MB)

■ 8.2 Registers (10 × 24-bit registers)

• A (0) – Accumulator
• X (1) – Index register
• L (2) – Linkage register (JSUB/RSUB)
• B (3) – Base register
• S (4) – General register
• T (5) – General register
• F (6) – Floating Point Accumulator (48 bits)
• PC (8) – Program Counter
• SW (9) – Status Word (includes Condition Code, CC)

■ 8.3 Data Formats

• Integers: 24-bit, 2's complement format
• Characters: 8-bit ASCII format
• Floating point: 48-bit signed-exponent-fraction format
– Fraction: 36-bit number (value between 0 and 1)
– Exponent: 11-bit unsigned binary number (0 to 2047)
– Sign bit s: 0 = positive, 1 = negative
– Absolute value formula: f × 2^(e-1024)

■ 8.4 Instruction Formats

• Format 1 – 1 byte: op {8}
• Format 2 – 2 bytes: op {8} | r1 {4} | r2 {4}
• Format 3 – 3 bytes (with addressing mode flag bits)
• Format 4 – 4 bytes (with addressing mode flag bits)

■ 8.5 Addressing Modes (Formats 3 & 4)

• n=0 & i=1 → Immediate addressing (TA used as operand value)
• n=1 & i=0 → Indirect addressing (word at TA used as address)
• n=0 & i=0 or n=1 & i=1 → Simple addressing
• Flag x=1 → Indexed addressing (add contents of X to TA)
• Flag b & p (Format 3 only):
– b=0 & p=0 → Direct addressing
– b=0 & p=1 → PC-relative addressing (TA = PC + disp)
– b=1 & p=0 → Base-relative addressing (TA = B + disp)
• Flag e: e=0 → Format 3 | e=1 → Format 4

■ 8.6 Instructions (9 Categories)

• Load/Store registers: LDA, LDX, LDCH, STA, STX, STCH, etc.
• Integer arithmetic: ADD, SUB, MUL, DIV (result in register A)
 • Compare (COMP): sets CC to <, >, or =; conditional jumps: JLT, JEQ, JGT
• Subroutine linkage: JSUB, RSUB (uses register L)
• Input & output control: RD, WD, TD
• Floating point arithmetic: ADDF, SUBF, MULF, DIVF
• Register manipulation: RMO, COMPR, SHIFTR, SHIFTL, ADDR, SUBR, MULR, DIVR

■ 8.7 Input and Output

• Up to 256 (2^8) I/O devices, each with unique 8-bit address
• 1 byte transferred to/from rightmost 8 bits of register A
• Three I/O instructions: RD (Read Data), WD (Write Data), TD (Test Device)
• CC set by TD: < = device ready | = = device not ready
• Programmed I/O – 3 additional instructions:
– SIO – Start I/O
– HIO – Halt I/O
– TIO – Test I/O

◆ 9. Loaders and Linkers

■ 9.1 Introduction
• Loader – Definition and role
• Loading – bringing object program into memory for execution
• Relocation – modifying object program for a different load address
• Linking – combining separate object programs and resolving references
• Linker (Linkage Editor) vs Loader – separate roles

■ 9.2 Basic Loader Functions

• Bringing an object program into memory
• Starting its execution

■ 9.3 Machine-Dependent Loader Features

• Absolute Loader – disadvantages
• Need for Relocatable Programs
• Subroutine library efficiency issues with absolute addresses
• Relocating Loaders / Relative Loaders

■ 9.4 Relocation
• First Method – Modification Records
– Modification record format: starting address + length + modification
– Most instructions use relative/immediate addressing
– Extended format instructions on lines 15, 35, 65 contain actual addresses
– Each Modification record adds value of symbol COPY (start address)
– Object program structure for SIC/XE
• Second Method – Relocation by Bit Mask
– No Modification records; relocation bit per word of object code
– Relocation bits gathered into bit mask in each Text record
– Bit = 1: add program's starting address during relocation
– Bit = 0: no modification needed
– Unused word bits set to 0
 – Example: bit mask FFC (111111111100) → all 10 words modified

■ 9.5 Program Linking

• Three separately assembled programs: PROGA, PROGB, PROGC
• REF1 – handling in PROGA, PROGB, PROGC
– PROGA: PC-relative instruction, no modification needed
– PROGB: Extended-format instruction; Modification record adds LISTA
– PROGC: Handled same way as PROGB
• REF2 – processed similarly to REF1
• REF3 – immediate operand: difference between ENDA and LISTA
– PROGA: assembler computes value directly
– PROGB / PROGC: assembled as external reference with two Modification records
• REF4 – complex expression across programs
– PROGA: initial value 000014H, one Modification record
– PROGB: initial value 000000, three Modification records
– PROGC: relative address of LISTC (000030H) with Modification records
• Corresponding Object Programs: PROGA, PROGB, PROGC
• Fig (4): Programs in memory after loading and linking
• Fig (5): Relocation and linking operations on REF4 in PROGA

■ 9.6 Algorithm and Data Structures for a Linking Loader

• External Symbol Table (ESTAB) – analogous to SYMTAB in assembler
• PROGADDR – beginning load address (supplied by OS)
• CSADDR – starting address of current control section being scanned
• Pass 1 – assigns addresses to all external symbols
– Algorithm for Pass 1 of a Linking Loader
– PROGADDR → CSADDR for first control section
– Control section name entered into ESTAB with CSADDR value
– External symbols from Define record entered into ESTAB
– CSLTH added to CSADDR at End record for next section
– Load map output option
• Pass 2 – actual loading, relocation, and linking
– Algorithm for Pass 2 of a Linking Loader
– Text records: object code moved to specified address + CSADDR
– Modification records: symbol looked up in ESTAB; value added/subtracted
– End record: transfer point to begin execution
– Handling multiple transfer addresses
– Reference numbers assigned to external symbols for efficiency

■ 9.7 Machine-Independent Loader Features

• Automatic Library Search
– Tracking undefined external symbols after Pass 1
– Searching libraries for routines defining unresolved symbols
– Repeated search until all references resolved
– Unresolved references treated as errors
• Loader Options
– Option 1: INCLUDE program-name (library-name) – alternative input sources
– Option 2: DELETE csect-name | CHANGE name1, name2 – delete/rename symbols
– Option 3: LIBRARY MYLIB – automatic library inclusion
– NOCALL STDDEV, PLOT, CORREL – leave references unresolved
■ 9.8 Loader Design Options
• Linking Loaders – linking and relocation at load time
• Linkage Editors – linking performed prior to load time
– Relocation of all control sections relative to program start
– Loading in one pass; no external symbol table required
– Useful when program runs many times without reassembly
– Commands: INCLUDE, DELETE, INCLUDE (new version), REPLACE
– Building packages of subroutines with linkage editors
• Dynamic Linking – linking performed at execution time
– Load on call: subroutine loaded and linked when first called
– Sharing one copy of subroutine among several programs
– Fig (a): Load-and-call service request to OS
– Fig (b): OS checks internal tables; loads routine if needed
– Fig (c): Control passed from OS to called routine
– Fig (d): Subroutine returns to OS; OS returns to calling program
– Fig (e): Second call – control passed directly if still in memory

■ 9.9 Bootstrap Loaders

• Definition and purpose
• Three ways to implement bootstrap loading:
– Operator enters object code via console switches
– Absolute loader program permanently resident in ROM
– Built-in hardware reads fixed-length record into memory at fixed location
• ROM program execution on hardware signal
• First record causes reading of more records – bootstrapping
• Bootstrap loader added to beginning of all object programs for empty systems
• Includes OS and all stand-alone programs
 UNIT II — Machine and Compiler

◆ 1. Compiler
• Definition of Compiler (HLL → MLL)
• Structure of Compiler (Source Program → Compiler → Target Program)
• Error messages to programmer
• Examples: C, C++, Pascal
• Execution process: Compilation → Object Program → Load → Execute

◆ 2. Interpreter
• Definition – executes source program as if it were machine language
• Languages: BASIC, SNOBOL, LISP, JAVA

■ 2.1 Phases of Interpretation

■ Phase 1: Lexical Analysis

• Also called the Scanner
• Separates source characters into tokens
• Types of tokens:
– Keywords – e.g., DO, IF
– Identifiers – e.g., x, num
– Operator symbols – e.g., <, =, +
– Punctuation symbols – e.g., parentheses, commas
• Output: stream of tokens passed to syntax analyzer

■ Phase 2: Syntax Analysis

• Groups tokens into syntactic structures
• Example: A + B → expression
• Expressions combined to form statements
• Syntactic structures represented as a tree
– Leaves = tokens
– Interior nodes = logically grouped token strings
• Syntax tree for READ statement in PASCAL (Fig. 1)

■ Phase 3: Semantic Analysis

• Checks logical consistency of program meaning
• Goes beyond grammar rules
• Uses Abstract Syntax Tree (AST) and Symbol Table
• Catches errors: type mismatches, undeclared variables, incorrect function arguments
• Prepares code for intermediate code generation

■ Phase 4: Code Generation

• Last phase of translation
• Optimizations to reduce machine language program length
• Output: machine language program for specified computer
◆ 3. Translator
• Definition – takes input program in one language; produces output in another
• Error-detection role
• Two important roles:
– 1. Translating HLL program into equivalent machine language program
– 2. Providing diagnostic messages for HLL specification violations

◆ 4. Machine-Dependent Compiler Features

• Syntax analysis is relatively machine-independent
• Real machine dependencies: code generation and optimization
• Complex issues: register allocation, rearrangement of instructions
• Code optimization done via intermediate form of the program
• Intermediate form: syntax and semantics fully analyzed; no machine code yet
• Intermediate form easier to analyze and manipulate than source or machine code

◆ 5. Intermediate Form of the Program

• Many possible representations for code analysis and optimization
• Common form: sequence of quadruples
– Format: operation, op1, op2, result
• Example 1: SUM := SUM + VALUE
– + , SUM, VALUE, i1
– := , i1, , SUM
• Example 2: VARIANCE := SUMSQ DIV 100 – MEAN * MEAN
– DIV, SUMSQ, #100, i1
– *, MEAN, MEAN, i2
– -, i1, i2, i3
– :=, i3, , VARIANCE
• Quadruples created by intermediate code-generation routines
• Optimizations possible on quadruples:
– Eliminate redundant load/store operations
– Assign intermediate results to registers or temporary variables
• Modified quadruples translated into machine code after optimization
• Fig: Sequence of quadruples corresponding to source program

◆ 6. Immediate Form of the Program

• Executable Program Form – machine code ready to run
– Source code → Assembler/Compiler → Machine Code → Executable File
– OS loads machine code into memory and creates a process
– CPU fetches, decodes, and executes instructions
• Immediate Addressing Mode
– Operand value contained within the instruction itself
– CPU uses value immediately without extra memory reference

◆ 7. Machine-Dependent Code Optimization

 • Problem: assignment and use of registers
• General-purpose registers hold useful data
• Register instructions faster than memory reference instructions
• Prefer to keep frequently used variables/results in registers
• Problem: selecting which register value to replace when needed elsewhere
• Approach: scan program for next use of each register value; replace longest-not-needed
• Compiler must consider control flow – Jump instructions complicate register tracking
• Solution: divide program into basic blocks
– Basic block: sequence of quadruples with one entry, one exit, no internal jumps
– CALL operation begins a new basic block
• Flow graph – representation of control flow (Fig 5.23)
• Rearranging quadruples before machine code generation (Fig 5.24 a & b)
– Rearrangement reduces instruction count
– Reduces number of temporary variables needed
• Taking advantage of specific machine instructions and addressing modes

◆ 8. Machine-Independent Compiler Features

• Definition: translates HLL into intermediate code runnable on different architectures

■ 8.1 Intermediate Code Generation

• Intermediate Representation (IR) – e.g., Java bytecode, LLVM IR
• Portability: IR is independent of target machine architecture

■ 8.2 Optimization Techniques

• Machine-Independent Optimization:
– Constant folding
– Dead code elimination
– Loop unrolling
• Control Flow Optimization – simplifying branches and loops

■ 8.3 Abstract Syntax Tree (AST)

• High-Level Abstraction – machine-independent program structure
• Language Semantics Representation – captures HLL semantics

■ 8.4 Platform-Agnostic Code Generation

• Separation of Front-End and Back-End
– Front-End: parsing, syntax analysis, semantic analysis
– Back-End: code generation, optimization
• Code Generation Templates – same IR reused across platforms

■ 8.5 Target Machine Abstraction

• Machine-Independent Libraries and Runtime
– Memory management, I/O, system calls
• Platform-Independent Execution Model (e.g., JVM for Java bytecode)

■ 8.6 Portability
• Cross-Platform Support – same source code on different OS/hardware
• Source-to-Intermediate Compilation
 – Example: Java → bytecode → JVM on any platform

■ 8.7 Error Checking and Reporting

• Machine-Independent Error Handling
• Semantic Checking – type mismatches, undefined variables

■ 8.8 Cross-Compilation
• Targeting different architectures from host system
• Example: x86 host compiling ARM machine code for mobile device

■ 8.9 Support for High-Level Language Features

• Language Feature Abstraction – classes, functions, inheritance
• Multiplatform Support for multi-threading, memory allocation, etc.

■ 8.10 Modularity and Extensibility

• Modular Design – back-end modified/extended for new targets
• Extensibility for New Platforms – only back-end changes needed

■ Examples of Machine-Independent Compilers

• Java Compiler (javac) – compiles to platform-independent bytecode
• LLVM Compiler – generates machine-independent intermediate code

◆ 9. Compiler Design
• Compiler: translates Source Language (HLL) → Target Language (MLL/Assembly)
• Compiler design: process of developing a compiler

■ 9.1 Language Processing System

• Hardware understands machine language; humans write in HLL
• Programs processed through tools and OS components
• High-level language → binary language through various phases
• Compiler: HLL → Assembly Language
• Assembler: Assembly Language → Machine-Level Language
• Execution of C program on host machine (diagram)

■ 9.2 Preprocessor
• Part of compiler; produces input for compilers
• Handles: macro-processing, augmentation, file inclusion, language extension

■ 9.3 Interpreter
• Compiler vs Interpreter comparison
– Compiler: reads whole source at once; multiple passes
– Interpreter: reads one statement; converts; executes; next statement
– Interpreter stops at error; Compiler reads whole program despite errors

■ 9.4 Assembler
• Translates assembly language programs into machine code
• Output: object file (machine instructions + data for memory placement)
■ 9.5 Linker
• Links and merges various object files into an executable file
• Searches and locates referenced modules/routines
• Determines memory locations for code loading
• Provides absolute references in program instructions

■ 9.6 Loader
• Part of operating system
• Loads executable files into memory and executes them
• Calculates program size (instructions and data)
• Creates memory space; initializes registers for execution

◆ 10. Compiler Architecture

• Two main phases: Analysis Phase and Synthesis Phase

■ 10.1 Analysis Phase (Front-End)

• Reads the source program
• Divides into core parts
• Checks for lexical, grammar, and syntax errors
• Generates intermediate representation and symbol table

■ 10.2 Synthesis Phase (Back-End)

• Generates target program
• Uses intermediate source code representation and symbol table

■ 10.3 Pass vs Phase

• Pass: traversal of compiler through entire program
• Phase: distinguishable stage (input → process → output)
• A pass can have more than one phase

◆ 11. Phases of Compiler

■ Phase 1: Lexical Analysis

• First phase – works as a text scanner
• Scans source code as stream of characters
• Converts characters into meaningful lexemes
• Represents lexemes as tokens:

■ Phase 2: Syntax Analysis

• Takes tokens from lexical analysis as input
• Generates parse tree (syntax tree)
• Checks token arrangements against source code grammar
• Parser checks syntactic correctness of expressions

■ Phase 3: Semantic Analysis

• Checks if parse tree follows language rules
 • Example: compatible data types in value assignments
• Tracks identifiers, their types, and expressions
• Checks: identifiers declared before use
• Output: annotated syntax tree

■ Phase 4: Intermediate Code Generation

• Generates intermediate code for target machine after semantic analysis
• Represents program for some abstract machine
• Between high-level language and machine language
• Designed for easy translation to target machine code

■ Phase 5: Code Optimization

• Optimizes intermediate code
• Removes unnecessary code lines
• Arranges statement sequence to speed up execution
• Does not waste resources (CPU, memory)

■ Phase 6: Code Generation

• Code generator maps optimized intermediate code to target machine language
• Translates intermediate code into re-locatable machine code sequence
• Machine code performs same task as intermediate code

■ Symbol Table
• Data structure maintained throughout all phases
• Stores all identifier names and their types
• Enables quick search and retrieval of identifier records
• Used for scope management

◆ 12. Interpreters (Detailed)

• Converts high-level instructions line-by-line to machine-level language
• Checks source code line-by-line; stops at error until resolved
• Line-by-line error makes error correction easy
• Takes more time to complete execution than compiler
• First used in 1952 to ease programming on limited computers
• Translates source code into efficient intermediate representation; executes immediately

■ Advantages and Disadvantages of Interpreters

• Advantage: line-by-line execution helps users find errors easily
• Disadvantage: takes more time to execute than compiler

◆ 13. P-Code Compilers

• Also called bytecode compilers
• Intermediate form: machine language for a hypothetical computer (P-machine / Pseudo-machine)
• Main advantage: portability of software
• P-code object program executes on any machine with a P-code interpreter
• Compiler can be transported if written in the language it compiles
 • Source → P-code Compiler → Object Program P-Code → P-code Interpreter → Execute
• P-code for Pascal compiler includes single P-instructions for:
– Array subscript calculation
– Procedure entry and exit handling
– Elementary operations on sets
• P-code object program often much smaller than machine code
• Useful on machines with severely limited memory
• Disadvantage: interpretive execution much slower than equivalent machine code
• Many P-code compilers designed for single user on dedicated microcomputer
• Execution speed: machine-language subroutines can improve performance
• Sacrifices some portability for improved speed

◆ 14. Compiler-Compilers
• Also called Compiler Generators or Translator Writing Systems
• Software tool to help in compiler construction
• Compiler writer provides description of language to be translated
– Set of lexical rules for defining tokens
– Grammar for the source language
• Some compiler-compilers: generate scanner and parser directly
• Others: create tables for standard table-driven scanning and parsing routines
• Compiler writer provides semantic / code-generation routines
– One routine for each grammar rule
– Parser calls routine when it recognizes language construct
• Some compiler-compilers pass internal form (part of parse tree) to semantic routine
• Used when code optimization is to be performed
• Compiler-compilers provide special languages, notations, data structures for semantic routines
• Main advantage: ease of compiler construction and testing
• Generated compilers may require more memory and compile more slowly
• Compiler writer freed from mechanical details → can focus on code generation and optimization
 UNIT III — Operating System

◆ 1. Introduction to Operating System

• Definition – intermediary between user and computer hardware
• Considered the brain of the computer
• Controls internal activities of hardware; provides user interface
• Enables efficient use of hardware resources
• First program loaded into computer memory via 'booting'

◆ 2. Components of a Computer System

• Four components: Hardware, Operating System, Application Programs, User
• Application programs do not access hardware resources directly
• Hardware resources: I/O devices, primary memory, secondary memory, microprocessor
• OS required to access and use hardware resources
• Application programs communicate with resources through OS
• OS is first program loaded into main memory on power-on
• Popular OSes: Windows 9x (95,98), Linux, Unix, Windows XP, Vista

◆ 3. Objectives of an Operating System

• Convenience – makes computer system easy to use
• Efficiency – allows efficient use of hardware
• Ability to Evolve – permits development/testing of new functions without disturbing service

◆ 4. Structure of an Operating System

• Four layers: Hardware → Kernel → System Call Interface (Shell) → Application Programs

■ 4.1 Kernel
• Vital part of the OS; interacts directly with hardware
• Programs interact with kernel through system calls
• System Call: provides interface to OS services
• System call tasks: open/write/get info on file, execute program, terminate process
• Main functions of Kernel:
– Manage computer memory
– Maintain file system
– Allocation of resources
– Control access to the computer
– Handle interrupts

■ 4.2 System Call Interface (Shell)

• Command-line interpreter that interprets commands given by user
• Acts as mediator between kernel and user
• Shell reads commands → interprets → sends request to execute program
■ 4.3 Hardware
• Physical parts of a computer: monitor, mouse, keyboard, HDD, motherboard, chips, etc.
• All physical objects that can be touched

■ 4.4 Utility and Application Programs

• Utility programs: manage, maintain, and control computer resources
• Help with day-to-day personal computing tasks
• Application software: causes computer to perform useful tasks beyond running itself
• Examples: word processors, database programs, web browsers, development tools, image editors

◆ 5. Evolution of Operating Systems

1. Serial operating system
2. Batch operating system
3. Multiprogramming operating system
4. Time-Sharing operating system
5. Real-Time operating system
6. Multiprocessing operating system
7. Distributed operating system

◆ 6. Process
• Process – a program in execution
• Process – currently executable task
• Process execution must progress in a sequential manner

■ 6.1 Process vs Program Comparison

• Process: set of machine code instructions (dynamic, active entity)
• Program: set of instructions in programming language (static, passive entity)
• Process: lives in main memory; time-limited
• Program: lives in secondary storage; unlimited time span
• Process: expressed in assembly/machine language
• Program: expressed through a programming language

■ 6.2 Process in Memory – Sections

• Stack – contains local variables
• Heap – memory dynamically allocated during runtime
• Data – contains global variables
• Text – contains code or instructions

◆ 7. Process State & State Transitions

• Process creation → inserted into ready list
• Process moves toward head of ready list as others complete
• Dispatching: assigning processor to first process on ready list
• Dispatcher: system entity that performs dispatching
• Awake processes: those in ready or running states
• Interval timer (interrupting clock): limits process run time to a quantum
■ 7.1 New State
• Created when user makes a request
• Newly created process enters new state
• Resides in secondary memory in job queue / job pool

■ 7.2 Ready State

• Process needs CPU to execute
• Selected processes copied from secondary memory to main memory
• Resides in ready queue in main memory

■ 7.3 Running State

• Process moves from ready queue; starts execution using CPU

■ 7.4 Waiting State / Blocked State

• Process moves to waiting state if:
– Needs an event/I/O device not immediately available
– Higher-priority process arrives at CPU
• Process said to 'block itself'
• Blocked processes are 'asleep' – cannot execute even if CPU available

■ 7.5 Terminated State

• Process exits system after completing execution
• Terminated state converts process back into a program
• OS may terminate process due to:
– Exceeding time limit
– I/O failure
– Unavailability of memory
– Protection error

◆ 8. Process Control Block (PCB)

• OS assigns Process Identification Number (PID)
• OS creates PCB (also called process descriptor)
• PCB contents:
– PID
– Process state (running, ready, blocked)
– Program counter (next instruction to execute)
– Scheduling priority
– Credentials (resources this process can access)
– Pointer to parent process
– Pointers to child processes
– Pointers to process data and instructions in memory
– Pointers to allocated resources (e.g., files)
• PCB stores register contents – execution context
• OS maintains pointers to each PCB in process table
• On termination: memory freed, process removed from table

◆ 9. Process Operations
 • Create a process
• Destroy a process
• Suspend a process
• Resume a process
• Change a process's priority
• Block a process
• Wake up a process
• Dispatch a process

◆ 10. Process Scheduling

• Objective of multiprogramming: always have process running; maximize CPU utilization
• Objective of time sharing: switch CPU frequently among processes
• Process Scheduling: procedure for determining next process to execute on CPU
• Scheduler: OS module that makes scheduling decisions

■ 10.1 Scheduling Queue

• Job Queue: all processes in system on mass storage (e.g., hard disk)
• Ready Queue: processes in main memory waiting for CPU
• Device Queue: processes waiting for a particular I/O device
• Suspended Queue: stores list of suspended processes

■ 10.2 Scheduler Types

• Long-Term Scheduler (Job Scheduler)
• Short-Term Scheduler (CPU Scheduler)
• Medium-Term Scheduler

■ 10.3 Context Switching

• Saving context of currently running process
• Loading context of another ready process
• Context = process state + memory management info + CPU scheduling info
• Switching time depends on memory speed and number of registers

◆ 11. Interrupt Processing

• Interrupt: signal/event that temporarily halts normal program execution
• System addresses urgent task; resumes previous state after handling

■ 11.1 Types of Interrupts

• Hardware Interrupts:
– Triggered by hardware devices (keyboard, mouse, timer)
– Maskable interrupts: can be temporarily disabled
– Non-maskable interrupts (NMI): cannot be ignored; must be handled immediately
• Software Interrupts:
– Initiated by software (special instruction or system call)
– Requests OS services (I/O operations, memory allocation)
– Can be caused by errors (divide-by-zero, illegal memory access)
– Timer interrupts: periodic; allow OS to do time-based tasks
■ 11.2 How Interrupts Work
• Program execution paused; system saves state (registers, program counter)
• Control passed to Interrupt Handler / Interrupt Service Routine (ISR)
• ISR processes the interrupt
• System resumes original program after interrupt handled

■ 11.3 Interrupt Classes

• Hardware interrupts – generated by external devices
• Software interrupts – triggered by programs or OS (system calls, error handling)

◆ 12. Storage Management – Introduction

• Handles primary (RAM) and secondary (disk) memory
• Ensures fast access, security, optimal space use
• Techniques: file systems, partitioning, allocation, virtual memory, caching, disk scheduling

■ 12.1 Key Functions of OS Storage Management

• File System Management: organizes data into files and directories (NTFS, ext4, FAT)
• Disk Management:
– Partitioning: divides physical disks into logical sections
– Formatting: prepares partitions with a file system
– Mounting/Unmounting: makes disks available or disconnects them
– Space Allocation: assigns disk blocks to files
– Defragmentation: reorganizes scattered data
– Error Handling: detects and recovers from disk errors
• Memory Management (Primary Storage):
– Allocation/Deallocation: assigns RAM to processes and reclaims it
– Virtual Memory: uses disk space as RAM extension (swapping/paging)
– Caching: stores frequently used data in faster memory
• Disk Scheduling: optimizes order of disk access requests (FCFS, SCAN, C-SCAN)

◆ 13. Real Storage – Introduction

• Physical memory / RAM in a computer system
• Directly accessible by the processor
• Key Characteristics:
– Physical Memory: hardware-based (DRAM chips)
– Volatile: loses content when power is turned off
– Fast Access: high-speed read/write for efficient execution
– Temporary Storage: stores actively used data/programs
• Real Storage vs Virtual Storage:
– Real Storage: actual physical memory (RAM)
– Virtual Storage: abstraction allowing use of more memory than physically available

◆ 14. Real Storage Management Strategies

• Continuous Memory Management (Main Memory)
• Non-Continuous Memory Management (Virtual Memory)

■ 14.1 Contiguous Memory Allocation

 • Single contiguous section of memory allocated to a process/file
• All available memory space resides together
• Free partitions not distributed in random fashion

■ 14.2 Non-Contiguous Memory Allocation

• Memory space allocated in different locations as per process requirements
• Available memory in a distributed pattern
• Helps reduce memory waste
• Can give rise to Internal and External Fragmentation

■ 14.3 Difference: Contiguous vs Non-Contiguous Memory Allocation

• Contiguous: consecutive blocks | Non-Contiguous: separate blocks
• Contiguous: faster execution | Non-Contiguous: slower execution
• Contiguous: easier OS control | Non-Contiguous: harder OS control
• Contiguous: min overhead | Non-Contiguous: more overhead
• Contiguous: both internal & external fragmentation | Non-Contiguous: only external
• Contiguous: single/multi-partition | Non-Contiguous: paging and segmentation
• Contiguous: memory wastage | Non-Contiguous: no wastage
• Contiguous: implemented using Arrays | Non-Contiguous: Linked Lists
• Contiguous: fixed degree of multiprogramming | Non-Contiguous: not fixed

◆ 15. Single Partition Allocation

• Entire RAM allocated to single partition for one process
• Key Features:
– Single Process at a Time
– No Multiprogramming
– No Memory Fragmentation
• Advantages: Simplicity; No Fragmentation
• Disadvantages: Inefficient Memory Usage; No Multiprogramming; Limited Scalability

◆ 16. Fixed-Partition Multiprogramming

• Processor underutilization in single-user batch systems
• Multiprogramming: several users simultaneously compete for system resources
• I/O operations and processor calculations occur simultaneously
• Several processes in main memory at the same time
• Absolute assembler/compiler: job location fixed before launch
• Wasted memory: job waits if its partition is occupied
• Memory waste under fixed-partition (Fig 9.8)
• Fixed-partition with relocatable translation and loading
• Protection schemes:
– Boundary Registers (Base and Limit registers)
– Two boundary registers per partition: low (base) and high (limit)

◆ 17. Variable Partition Multiprogramming

• System memory divided into variable-sized partitions
• Partition size adjusted at runtime
 • Used in general-purpose operating systems
• OS makes no assumption about job size (except must fit in memory)
• External fragmentation – holes appear as processes finish
• No internal fragmentation (partition = exact process size)
• Memory 'holes' (Fig 9.13)
• Coalescing: merging adjacent free holes into single larger hole

■ 17.1 Memory Placement Strategies

• First-fit Strategy: place job in first hole large enough
– Advantage: fast placement decision
• Best-fit Strategy: place job in smallest fitting hole
– Advantage: minimizes wasted space per placement
– Disadvantage: requires searching all holes; leaves many small unusable holes
• Worst-fit Strategy: place job in largest available hole
– Advantage: remaining hole often still large enough for new process
– Disadvantage: requires searching for largest hole; leaves many small unusable holes
 UNIT IV — Virtual Storage

◆ 1. Virtual Memory
• Combines physical RAM and disk space (paging file/swap space)
• Creates illusion of a single, large memory space (virtual address space)
• Allows programs larger than physical RAM to run
• Increases multitasking by moving inactive data to disk
• Simplifies programming – vast addressable space
• MMU (Memory Management Unit) translates logical → physical addresses
• Page fault triggers data movement between RAM and disk

■ 1.1 Objectives of Virtual Memory

• Program does not need to be fully loaded to run – only needed parts loaded
• Programs can be bigger than physical memory available
• Creates illusion of large memory even if actual RAM is small
• Uses both RAM and disk storage; loads only parts of programs into RAM as needed
• Allows system to run more programs at once; manages memory more efficiently

◆ 2. Virtual Storage Management Strategies

• Virtual memory uses both hardware and software
• Programs use virtual addresses (not real memory locations)
• System converts virtual addresses → physical addresses at runtime
• Only small portion of code/data needs to be in main memory at once
• Key: mapping virtual addresses to physical addresses (translation)
• Translation must happen quickly to avoid performance degradation

■ 2.1 Dynamic Address Translation (DAT)

• DAT mechanisms convert virtual addresses to physical addresses during execution
• Artificial Contiguity: contiguous virtual addresses need not be contiguous in physical memory
• Fig 4.1 – Virtual Memory process
• Fig 4.2 – Mapping virtual addresses to real addresses
• Fig 4.3 – Artificial contiguity
• Programmer freed from concerns about memory placement and overlays
• Programmer focuses on algorithm efficiency and program structure

◆ 3. Page Replacement Strategies

■ 3.1 What is Paging?

• Memory management technique for allocating memory to processes
• Physical memory (RAM) divided into fixed-size blocks called frames
• Logical memory divided into blocks of same size called pages
• When process executes: pages loaded into available frames
• Efficiency of page replacement algorithm affects page fault rate → system performance
■ 3.2 Common Page Replacement Techniques

■ Technique 1: Random (RAND) Page Replacement

• Each page in main memory has equal likelihood of being replaced
• Easy to implement; low overhead
• Problem: may accidentally replace page that will be referenced next
• Benefit: makes replacement decisions quickly and fairly
• Rarely used due to hit-or-miss approach

■ Technique 2: First-In-First-Out (FIFO) Page Replacement

• Replaces the page that has been in the system the longest
• System keeps track of order in which pages enter main memory
• Tail of queue = new pages; Head of queue = oldest pages (to be replaced)
• Intuitive appeal: oldest page has had its chance; time to give another a chance
• Fig 11.2 – FIFO page replacement diagram

■ Technique 3: Least-Recently Used (LRU) Page Replacement

• Relies on locality heuristic: recent past behavior predicts near future behavior
• Replaces page that has spent longest time without being referenced
• Better performance than FIFO – at cost of higher system overhead
• Implementation: list structure with one entry per occupied page frame
– Every time a page frame is referenced → its entry moved to head of list

■ Technique 4: Least Frequently Used (LFU) Page Replacement

• Makes replacement decisions based on intensity of page usage
• Replaces page that is least frequently used / least intensively referenced
• Based on heuristic: page not intensively used is less likely to be needed
• Implementation: counter updated each time page is referenced
• Disadvantage: may select most recently brought-in page (used once) for replacement

◆ 4. Working Set Model

• Aims to keep process's working set entirely in main memory

■ 4.1 Defining the Working Set

• Working Set Window (∆): time-based parameter (e.g., last 1000 memory accesses)
• Working Set: all unique pages referenced within this window
• Working Set Size (WSS): number of pages in working set

■ 4.2 Dynamic Frame Allocation

• OS allocates frames equal to working set size
• All actively used pages stay in main memory
• Minimizes page faults; prevents thrashing

■ 4.3 Adapting to Change

• Working set size changes as process's locality of reference changes
• OS dynamically adjusts frame allocation:
– More frames when working set grows
 – Reclaims frames when working set shrinks

■ 4.4 Handling Memory Shortage

• If total frames required > total available frames
• OS may suspend one or more processes to free frames
• Prevents entire system from thrashing

◆ 5. Demand Paging
• Optimization on top of paging memory management method
• Pages loaded into memory only when needed (on demand)
• Not all pages loaded when process starts
• Page Fault: process accesses page not currently in physical memory
• OS loads required pages from virtual memory (disk) into physical memory
• If physical memory is full: OS uses page replacement algorithm

■ 5.1 Steps of Demand Paging

• 1. CPU requests Page 2 → page table checked → page not in memory → page fault occurs
• 2. Page Fault Handling: OS notified → locates Page 2 on disk → finds free frame
• 3. Loading the Page: OS loads Page 2 from disk into free frame → page table updated
• 4. Resuming the Process: CPU notified → process continues executing

◆ 6. Page Size
• Fixed, small unit of virtual memory (e.g., 4KB, 8KB)
• OS uses page size to manage data transfer between RAM and disk
• Breaks programs into pages; physical memory into matching 'frames'
• Efficiently handles memory; solves fragmentation
• Allows processes larger than physical memory to run
• Default: often 4KB; modern CPUs support huge pages (2MB, 1MB) for performance
• Page size balances memory overhead against fragmentation

◆ 7. Processor Management
• Core OS function – creating, scheduling, and coordinating processes
• Ensures efficient CPU utilization and smooth system performance
• Single-tasking: easy management (one process at a time)
• Multiprogramming/Multitasking: complex; multiple processes share CPU
• Resource sharing: active processes may share memory and other resources
• Process synchronization: needed when processes interact/communicate

■ 7.1 Process Management Tasks

• Process Creation and Termination
– Creation: create PID, set up PCB
– Termination: clear all allocated resources
• CPU Scheduling: smooth execution of multiple processes
• Deadlock Handling: prevent cyclic dependency among processes
• Inter-Process Communication: shared memory, message passing
• Process Synchronization: controlled access to shared resources
◆ 8. Process Scheduling
• Handles removal of running process from CPU and selection of next process
• Process moves between scheduling queues throughout its lifetime

◆ 9. Process Scheduler
• Decides order in which processes are executed by CPU
• Manages CPU time allocation among competing tasks/processes

◆ 10. Types of Process Schedulers

■ 10.1 Long-Term Scheduler (Job Scheduler)

• Loads processes from disk into main memory to begin execution
• New process → Ready state
• Key Functions:
– Transfers processes from Job Queue to Ready Queue
– Controls degree of multiprogramming
– Selects balanced mix of I/O-bound and CPU-bound processes
– Prevents CPU or I/O devices from being idle
– May not exist in modern time-sharing systems (e.g., Windows)
• Performance: slowest scheduler; operates least frequently

■ 10.2 Short-Term Scheduler (CPU Scheduler)

• Selects process from ready queue and assigns CPU to it
• Key Functions:
– Frequently selects next process to execute from ready state
– Ensures no process suffers from starvation
– Uses CPU scheduling algorithms to decide process order
– Maximizes CPU utilization
– Calls dispatcher for actual context switch
• Performance: fastest scheduler; operates every few milliseconds
• Saves context (PCB) of previously running process
• Switches system mode from kernel to user mode
• Jumps to proper location in newly loaded program
• Note: Time taken by dispatcher = dispatch latency / process context switch time

■ 10.3 Dispatcher
• Special program that transfers CPU control to chosen process
• Functions:
– Context Switching: saves state of old process; restores state of new one
– Mode Switching: transitions from kernel mode to user mode
– Program Control Transfer: jumps to correct starting point in new program
• Dispatcher Example (FCFS: P1→P2→P3→P4):
– Scheduler selects P1 → Dispatcher loads P1 onto CPU
– Scheduler selects P2 → Dispatcher assigns P2 → and so on
– Time for context switching = dispatch latency
■ 10.4 Medium-Term Scheduler
• Manages swapping – temporarily moves processes between memory and disk
• Key Functions:
– Swaps processes out of memory when waiting (e.g., blocked for I/O)
– Reduces degree of multiprogramming
– Frees memory for other active processes
– Swaps processes back in when ready to continue
– Maintains effective mix of CPU-bound and I/O-bound processes
• Performance: faster than long-term; slower than short-term scheduler

◆ 11. Comparison of Schedulers

• Long-Term: job scheduler | Short-Term: CPU scheduler | Medium-Term: process-swapping scheduler
• Speed: Long-Term (slowest) | Short-Term (fastest) | Medium-Term (in between)
• Control: Long-Term (controls degree of multiprogramming)
• Control: Short-Term (less control over multiprogramming degree)
• Medium-Term reduces degree of multiprogramming
• Time-sharing: Long-Term (barely present) | Short-Term (essential) | Medium-Term (component)
• Re-introduction: Long-Term and Medium-Term can re-enter process into memory

◆ 12. Categories of Scheduling

• Non-Preemptive: process runs until it finishes or transitions to waiting; then CPU switches
• Preemptive: OS can switch process from running to ready state at any time
– Switching because higher-priority process arrives

◆ 13. Scheduling Algorithms

■ 13.1 First-In-First-Out (FIFO) / FCFS Scheduling

• Simplest scheduling algorithm; also called First-Come-First-Served (FCFS)
• Processes dispatched according to arrival time at ready queue
• Non-preemptive: once a process has CPU, it runs to completion
• Fair: treats all processes equally by arrival time
• Unfair: long processes make short processes wait
• Not useful for interactive processes – cannot guarantee short response times
• Fig: First-in-first-out scheduling diagram

■ 13.2 Round-Robin (RR) Scheduling

• Processes dispatched FIFO but given limited processor time (time slice / quantum)
• If process does not complete before quantum expires: system preempts it
• Preempted process placed at back of ready queue
• Effective for interactive environments – guarantees reasonable response times
• Reduces preemption overhead via efficient context-switching
• Often found within more complex scheduling algorithms
• FIFO and RR required by POSIX specification for real-time systems
• Fig: Round-robin scheduling diagram

■ 13.3 Shortest-Process-First (SPF) Scheduling

 • Non-preemptive: selects waiting process with smallest estimated run-time-to-completion
• Reduces average waiting time compared to FIFO
• Waiting times have larger variance (more unpredictable), especially for large processes
• Minimizes number of waiting processes
• Minimizes average waiting time of processes

■ 13.4 Shortest-Remaining-Time (SRT) Scheduling

• Preemptive counterpart of SPF
• Selects process with smallest estimated run-time-to-completion
• Newly arriving process with shorter estimated run-time preempts running process
• In SPF: process runs to completion once started
• In SRT: shorter arriving process can preempt longer running process
• Algorithm maintains elapsed service time of running process
• Newly arriving short processes execute almost immediately
• Longer processes: even longer mean waiting time and variance than in SPF
• Greater overhead in SRT than SPF

■ 13.5 Multilevel Feedback Queues Scheduling

• Used when nature of process not yet established
• I/O-bound: uses CPU briefly before I/O request
• Processor-bound: may use CPU for hours if available
• Scheduling goals:
– Favor short processes
– Favor I/O-bound processes for good I/O utilization and interactive response
– Determine process nature quickly; schedule accordingly
• New process enters tail of highest queue → progresses in FIFO order
• Process completes or gives up CPU → exits queuing network
• Process quantum expires → placed at tail of next lower-level queue
• Process keeps moving to lower queues as long as it uses full quantum
• Bottom-level queue: process circulates round-robin until completion
• Next process = head of highest non-empty queue
• Running process preempted by one arriving in higher queue

◆ 14. Priorities
• Schedulers use priorities to decide scheduling and dispatching
• Priorities quantify relative importance of processes

■ 14.1 Static Priorities

• Remain fixed – relatively easy to implement
• Low overhead
• Not responsive to environment changes

■ 14.2 Dynamic Priorities

• Responsive to change
• Example: increase priority of process holding key resource needed by higher-priority process
• Lower priority after resource relinquished
• More complex to implement; greater overhead than static schemes
◆ 15. Deadline Scheduling
• Certain processes scheduled to complete by a specific time or deadline
• High value if delivered on time; little or no value otherwise
• Complexity reasons:
– User must supply precise resource requirements in advance (rarely available)
– System should not degrade service to other users
– Careful resource planning required through to deadline
– New arriving processes make unpredictable demands
– Many active deadline processes can make scheduling extremely complex
 UNIT V — Device and Information Management

◆ 1. Disk Management
• Processor and main memory speeds increased faster than secondary storage devices
• Processes requesting secondary storage data experience relatively long delays

◆ 2. Evolution of Secondary Storage

• Early computers: punched cards and punched paper tape (holes represent bits)
• Labor-intensive and slow to write/load software using such media
• Need for inexpensive, rewritable persistent storage → magnetic storage development
• Magnetic storage: records data bits by changing magnetization direction on medium surface
• Read-write head: hovers above medium; reads by measuring current changes; writes by changing
magnetization
• Challenge: head must float extremely close to surface without touching it

■ 2.1 Magnetic Tape Storage

• Introduced in 1951 by designers of UNIVAC 1
• Persistent and rewritable; sequential access storage
• Similar to audio/video cassettes
• Inappropriate for transaction-processing applications

■ 2.2 Hard Disk Drive (HDD)

• IBM introduced first commercial HDD: RAMAC (Random Access Method of Accounting and Control), 1957
• Random access / direct access device – not limited to sequential data access
• RAMAC capacity: 5 megabytes; cost: $50,000
• High cost initially limited use to large installations

◆ 3. Characteristics of Moving Head Disk Storage

• Variable access speed depending on relative position of read-write head and data
• Data recorded on magnetic platters connected to spindle rotating at high speed

■ 3.1 Physical Components

• Platters: magnetic disks on spindle
• Spindle: rotates platters at thousands of revolutions per minute (RPM)
• Read-write head: separated by tiny gap from disk surface
• Disk arm: connects read-write head to actuator
• Actuator (boom / moving-arm assembly): moves disk arm parallel to disk surface
• Cylinder: vertical set of circular tracks accessible at a given arm position

■ 3.2 Timing Components

• Rotational Latency Time: time for data to rotate to read-write head
• Average Rotational Latency: half the time for one full revolution
• Seek Operation: moving disk arm to a new cylinder
• Seek Time: time for head to move from current cylinder to target cylinder
 • Sectors: tracks divided into sectors (often 512 bytes each)
• Locating data: specify Head + Cylinder + Sector
• Transmission Time: time for record to spin by the read-write head

■ 3.3 Hard Disk Models – Average Seek & Rotational Latency Table
• Maxtor Diamondmax Plus9 (High-end Desktop): Seek 9.3ms | Latency 4.2ms
• WD Caviar (High-end Desktop): Seek 8.9ms | Latency 4.2ms
• Toshiba MK8025GAS (Laptop): Seek 12.0ms | Latency 7.14ms
• WD Raptor (Enterprise): Seek 5.2ms | Latency 2.99ms
• Cheetah 15K3 (Enterprise): Seek 3.6ms | Latency 2.0ms

■ 3.4 Diagrams
• Fig: Schematic side view of a moving-head disk
• Fig: Schematic top view of a disk surface

◆ 4. Need for Disk Scheduling

• Multiple processes generate simultaneous disk read/write requests
• Requests arrive faster than disk can service them → waiting queues build up
• Early systems: First-Come-First-Served (FCFS) – fair but can cause long wait times under heavy load
• FCFS: random seek pattern → time-consuming seeks between innermost/outermost cylinders
• Disk Scheduling: reordering request queue to reduce total seek time
• Disk scheduling can significantly improve throughput
• Disk scheduler examines positional relationships; reorders for minimum mechanical motion
• Two types: Seek Optimization and Rotational Optimization
• Most algorithms focus on minimizing total seek time (seek times > latency times)

◆ 5. Disk Scheduling Strategies

• Evaluation criteria:
– Throughput: number of requests serviced per unit time
– Mean Response Time: average time spent waiting for a request
– Variance of Response Times: measure of predictability
• Goal: maximize throughput + minimize mean response time
• Many strategies minimize lengthy seeks to achieve these goals
• Fig: Disk Pattern Request (example: requests at 82,170,43,140,24,16,190; head at 50)

■ 5.1 FCFS (First-Come-First-Served) Disk Scheduling

• Simplest disk scheduling algorithm
• Requests addressed in order they arrive in disk queue
• Example: requests (82,170,43,140,24,16,190), head at 50
• Advantages: every request gets fair chance; no indefinite postponement
• Disadvantages: does not optimize seek time; may not provide best service

■ 5.2 SSTF (Shortest Seek Time First)

• Executes request with shortest seek time first
• Seek time calculated in advance for all queued requests
• Request nearest to current disk arm position executed first
 • Improvement over FCFS: decreases average response time; increases throughput
• Example: requests (82,170,43,140,24,16,190), head at 50
• Advantages: lower average response time; higher throughput
• Disadvantages: overhead to calculate seek time; can cause starvation; high variance of response time

■ 5.3 SCAN (Elevator Algorithm)

• Disk arm moves in one direction; services requests in its path
• After reaching end of disk: reverses direction; services requests in new path
• Works like an elevator – also known as Elevator Algorithm
• Requests at midrange serviced more; requests behind arm must wait
• Example: requests (82,170,43,140,24,16,190), head at 50, moving toward larger values
• Advantages: high throughput; low variance of response time; average response time
• Disadvantages: head may move to disk end unnecessarily; high waiting time for some; new requests may
wait longer

■ 5.4 C-SCAN (Circular SCAN)

• SCAN problem: re-scans already scanned area after reversing
• C-SCAN: arm does not reverse; goes to other end of disk and starts servicing from there
• Disk arm moves in circular fashion
• Example: requests (82,170,43,140,24,16,190), head at 50, moving toward larger values
• Advantages: eliminates starvation; better performance for heavy disk load; more fair than SCAN
• Disadvantages: extra head movement due to return to start; increased seek time vs SCAN in light load;
more overhead

■ 5.5 LOOK
• Similar to SCAN except arm goes only as far as last request in current direction
• Reverses from last request position (not from end of disk)
• Prevents extra delay from unnecessary traversal to disk end
• Example: requests (82,170,43,140,24,16,190), head at 50, moving toward larger values
• Advantages: reduced unnecessary movement; faster response
• Disadvantages: waiting time can still be high for some requests; performance depends on request
distribution; not completely fair to newly arrived requests

■ 5.6 C-LOOK
• C-LOOK is to LOOK as C-SCAN is to SCAN
• Arm goes only to last request in current direction
• From there: jumps to other end's last request (circular pattern)
• Prevents extra delay from unnecessary traversal to disk end
• Example: requests (82,170,43,140,24,16,190), head at 50, moving toward larger values
• Advantages: uniform wait time; reduced head movement vs C-SCAN
• Disadvantages: extra head movement from circular scanning; increased seek time vs LOOK in light load;
newly arrived requests may wait for full cycle

◆ 6. Seek Optimization
• Seek Time: time required by read/write head to move from one track to another
• Most disk scheduling algorithms use seek time as the optimization criterion
• Seek time can be reduced if successive requests belong to same or nearby track
 • Formula: Seek Time = (Time to cross 1 cylinder/track) × (Number of cylinders/tracks crossed)
• Important points:
– Time required by read/write head to move from one track to another
– Most disk scheduling algorithms only use seek time
– Can be reduced if subsequent requests are on the same or nearby track

◆ 7. File and Database System

■ 7.1 Data Hierarchy

• Bits: lowest level; absence or presence of holes/signal
• Fixed-length bit patterns: bytes (8 bits), characters, words (32-bit or 64-bit)
• Characters: map bytes to symbols (letters, numbers, punctuation)
• Character sets: ASCII (8-bit; 256 possible characters), EBCDIC (mainframe; 8-bit), Unicode
• Field: group of characters (e.g., name, address, phone number)
• Record: group of fields (e.g., student record)
• File: group of related records
• Volume: unit of data storage holding multiple files (physical and logical)

■ 7.2 Files
• Named collection of data manipulated as a unit
• File operations:
– open – prepare file to be referenced
– close – prevent further reference until reopened
– create – create a new file
– destroy – remove a file
– copy – copy contents of one file to another
– rename – change name of a file
– list – print or display file contents
• Data item operations:
– read – copy data from file to process memory
– write – copy data from process memory to file
– update – modify existing data item in file
– insert – add new data item to file
– delete – remove data item from file
• File attributes:
– size – amount of data stored
– location – where file is stored
– accessibility – access restrictions
– type – how file data is used (executable, data file)
– volatility – frequency of additions/deletions
– activity – percentage of records accessed in a period
• Physical record (physical block): unit actually read/written to storage
• Logical record (logical block): collection of data treated as unit by software
• Blocked records: physical record contains multiple logical records
• Unblocked records: physical record contains exactly one logical record
• Fixed-length records: all records same length
• Variable-length records: records vary in size up to block size

■ 7.3 File Systems

 • Organizes files and manages access to data
• Responsibilities:
– File management: stored, referenced, shared, secured
– Auxiliary storage management: allocates space on secondary/tertiary storage
– File integrity mechanisms: ensures stored information is uncorrupted
– Access methods: how stored data can be accessed
• Primarily manages secondary storage (disk storage)

■ 7.4 Directories
• Files containing names and locations of other files in the file system
• Directory field table:
– Name: character string representing file name
– Location: physical block or logical location (pathname)
– Size: number of bytes consumed by file
– Type: file purpose (data file or directory file)
– Access time: time file was last accessed
– Modified time: time file was last modified
– Creation time: time file was created

■ 7.4.1 Single Level File System

• Simplest organization – flat directory structure
• All files stored using one directory
• No two files can have same name
• Rarely implemented – most environments have many files sharing same names

■ 7.4.2 Hierarchically Structured File System

• Root: shows where root directory begins on storage device
• Directories: files that can point to other directories and files
• Root directory → user directories → individual files
• Windows: root = C:, delimiter = backslash (e.g., C:\Jones\Payroll)
• UNIX-based: root = /, delimiter = slash (e.g., /jones/payroll)
• Parent directory: one level higher in hierarchy
• '..' reference: parent directory (in Windows and UNIX-based systems)
• Fig: Two-level Hierarchical File System

■ 7.4.3 Links
• Link: directory entry referencing file/directory in different directory
• Used to simplify navigation and share files
• Soft Link (Symbolic Link / Shortcut / Alias):
– Directory entry containing pathname of another file
– File system locates target by traversing directory structure
• Hard Link:
– Directory entry specifying physical location of file (block number)
– File system locates data by directly accessing referenced physical block

■ 7.5 File Organization

• Refers to arrangement of records on secondary storage
• Four schemes:
– Sequential: records in physical order; next record physically follows previous
 – Direct: records directly accessed by physical addresses on DASD (random access)
– Indexed Sequential: records in logical sequence by key; index holds physical addresses; sequential or direct
access
– Partitioned: file of sequential sub-files (members); starting address of each member in file's directory

■ 7.6 File Allocation

• Problem similar to main memory allocation under variable-partition multiprogramming
• Fragmentation increases as files are allocated and freed over time

■ 7.6.1 Contiguous File Allocation

• File data placed at contiguous addresses on storage device
• User specifies amount of space needed in advance
• Cannot create file if desired contiguous space unavailable
• Advantage: successive logical records physically adjacent → faster access
• Advantage: directories only store start address and length
• Disadvantage: external fragmentation (same as variable-partition multiprogramming)
• Disadvantage: file growth beyond original size requires transfer to new area → extra I/O
• Disadvantage: users may overestimate storage needs → inefficient allocation
• Useful for write-once CDs and DVDs

■ 7.6.2 Linked-List Non-Contiguous File Allocation

• Directory entry points to first sector of file
• Each sector: data portion + pointer to next sector
• Sequential sector access for read/write head
• Advantage: solves some contiguous allocation problems
• Disadvantage: records scattered → many extra seeks for direct/sequential access
• Disadvantage: pointers reduce space available for file data per sector
• Block Allocation (Extents):
– Allocate blocks (contiguous sectors) instead of individual sectors
– System allocates new blocks as close as possible to existing file blocks
• Block Chaining:
– Directory entry → first block of file
– Each block: data portion + pointer to next block
– Smallest allocation unit: fixed-size block (many sectors)
– Finding record: search block chain then search within block
– Chain searched from beginning → slow if blocks are dispersed
– Insertion/deletion: modify pointer in previous block
– Some systems use doubly linked lists for bidirectional search

■ 7.6.3 Tabular Non-Contiguous File Allocation

• Pointers to file blocks stored contiguously in tables
• Reduces number of lengthy seeks for accessing records
• Directory entry indicates first block of file
• Block number used as index into block allocation table → next block found
• Last block's table entry stores null value
• Example: Microsoft's FAT (File Allocation Table) file system
– First incorporated in MS-DOS 1.0

■ 7.6.4 Indexed Non-Contiguous File Allocation

 • Uses index blocks to point to data in a file
• Each file has one or more index blocks
• Index block: list of pointers to file data blocks
• File's directory entry → index block
• To locate record: traverse directory → load index block → use pointers
• Large files: multiple index blocks needed
• Chaining: last few entries in index block point to more index blocks
• Fig: Index block chaining

■ 7.7 Free Space Management

■ 7.7.1 Freelist Method

• Linked list of blocks containing locations of free blocks
• Last entry of free list block → pointer to next free list block
• Last entry of last free list block → null pointer
• Allocating: find free block in free list → write new data → remove entry from list
• System allocates from beginning of free list; freed blocks appended to end
• Head and tail pointers stored in file system's superblock
• Free block located with single pointer; addition requires following one pointer
• Low overhead for maintenance operations
• Disadvantage: fragmentation of free space → non-contiguous allocation → slower file access

■ 7.7.2 Bitmap Method

• Contains one bit for each block in the file system
• i-th bit corresponds to i-th block
• Bit = 1: block in use | Bit = 0: block free
• Bitmap spans multiple blocks
• Example: if each block stores 32 bits, 15th bit of 3rd bitmap block = block 79
• Fig: Free space management using a bitmap

■ 7.8 File Descriptors

• File open operation → OS traverses directory structure to find file info
• System maintains open-file table in main memory to avoid repeated traversals
• File open operation returns file descriptor (non-negative integer)
• File descriptor indexes into open-file table
• All subsequent file access directed through file descriptor
• Open-file table contains File Control Blocks (FCB) – also called file attributes
• Typical FCB contents:
– Symbolic name
– Location in secondary storage
– Organization structure (sequential, direct access, etc.)
– Device type (hard disk, CD-ROM)
– Access control data (which users can access; type of access permitted)
– Type (data file, object program, C source program, etc.)
– Disposition (permanent vs. temporary)
– Creation date and time
– Date and time last modified
– Access activity counts (number of reads, etc.)
■ 7.9 File Access Control

■ 7.9.1 Access Control Matrix

• Two-dimensional matrix listing all users and all files
• Entry a[i][j] = 1: user i allowed access to file j | 0: not allowed
• Example: user 5 can access all 10 files; user 4 can access only file 1
• Problem: large matrix in installations with many users and files
• Matrix is extremely sparse (access is the exception, not the rule)
• Codes indicate types of access: read-only, write-only, execute-only, read/write
• Using codes substantially increases matrix size
• Fig: Access control matrix

■ 7.9.2 Access Control by User Classes

• Requires much less space than access control matrix
• Common file access classification scheme:
– Owner: user who created the file; unrestricted access; can change permissions
– Specified User: owner specifies another individual may use the file
– Group (or Project): members of a group working on a project; access to shared project files
– Public: file designated as public; accessible by any system user; typically read/execute only, not write

System Software and Operating Systems | Subject Code: 43A | Dept. of IT