BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

BESC104E / 204E · Essentials of Information Technology · VTU 2025 Scheme

Module 2
Operating Systems & Algorithms
Textbook 1 · Chapter 3 & Chapter 5 (5.1–5.3) · 8 Hours

Section Topic

3.1 History of Operating Systems

3.2 Operating System Architecture

3.3 Coordinating the Machine's Activities

3.4 Handling Competition Among Processes

3.5 OS Security

5.1 The Concept of an Algorithm

5.2 Algorithm Representation

5.3 Algorithm Discovery (Problem Solving)

Page 1
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

— Part A — Operating Systems —

3.1

History of Operating Systems

An Operating System (OS) is system software that acts as an intermediary between the user/application
programs and the computer hardware. It manages hardware resources and provides services for
applications. The evolution of OSes mirrors the evolution of computers themselves.

KEY DEFINITION

An Operating System is a collection of programs that manage computer hardware

resources, provide common services for application programs, and serve as the
interface between users and hardware.

Generation 1 — No OS (1940s)

Early computers like ENIAC had no operating system. Programmers operated the machine directly by
plugging cables and setting switches. Each job (program) was loaded manually — one program ran at a
time. Computers were exclusively available to one user at a time and were incredibly slow to use.

Generation 2 — Batch Processing (1950s)

Operators collected a batch of jobs (on punched cards or magnetic tape), fed them sequentially into the
computer, and collected the output. A simple resident monitor (precursor to the OS) automatically loaded
and ran each job. No user interaction with the running job was possible.

ANALOGY

Batch processing is like a laundromat — you drop off all your clothes (jobs), they are
processed in sequence without your involvement, and you pick up the results later.

Generation 3 — Multiprogramming & Time-Sharing (1960s)

Multiprogramming: Multiple programs are loaded into memory simultaneously. When one program waits
for I/O, the CPU switches to another — dramatically improving CPU utilization. Time-sharing (CTSS,
Multics) rapidly switched the CPU among multiple users, giving each the illusion of having the whole
machine, enabling interactive computing for the first time.

Generation 4 — Personal Computers (1980s–1990s)

Microprocessors led to affordable personal computers. OSes like MS-DOS (single-user, command-line) and
then Windows/macOS (graphical user interfaces with windows, icons, menus, pointer) made computers
accessible to non-experts.

Generation 5 — Distributed & Mobile Systems (2000s–present)

Modern OSes manage networked/distributed systems (Linux, Windows Server), mobile platforms (Android,
iOS), cloud infrastructure, and embedded systems. Key concerns: security, power management, multi-core

Page 2
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

processing, and virtualization.

Era Key Development Example

1940s No OS — manual operation ENIAC

1950s Batch processing — simple monitors IBM 701

1960s Multiprogramming & time-sharing Multics, IBM OS/360

1970s Unix — multi-user, portable OS UNIX (Bell Labs)

1980s–90s Personal computer OSes, GUIs MS-DOS, Windows, macOS

2000s+ Distributed, mobile, cloud OSes Linux, Android, iOS

3.2

Operating System Architecture

The architecture of an OS defines how it is internally organized. At the bottom sits the hardware; at the top
sit the user applications; in between is the OS providing services through a well-defined interface.

The Kernel

The kernel is the core of the OS — it runs in privileged mode and has direct access to hardware.
Everything else is user-mode software that requests services from the kernel via system calls. The kernel
handles memory management, process scheduling, device drivers, and inter-process communication.

KEY CONCEPT — DUAL MODE OPERATION

Modern CPUs operate in two modes. Kernel mode: All instructions and hardware access
are permitted. User mode: Programs have restricted access — they cannot directly
access hardware or modify OS data. When an application needs a service (like reading
a file), it makes a system call, which temporarily switches the CPU to kernel mode.

Example
Architecture Description Pros Cons s

A bug
Fast — no anywhere
Entire OS runs in mode can crash
Monolithic kernel mode as one switching the whole Linux,
Kernel large program overhead OS Unix

Slower —
Only minimal core in message Mach,
kernel; rest in user Stable and passing QNX,
Microkernel space secure overhead Minix

Page 3
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Example
Architecture Description Pros Cons s

OS divided into layers; Clean Hard to THE

each uses only layer separation of define layers system,
Layered below concerns cleanly OS/2

Balance of Windows
performance NT,
Monolithic kernel with and macOS
Hybrid microkernel features modularity Complex XNU

Key OS Components: Process manager (creates, schedules, terminates processes), Memory manager
(allocates RAM, handles virtual memory), File system (organized persistent storage), Device manager
(communicates with I/O hardware via drivers), Network manager (handles communication protocols),
Security manager (enforces access control).

3.3

