←
Computer Science and Electronics for Digital Assistant · Chapter 3

Operating Systems

What to remember

  • An operating system (OS) is system software that manages hardware and gives services to programs and users. Its main jobs are process, memory, file and device management.
  • The CPU scheduler picks which process runs next. Memory management uses paging and virtual memory. Deadlock needs four conditions together.
  • Know the main types (batch, multiprogramming, time sharing, real time, distributed), the Linux/Windows basics and the standard algorithms with simple worked examples.

1. Role and types of OS

The OS sits between the user and the hardware. It acts as a resource manager (CPU, memory, files, devices) and as an interface for users. Examples: Windows, Linux, Unix, macOS, Android (a Linux-based mobile OS).

Main functions: process management, memory management, file management, device (I/O) management, security and protection, job scheduling, error handling.

TypeMeaning
BatchSimilar jobs are collected and run together, with no user interaction
MultiprogrammingSeveral programs kept in memory; CPU switches when one waits for I/O; raises CPU use
Multitasking / time sharingCPU time is divided into small slices so many users feel they have the machine at once
MultiprocessingTwo or more CPUs work together
Real timeMust respond within a fixed time; hard (strict) and soft types
DistributedMany computers act as one system
NetworkComputers share resources over a network

The kernel is the core part of the OS that runs in privileged (kernel) mode. A system call is how a user program asks the kernel for a service. The shell is the command interpreter. A monolithic kernel has all services in one block; a microkernel keeps only the basic services in the kernel.

2. Process management

A program is a passive set of instructions on disk. A process is a program in execution. Each process has a Process Control Block (PCB) holding its state, program counter, registers and memory details.

Process states: New → Ready → Running → Waiting (Blocked) → Terminated. A running process goes back to Ready if its time slice ends; it goes to Waiting when it needs I/O. A context switch saves one process's state and loads another's. A thread is a light-weight unit of a process; threads of one process share code, data and files but have their own stack and registers.

Process vs thread: a process has its own memory; threads share the memory of their process, so they are faster to create and switch.

3. CPU scheduling

The scheduler chooses a process from the ready queue. Preemptive scheduling can take the CPU away; non-preemptive lets a process run until it finishes or waits.

AlgorithmIdeaNote
FCFSFirst come, first servedSimple; convoy effect
SJFShortest job firstLeast average waiting time (non-preemptive); needs burst time
SRTFShortest remaining time firstPreemptive form of SJF
PriorityHighest priority firstStarvation possible; cured by aging
Round RobinFixed time quantum in turnPreemptive; good for time sharing

Formulas: Turnaround time = Completion time − Arrival time. Waiting time = Turnaround time − Burst time.

Worked example (FCFS): P1, P2, P3 arrive at time 0 with burst times 5, 3, 2. P1 finishes at 5, P2 at 8, P3 at 10. Waiting times are 0, 5, 8. Average = 13/3 ≈ 4.33. In SJF the order is P3, P2, P1; waiting times 0, 2, 5; average = 7/3 ≈ 2.33.

4. Synchronization and deadlock

A critical section is code that uses shared data. A race condition occurs when the result depends on the order of execution. A solution must give mutual exclusion, progress and bounded waiting. A semaphore is an integer variable used with two operations, wait (P) and signal (V). A binary semaphore takes values 0 and 1 (like a mutex); a counting semaphore can take any non-negative value. Classic problems: producer-consumer, readers-writers, dining philosophers.

