Operating system and system programing

Injibara university

College of Engineering and Technology

Department of Software Engineering
Operating Systems and System Programming
Course code: (SEng3122 )

Group 3 members
No Name ID
1 Abebe Ayana ……………….. INU 1600672
2 Abebe Shitie ………………. INU 1600673
3 Asmare Berihun…………… INU 1600845
4 Atinkut Minuye ……………… INU 1600860
5 Firew Mulat ………………. INU 1601192
6 Gizachew Wasihun…………. INU 1601263
7 Tigist Belayneh …………….. INU 1601664

Advisor name: Shimels T

1|Page 2018
 Operating system and system programing

Introduction
Imagine trying to run several powerful applications on a computer that doesn't have enough
physical memory (RAM). It sounds like a recipe for crashes and slowdowns, right? This is where
the operating system performs a kind of magic trick called virtual memory. It creates the
illusion of a vast, continuous memory space, allowing you to work with large files and multitask
seamlessly, even when your physical RAM is full. This is achieved by smartly using a portion of
your hard drive or SSD as an extension of your RAM, swapping data back and forth as needed.

Alongside managing memory, an operating system is also a master scheduler, deciding which
process gets to use the CPU and when. One of the most efficient techniques for this is
the Shortest Remaining Time First (SRTF) algorithm. Think of it like a savvy store manager
who always prioritizes the customer with the quickest question, ensuring that the majority of
people are served as fast as possible. This document dives deep into both these fascinating
concepts—virtual memory and the SRTF scheduling algorithm—explaining how they work, why
they're beneficial, and what their limitations are.

2|Page 2018
 Operating system and system programing

Virtual Memory in Operating System

Virtual memory is a memory management technique used by operating systems to make
programs believe they have a large, continuous block of memory, even when the physical
RAM is small or fragmented. It works by dividing the program into fixed-size units
called pages, storing some pages in RAM and moving inactive pages to secondary
storage such as a hard drive or SSD. When a page is needed again, the OS brings it back
to RAM automatically. This allows the system to run large applications, multitask
efficiently, and use memory more flexibly than what is physically available.

Objectives of Virtual Memory

 A program doesn’t need to be fully loaded in memory to run. Only the needed
parts are loaded.
 Programs can be bigger than the physical memory available in the system.
 Virtual memory creates the illusion of a large memory, even if the actual memory
(RAM) is small.
 It uses both RAM and disk storage to manage memory, loading only parts of
programs into RAM as needed.
 This allows the system to run more programs at once and manage memory more
efficiently.

How Virtual Memory Works

 Virtual memory works by using both the computer’s hardware and operating
system. Normally, programs store their data in RAM. A hardware component
called the Memory Management Unit (MMU) helps the system translate program
addresses to their actual locations in RAM.
 When RAM becomes full or another program needs memory urgently, the
operating system moves some data from RAM to a special area on the hard drive
or SSD. This area is called virtual memory (page file or swap space). The OS
keeps track of which data was moved out, and if a program needs that data again,
the MMU brings it back into RAM.

3|Page 2018
 Operating system and system programing

 The OS divides virtual memory into small blocks called pages. Each page is
stored on the disk, and when needed, the OS copies it back into RAM and
translates the virtual address into a physical address.
 This swapping process allows the computer to run more programs than the
available RAM can hold. However, moving data between RAM and the disk is
slow, so using virtual memory can reduce performance. That’s why computers
with more RAM usually run faster they rely less on virtual memory.

EXAMPLE:

Suppose the CPU wants to access process P1, divided into ten pages. So following the
idea of virtual memory, only P1, P3, P5, P6, and P8 Pages are selected to be loaded in the
main memory. For that have to consult the page table. First CPU will check whether that
page has a valid (v) or invalid bit (I). Valid bit indicates that the page is in main memory
and invalid bit indicates that the page is not in main memory and has to load from
secondary memory. Like from the page table, we can see that page 1 is at frame 1, page 3
is at frame 2, page 5 is in frame 3, and so on. If the page is not in the main memory, then
those pages not in use are swapped out, and a new required page is swapped in. In short
virtual memory includes the concept of demand paging and swapping.

4|Page 2018
 Operating system and system programing