Coordinating the Machine's Activities

Processes and Programs

A program is a passive set of instructions stored on disk. A process is a program in execution — it is

active and has state (its current position in the code, values of its variables, and the resources allocated to
it). One program can spawn multiple processes.

PROCESS COMPONENTS

Every process has: a Program Counter (current instruction), CPU registers (current
working values), a stack (local variables and function calls), heap memory (dynamically
allocated data), and a code/text segment (the program instructions).

Process States

State Meaning

New Process is being created

Ready Loaded in memory, waiting for CPU time

Running Currently executing on the CPU

Waiting / Blocked Waiting for an I/O event or resource

Terminated Finished execution — being cleaned up

CPU Scheduling

Since there are typically many more processes than CPUs, the OS must decide which process gets the
CPU at any given moment. The CPU scheduler aims to maximize CPU utilization, ensure fairness,

Page 4
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

minimize response time, and maximize throughput.

Algorithm How It Works Key Feature

First-Come
First-Served Processes get CPU in arrival Simple; can cause convoy effect —
(FCFS) order short jobs wait behind long ones

Shortest Job First Process with shortest CPU Optimal average wait time; requires
(SJF) burst goes next knowing burst time in advance

Each process gets a fixed

time quantum; then goes to Fair; good for time-sharing; choice of
Round Robin (RR) back of queue quantum is critical

Highest priority process runs Can cause starvation of low-priority

Priority Scheduling first processes

Multiple queues with different

Multilevel Queue priorities and algorithms Flexible; used in most real OSes

ANALOGY — ROUND ROBIN

Round Robin is like a teacher giving each student exactly 2 minutes to ask questions
before moving to the next student. Everyone gets a fair turn; no one monopolizes the
teacher's time.

Context Switching

When the CPU switches from one process to another, it saves the entire state of the current process into
that process's Process Control Block (PCB), and loads the saved state of the next process. This is a
context switch — it is pure overhead; the CPU does no useful work during this time. The OS minimizes
how often they occur.

3.4

Handling Competition Among Processes

When multiple processes run concurrently and share resources (memory, files, devices), conflicts arise.
The OS must manage this competition carefully to prevent errors and ensure system stability.

The Critical Section Problem

A critical section is a segment of code that accesses a shared resource and must not be executed by
more than one process at the same time. If two processes enter their critical sections simultaneously, a
race condition can occur — the final result depends on the unpredictable order of instruction execution,
leading to incorrect outcomes.

RACE CONDITION — EXAM FAVOURITE

Page 5
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Example: Two processes both read a shared counter (value = 5), both add 1, and both
write back 6. The correct answer should be 7. This data corruption is a race condition —
the outcome depends on execution order, which is non-deterministic.

Mutual Exclusion

Mutual exclusion guarantees that only one process can be in its critical section at any time. Solutions must
satisfy three requirements: (1) Only one process in critical section at a time; (2) Progress — a waiting
process should eventually enter; (3) Bounded waiting — no process waits indefinitely.

Semaphores

A semaphore is an integer variable used for synchronization, accessible only through two atomic
operations: wait() (also P/down — decrements the value; if negative, the process blocks) and signal() (also
V/up — increments the value; if any process was blocked, one is woken up). A binary semaphore (0 or 1)
acts as a mutex lock. A counting semaphore controls access to a resource pool.

Deadlock

A deadlock is a situation where two or more processes are permanently blocked, each waiting for a
resource held by another. For deadlock to occur, all four conditions must hold simultaneously:

Condition Meaning

Mutual Exclusion At least one resource is held in a non-sharable mode

Hold and Wait A process holds at least one resource and waits to acquire more

No Preemption Resources cannot be forcibly taken; they must be voluntarily released

A circular chain exists: each process waits for a resource held by the
Circular Wait next

CLASSIC DEADLOCK — THE DINING PHILOSOPHERS

5 philosophers sit at a table. Each needs two forks (shared with neighbors) to eat. If all
pick up their left fork simultaneously, everyone waits for the right fork — deadlock!
Removing any one of the four conditions (e.g., limiting how many can eat at once)
breaks the deadlock.

DEADLOCK vs. STARVATION

Deadlock: a set of processes are ALL permanently stuck — none can proceed.
Starvation: a process CAN proceed but is indefinitely denied resources because others
always get priority. Deadlock requires mutual blocking; starvation does not.

Page 6
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

3.5

OS Security

OS security involves protecting computer resources from unauthorized access, modification, or destruction.
The OS is the first line of defence — if it is compromised, every application running on it is at risk.

Authentication

Authentication verifies the identity of a user or process. Methods: something you know (password, PIN),
something you have (smart card, token), something you are (biometrics — fingerprint, face). Modern
systems use multi-factor authentication (MFA) combining two or more.