Deadlock is a state where processes wait forever for resources held by each other. Four necessary conditions (Coffman): mutual exclusion, hold and wait, no preemption, circular wait. Handling methods: prevention (break a condition), avoidance (Banker's algorithm), detection and recovery, and ignoring it (the ostrich method). Starvation is long waiting of a process without deadlock.

5. Memory management

Memory is divided so many processes can stay in it. Logical address is made by the CPU; physical address is the real location. The MMU maps logical to physical.

  • Contiguous allocation: fixed partitions or variable partitions. Internal fragmentation is wasted space inside an allocated block; external fragmentation is scattered free holes. Placement strategies: first fit, best fit, worst fit.
  • Paging: logical memory is split into equal pages and physical memory into frames of the same size. A page table maps pages to frames. Paging removes external fragmentation but can leave internal fragmentation in the last page.
  • Segmentation: memory split by logical parts of different sizes (code, data, stack).
  • Virtual memory: lets programs larger than RAM run, by keeping part of the process on disk. Demand paging loads a page only when needed. A page fault occurs when a needed page is not in memory. Thrashing is too much paging, so the CPU does little real work.

Page replacement algorithms: FIFO, Optimal (replaces the page not used for the longest time in the future; lowest faults, but cannot be built in practice), LRU (replaces the least recently used page). Belady's anomaly: with FIFO, more frames can give more page faults.

Worked example: reference string 1,2,3,1,4 with 3 frames under FIFO: faults at 1, 2, 3 (three), 1 is a hit, 4 replaces 1 (fault). Total 4 faults.

6. File and disk management

A file is a named collection of related data. Operations: create, open, read, write, delete, close. Access methods: sequential, direct, indexed. A directory holds file information; structures are single-level, two-level and tree. File allocation: contiguous, linked and indexed. File extensions show the type, for example .txt, .exe, .jpg.

Disk scheduling orders disk requests to cut head movement: FCFS, SSTF (shortest seek time first), SCAN (elevator) and C-SCAN. Seek time is the time to move the head to the track; rotational latency is the wait for the sector to come under the head.

7. Boot, Windows and Linux basics

Booting loads the OS into RAM. Cold boot is starting from power off; warm boot is a restart. The BIOS/firmware runs the power-on self-test (POST) and starts the bootloader. A device driver lets the OS talk to a device.

Windows: a graphical, mostly single-user, commercial OS from Microsoft. Common file systems: FAT32, NTFS. Task Manager shows running processes. The Registry stores settings.

Linux: open-source, multi-user, multitasking, based on Unix, first released by Linus Torvalds. Common commands: `ls` (list), `cd` (change directory), `pwd` (present directory), `mkdir`, `rm`, `cp`, `mv`, `cat`, `chmod` (change permissions), `ps` (processes), `kill`. The root user is the super user.

Worked examples

  • 1. Round Robin: P1, P2, P3 arrive at 0 with burst times 4, 3, 2 and the quantum is 2. Order: P1 (0-2), P2 (2-4), P3 (4-6, done), P1 (6-8, done), P2 (8-9, done). Completion times: P3 = 6, P1 = 8, P2 = 9. Turnaround = completion (arrival 0). Waiting: P1 = 8 − 4 = 4, P2 = 9 − 3 = 6, P3 = 6 − 2 = 4. Average waiting = 14/3 ≈ 4.67.
  • 2. Page size: With 4 KB pages, a logical address of 10,000 lies in page 2 (10,000 ÷ 4,096 = 2 remainder 1,808), at offset 1,808.
  • 3. Paging bits: A logical address space of 2¹⁶ bytes with 2⁸-byte pages has 2⁸ = 256 pages; 8 bits give the page number and 8 bits the offset.
  • 4. Effective access: If a memory access takes 100 ns and the page fault rate is 0, the access time is 100 ns; each fault adds a very large disk delay, so even a tiny fault rate slows the system.
  • 5. Deadlock check: Process A holds R1 and waits for R2, while process B holds R2 and waits for R1. Mutual exclusion, hold and wait, no preemption and circular wait all hold, so deadlock exists.

Exam traps

  • Program vs process: a program is passive, a process is in execution.
  • SJF gives the lowest average waiting time; FCFS can give a long one.
  • Paging has no external fragmentation; segmentation can have it.
  • Page fault is an event, not an error; thrashing is the heavy case.
  • Deadlock needs all four conditions; breaking one prevents it.
  • Process has own memory; threads share it.
  • Multiprogramming (many programs in memory) is not the same as multiprocessing (many CPUs).
  • Optimal replacement is the best but cannot be implemented.

One-liners

  • 1. The OS is system software that manages resources.
  • 2. The PCB stores process information.
  • 3. Process states: new, ready, running, waiting, terminated.
  • 4. Round Robin uses a time quantum.
  • 5. Waiting time = turnaround time − burst time.
  • 6. Banker's algorithm is for deadlock avoidance.
  • 7. A page is a block of logical memory; a frame is a block of physical memory.
  • 8. Virtual memory uses disk as an extension of RAM.
  • 9. Thrashing means excessive paging.
  • 10. A semaphore is a synchronization variable with wait and signal.
  • 11. Linux was started by Linus Torvalds.
  • 12. NTFS is a Windows file system.

Practice questions

  1. The core part of an operating system that runs in privileged mode is the

    1. kernel
    2. BIOS chip
    3. compiler
    4. shell
    Answer

    A. kernel

    The kernel is the central part of the OS.

  2. A process is best described as

    1. a hardware device
    2. a compiler option
    3. a file on disk
    4. a program in execution
    Answer

    D. a program in execution

    A program is passive; a process is a program being executed.

  3. Which data structure holds the state, program counter and registers of a process?

    1. Page table
    2. Process Control Block
    3. File allocation table
    4. Interrupt vector only
    Answer

    B. Process Control Block

    The PCB stores process information.

  4. Which scheduling algorithm uses a fixed time quantum?

    1. Priority
    2. SJF
    3. Round Robin
    4. FCFS
    Answer

    C. Round Robin

    Round Robin gives each process one quantum in turn.

  5. The scheduling algorithm that gives the minimum average waiting time for non-preemptive jobs is

    1. First Come First Served
    2. Round Robin
    3. Longest Job First
    4. Shortest Job First
    Answer

    D. Shortest Job First

    SJF is optimal for average waiting time.

  6. The four conditions for deadlock include mutual exclusion, hold and wait, no preemption and

    1. circular wait
    2. aging
    3. thrashing
    4. starvation
    Answer

    A. circular wait

    Circular wait completes the four Coffman conditions.

  7. The algorithm used for deadlock avoidance is

    1. Round Robin
    2. Banker's algorithm
    3. LRU
    4. SCAN
    Answer

    B. Banker's algorithm

    Banker's algorithm checks that the system stays in a safe state.

  8. In paging, fixed-size blocks of physical memory are called

    1. sectors
    2. pages
    3. frames
    4. segments
    Answer

    C. frames

    Logical blocks are pages; physical blocks are frames.

  9. An event in which a required page is not found in main memory is a

    1. deadlock
    2. interrupt vector
    3. context switch
    4. page fault
    Answer

    D. page fault

    A page fault triggers loading the page from disk.

  10. Excessive paging that leaves little time for useful work is called

    1. thrashing
    2. aging
    3. booting
    4. spooling
    Answer

    A. thrashing

    Thrashing happens when processes keep faulting.

  11. Which Linux command lists files in a directory?

    1. rm
    2. ls
    3. cd
    4. pwd
    Answer

    B. ls

    ls lists; cd changes directory; pwd shows the present directory.

  12. Linux was first released by

    1. Bill Gates
    2. Dennis Ritchie
    3. Linus Torvalds
    4. Steve Jobs
    Answer

    C. Linus Torvalds

    Linus Torvalds started the Linux kernel.

  13. Which of the following is a file system used by Windows?

    1. NTFS
    2. APFS
    3. XFS
    4. ext4
    Answer

    A. NTFS

    NTFS and FAT32 are Windows file systems; ext4 is common on Linux.

  14. A process moves from Running to Waiting when

    1. it has finished
    2. it requests an I/O operation
    3. its time slice ends
    4. it is created
    Answer

    B. it requests an I/O operation

    I/O request blocks the process; a time slice end sends it to Ready.

  15. Turnaround time of a process is

    1. burst time minus arrival time
    2. waiting time minus burst time
    3. arrival time plus burst time
    4. completion time minus arrival time
    Answer

    D. completion time minus arrival time

    Turnaround = completion − arrival.

  16. Processes P1, P2, P3 arrive together with burst times 5, 3 and 2 and run in FCFS order. The average waiting time is about

    1. 4.33
    2. 5.0
    3. 2.33
    4. 3.33
    Answer

    A. 4.33

    Waits are 0, 5 and 8; the sum 13 divided by 3 is 4.33.

  17. For the same jobs (5, 3, 2) under SJF, the average waiting time is about

    1. 1.67
    2. 2.33
    3. 4.33
    4. 3.67
    Answer

    B. 2.33

    Order 2, 3, 5 gives waits 0, 2, 5; the sum 7 divided by 3 is 2.33.

  18. A reference string 1,2,3,1,4 is run with 3 frames using FIFO. The number of page faults is

    1. 4
    2. 3
    3. 5
    4. 2
    Answer

    A. 4

    Faults at 1, 2, 3 and 4; the second 1 is a hit.

  19. A logical address space is 2^16 bytes and the page size is 2^8 bytes. The number of bits used for the page number is

    1. 16
    2. 8
    3. 24
    4. 4
    Answer

    B. 8

    Offset takes 8 bits, so the remaining 16 − 8 = 8 bits give the page number.

  20. With 4 KB pages, the page number of logical address 10,000 is

    1. 1
    2. 3
    3. 2
    4. 0
    Answer

    C. 2

    10,000 divided by 4,096 is 2 with remainder 1,808.

  21. Which scheduling method can cause starvation of low-priority processes?

    1. FCFS
    2. Round Robin
    3. Multilevel with aging
    4. Priority scheduling
    Answer

    D. Priority scheduling

    Low-priority jobs may wait forever unless aging is used.

  22. The technique that raises the priority of a long-waiting process is

    1. swapping
    2. paging
    3. aging
    4. spooling
    Answer

    C. aging

    Aging prevents starvation.

  23. Which memory management scheme removes external fragmentation?

    1. Segmentation
    2. Best-fit allocation
    3. Variable partitioning
    4. Paging
    Answer

    D. Paging

    Equal-size pages and frames leave no external holes.

  24. Which page replacement algorithm gives the fewest page faults but cannot be implemented in practice?

    1. LRU
    2. Optimal
    3. Clock
    4. FIFO
    Answer

    B. Optimal

    Optimal needs knowledge of future references.

  25. Belady's anomaly can occur with which algorithm?

    1. LRU
    2. Optimal
    3. Both LRU and Optimal
    4. FIFO
    Answer

    D. FIFO

    With FIFO, adding frames can increase faults.

  26. Which statement about threads of the same process is correct?

    1. They share the code and data of the process
    2. They cannot share files
    3. They share the stack and registers
    4. They have separate address spaces
    Answer

    A. They share the code and data of the process

    Threads share memory but have their own stack and registers.

  27. A semaphore that takes only the values 0 and 1 is a

    1. monitor
    2. spooler
    3. binary semaphore
    4. counting semaphore
    Answer

    C. binary semaphore

    A binary semaphore works like a mutex lock.

  28. The disk scheduling algorithm that serves the request nearest to the current head position is

    1. SSTF
    2. SCAN
    3. FCFS
    4. C-SCAN
    Answer

    A. SSTF

    Shortest Seek Time First picks the nearest track.

  29. The technique of loading a page into memory only when it is first referenced is called

    1. compaction
    2. demand paging
    3. batch processing
    4. segmentation
    Answer

    B. demand paging

    Demand paging loads pages only on need.

  30. Wasted space inside an allocated memory block is called

    1. thrashing
    2. swapping
    3. internal fragmentation
    4. external fragmentation
    Answer

    C. internal fragmentation

    Internal fragmentation is unused space within a block.

  31. Consider these statements about operating systems. 1. A program is passive but a process is active. 2. The PCB stores the information of a process. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are true.

  32. Consider these statements about deadlock. 1. All four necessary conditions must hold together. 2. Breaking any one condition prevents deadlock. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Deadlock needs all four; removing one prevents it.

  33. Consider these statements about paging. 1. It can cause external fragmentation. 2. The last page of a process may have internal fragmentation. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    B. 2 only

    Paging removes external fragmentation; so only 2 is correct.

  34. Consider these statements about SJF and FCFS. 1. FCFS always gives the least average waiting time. 2. SJF needs the burst times to be known. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    B. 2 only

    SJF gives the least average waiting; statement 1 is wrong.

  35. Consider these statements about threads. 1. Threads of a process share its memory. 2. A context switch between threads is usually faster than between processes. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both statements are correct.

  36. Consider these statements. 1. Multiprocessing uses more than one CPU. 2. Multiprogramming keeps several programs in memory. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are correct definitions.

  37. Consider these statements about virtual memory. 1. It lets a program larger than RAM run. 2. It removes the need for a page table. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    Virtual memory uses page tables; statement 2 is wrong.

  38. Match the Linux command with its use. P. pwd Q. mkdir R. chmod 1. Create a directory 2. Show present directory 3. Change permissions

    1. P-1, Q-2, R-3
    2. P-2, Q-3, R-1
    3. P-3, Q-1, R-2
    4. P-2, Q-1, R-3
    Answer

    D. P-2, Q-1, R-3

    pwd shows the directory, mkdir creates, chmod changes permissions.

  39. Match the algorithm with its idea. P. SRTF Q. LRU R. Banker's 1. Deadlock avoidance 2. Preemptive version of SJF 3. Replaces the page not used for the longest time

    1. P-2, Q-1, R-3
    2. P-3, Q-2, R-1
    3. P-1, Q-3, R-2
    4. P-2, Q-3, R-1
    Answer

    D. P-2, Q-3, R-1

    SRTF is preemptive SJF; LRU replaces the least recently used page; Banker's avoids deadlock.

  40. Match the OS type with its feature. P. Real time Q. Time sharing R. Batch 1. Jobs run together without user interaction 2. Fixed response deadline 3. CPU divided into slices among users

    1. P-3, Q-2, R-1
    2. P-2, Q-1, R-3
    3. P-1, Q-3, R-2
    4. P-2, Q-3, R-1
    Answer

    D. P-2, Q-3, R-1

    Real time has deadlines; time sharing uses slices; batch runs without interaction.

  41. Three processes arrive at 0 with burst times 4, 3 and 2 under Round Robin with quantum 2. Process P3 (burst 2) finishes at time

    1. 2
    2. 6
    3. 9
    4. 4
    Answer

    B. 6

    Order: P1 (0-2), P2 (2-4), P3 (4-6), so P3 finishes at 6.

  42. In the above Round Robin case (bursts 4, 3, 2; quantum 2), the average waiting time is about

    1. 4.67
    2. 2.67
    3. 5.33
    4. 3.67
    Answer

    A. 4.67

    Completion 8, 9, 6 gives waits 4, 6, 4; the sum 14 divided by 3 is 4.67.

  43. Process A holds R1 and waits for R2 while process B holds R2 and waits for R1. This is an example of

    1. deadlock
    2. thrashing
    3. starvation
    4. paging
    Answer

    A. deadlock

    A circular wait with resources held is deadlock.

  44. Which part of an OS accepts user commands and passes them to the kernel?

    1. Shell
    2. Loader only
    3. BIOS
    4. Driver
    Answer

    A. Shell

    The shell is the command interpreter.

  45. Which program lets the OS communicate with a particular hardware device?

    1. Assembler
    2. Compiler
    3. Linker
    4. Device driver
    Answer

    D. Device driver

    A device driver controls a device on behalf of the OS.

Page 1 of 1
‹
›