Computer Science संगणकशास्त्र

Quick summary

This topic goes deeper into how an operating system manages processes. It covers the process concept and process states, the process control block (PCB), context switching, threads, inter-process communication, the critical-section problem and its solutions (semaphores), classic synchronisation problems, and deadlocks with their conditions, prevention, avoidance (Banker's algorithm) and detection.

Key points

• A process is a program in execution. A program is passive (a file); a process is active (has a program counter, registers, stack, data).
• Process states: new → ready → running → waiting (blocked) → ready … → terminated. The scheduler moves a process from ready to running; an I/O request moves it to waiting.
• PCB stores everything about a process: process ID, state, program counter, CPU registers, scheduling information, memory information, open files, I/O status.
• Context switch: saving the state of the running process in its PCB and loading the state of the next one. It is pure overhead.
• Thread: the smallest unit of CPU execution inside a process. Threads of one process share code, data and files but have their own stack and registers. Multithreading improves responsiveness and resource sharing.
• Inter-process communication (IPC): shared memory and message passing.
• Race condition: the result depends on the order in which processes access shared data.
• Critical section: the part of code that accesses shared data. A solution must satisfy mutual exclusion, progress and bounded waiting.
• Semaphore (Dijkstra): an integer variable accessed only by atomic wait() (P) and signal() (V) operations. Binary semaphore (mutex) and counting semaphore.
• Classic problems: producer–consumer (bounded buffer), readers–writers, dining philosophers.
• Deadlock: a set of processes each waiting for a resource held by another, so none can proceed.
• Four necessary conditions (Coffman): mutual exclusion, hold and wait, no preemption, circular wait. All four must hold together.
• Handling deadlock: prevention (break one condition), avoidance (Banker's algorithm keeps the system in a safe state), detection and recovery (kill a process or preempt resources), or ignore it (ostrich approach).

Important terms

• Process (प्रक्रिया) – program in execution.
• PCB – data structure the OS keeps for each process.
• Mutual exclusion – only one process in the critical section at a time.
• Safe state – state in which the OS can give every process its maximum need in some order.
• Starvation – a process waits indefinitely while others are served.

Formulas

• Banker's algorithm: Need = Max − Allocation
• A process Pᵢ can run if Needᵢ ≤ Available; after it finishes, Available = Available + Allocationᵢ
• Semaphore operations:

5 important questions

Q1. Differentiate between a process and a thread.

A process is an independent program in execution with its own memory space; creating and switching processes is costly. A thread is a lightweight unit inside a process that shares code, data and files with other threads of the same process; switching is cheaper.

Q2. State the four necessary conditions for deadlock.

Mutual exclusion (a resource used by one process at a time), hold and wait (a process holds some resources while waiting for others), no preemption (resources cannot be taken away forcibly), and circular wait (a closed chain of processes, each waiting for the next).

Q3. Five processes P0–P4, one resource type, Available = 3. Allocation = (1, 2, 2, 1, 0), Max = (4, 3, 7, 2, 4). Is the system safe?

• Need = Max − Allocation = (3, 1, 5, 1, 4)
• Available 3 → P1 (need 1) runs; Available = 3 + 2 = 5
• P3 (need 1) runs; Available = 5 + 1 = 6
• P0 (need 3) runs; Available = 6 + 1 = 7
• P4 (need 4) runs; Available = 7; P2 (need 5) runs; Available = 9
• Safe sequence: P1, P3, P0, P4, P2 → system is safe.

Q4. Draw and explain the process state diagram.

• New: process is being created.
• Ready: waiting in the ready queue for the CPU.
• Running: instructions are being executed.
• Waiting: waiting for an I/O or event.
• Terminated: finished.
• Transitions: admitted (new → ready), dispatch (ready → running), interrupt/time-out (running → ready), I/O wait (running → waiting), I/O done (waiting → ready), exit (running → terminated).

Q5. Explain the producer–consumer problem and its solution using semaphores.

• Producer puts items in a bounded buffer of size n; consumer removes them.
• Semaphores: mutex = 1 (mutual exclusion), empty = n (free slots), full = 0 (filled slots).
• Producer: wait(empty); wait(mutex); add item; signal(mutex); signal(full).
• Consumer: wait(full); wait(mutex); remove item; signal(mutex); signal(empty).
• This prevents overflow, underflow and race conditions.

Exam tip

Banker's algorithm and process-state diagram questions are almost certain. In Banker's problems, write the Need table first and show Available after each process.

Quick summary

CPU scheduling decides which process in the ready queue gets the CPU next. Good scheduling keeps the CPU busy and gives quick response. This topic covers scheduling criteria, preemptive and non-preemptive scheduling, the main algorithms (FCFS, SJF, SRTF, Priority, Round Robin, multilevel queue), Gantt charts, and how to calculate waiting time and turnaround time.

Key points

• Long-term scheduler (job scheduler) chooses which jobs enter memory. Short-term scheduler (CPU scheduler) chooses which ready process runs next. Medium-term scheduler swaps processes out and in.
• Dispatcher gives control of the CPU to the selected process; the time it takes is dispatch latency.
• Non-preemptive: once a process gets the CPU, it keeps it until it finishes or waits for I/O. Preemptive: the OS can take the CPU away (time slice over or a higher-priority process arrives).
• Criteria: maximise CPU utilisation and throughput; minimise turnaround time, waiting time and response time.
• FCFS (First Come First Served): simplest, non-preemptive; can cause the convoy effect (short jobs wait behind a long one).
• SJF (Shortest Job First): picks the shortest burst; gives the minimum average waiting time; burst length must be predicted. Preemptive SJF is SRTF (Shortest Remaining Time First).
• Priority scheduling: highest priority first; can cause starvation of low-priority processes, solved by ageing (slowly raising the priority of waiting processes).
• Round Robin (RR): each process gets a fixed time quantum in turn; preemptive; good for time-sharing. Very large quantum makes it like FCFS; very small quantum causes too many context switches.
• Multilevel queue: separate queues (e.g. system, interactive, batch) with their own algorithms. Multilevel feedback queue lets processes move between queues.
• A Gantt chart is a bar showing which process runs in which time interval.

Important terms

• Burst time – CPU time a process needs.
• Arrival time – time a process enters the ready queue.
• Turnaround time (TAT) – total time from arrival to completion.
• Waiting time (प्रतीक्षा वेळ) – time spent waiting in the ready queue.
• Time quantum – fixed CPU time slice in Round Robin.

Formulas

• Turnaround Time = Completion Time − Arrival Time
• Waiting Time = Turnaround Time − Burst Time
• Response Time = First time on CPU − Arrival Time
• Average = sum for all processes ÷ number of processes
• Throughput = number of processes completed ÷ total time

5 important questions

Q1. Differentiate preemptive and non-preemptive scheduling.

In non-preemptive scheduling a running process keeps the CPU until it ends or blocks (FCFS, non-preemptive SJF). In preemptive scheduling the OS may interrupt it to give the CPU to another process (RR, SRTF). Preemptive gives better response but more context switches.

Q2. What is starvation? How is it removed?

Starvation is when a low-priority process waits indefinitely because higher-priority processes keep getting the CPU. It is removed by ageing: gradually increasing the priority of processes that wait for a long time.

Q3. Processes P1, P2, P3 arrive at time 0 with burst times 24, 3, 3 ms. Find average waiting time with FCFS and SJF.

• FCFS order P1, P2, P3: Gantt 0–24 P1, 24–27 P2, 27–30 P3. Waiting: 0, 24, 27 → average = 51/3 = 17 ms.
• SJF order P2, P3, P1: Gantt 0–3 P2, 3–6 P3, 6–30 P1. Waiting: P2 0, P3 3, P1 6 → average = 9/3 = 3 ms.
• SJF greatly reduces waiting time (convoy effect in FCFS).

Q4. Using Round Robin with quantum 4 ms for the same processes (P1 = 24, P2 = 3, P3 = 3, all arriving at 0), draw the Gantt chart and find average waiting and turnaround time.

• Gantt: P1 0–4, P2 4–7, P3 7–10, then P1 runs 10–30 (alone, in slices of 4).
• Completion: P1 = 30, P2 = 7, P3 = 10.
• TAT: P1 30, P2 7, P3 10 → average = 47/3 = 15.67 ms.
• Waiting = TAT − burst: P1 30 − 24 = 6, P2 7 − 3 = 4, P3 10 − 3 = 7 → average = 17/3 = 5.67 ms.

Q5. Explain scheduling criteria and any two algorithms.

• Criteria: CPU utilisation, throughput, turnaround time, waiting time, response time.
• FCFS: simple queue; non-preemptive; convoy effect.
• Round Robin: time quantum; fair; good response; performance depends on quantum size.
• Also mention SJF is optimal for average waiting time but needs burst prediction.

Exam tip

Always draw the Gantt chart with time marks under it, then make a table of CT, TAT and WT. Most errors come from skipping the table.

Quick summary

Memory management is the OS function that allocates main memory to processes and keeps track of which parts are free or in use. This topic covers logical and physical addresses, contiguous allocation (fixed and variable partitions), fragmentation, paging, segmentation, virtual memory with demand paging, page replacement algorithms (FIFO, Optimal, LRU) and thrashing.

Key points

• Logical (virtual) address is generated by the CPU; physical address is the actual location in RAM. The MMU (memory management unit) converts logical to physical addresses.
• Swapping: moving a process temporarily from memory to disk and back.
• Contiguous allocation: each process gets one continuous block. Fixed partitions or variable (dynamic) partitions.
• Placement strategies for variable partitions: first fit (first hole big enough), best fit (smallest hole big enough), worst fit (largest hole).
• Internal fragmentation: unused space inside an allocated block (fixed partitions, paging). External fragmentation: free memory is split into small scattered holes that cannot hold a process. Compaction removes external fragmentation by shifting processes together.
• Paging: logical memory is divided into fixed-size pages, physical memory into frames of the same size. A page table maps pages to frames. Paging removes external fragmentation.
• A TLB (translation look-aside buffer) is a small fast cache of page-table entries that speeds up address translation.
• Segmentation: memory is divided into variable-size logical units (code, data, stack). Each address = (segment number, offset). It matches the programmer's view but has external fragmentation.
• Virtual memory: lets a program run even if it is not fully in RAM; only needed pages are loaded (demand paging).
• Page fault: the needed page is not in memory, so the OS loads it from disk.
• Page replacement algorithms: FIFO (remove the oldest page), Optimal (remove the page not needed for the longest time in future; ideal but not practical), LRU (remove the page not used for the longest time in the past).
• Belady's anomaly: in FIFO, more frames can sometimes cause more page faults.
• Thrashing: the system spends more time swapping pages than executing, because processes do not have enough frames.

Important terms

• Frame – fixed-size block of physical memory.
• Page – fixed-size block of logical memory, same size as a frame.
• Page table (पृष्ठ सारणी) – table mapping page numbers to frame numbers.
• Page fault – reference to a page not in main memory.
• Fragmentation – wasted memory that cannot be used.

Formulas

• Physical address = frame number × page size + offset
• Logical address split: page number = address ÷ page size; offset = address mod page size
• Number of pages = logical address space ÷ page size
• Effective access time (with TLB) = h × (TLB time + memory time) + (1 − h) × (TLB time + 2 × memory time), h = hit ratio
• Page fault rate = page faults ÷ total references

5 important questions

Q1. Differentiate internal and external fragmentation.

Internal fragmentation is wasted space inside an allocated block because the block is larger than needed (fixed partitions, paging). External fragmentation is free memory broken into small non-contiguous holes, so a large process cannot fit even though total free space is enough (variable partitions, segmentation).

Q2. What is thrashing?

Thrashing happens when processes do not have enough frames, so page faults occur continuously. The CPU spends most of its time moving pages between disk and memory, and useful work (CPU utilisation) drops sharply.

Q3. For the reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3 with 3 frames, find page faults using FIFO.

• 7 F [7]; 0 F [7,0]; 1 F [7,0,1]
• 2 F replace 7 → [2,0,1]; 0 hit
• 3 F replace 0 → [2,3,1]; 0 F replace 1 → [2,3,0]
• 4 F replace 2 → [4,3,0]; 2 F replace 3 → [4,2,0]; 3 F replace 0 → [4,2,3]
• Total page faults = 9 (hits = 1)

Q4. For the same string and 3 frames, find page faults using LRU.

• 7 F, 0 F, 1 F → [7,0,1]
• 2 F replace 7 (least recently used) → [2,0,1]; 0 hit
• 3 F replace 1 → [2,0,3]; 0 hit
• 4 F replace 2 → [4,0,3]; 2 F replace 3 → [4,0,2]; 3 F replace 0 → [4,3,2]
• Total page faults = 8 (hits = 2)

Q5. Explain paging with a diagram (in words).

• Logical memory split into pages; physical memory into equal frames.
• CPU address = (page number p, offset d).
• p indexes the page table to get frame f.
• Physical address = f × page size + d.
• Diagram: CPU → (p, d) → page table → (f, d) → physical memory.
• Advantages: no external fragmentation, easy allocation; disadvantage: internal fragmentation in the last page and page-table overhead.

Exam tip

Page replacement numericals appear every year. Draw a frame table column by column and mark F for each fault — it makes counting error-free.

Quick summary

The file system is the part of the operating system that organises data on disk as files and directories. Disk scheduling decides the order in which pending disk requests are served so that the read/write head moves as little as possible. This topic covers file concepts and attributes, access methods, directory structures, allocation methods (contiguous, linked, indexed), free-space management, and the disk scheduling algorithms FCFS, SSTF, SCAN, C-SCAN and LOOK with a solved example.

Key points

• A file is a named collection of related data stored on secondary storage.
• File attributes: name, type (extension), location, size, protection (permissions), owner, time and date.
• File operations: create, open, read, write, seek (reposition), delete, truncate, close.
• Access methods: sequential (one record after another, like a tape), direct/random (jump to any block), indexed (an index points to blocks).
• Directory structures: single-level (all files in one directory), two-level (one directory per user), tree-structured (folders inside folders; absolute and relative paths), acyclic graph (shared files through links).
• Contiguous allocation: each file occupies continuous blocks; fast access, but external fragmentation and hard to grow.
• Linked allocation: each block points to the next; no external fragmentation, but only sequential access and space used by pointers. FAT (File Allocation Table) keeps these links in a table.
• Indexed allocation: an index block holds the addresses of all blocks of the file; supports direct access; Unix inodes use this idea.
• Free-space management: bit vector (1 bit per block), linked list of free blocks, grouping, counting.
• Disk access time = seek time + rotational latency + transfer time. Scheduling aims to reduce seek time, measured as total head movement in cylinders.
• FCFS: serve in arrival order — fair, but large head movement.
• SSTF: serve the nearest request next — less movement, but can starve far requests.
• SCAN (elevator): head moves to one end serving requests, then reverses. LOOK: like SCAN but turns at the last request instead of the disk end.
• C-SCAN: serves in one direction only; at the end it jumps back to the start; gives more uniform waiting time. C-LOOK is the LOOK version.

Important terms

• Block – fixed-size unit of disk storage.
• Inode – Unix structure that stores a file's attributes and block addresses.
• Seek time – time to move the head to the required cylinder.
• Starvation – a request waiting indefinitely.
• Mount – attaching a file system to the directory tree.

Formulas

• Total head movement = Σ |next cylinder − current cylinder|
• Average seek distance = total head movement ÷ number of requests
• Bit-vector size (bytes) = number of blocks ÷ 8

Example used below: disk cylinders 0–199, head at 53, queue: 98, 183, 37, 122, 14, 124, 65, 67.

5 important questions

Q1. Compare contiguous, linked and indexed allocation.

Contiguous: fast sequential and direct access, but external fragmentation and the file size must be known in advance. Linked: no external fragmentation and files grow easily, but direct access is slow and a broken pointer loses data. Indexed: direct access without external fragmentation, but the index block takes extra space.

Q2. A disk has 2 GB of space in 4 KB blocks. How much memory does a bit vector need?

• Blocks = 2 GB ÷ 4 KB = 2³¹ ÷ 2¹² = 2¹⁹ = 524,288 blocks
• Bit vector = 524,288 bits ÷ 8 = 65,536 bytes = 64 KB

Q3. Find the total head movement using FCFS and SSTF for the example.

• FCFS order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
• Movement = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders
• SSTF order: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
• Movement = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders

Q4. Find the total head movement using SCAN and LOOK, with the head moving towards 0.

• SCAN order: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183
• Movement = (53 − 0) + (183 − 0) = 53 + 183 = 236 cylinders
• LOOK order: 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183 (turns at 14)
• Movement = (53 − 14) + (183 − 14) = 39 + 169 = 208 cylinders
• C-SCAN moving towards 199: 53 → 65 … 183 → 199 → 0 → 14 → 37; movement = 146 + 199 + 37 = 382 (counting the return jump; some books leave the jump out).

Q5. Explain the directory structures with merits and demerits.

Outline: single-level (simple; name clashes, no grouping) → two-level (separate user directories, no clashes between users; no sub-folders, hard to share) → tree-structured (sub-directories, absolute vs relative path, current directory; sharing still awkward) → acyclic-graph (shared files and folders through links; deletion and dangling links must be handled) → general graph (cycles possible, needs garbage collection).

Exam tip

For disk scheduling, always write the full order of service, then the movement for each step and the total. State the head's direction for SCAN/LOOK clearly.

Quick summary

Linux is a free, open-source, Unix-like operating system created by Linus Torvalds in 1991. Users talk to it through the shell, a command interpreter such as bash. This topic covers the Linux architecture and file system layout, common commands for files, directories, permissions, processes and text filtering, pipes and redirection, and writing shell scripts with variables, conditions and loops.

Key points

• Architecture: hardware → kernel (core: process, memory, device and file management) → shell (reads and interprets commands) → utilities and applications → user.
• Popular shells: sh (Bourne), bash (Bourne Again Shell, default on most systems), csh, ksh, zsh.
• File system is one tree starting at root /: /bin (commands), /etc (configuration), /home (user folders), /root, /dev (devices), /tmp, /usr, /var (logs).
• Everything is a file: regular files, directories, device files, links.
• Linux is case-sensitive: File.txt and file.txt are different.
• Permissions: read (r = 4), write (w = 2), execute (x = 1) for owner (u), group (g) and others (o). ls -l shows them, e.g. -rwxr-xr--.
• chmod 754 file gives owner rwx (7), group r-x (5), others r-- (4).
• Redirection: > writes output to a file (overwrite), >> appends, < takes input from a file, 2> redirects errors.
• Pipe | sends the output of one command as input to the next, e.g. ls -l | wc -l.
• Filters: grep (search pattern), sort, uniq, wc, head, tail, cut, tr.
• Processes: ps (list), top (live view), kill PID (stop), & (run in background), jobs, fg, bg.
• A shell script is a text file of commands. First line #!/bin/bash (shebang). Make it runnable with chmod +x file.sh, run with ./file.sh.
• Variables: name="Ravi" (no spaces around =), used as $name.
• Arithmetic: $((a + b)), or (( … )) for tests and counting.
• Input: read x.
• Arguments: the first one is $1, the second is 2 with a dollar sign in front, and so on.
• Argument count is $#.
• Script name is $0.
• Test operators: numbers -eq -ne -gt -lt -ge -le; strings = and !=; files -f (file exists), -d (directory).

Important terms

• Kernel – core of the OS that talks to the hardware.
• Shell – command-line interpreter between user and kernel.
• Root / superuser – administrator account; sudo runs a command as root.
• Pipe – joins commands so one's output feeds the next.
• Shebang – #! line naming the interpreter for a script.

Formulas

• Permission digit = r(4) + w(2) + x(1): rwx = 7, r-x = 5, r-- = 4, rw- = 6

5 important questions

Q1. Differentiate kernel and shell.

The kernel is the core of Linux; it manages processes, memory, devices and files and talks directly to the hardware. The shell is a user program that reads typed commands, interprets them and asks the kernel to run them. Users never talk to the kernel directly.

Q2. What does chmod 754 report.txt do? Write the permission string.

7 = rwx for the owner, 5 = r-x for the group, 4 = r-- for others. The ls -l string becomes -rwxr-xr--.

Q3. Write a shell script to find the factorial of a number given as an argument.

• Run as ./fact.sh 5 → Factorial = 120. Inside (( )) variables can be used without the dollar sign.

Q4. Write a script to find the largest of three numbers.

• ./big.sh 12 45 30 prints 45 is largest.

Q5. Explain redirection and pipes with examples.

• ls > list.txt saves the listing in a file (overwrites); date >> list.txt adds a line at the end.
• sort < names.txt reads input from a file; gcc a.c 2> err.txt saves error messages.
• Pipe: cat marks.txt | sort -k2 -n -r | head -2 shows the two highest scorers. With lines "ravi 72, asha 85, neha 91, amit 58" the output is neha 91 and asha 85.
• ls | wc -l counts files in a folder.

Exam tip

In shell scripts, never put spaces around = in assignments, and always leave spaces inside [ ]. Write the sample run and output below every script.

Quick summary

A computer network is a group of computers and devices connected to share data and resources. This topic covers network types (PAN, LAN, MAN, WAN), topologies, transmission media, network devices, the seven-layer OSI reference model with the job of each layer, and a comparison with the TCP/IP model.

Key points

• Uses of networks: sharing files, printers and internet, communication (email, chat), centralised data, remote work.
• Types by area: PAN (personal, a few metres, Bluetooth), LAN (a building or campus), MAN (a city), WAN (a country or the world; the Internet is the largest WAN).
• Topologies: bus (single backbone cable), star (all nodes to a central hub/switch; most common in LANs), ring (closed loop), mesh (every node linked to others; very reliable), tree (hierarchy of stars), hybrid.
• Transmission media: guided (twisted pair, coaxial cable, optical fibre) and unguided (radio waves, microwaves, infrared, satellite). Optical fibre gives the highest bandwidth and is immune to electromagnetic interference.
• Devices: hub (sends to all ports, layer 1), switch (sends to the correct port using MAC address, layer 2), router (connects networks using IP address, layer 3), modem (converts digital ↔ analog), repeater (regenerates signal), gateway (connects different protocols), bridge (joins two LAN segments).
• OSI model (by ISO) has 7 layers, from bottom to top: Physical, Data Link, Network, Transport, Session, Presentation, Application. Memory aid: "Please Do Not Throw Sausage Pizza Away".
• Each layer serves the layer above it and uses the layer below it. Data is encapsulated (headers added) going down and decapsulated going up.
• Transmission modes: simplex (one way, like TV broadcast), half duplex (both ways, one at a time, walkie-talkie), full duplex (both ways at once, telephone).
• Switching: circuit switching (dedicated path, old telephone), packet switching (data in packets, Internet).

Important terms

• Protocol (शिष्टाचार / नियमावली) – set of rules for communication.
• Bandwidth – maximum data rate of a channel (bits per second).
• MAC address – 48-bit hardware address of a network card.
• Topology – physical or logical layout of a network.
• PDU – protocol data unit: bits (physical), frame (data link), packet (network), segment (transport).

Formulas

• Number of links in a full mesh of n nodes = n(n − 1)/2

5 important questions

Q1. Differentiate hub and switch.

A hub works at the physical layer and sends incoming data to all ports, causing more collisions. A switch works at the data link layer and forwards data only to the port of the destination MAC address, so it is faster and more secure.

Q2. How many cables are needed to connect 6 computers in a full mesh?

Links = n(n − 1)/2 = 6 × 5/2 = 15 cables. Each computer needs 5 ports.

Q3. Explain the OSI model with the functions of each layer.

• Physical: transmits raw bits; defines cables, voltage, connectors.
• Data link: frames, MAC addresses, error detection (CRC), flow control.
• Network: IP addressing and routing of packets.
• Transport: reliable end-to-end delivery, segmentation, port numbers.
• Session: dialogue control and synchronisation.
• Presentation: data format, encryption, compression.
• Application: network services for users (web, mail, file transfer).

Q4. Explain any four network topologies with merits and demerits.

• Bus: cheap, less cable; a break in the backbone stops the whole network.
• Star: easy to add nodes and find faults; central device failure stops all.
• Ring: equal access; one failure can break the ring.
• Mesh: very reliable, many paths; costly cabling.
• Tree: scalable hierarchy; depends on root.
• Give a one-line diagram description for each.

Q5. Compare the OSI and TCP/IP models.

• OSI has 7 layers; TCP/IP has 4 (Network Access, Internet, Transport, Application).
• OSI is a theoretical reference model; TCP/IP is the practical model used on the Internet.
• OSI's session and presentation jobs are inside TCP/IP's application layer.
• OSI clearly separates services, interfaces and protocols; TCP/IP was designed around its protocols.
• Both have transport and network (Internet) layers with similar jobs.

Exam tip

Learn the seven layers in order with one protocol and one device per layer — this single table answers many short and long questions.

Quick summary

When bits travel over a network, noise can change a 0 into a 1 or a 1 into a 0. The data link layer adds extra (redundant) bits so the receiver can detect, and sometimes correct, such errors. This topic covers types of errors, parity checks (simple and two-dimensional), checksum, cyclic redundancy check (CRC) and Hamming code, with solved examples, plus a short note on flow control and ARQ.

Key points

• Single-bit error: only one bit changes. Burst error: two or more bits change in a row (the burst length is from the first to the last changed bit).
• Redundancy: extra bits added to the data only for checking.
• Detection finds that an error happened; correction also finds which bit and fixes it.
• Simple parity (VRC): add one bit so the total number of 1s is even (even parity) or odd (odd parity). Detects all single-bit errors, but misses errors in an even number of bits.
• Two-dimensional parity (LRC + VRC): parity for each row and each column of a block; detects most burst errors and can correct a single-bit error.
• Checksum: sender adds the data words using 1's complement arithmetic (carry wrapped round) and sends the complement of the sum. Receiver adds everything including the checksum; the result should be all 1s (complement = 0). Used in IP, TCP and UDP headers.
• CRC: data is treated as a binary polynomial and divided (modulo-2, i.e. XOR, no carries) by a generator. If the generator has r + 1 bits, append r zeros, divide, and replace the zeros by the r-bit remainder. Receiver divides the whole frame; remainder 0 means no error. Used in Ethernet and Wi-Fi.
• Hamming code: places parity bits at positions 1, 2, 4, 8 … ; each checks the positions whose binary number contains it. The receiver's check bits (syndrome) give the position of a single-bit error.
• Flow control stops a fast sender from flooding a slow receiver: stop-and-wait, sliding window.
• ARQ (Automatic Repeat reQuest) retransmits frames that arrive with errors: stop-and-wait ARQ, go-back-N, selective repeat.

Important terms

• Redundant bits – extra bits used for checking.
• Syndrome – the check result that shows whether and where an error is.
• Modulo-2 arithmetic – addition and subtraction both done by XOR.
• Generator polynomial – the divisor used in CRC, e.g. x³ + x² + 1 = 1101.
• Code word – data bits plus redundant bits.

Formulas

• Hamming: number of parity bits r must satisfy 2ʳ ≥ m + r + 1 (m = data bits)
• Hamming(7,4): p1 checks bits 1, 3, 5, 7; p2 checks 2, 3, 6, 7; p4 checks 4, 5, 6, 7
• Error position = c4 c2 c1 read as a binary number
• CRC: append r zeros (r = generator bits − 1), divide by XOR, remainder = CRC

5 important questions

Q1. What is parity checking? What is its limitation?

One extra bit is added to make the count of 1s even (or odd). For data 1011001 (four 1s) the even-parity bit is 0, giving 10110010. If two bits flip, the count stays even, so the error is not detected — simple parity misses any even number of bit errors.

Q2. Find the checksum for the 8-bit words 10110011 and 01101010.

• Sum: 10110011 + 01101010 = 1 00011101 (9 bits)
• Wrap the carry: 00011101 + 1 = 00011110
• Checksum = 1's complement = 11100001
• Check at receiver: 00011110 + 11100001 = 11111111 → complement 0 → no error.

Q3. Find the CRC for data 100100 with generator 1101.

• Generator has 4 bits, so append 3 zeros: 100100000
• XOR steps: 1001 ⊕ 1101 = 0100 → bring down → 1000 ⊕ 1101 = 0101 → 1010 ⊕ 1101 = 0111 → 1110 ⊕ 1101 = 0011 → 1100 ⊕ 1101 = 0001
• Remainder = 001; transmitted frame = 100100001
• Receiver divides 100100001 by 1101: remainder 000, so it is accepted.

Q4. Build the Hamming(7,4) code for data 1011 (even parity). If bit 6 is received wrong, show how it is found.

• Positions 1–7 = p1 p2 d1 p4 d2 d3 d4, with d1 d2 d3 d4 = 1 0 1 1
• p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0; p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1; p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0
• Code word = 0110011
• Bit 6 flips → received 0110001
• c1 (bits 1, 3, 5, 7) = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0; c2 (2, 3, 6, 7) = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1; c4 (4, 5, 6, 7) = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
• c4 c2 c1 = 110 = 6 → flip bit 6 back to get 0110011.

Q5. Explain error detection methods and compare them.

Outline: why errors occur (noise, interference) → single-bit vs burst → redundancy idea → parity (simple and 2-D) with example → checksum steps → CRC steps and where used → comparison table → mention that correction is done by Hamming code or by retransmission (ARQ).

Exam tip

In CRC, write every XOR step under the previous one and remember the remainder has one bit fewer than the generator. In Hamming, list which positions each parity bit covers before calculating.

Quick summary

TCP/IP is the set of protocols on which the Internet works. This topic covers the four layers of the TCP/IP model, IP addressing (IPv4 classes, subnet mask, private addresses, IPv6), TCP versus UDP, port numbers, important application protocols (HTTP, HTTPS, FTP, SMTP, DNS, DHCP), how DNS works, and basic Internet terms like ISP, URL and web browser.

Key points

• The TCP/IP model has 4 layers: Network Access (Link), Internet, Transport, Application.
• IP (Internet Protocol) gives each device a logical address and routes packets. It is connectionless and does not guarantee delivery.
• IPv4 address: 32 bits, written as four decimal numbers 0–255 separated by dots (dotted decimal), e.g. 192.168.1.10. About 4.3 billion addresses (2³²).
• Classful addressing: Class A (first octet 1–126), B (128–191), C (192–223), D (224–239, multicast), E (240–255, reserved). 127.x.x.x is loopback.
• Subnet mask separates the network part from the host part: 255.255.255.0 (/24). CIDR notation writes the prefix length, e.g. 192.168.1.0/24.
• Private ranges (not routed on the Internet): 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16. NAT lets many private devices share one public IP.
• IPv6: 128-bit address written in hexadecimal groups separated by colons; created because IPv4 addresses ran short.
• TCP: connection-oriented, reliable (acknowledgements, retransmission), ordered, with flow and congestion control; uses a three-way handshake (SYN, SYN-ACK, ACK). Used for web, email, file transfer.
• UDP: connectionless, no guarantee, low overhead, fast. Used for video calls, online games, DNS queries, live streaming.
• Port numbers identify applications: HTTP 80, HTTPS 443, FTP 20/21, SSH 22, SMTP 25, DNS 53, POP3 110, IMAP 143.
• DNS converts domain names (like a website name) into IP addresses; it is a distributed hierarchical system (root → top-level domain → authoritative server).
• DHCP automatically gives IP addresses to devices joining a network.
• URL parts: protocol (https), domain name, path, e.g. https://www.example.com/notes/page.html.
• HTTP is the protocol of the World Wide Web (invented by Tim Berners-Lee, 1989–91); HTTPS adds encryption with TLS.

Important terms

• IP address (आयपी पत्ता) – logical address of a device on a network.
• Port – number that identifies a service on a host.
• Socket – combination of IP address and port number.
• ISP – Internet Service Provider, company that gives Internet access.
• Packet – small unit of data sent over a network.

Formulas

• Number of hosts in a subnet = 2ʰ − 2 (h = host bits; minus network and broadcast addresses)
• Number of subnets when borrowing s bits = 2ˢ
• /24 → 255.255.255.0; /16 → 255.255.0.0; /26 → 255.255.255.192

5 important questions

Q1. Identify the class of these IPv4 addresses: 10.2.3.4, 172.20.5.1, 200.1.1.1.

10.2.3.4 – first octet 10 → Class A. 172.20.5.1 – 172 → Class B. 200.1.1.1 – 200 → Class C. (10.x and 172.20.x are also private addresses.)

Q2. What is DNS? Why is it needed?

DNS (Domain Name System) translates easy-to-remember domain names into numeric IP addresses that computers use. Without DNS, users would have to remember IP addresses for every website.

Q3. A network is 192.168.10.0/26. Find the subnet mask, number of usable hosts and the first and last usable address of the first subnet.

• /26 → 26 network bits; mask = 255.255.255.192
• Host bits = 32 − 26 = 6 → hosts = 2⁶ − 2 = 62
• First subnet: 192.168.10.0 to 192.168.10.63 (block size 64)
• Network address .0 and broadcast .63 are reserved
• Usable range: 192.168.10.1 to 192.168.10.62

Q4. Explain the three-way handshake of TCP.

• Client sends SYN (synchronise) with its initial sequence number.
• Server replies with SYN-ACK: acknowledges the client's number and sends its own.
• Client sends ACK to acknowledge the server.
• Connection is now established; data transfer starts.
• Connection is closed with FIN and ACK segments.

Q5. Explain the TCP/IP model with protocols at each layer.

• Application: HTTP, HTTPS, FTP, SMTP, DNS, DHCP — user services.
• Transport: TCP and UDP — end-to-end delivery, ports.
• Internet: IP, ICMP (ping), ARP — addressing and routing.
• Network access: Ethernet, Wi-Fi — physical transmission and framing.
• Compare briefly with the 7-layer OSI model.

Exam tip

Subnetting numericals look hard but follow one rule: hosts = 2ʰ − 2. Practise /24, /25, /26 and /27 and you can solve most questions.

Quick summary

Every device on a TCP/IP network needs a unique IP address so that data can reach it. This topic covers the IPv4 address format, classful addressing (classes A to E), network and host parts, subnet masks, private and special addresses, subnetting and CIDR notation with solved problems, and a short introduction to IPv6.

Key points

• An IPv4 address is 32 bits, written as four decimal numbers (octets) from 0 to 255 separated by dots, e.g. 192.168.10.75 (dotted decimal).
• Each address has a network part (which network) and a host part (which device on it).
• Classful addressing (old system), decided by the first octet:
• Class A 1–126, default mask 255.0.0.0 (/8); Class B 128–191, 255.255.0.0 (/16); Class C 192–223, 255.255.255.0 (/24); Class D 224–239 multicast; Class E 240–255 reserved/experimental.
• 127.x.x.x is the loopback range (127.0.0.1 = this computer).
• Private addresses (not routed on the Internet): 10.0.0.0/8, 172.16.0.0 to 172.31.255.255 (172.16.0.0/12), 192.168.0.0/16. NAT lets them share one public address.
• In every network, the first address (host bits all 0) is the network address and the last (host bits all 1) is the broadcast address; neither can be given to a host.
• A subnet mask has 1s for network (and subnet) bits and 0s for host bits. ANDing an IP with the mask gives the network address.
• Subnetting borrows host bits to make smaller networks: less broadcast traffic, better security and organisation.
• CIDR (Classless Inter-Domain Routing) writes the mask as a prefix length, e.g. 192.168.10.0/26, and allows any prefix, not only /8, /16, /24.
• IPv6 uses 128-bit addresses written as eight groups of four hex digits, e.g. 2001:0db8:0000:0000:0000:0000:0000:0001, shortened to 2001:db8::1. It gives about 3.4 × 10³⁸ addresses and has no broadcast.
• DHCP gives addresses automatically; ARP finds the MAC address for an IP address on a LAN.

Important terms

• Octet – 8 bits of an IPv4 address.
• Prefix length – number of 1s in the mask (/24).
• Subnet – a smaller network made from a bigger one.
• Default gateway – router address used to reach other networks.
• NAT – translating private addresses to a public address.

Formulas

• Number of subnets = 2ⁿ (n = bits borrowed)
• Usable hosts per subnet = 2ʰ − 2 (h = host bits left)
• Block size (addresses per subnet) = 2ʰ = 256 − value of the mask's interesting octet
• Network address = IP AND mask

5 important questions

Q1. Find the class, default mask and whether these are private: 10.5.2.1, 172.20.1.9, 200.1.1.1.

• 10.5.2.1 → Class A, 255.0.0.0, private (10.0.0.0/8)
• 172.20.1.9 → Class B, 255.255.0.0, private (172.16–172.31 range)
• 200.1.1.1 → Class C, 255.255.255.0, public

Q2. Convert 200.15.8.1 to binary and state its class.

200 = 11001000, 15 = 00001111, 8 = 00001000, 1 = 00000001. Address = 11001000.00001111.00001000.00000001. The first bits are 110, so it is Class C.

Q3. Divide 192.168.10.0/24 into 4 equal subnets. Give the mask, subnets and host ranges.

• 4 subnets → borrow 2 bits (2² = 4) → /26, mask 255.255.255.192
• Host bits left = 6 → 64 addresses, 62 usable hosts per subnet

Q4. For the host 192.168.10.75/26, find the network address, broadcast address and number of usable hosts.

• Block size = 256 − 192 = 64 → subnets start at 0, 64, 128, 192
• 75 lies between 64 and 127 → network = 192.168.10.64
• Broadcast = 192.168.10.127
• Usable hosts = 2⁶ − 2 = 62 (192.168.10.65 to 192.168.10.126)

Q5. A company has the network 172.16.0.0 and needs 6 subnets. Find the new mask and hosts per subnet.

• Need 2ⁿ ≥ 6 → n = 3 (8 subnets)
• Class B default /16 + 3 = /19 → mask 255.255.224.0
• Host bits = 32 − 19 = 13 → 2¹³ − 2 = 8190 hosts per subnet
• First subnets: 172.16.0.0/19, 172.16.32.0/19, 172.16.64.0/19 (block size 32 in the third octet).

Exam tip

In subnetting problems, first find the block size (256 − mask octet); then networks, broadcasts and host ranges follow quickly. Always subtract 2 for network and broadcast when counting hosts.