Access Control

Once authenticated, access control determines what a user can do. Access Control Lists (ACL) — each
resource has a list of users and their permissions (read, write, execute). Capabilities — each user/process
holds a token granting specific rights. Unix/Linux uses owner/group/other categories, each with read (r),
write (w), execute (x) bits.

Threat Description

Malware Viruses, worms, trojans that compromise the OS or steal data

Privilege Escalation A user gains more access than authorized (e.g., gaining root/admin)

Buffer Overflow Writing beyond allocated memory to overwrite OS data or inject code

Denial of Service
(DoS) Overwhelming system resources so legitimate users cannot be served

Rootkits Malware that hides within the OS kernel to avoid detection

OS SECURITY MECHANISMS

Memory protection (each process has its own address space) · File permissions (ACLs) ·
User account control · Firewalls and sandboxing · Encryption of stored and transmitted
data · Audit logs and intrusion detection

— Part B — Algorithms —

5.1

The Concept of an Algorithm

An algorithm is a finite, ordered set of unambiguous and effectively computable steps that, when followed,
solves a problem or accomplishes a task. Algorithms are the most fundamental concept in computer
science — every program ever written is simply an implementation of one or more algorithms.

Page 7
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

KEY DEFINITION

An algorithm is a well-defined computational procedure that takes some value (or set of
values) as input and produces some value (or set of values) as output. It must be: finite
(must terminate), definite (each step is precisely defined), effective (each step can be
carried out), and correct (produces the right output for all valid inputs).

Five Essential Properties of an Algorithm

Property Meaning Why It Matters

The algorithm must always

terminate after a finite number of
Finiteness steps An infinite loop is not an algorithm

Every step must be precisely and No room for interpretation or

Definiteness unambiguously defined guesswork

Defines what data the algorithm

Input Zero or more well-defined inputs operates on

One or more well-defined Every algorithm must produce a

Output outputs (results) result

Every step must be basic enough

Effectivenes to be carried out exactly in finite Steps like 'find the best solution' are
s time not effective

Algorithm vs. Program: An algorithm is a logical, language-independent description of a solution. A

program is a specific implementation in a particular programming language. The same algorithm can be
implemented in Python, Java, or C. The algorithm is the idea; the program is the realization.

Complexity — Measuring Algorithm Efficiency

Notation Name Growth Rate Example Algorithm

Same time
O(1) Constant regardless of n Accessing an array element by index

Doubling input
adds only 1 extra
O(log n) Logarithmic step Binary search

Directly
O(n) Linear proportional to n Linear search, finding max value

O(n log Slightly worse than

n) Log-linear linear Merge sort, heap sort

Doubling input →
O(n²) Quadratic 4x the work Bubble sort, selection sort

Page 8
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Notation Name Growth Rate Example Algorithm

Extremely fast
O(2■) Exponential growth Brute-force subset problems

WHY COMPLEXITY MATTERS

An O(n²) algorithm on 1,000 items does 1,000,000 operations. An O(n log n) algorithm
does only ~10,000. For 1,000,000 items: a trillion vs. 20 million operations. Choosing the
right algorithm is often far more impactful than buying faster hardware.

5.2

Algorithm Representation

Before writing code, an algorithm must be expressed in a form that is clear and unambiguous. Three
common representations are used in practice.

1. Natural Language Description

The simplest representation — describe steps in plain English. Useful for initial brainstorming and
communicating the high-level idea to a non-technical audience, but can be ambiguous and verbose.

EXAMPLE — Finding maximum of two numbers (Natural Language)

1. Get the first number and call it A. 2. Get the second number and call it B. 3. If A is
greater than B, then the maximum is A. Otherwise, the maximum is B. 4. Display the
maximum.

2. Pseudocode

Pseudocode is an informal, structured description of an algorithm using constructs similar to programming

languages (if/else, while, for) but without strict syntax rules. It is language-independent, concise, and easy
to convert into actual code. It is the most commonly used representation in textbooks and technical
interviews.

ALGORITHM FindMaximum(A, B)
IF A > B THEN
max <- A
ELSE
max <- B
END IF
RETURN max
END ALGORITHM

3. Flowcharts

A flowchart is a graphical representation of an algorithm using standardized symbols. Each symbol

represents a specific type of operation:

Page 9
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Symbol Shape Meaning

Oval / Rounded
Terminal rectangle Start or End of the algorithm

Process Rectangle A computation or assignment step

Decision Diamond A condition (yes/no or true/false branch)

Input/Output Parallelogram Reading input or producing output

Flow Arrow Arrow Direction of control flow

PSEUDOCODE vs. FLOWCHART