Types of Virtual Memory

In a computer, virtual memory is managed by the Memory Management Unit (MMU),
which is often built into the CPU. The CPU generates virtual addresses that the MMU
translates into physical addresses. There are two main types of virtual memory:
 Paging
 Segmentation

Paging
 Paging divides memory into sections or paging files. When a computer uses up its
available RAM, pages not in use are transferred to the hard drive or SSD using a
swap file. A swap file is a space set aside on the hard drive to be used as the
virtual memory extension for the computer's RAM. When the swap file is needed,
it is sent back to RAM using a process called page swapping. This system ensures
the computer's OS and applications do not run out of real memory. The maximum
size of the page file can be one and a half to four times the physical memory of
the computer.
 The virtual memory paging process uses page tables, which translate the virtual
addresses that the OS and applications use into the physical addresses that the
MMU uses. Entries in the page table indicate whether the page is in RAM. If the
OS or a program does not find what it needs in RAM, then the MMU responds to
the missing memory reference with a page fault exception to get the OS to move
the page back to memory when it is needed. Once the page is in RAM, its virtual
address appears in the page table.

5|Page 2018
 Operating system and system programing

Segmentation
 Segmentation is also used to manage virtual memory. This approach divides
virtual memory into segments of different lengths. Segments not in use in
memory can be moved to virtual memory space on the drive. Segmented
information or processes are tracked in a segment table, which shows if a segment
is present in memory, whether it has been modified and its physical address. In
addition, file systems in segmentation are only made up of segments that are
mapped into a potential address space of a process.
 Segmentation and paging differ as an amount of memory model in terms of how
memory is divided; however, the processes can also be combined. When
combined, memory gets divided into frames or pages. The segments take up
multiple pages, and the virtual address includes both the segment number and the
page number.

6|Page 2018
 Operating system and system programing

Applications of Virtual memory

Virtual memory has the following important characteristics that increase the capabilities of the
computer system.

 Increased Effective Memory: It enables a computer to have more memory than

the physical memory using the disk space. This allows for the running of larger
applications.
 Memory Isolation: Virtual memory allocates a unique address space to each
process, such separation increases safety and reliability based on the fact that one
process cannot interact with another.
 Efficient Memory Management: Virtual memory also helps in better utilization
of the physical memories through methods that include paging and segmentation.
 Simplified Program Development: For case of programmers, they can program
‘as if’ there is one big block of memory and this makes the programming easier
and more efficient in delivering more complex applications.

Management of Virtual Memory

Here are 5 key points on how to manage virtual memory:

1. Adjust the Page File Size

 Automatic Management: All contemporary OS including Windows contain the
auto-configuration option for the size of the empirical page file. But depending on
the size of the RAM, they are set automatically, although the user can manually
adjust the page file size if required.
 Manual Configuration: For tuned up users, the setting of the custom size can
sometimes boost up the performance of the system. The initial size is usually
advised to be set to the minimum value of 1.
2. Place the Page File on a Fast Drive
 SSD Placement: If this is feasible, the page file should be stored in the SSD
instead of the HDD as a storage device. It has better read and write times and the
virtual memory may prove beneficial in an SSD.

7|Page 2018
 Operating system and system programing

Separate Drive: Regarding systems having multiple drives involved, the page file needs to be
placed on a different drive than the OS and that shall in turn improve its performance.

3. Monitor and Optimize Usage

 Performance Monitoring: Employ the software tools used in monitoring the
performance of the system in tracking the amounts of virtual memory.
 Regular Maintenance: Make sure there is no toolbar or other application running
in the background, take time and uninstall all the tool bars to free virtual memory.
4. Disable Virtual Memory for SSD
 Sufficient RAM: If for instance your system has a big physical memory,
Example: 16GB and above then it would be advised to freeze the page file in
order to minimize SSD usage. But it should be done, carefully and only if the
additional signals that one decides to feed into his applications should not likely
use all the available RAM.
5. Optimize System Settings
 System Configuration: Change some general properties of the system
concerning virtual memory efficiency. This also involves enabling additional
control options in Windows.
 Regular Updates: Ensure that your drivers are run in their newest version
because new releases contain some enhancements and issues regarding memory
management.

