Lecture 1: BCS401 Operating System — Pre-University Test Solved Paper

BCS401 Operating System — Pre-University Test Solved Paper

Section A: Short Answer Questions

Marks: 02 × 07 = 14

1(a) Multiprocessor System

A multiprocessor system is a computer system having two or more processors that share main memory, I/O devices, and the system bus. It allows multiple processes to execute simultaneously.

• It increases system throughput.
• It improves performance through parallel processing.
• It provides better reliability.
• It reduces cost by sharing memory and I/O devices.

1(b) SPOOL

SPOOL stands for Simultaneous Peripheral Operations On-Line. It is a technique in which data is temporarily stored on disk before being sent to a slow peripheral device.

Example: Print jobs are stored in a print queue before printing.

1(c) Race Condition

A race condition occurs when two or more processes access shared data concurrently, and the final result depends on the order of execution.

counter = counter + 1;

If two processes read the same value of counter simultaneously, both may write the same updated value. This produces an incorrect result.

1(d) Critical Section

A critical section is the part of a program where a process accesses shared resources such as shared variables, files, or memory. Only one process should execute in the critical section at a time.

1(e) Multiprocessor Scheduling

Multiprocessor scheduling is the scheduling of processes or threads on multiple CPUs.

• Asymmetric multiprocessing: One master processor performs scheduling.
• Symmetric multiprocessing: Each processor schedules its own processes.
• Load balancing: Work is distributed among processors.
• Processor affinity: A process is kept on the same CPU to improve cache use.

1(f) Frame Allocation Algorithms

Frame allocation algorithms decide how many memory frames are assigned to each process.

• Equal allocation: Each process receives equal frames.
• Proportional allocation: Frames are allocated according to process size.
• Priority allocation: Higher priority processes receive more frames.
• Global allocation: A process may take frames from other processes.
• Local allocation: A process replaces only its own frames.

1(g) File Access Methods

• Sequential access: Records are accessed one after another in order.
• Direct or random access: Any block can be accessed directly by its number.
• Indexed access: An index is used to locate records quickly.

Section B: Descriptive and Numerical Questions

Marks: 07 × 03 = 21

2(a) Important Terms

Interactive System: An interactive system allows direct communication between user and computer. The user gives input and receives output immediately.

Distributed System: A distributed system is a collection of independent computers connected through a network and working together as a single system.

System Call: A system call is a mechanism by which a user program requests services from the operating system kernel.

Multithreading: Multithreading means executing multiple threads within a single process. Threads share code, data, and files, but have their own stack and registers.

2(b) Semaphore and Reader-Writer Problem

A semaphore is an integer synchronization variable accessed only through atomic operations wait() and signal().

semaphore mutex = 1;

Process Pi:
wait(mutex);
    // critical section
signal(mutex);

In the reader-writer problem, multiple readers may read simultaneously, but only one writer can write at a time.

Reader Process

wait(mutex);
readcount++;

if (readcount == 1)
    wait(wrt);

signal(mutex);

/* reading */

wait(mutex);
readcount--;

if (readcount == 0)
    signal(wrt);

signal(mutex);

Writer Process

wait(wrt);

/* writing */

signal(wrt);

2(c) CPU Scheduling Numerical

FCFS

0    8    12    21    26
| P1 | P2 | P3  | P4 |

Average Turnaround Time: 15.25

Average Waiting Time: 8.75

Pre-emptive SJF / SRTF

0  1    5    10    17    26
|P1| P2 | P4 | P1  | P3 |

Average Turnaround Time: 13

Average Waiting Time: 6.5

Round Robin, Quantum = 1

0 P1 1 P2 2 P1 3 P3 4 P2 5 P4 6 P1 7 P3 8 P2 9 P4
10 P1 11 P3 12 P2 13 P4 14 P1 15 P3 16 P4 17 P1
18 P3 19 P4 20 P1 21 P3 22 P1 23 P3 24 P3 25 P3 26

Average Turnaround Time: 19

Average Waiting Time: 12.5

2(d) Fragmentation and Memory Allocation

Internal fragmentation occurs when allocated memory is larger than the required memory. External fragmentation occurs when enough total memory exists, but it is scattered in small non-contiguous blocks.

Memory blocks: 100K, 500K, 200K, 300K, 600K

Processes: 212K, 417K, 112K, 426K

Most efficient algorithm: Best Fit, because all processes are successfully allocated.

2(e) Disk Scheduling Algorithms

• FCFS: Requests are served in arrival order. It is simple but may cause high seek time.
• SSTF: The request closest to the current head position is served first.
• SCAN: Disk arm moves in one direction, services requests, then reverses.
• C-SCAN: Disk arm moves in one direction only and jumps back after reaching the end.
• LOOK: Similar to SCAN, but reverses after the last request instead of going to the end.
• C-LOOK: Similar to C-SCAN, but jumps between the last and first request only.