Pseudocode is better for complex algorithms with many steps — compact and translates
directly to code. Flowcharts are better for visualizing simple algorithm logic — useful for
teaching and documentation. Most professionals and textbooks prefer pseudocode.

Common Algorithm Patterns

Sequence: Steps executed one after another in order — the default flow. Selection (Branching): IF/ELSE
or SWITCH — chooses which steps to execute based on a condition. Iteration (Looping): A set of steps is
repeated either a fixed number of times (FOR loop) or until a condition is met (WHILE loop).

EXAMPLE — Sum of First N Natural Numbers (Pseudocode)

ALGORITHM SumToN(n) sum <- 0 i <- 1 WHILE i <= n DO sum <- sum + i i <- i + 1 END
WHILE RETURN sum END ALGORITHM

5.3

Algorithm Discovery (Problem Solving)

Algorithm discovery is the creative process of developing an algorithm to solve a problem. Unlike
representing an existing algorithm, discovery requires analytical thinking, creativity, and a systematic
approach — this is the heart of computer science.

The Problem-Solving Process — 5 Phases

Phase Action

1. Understand Read carefully; identify inputs, expected outputs, and constraints

2. Devise a plan Choose a design strategy or approach

3. Carry out the

plan Write the pseudocode or algorithm steps

4. Test / Trace Manually trace through with sample inputs to verify correctness

Page 10
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Phase Action

5. Analyze &
Refine Evaluate correctness and efficiency; refine if needed

Common Algorithm Design Strategies

Strategy Approach Example

Try all possible solutions Linear search, checking all

Brute Force exhaustively permutations

Divide and Split into sub-problems, solve

Conquer each, combine Merge sort, binary search, quicksort

At each step, make the locally Coin change (greedy), Dijkstra's

Greedy optimal choice algorithm

Store solutions to overlapping

Dynamic sub-problems; avoid
Programming recomputation Fibonacci, Floyd-Warshall shortest path

Build solution incrementally;

Backtracking abandon wrong paths early Sudoku solver, N-Queens problem

WORKED EXAMPLE — Discovering Binary Search

Problem: Find whether value X exists in a sorted list of N numbers. Naive approach
(brute force): Check each element one by one — O(n). Better approach (Divide and
Conquer — Binary Search): Look at the middle element. If it equals X: done. If X is
smaller: search the left half. If X is larger: search the right half. Each comparison halves
the search space → O(log n). For N = 1,000,000, only ~20 comparisons needed instead
of 1,000,000!

Recursion as an Algorithm Technique

Recursion is a technique where a function calls itself to solve a smaller version of the same problem. A
recursive algorithm must have: a base case (a condition under which it returns without calling itself) and a
recursive case (where it calls itself with a smaller input).

ALGORITHM Factorial(n)
IF n = 0 THEN
RETURN 1 <- base case
ELSE
RETURN n x Factorial(n - 1) <- recursive case
END IF
END ALGORITHM

RECURSION vs. ITERATION

Page 11
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

Any recursive algorithm can be converted to an iterative one and vice versa. Recursion
is often more elegant — especially for problems with natural recursive structure (trees,
graphs). Iteration is generally more memory-efficient — it does not use the call stack.

Page 12
BESC104E/204E — Essentials of Information Technology Module 2: Operating Systems & Algorithms

— Module 2 — Quick Revision Summary —

Key Takeaways at a Glance

Topic Core Idea to Remember

Interface between user/apps and hardware; manages all

OS Definition resources

OS History Manual → Batch → Multiprogramming → GUI → Mobile/Cloud

Core of OS; runs in privileged mode; handles all hardware

Kernel access

Kernel mode (full access) vs. User mode (restricted); system

Dual Mode calls bridge them

Program = passive file on disk; Process = active execution

Process vs. Program instance with state

Process States New → Ready → Running → Waiting → Terminated

FCFS, SJF, Round Robin, Priority — each with different

CPU Scheduling trade-offs

Context Switch Save current process PCB, load next PCB — pure overhead

Code accessing shared resource; only one process at a time

Critical Section (mutual exclusion)

Synchronization tool: wait() blocks, signal() wakes; binary =

Semaphore mutex lock

4 conditions must ALL hold: Mutual exclusion + Hold&Wait; +

Deadlock No Preemption + Circular Wait

Authentication + Access control + Memory protection +

OS Security Encryption

Finite, definite, effective steps that solve a problem — 5

Algorithm essential properties

Complexity O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2■)

Natural language (simple) → Pseudocode (technical) →

Representation Flowchart (visual)

Brute force / Divide & Conquer / Greedy / Dynamic

Design Strategies Programming / Backtracking

Function calls itself; must have a base case + recursive case to

Recursion terminate

Page 13