Unit 1: Scheduling, synchronization and memory management
Operating Systems Laboratory notes · PTU syllabus (UGCC2509)
On this page
Unit summary
This lab simulates the core algorithms of Operating Systems in C: CPU scheduling, deadlock avoidance, synchronisation problems, IPC with pipes, memory allocation and paging, page replacement and file allocation. Each program models what the OS does internally, so understanding the logic matters more than the code length.
After this unit you can
- Simulate FCFS, SJF and Round Robin scheduling and compute waiting and turnaround times
- Implement the Banker's algorithm and find a safe sequence
- Solve producer-consumer and dining philosophers with semaphores, and use pipes for IPC
- Simulate memory allocation, paging, MVT, FIFO page replacement and sequential file allocation
PTU syllabus topics
- FCFS/SJF/Round Robin CPU scheduling simulation
- Banker's algorithm for deadlock avoidance
- Producer-Consumer problem using semaphores
- IPC via pipes and FIFOs
- paging and segmentation memory management simulation
- best-fit and first-fit contiguous memory allocation
- Dining Philosophers problem
- MVT algorithm
- FIFO page replacement
- sequential file allocation
Topic 1
CPU scheduling simulation
Input the burst times (and arrival times), compute completion time (CT), turnaround time (TAT = CT − AT) and waiting time (WT = TAT − BT), and print averages.
c/* FCFS, all arriving at time 0 */
wt[0] = 0;
for (i = 1; i < n; i++)
wt[i] = wt[i - 1] + bt[i - 1];
for (i = 0; i < n; i++) {
tat[i] = wt[i] + bt[i];
avg_wt += wt[i]; avg_tat += tat[i];
}- SJF: sort processes by burst time first, then apply the FCFS logic.
- Round Robin: loop over processes, giving each min(quantum, remaining time) until all remaining times are zero.
Topic 2
Banker's algorithm
The Banker's algorithm avoids deadlock. Before granting a request, the operating system checks whether the system would still be in a safe state, that is, whether some order exists in which every process can finish.
- 1
Compute Need
Need[i][j] = Max[i][j] − Alloc[i][j]
- 2
Work = Available
- 3
Find an unfinished process with Need ≤ Work
- 4
Release its resources
Work = Work + Alloc[i]
- 5
Mark it finished and repeat
- 6
All finished?
Safe; print the sequence
Example
A small safety check: Available = 3. P1 has Allocation 2, Max 4, so Need 2. P2 has Allocation 3, Max 9, so Need 6. P3 has Allocation 2, Max 3, so Need 1. Work = 3. P3 (Need 1 ≤ 3) finishes: Work = 5. P1 (Need 2 ≤ 5) finishes: Work = 7. P2 (Need 6 ≤ 7) finishes: Work = 10. Safe sequence: P3, P1, P2.
Exam tip
Need = Max − Allocation. The state is safe if every process can be marked finished.
Topic 3
Synchronisation and IPC
- Producer-consumer: semaphores
empty(initially buffer size),full(0) andmutex(1). Producer: wait(empty), wait(mutex), add item, signal(mutex), signal(full). Consumer does the reverse. - Dining philosophers: five philosophers and five chopsticks (semaphores); to avoid deadlock, allow at most four to pick up chopsticks, or make one philosopher pick up the right chopstick first.
- Pipes and FIFOs:
pipe(fd)creates a one-way channel; afterfork(), the parent writes tofd[1]and the child reads fromfd[0]. A FIFO (named pipe) is created withmkfifoand works between unrelated processes.
Topic 4
Memory management simulations
- First fit / best fit: for each process, search the list of free blocks for the first block (or the smallest block) large enough, allocate it and reduce the block size.
- Paging: given a logical address, page number = address / page size and offset = address % page size; look up the frame in the page table.
- MVT: allocate memory exactly equal to each process size until memory runs out, then report external fragmentation.
- FIFO page replacement: keep frames in a circular array; on a miss, replace the frame at the pointer and advance it; count faults.
- Sequential file allocation: a file occupies consecutive disk blocks from a starting block; check that the required blocks are free.
Key terms
- Gantt chart
- A timeline showing which process runs when
- Safe sequence
- An order in which all processes can finish
- pipe()
- A system call creating a one-way communication channel
- Page fault count
- Number of misses in page replacement
Quick revision
- TAT = CT − AT; WT = TAT − BT.
- Banker's: Need = Max − Allocation; Need ≤ Work.
- Producer-consumer uses empty, full and mutex semaphores.
- Page number = address / page size; offset = address % page size.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.How are waiting time and turnaround time calculated?
- Q2.What are the three semaphores in the producer-consumer problem?
- Q3.How can deadlock be avoided in the dining philosophers problem?
- Q4.Differentiate between a pipe and a FIFO.
- Q5.How do you count page faults in FIFO replacement?
Long-answer questions
- Q1.Write a program to simulate Round Robin scheduling and explain its output.
- Q2.Implement the Banker's algorithm and find whether the system is in a safe state.
- Q3.Write a program to simulate first-fit and best-fit memory allocation.
- Q4.Implement FIFO page replacement and count the page faults for a given reference string.
Stuck on this unit?
Message SBS on WhatsApp for help with Operating Systems Laboratory, or to ask about studying BCA at Synetic.