8|Page 2018
 Operating system and system programing

Benefits of using virtual memory

 It can handle twice as many addresses as main memory.
 It enables more applications to be used at once.
 It frees applications from managing shared memory and saves users from having
to add memory modules when RAM space runs out.
 It can increase speed when only a segment of a program is needed for execution.
 It increases security because of memory isolation.
 It enables multiple larger applications to run simultaneously.
 Allocating memory is relatively inexpensive.
 It does not need external fragmentation.
 CPU use is effective for managing logical partition workloads.
 Data can be moved automatically.
 Pages in the original process can be shared during a fork system call operation
that creates a copy of itself.

Limitations of using virtual memory

 Applications run slower if they are running from virtual memory.
 Data must be mapped between virtual and physical memory, which requires extra
hardware support for address translations and may also affect performance.
 The size of virtual storage is limited by the amount of secondary storage, as well
as the addressing scheme with the computer system.
 Thrashing can occur if there is not enough RAM, which makes the computer
perform slower.
 It may take time to switch between applications using virtual memory.
 Virtual memory reduces the amount of available drive space.

9|Page 2018
 Operating system and system programing

Virtual Memory VS Physical Memory

Let us compare the virtual memory with the physical memory.
Feature Virtual Memory Physical Memory (RAM)
Definition An abstraction that The actual hardware (RAM) that
extends the available stores data and instructions
memory by using disk currently being used by the CPU
storage
Location On the hard drive or SSD On the computer's motherboard
Speed Slower (due to disk I/O Faster (accessed directly by the
operations) CPU)
Capacity Larger, limited by disk Smaller, limited by the amount
space of RAM installed
Cost Lower (cost of additional Higher (cost of RAM modules)
disk storage)
Data Indirect (via paging and Direct (CPU can access data
Access swapping) directly)
Volatility Non-volatile (data Volatile (data is lost when
persists on disk) power is off)

10 | P a g e 2018
 Operating system and system programing

Shortest Remaining Time First (Preemptive SJF) Scheduling

Algorithm
 The pre-emptive version of Shortest Job First (SJF) scheduling is called Shortest
Remaining Time First (SRTF). In SRTF, the process with the least time left to
finish is selected to run. The running process continues until it finishes or a new
process with a shorter remaining time arrives, ensuring the fastest finishing
process always gets priority.
 The choice of preemptive and non-preemptive arises when a new process arrives
at the ready queue and a previous process is not finished and is being executed. If
the next CPU burst of new process is shorter than current executing process, then
in preemptive version, it will stop that process and will start executing the newly
arrived process.
 While, in non- preemptive version of SJF, even if the arriving process is shorter
than currently executing process, current process is not stopped. After the current
process finishes, then the new process gets in the queue. This is the key difference
between preemptive and preemptive version of SJF.
 The current state of the process is saved by the context switch and the CPU is
given to another process.
 Note – If 2 processes have same execution time, then jobs are based on First
Come First Serve Basis.

EXAMPLE 1: Consider the following table of arrival time and burst time for five
processes calculate total around time and waiting time
Process Arrival time Burst time
P1 3 1
P2 1 4
P3 4 2
P4 0 6
P5 2 3

11 | P a g e 2018
 Operating system and system programing

1. Time 0-1 (P4): P4 runs for 1 ms (total time left: 5 ms)

2. Time 1-3 (P2): P2 runs for 2 ms (total time left: 2 ms)
3. Time 3-4 (P1): P1 runs for 1 ms (total time left: 0 ms)
4. Time 4-6(P2): P2 runs for 2 ms (total time left: 0 ms)
5. Time 6-8(P3): P3 runs for 2 ms (total time left: 0 ms)
6. Time 8-11(P5): P5 runs for 3 ms (total time left: 0 ms)
7. Time 11-16(P4): P4 runs for 5 ms (total time left: 0 ms)

Gantt Chart
P1 P2 P1 P2 P3 P5 P4

0 1 3 4 6 8 11 16

Process Arrival Time Burst Completion TAT WT

Time Time
P1 3 1 4 1 0
P2 1 4 6 5 1
P3 4 2 8 4 2
P5 2 3 11 9 6
P4 0 6 16 16 10