Section C: Long Answer Questions

Marks: 07 × 05 = 35

3(a) Operating System and Its Services

An Operating System is system software that acts as an interface between the user and computer hardware. It manages hardware resources and provides services for program execution.

• Program execution
• I/O operations
• File system management
• Communication between processes
• Error detection
• Resource allocation
• Accounting and logging
• Protection and security
• User interface

3(b) Design Structures of Operating System

• Simple structure: Used in early systems such as MS-DOS.
• Monolithic structure: The complete OS runs as one large kernel.
• Layered structure: The OS is divided into layers, where each layer uses services of the lower layer.
• Microkernel: Only essential services run in kernel mode; other services run in user mode.
• Modular structure: The kernel supports dynamically loadable modules.
• Hybrid structure: Combines features of monolithic and microkernel designs.

4(a) Sleeping Barber Problem Using Semaphore

In the sleeping barber problem, there is one barber, one barber chair, and n waiting chairs. If no customer is present, the barber sleeps. If a customer arrives and the barber is sleeping, the customer wakes him. If all waiting chairs are full, the customer leaves.

semaphore customers = 0;
semaphore barber = 0;
semaphore mutex = 1;

int waiting = 0;
int chairs = n;

Barber Process

while (true)
{
    wait(customers);

    wait(mutex);
    waiting--;
    signal(barber);
    signal(mutex);

    cut_hair();
}

Customer Process

wait(mutex);

if (waiting < chairs)
{
    waiting++;
    signal(customers);
    signal(mutex);

    wait(barber);
    get_haircut();
}
else
{
    signal(mutex);
    leave_shop();
}

4(b) Process, Process States, and PCB

A process is a program in execution. It is an active entity that requires CPU time, memory, files, and I/O resources.

Main process states: New, Ready, Running, Waiting, and Terminated.

A Process Control Block (PCB) is a data structure maintained by the OS for each process. It stores process ID, process state, program counter, CPU registers, scheduling information, memory information, accounting information, and I/O status.

5(a) Deadlock

Deadlock is a condition in which a set of processes are permanently blocked because each process is waiting for a resource held by another process.

Necessary conditions for deadlock:

• Mutual exclusion: At least one resource is non-shareable.
• Hold and wait: A process holds one resource and waits for another.
• No preemption: Resources cannot be forcibly taken from a process.
• Circular wait: A circular chain of waiting processes exists.

Deadlock can be avoided using Banker’s Algorithm. The OS grants a request only if the system remains in a safe state after allocation.

5(b) Banker’s Algorithm Numerical

Formula: Need = Max − Allocation

Initial Available: (1, 5, 2, 0)

Safe sequence: P0 → P2 → P1 → P3 → P4

Therefore, the system is in a safe state.

Request from P1 = (0, 4, 2, 0). Since the request is less than or equal to Need and Available, it may be checked for safety. After allocation, a safe sequence still exists.

Conclusion: The request can be granted immediately.

6(a) Paging

Paging is a memory management scheme in which logical memory is divided into fixed-size pages and physical memory is divided into fixed-size frames. Page size and frame size are equal.

Logical Address = Page Number + Page Offset
Physical Address = Frame Number + Same Offset

• Paging eliminates external fragmentation.
• It allows non-contiguous memory allocation.
• It supports virtual memory.
• It helps in memory protection.

Paging causes internal fragmentation, because the last page of a process may not be completely filled.

Page size is usually a power of 2 because binary address translation becomes simple. If page size is 2n, then lower n bits represent the offset and the remaining bits represent the page number.

6(b) LRU Page Replacement Numerical

Memory references: 09, 21, 114, 190, 53, 313, 185, 236, 281, 634, 458, 564, 701, 740

Page size: 100 words

Primary memory: 300 words

Number of frames: 300 / 100 = 3 frames

Reference string: 0, 0, 1, 1, 0, 3, 1, 2, 2, 6, 4, 5, 7, 7

Total page faults: 8

7(a) File Sharing, System Threats, and File Protection

File Sharing: File sharing allows multiple users or processes to access the same file through local, network, distributed, or cloud-based file systems.

System Threats: System threats are attacks that misuse system services or damage system operation. Examples include viruses, worms, denial-of-service attacks, rootkits, and port scanning.

File Protection: File protection controls access to files using permissions such as read, write, execute, append, delete, and list. It may be implemented using passwords, access control lists, user/group permissions, and encryption.

7(b) Disk Scheduling Numerical

Total cylinders: 5000

Current head position: 143

Previous request: 125

Direction: Upward

Request queue: 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

Minimum head movement: SSTF = 1745 cylinders.