GATE Computer Science Engineering(CSE) 2027 Test: Operating System - 2

• Mid-term scheduler: swap the processes from the wait state to hard disk
• Short-term scheduler: selects the processes that are ready to execute and allocates the CPU to one of them
• Dispatcher: Context switches, in which the dispatcher saves the state of the previous process then the dispatcher loads the saved state of the new process selected by the short-term scheduler
• Long-term scheduler: bring the processes to main memory from the hard disk

Service time = s milliseconds = 1000s microseconds

Hit ratio = h % = h ÷ 100

∴ miss ratio = p = (1 - h ÷ 100) (page fault rate)

EMAT = e millisecond = 1000e microseconds

If m is considered

EMAT = p × (s + m) + (1 - p) × m

EMAT = p × s + m

Substitute the values:

1000e = (1 – (h ÷ 100)) 1000s + m

∴ m = 1000 × e - 1000 × s + 10 × s × h

∴ m = 10 × (100 × (e - s) + s × h)

Important Points:
EMAT → effective memory access time

p → page fault rate

s → service time

m → memory access time

Confusion point:

m is very large, in this case m is ignored and not take with service time

EMAT = p × s + (1 - p) × m

If m is considered

EMAT = p × (s + m) + (1 - p) × m

EMAT = p × s + m

Data:

TLB hit ratio = p = 0.8

TLB access time = 5 milliseconds

Memory access time = m = 70 milliseconds

Formula:

EMAT = p × (t + m) + (1 – p) × (t + m + m)

Calculation:

EMAT = 0.8 × (5 + 70) + (1 – 0.8) × (5 + 70 + 70)

EMAT = 89 milliseconds.

Important points:

During TLB hit

The frame number is fetched from the TLB (5 ms)

and page is fetched from physical memory (70 ms)

During TLB miss

TLB no entry matches (5 ms)

The frame number is fetched from the physical memory (70 ms)

and pages are fetched from physical memory (70 ms)

(a) External Fragmentation exists when there is enough total memory space to satisfy a request but the available space is contiguous.

This statement is incorrect. As process are loaded and removed from memory, the free memory space is  broken into little pieces. External fragmentation exists when enough total memory space exists to satisfy a request but it is not contiguous; storage is fragmented into large number of small holes.  External fragmentation is also known as checker boarding. Suppose we have memory blocks available of size 400KB each. But if request come for 600Kb then it cannot be allocated.

(b) Memory Fragmentation can be internal as well as external.

This statement is correct. There is an important issue related to the contiguous multiple partition allocation scheme is to deal with memory fragmentation. There are two types of fragmentation: internal and external fragmentation. Internal fragmentation exists in the case of memory having multiple fixed partitions when the memory is allocated to a process is not fully used by the process.

(c) One solution to external Fragmentation is compaction.

Given statement is correct. To get rid of external fragmentation problem, it is desirable to relocated some or all portions of the memory in order to place all the free holes together at one end of memory to make one large hole. This technique of reforming the storage is known as compaction.

Deadlock can occur If any process gets < needed (requested) resource

Max resource per process to be in deadlock = max demand – 1 

For 6 process, max resource to be in deadlock = (7 – 1) + (5 – 1) + (3 – 1) + (8 - 1) + (4 - 1) + (6 - 1) =27 

For 6 process, min resource not to be in a deadlock: 27 + 1 =28

Tips and Tricks:

where P_i is the max resource needed by the ith process and n is the total number of process

Concept:

The round – robin scheduling algorithm is designed for time sharing systems. It is similar to FCFS but preemption is added to enable the system to switch between processes.

Some points about round- robin scheduling :

• To implement round robin, we keep the queue as a FIFO queue of processes.
• Round robin scheduling is preemptive.
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units. Each process must wait no longer than (n-1) × q time units until its next time quantum.
• Performance of the round robin algorithm depends on the size of time quantum.
• If time quantum is too large, then round robin behaves like FCFS.
• If time quantum is too small, then this approach is called processor sharing.

S₁: TRUE:

If a user-level thread block then entire process will get blocked

S₂: FALSE

Kernel level threads are independent that is why they also require more context switch than user – level threads.

S₃: TRUE

Every thread has its own register and stack

Therefore S₁ and S₃ are TRUE

Concept:

Fork system call is used to create a new process. Newly creates process is known as child process. Fork system call takes no arguments and return a process ID.

A process terminates when it finishes its final statement and asks the operating system to delete it by using the exit() system call. At that point, process may return a status value to its parent process. All the resources are deallocated by the operating system.

A parent may terminate the execution of one of its children for a variety of reasons such as :

• Child has exceeded its usage of some of the resources that it has been allocated
• The task assigned to the child is no longer required.
• The parent has terminated and operating system does not allow a child to exist. This is known as cascading termination.

Data

1 word (W) = 1 byte (B)

Logical address = 2⁶⁴ B

page size = 8 MB = 2²³ B

page table entry (PTE) = 16 B

Formula:

Page table size (PTS) = number of pages × PTE

Calculation:

number of pages = 2⁶⁴ / 2²³=2⁴¹

Page table size (PTS) = number of pages × y

PTS = 2⁴¹ × 16B=2⁴⁵B

∴ PTS = 32 TB

Important points

1 TB = 2⁴⁰ B

where B stands for byte

In case of exponential averaging, formula used is:

T’ = αt₁ + (1 - α)T

Here processes are given as:

Here α = 0.5, T₁ = 10

T₂ = 0.5 × 4 + (1 – 0.5) × 10

= 2 + 5 = 7

T₃ = 0.5 × 8 + 0.5 × 7

= 4 + 3.5 = 7.5

T₄ = 0.5 × 6 + 0.5 × 7.5

= 3 + 3. 75 = 6.75

T₅ = 0.5 × 7 + 0.5 × 6.75

= 3.5 + 3.375 = 6.875

Required burst time = 6.875 time units

Concept:

Shortest remaining time next:  pre-emptive scheduling

In shortest remaining time next, when a process of less burst time(run time) arrives than in ready queue then context switch will happen.

Concept:

If the probability of process spending its time in performing I/O operations is P.

Then probability that all processes goes for I/O is P*P*P……….*P for n processes i.e. Pⁿ.

Hence, the probability of CPU utilization will be 1- pⁿ.

Here, the probability that a process spends its time in performing I/O operations is 50% i.e. 0.5

Then probability that all processes are waiting for I/O = (0.5)⁴

The probability of CPU utilization = 1 – (0.5)ⁿ

From the table it is clear that fork is called 8 times

Formula:

If n times fork is called the number of child processes created = 2ⁿ – 1

Calculation:

Since n = 8

number of child processes created = 2⁸ - 1 = 255

Concept:

Mutual exclusion happens when two or more processes share the same resources but can not access the same resource at the same time. 

Mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions.

It is the requirement that one thread of execution never enters its critical section at the same time that another concurrent thread of execution enters its own critical section. This problem is resolved using different tools, e.g. semaphores.

Data:

Available identical Resources = R = 12

Max needs per process = 3

Concepts:

Deadlock can occur If any process gets available resource < needed (requested) resource

Max resource per process to be in deadlock = needed – 1 = 3 – 1 = 2

For Y process, max resource to be in deadlock = Y × 2 = 2Y

Condition for deadlock

2Y ≥ R

2Y ≥ 12

Y  ≥ 6

values of Y could lead to a deadlock is 6 and 7