Average TAT=1+5+4+9+16=35/5=7

Average WT=0+1+2+6+10=19/5=3.8

12 | P a g e 2018
 Operating system and system programing

13 | P a g e 2018
 Operating system and system programing

EXAMPLE 2:

Process Arrival Burst Completion Turn Around Waiting

Time(AT) Time(BT) Time (CT) Time (TAT) Time (WT)
P1 0 6 9 9-0 = 9 9-6 = 3

P2 1 3 4 4-1 = 3 3-3 = 0
P3 2 7 16 16-2 = 14 14-7 =
7
Average Turn Around Time = (9 + 14 + 3)/3 = 8.6
Average Waiting Time = (3 + 0 + 7 )/3 = 10/3 = 3.33

14 | P a g e 2018
 Operating system and system programing

C++ code of the above example

#include <iostream>

using namespace std;

int main() {

int n;

cout << "Enter number of processes: ";

cin >> n;

string name[20];

int arrival[20], burst[20], remaining[20], completion[20];

bool finished[20] = {false};

// INPUT

for (int i = 0; i < n; i++) {

cout << "\nProcess " << i+1 << ":\n";

cout << " Name: ";

cin >> name[i];

cout << " Arrival: ";

cin >> arrival[i];

cout << " Burst: ";

cin >> burst[i];

remaining[i] = burst[i];

completion[i] = -1; // -1 means not finished

int time = 0;

15 | P a g e 2018
 Operating system and system programing

int completed = 0;

int current = -1; // -1 means CPU idle

string gantt[100];

int ganttStart[100];

int g = 0;

cout << "\n=== EXECUTION LOG ===\n";

while (completed < n) {

// ====================================

// STEP 1: Check for new shortest process

// ====================================

int shortest = -1;

int minRemaining = 999999;

// Find process with smallest remaining time among arrived

for (int i = 0; i < n; i++) {

if (!finished[i] && arrival[i] <= time && remaining[i] > 0) {

if (remaining[i] < minRemaining) {

minRemaining = remaining[i];

shortest = i;

// ====================================

// STEP 2: Handle preemption or continue

// ====================================

if (shortest != current && shortest != -1) {

16 | P a g e 2018
 Operating system and system programing

// PREEMPTION OCCURS!

if (current != -1) {

cout << "Time " << time << ": PREEMPT " << name[current]

<< " -> " << name[shortest]

<< " (" << remaining[shortest] << " left)\n";

current = shortest;

// Add to Gantt chart (new block)

if (g == 0 || gantt[g-1] != name[current]) {

gantt[g] = name[current];

ganttStart[g] = time;

g++;

else if (shortest == -1 && current != -1) {

// Current process finished

cout << "Time " << time << ": " << name[current] << " FINISHES\n";

completion[current] = time;

finished[current] = true;

completed++;

current = -1;

// Check again for next process immediately

continue;

else if (shortest == -1) {

// CPU idle

if (g == 0 || gantt[g-1] != "IDLE") {

17 | P a g e 2018
 Operating system and system programing

gantt[g] = "IDLE";

ganttStart[g] = time;

g++;

time++;

continue;

// ====================================

// STEP 3: Execute current process for 1 unit

// ====================================

if (current != -1) {

// Execute for 1 time unit

remaining[current]--;

time++;

// Check if finished

if (remaining[current] == 0) {

cout << "Time " << time << ": " << name[current] << " FINISHES\n";

completion[current] = time;

finished[current] = true;

completed++;

current = -1;

// ====================================

// OUTPUT GANTT CHART

18 | P a g e 2018
 Operating system and system programing

// ====================================

cout << "\n=== GANTT CHART ===\n";

// Print process names

for (int i = 0; i < g; i++) {

cout << "| " << gantt[i] << " ";

cout << "|\n";

// Print timeline

cout << ganttStart[0];

for (int i = 0; i < g; i++) {

int endTime = (i < g-1) ? ganttStart[i+1] : time;

cout << " " << endTime;

cout << endl;

// ====================================

// OUTPUT RESULTS TABLE

// ====================================

cout << "\n=== RESULT TABLE ===\n";

cout << "Name\tAT\tBT\tCT\tTAT\tWT\n";

cout << "----------------------------------------\n";

float totalTAT = 0, totalWT = 0;

for (int i = 0; i < n; i++) {

int tat = completion[i] - arrival[i];

int wt = tat - burst[i];

19 | P a g e 2018
 Operating system and system programing

cout << name[i] << "\t"

<< arrival[i] << "\t"

<< burst[i] << "\t"

<< completion[i] << "\t"

<< tat << "\t"

<< wt << endl;

totalTAT += tat;

totalWT += wt;

cout << "\nAverage TAT = " << totalTAT / n << endl;

cout << "Average WT = " << totalWT / n << endl;

return 0;

Features of Shortest Job First (SJF) Preemptive Algorithm:

Preemptive Nature
The CPU is allocated to the process with the shortest remaining burst time.
If a new process arrives with a shorter burst time than the current running process, the
current process is preempted.
Optimal for Average Waiting Time
SJF (especially in its preemptive form) gives the lowest average waiting time among all
scheduling algorithms.
Based on Burst Time

20 | P a g e 2018
 Operating system and system programing

Scheduling decisions are made based on the estimated burst time (CPU time) of
processes.
Requires Prior Knowledge
The algorithm needs knowledge of the burst time in advance, which may not always be
feasible.
Dynamic Scheduling
As new processes arrive, the scheduler re-evaluates and may switch the running process
if the newcomer has a shorter remaining time.

21 | P a g e 2018
 Operating system and system programing

Advantages
 Minimizes Average Waiting Time: One of the most optimal algorithms in terms
of waiting time.
 Responsive to Short Processes: Prioritizes short jobs, improving responsiveness.
 Better for Time-sharing Systems: Suitable for interactive environments.

Disadvantages
 High Overhead: Requires continuous tracking of burst times.
 Starvation: Long processes may wait indefinitely if shorter jobs keep arriving.
 Complex Implementation: Real-time estimation of remaining burst time is
challenging.
 Needs Accurate Predictions: Burst time must be known in advance, which isn’t
always possible.

Final Thoughts
 Preemptive Shortest Job First (SJF), or Shortest Remaining Time First (SRTF),
is a powerful scheduling algorithm known for minimizing average waiting time.
It’s a theoretically optimal algorithm but comes with practical challenges in
implementation.
 It works best in environments where burst times can be predicted accurately, and
short tasks dominate the workload. However, if not implemented carefully, it can
lead to starvation for longer tasks.
How does Preemptive SJF differ from Non-Preemptive SJF?
 In Preemptive SJF, a running process can be interrupted if a new process arrives
with a shorter burst time. In contrast, Non-Preemptive SJF allows a process to run
to completion once it starts, regardless of whether a shorter job arrives afterward.

22 | P a g e 2018
 Operating system and system programing

Summary

In essence, this document explores two core pillars of modern operating systems that
work behind the scenes to make our computers more powerful and efficient.
First, we explored Virtual Memory, a brilliant memory management technique. It lets
our systems run programs that are larger than the physical RAM by using disk space as a
backup. The system breaks down programs into small chunks called "pages," keeping
only the active ones in fast RAM and storing the rest on the disk. While this gives us the
incredible ability to run memory-intensive applications and enhances security by isolating
processes, it does come with a trade-off: over-reliance on it can slow things down due to
the slower speed of disk drives compared to RAM.
Second, we unpacked the Shortest Remaining Time First (SRTF) scheduling
algorithm, which is the preemptive version of Shortest Job First. Its goal is simple yet
powerful: always run the process that is closest to completion. This leads to the lowest
possible average waiting time, making the system feel very responsive. However, this
efficiency comes with challenges. It requires knowing how long a process will take ahead
of time (which can be difficult to predict), and if not managed carefully, longer processes
can be left waiting indefinitely a problem known as starvation.
In conclusion, both virtual memory and the SRTF algorithm are testament to the
sophisticated design of operating systems. They employ clever strategies to maximize
limited resources, providing us with a smooth, responsive, and capable computing
experience, even on hardware with physical constraints. Understanding these concepts
gives us a real appreciation for the invisible work that powers our digital world.

23 | P a g e 2018