Operating System and Virtualization Winter 2022 GTU Paper Solution | 3141601

Single threaded and multithreaded process models are two different approaches to designing and implementing programs. The main difference between the two models is how they manage the execution of code within a program.

1. Single Threaded Process Model: In a single threaded process model, a program consists of a single thread of execution. This means that the program executes one instruction at a time, and each instruction must complete before the next instruction can begin. If an instruction requires some input or resource that is not yet available, the program must wait until it becomes available before it can continue executing. This can result in the program appearing unresponsive or slow, especially when dealing with time-consuming tasks.
2. Multithreaded Process Model: In a multithreaded process model, a program consists of multiple threads of execution that can run concurrently. Each thread can execute independently of the others and can communicate and share resources with other threads in the program. This allows the program to perform multiple tasks simultaneously, which can significantly improve its performance and responsiveness.

Multithreading can be used in many situations, such as in graphical user interfaces where the main thread can be used to handle user input and respond to events, while other threads perform time-consuming tasks in the background. Multithreading can also be used to implement parallel processing, where different parts of a task are distributed across multiple threads, allowing them to execute simultaneously on multiple cores or processors.

Here is the Gantt chart:

| P1 | P2 | P3 | P4 | P1 | P1 | P2 | P1 | P4 | P1 | P4 | P1 | P1 |

The average turnaround time is calculated by subtracting the arrival time of each process from its completion time and then adding up all the values and dividing by the number of processes.

Turnaround Time for P1 = 18 – 0 = 18 Turnaround Time for P2 = 11 – 1 = 10 Turnaround Time for P3 = 5 – 2 = 3 Turnaround Time for P4 = 14 – 3 = 11

Average Turnaround Time = (18 + 10 + 3 + 11) / 4 = 10.5

The average waiting time is calculated by subtracting the burst time of each process from its turnaround time and then adding up all the values and dividing by the number of processes.

Waiting Time for P1 = 18 – 9 = 9 Waiting Time for P2 = 10 – 5 = 5 Waiting Time for P3 = 3 – 3 = 0 Waiting Time for P4 = 11 – 4 = 7

Average Waiting Time = (9 + 5 + 0 + 7) / 4 = 5.25

Therefore, the average turnaround time is 10.5 and the average waiting time is 5.25.

If the time quantum is too small, it can lead to higher overhead due to frequent context switches between processes. This is because each process will get a very short amount of CPU time before being interrupted and switching to the next process in the queue. As a result, the CPU will spend more time switching between processes than actually executing them, leading to higher overhead and lower throughput. In extreme cases, the system may become unresponsive due to the high overhead of the scheduling algorithm.

On the other hand, if the time quantum is too large, it can result in higher waiting times and longer turnaround times, as described in the previous answer. In the specific case of the Round Robin scheduling algorithm with the given set of processes, a time quantum of 2 is appropriate because it strikes a balance between reducing waiting times and maximizing throughput without introducing too much overhead.

Hardware-based mutual exclusion refers to the use of hardware mechanisms to ensure that only one process can access a shared resource at a time, avoiding conflicts and inconsistencies.

There are two main hardware-based approaches to mutual exclusion:

1. Interrupt disabling: In this approach, the CPU hardware provides an instruction to disable interrupts. When a process enters the critical section, it executes this instruction to disable all interrupts, preventing any other process from interrupting it and accessing the shared resource. This approach is simple and fast, but it can lead to reduced system responsiveness and even deadlocks if a process gets stuck in the critical section.
2. Atomic hardware instructions: Many modern CPUs provide atomic hardware instructions, such as test-and-set or compare-and-swap, that can be used to implement mutual exclusion. These instructions allow a process to read and modify a memory location atomically, ensuring that no other process can access the same memory location simultaneously. The process can use this instruction to acquire a lock on a shared resource, and other processes will spin until the lock is released, avoiding conflicts and ensuring mutual exclusion. This approach is more efficient than interrupt disabling, and it can also support more sophisticated synchronization primitives such as semaphores and monitors.

To calculate the disk head movement for the given disk queue using the SCAN and C-SCAN scheduling algorithms, we need to first sort the I/O requests in ascending order of cylinder numbers since the disk head is moving towards decreasing cylinder numbers.

Sorted queue: 6, 10, 12, 15, 34, 44, 45, 54, 73, 97, 110, 128

We assume that the disk head is initially positioned at cylinder 23, and we calculate the head movement for both SCAN and C-SCAN algorithms as follows:

1. SCAN:

In the SCAN algorithm, the disk head moves from the current cylinder to the last cylinder in the direction of its movement, serving all the requests on its way. After reaching the last cylinder, the head changes its direction and moves to the other end of the disk, serving all the remaining requests on its way.

Sorted queue: 6, 10, 12, 15, 34, 44, 45, 54, 73, 97, 110, 128

Direction: decreasing

Head movement:

23 → 15 → 12 → 10 → 6 → 34 → 44 → 45 → 54 → 73 → 97 → 110 → 128 → 150 → 73 → 54 → 44 → 34 → 23

Total head movement = 365 cylinders

2. C-SCAN:

In the C-SCAN algorithm, the disk head moves from the current cylinder to the last cylinder in the direction of its movement, serving all the requests on its way. After reaching the last cylinder, the head jumps to the first cylinder and moves in the same direction, serving all the requests on its way until it reaches the last request before the initial cylinder.

Sorted queue: 6, 10, 12, 15, 34, 44, 45, 54, 73, 97, 110, 128

Direction: decreasing

Head movement:

23 → 15 → 12 → 10 → 6 → 150 → 128 → 110 → 97 → 73 → 54 → 45 → 44 → 34 → 23

Total head movement = 327 cylinders

Therefore, the total head movement for the given disk queue using SCAN is 365 cylinders, and using C-SCAN is 327 cylinders.

To calculate the disk head movement for the given disk queue using the SCAN and C-SCAN scheduling

We can use a frame of size 3 for the LRU page replacement algorithm to calculate the number of page faults for the given reference string.

Initially, all frames are empty, and each page request results in a page fault. Therefore, the first three requests will result in page faults.

Reference string: 5 0 2 1 0 3 0 2 4 3 0 3 2 1 3 0 1 5

1. 5: 5 _ _ (page fault)
2. 0: 5 0 _ (page fault)
3. 2: 5 0 2 (page fault)
4. 1: 5 0 2 (page fault)
5. 0: 5 0 2 (page fault)
6. 3: 3 0 2 (page fault)
7. 0: 3 0 2 (page fault)
8. 2: 3 0 2 (page fault)
9. 4: 4 0 2 (page fault)
10. 3: 4 3 2 (page fault)
11. 0: 4 3 0 (page fault)
12. 3: 4 3 0 (page fault)
13. 2: 4 3 2 (page fault)
14. 1: 4 3 2 (page fault)
15. 3: 4 1 3 (page fault)
16. 0: 0 1 3 (page fault)
17. 1: 0 1 3 (page fault)
18. 5: 5 1 3 (page fault)

Therefore, the total number of page faults for the given reference string using LRU page replacement algorithm with a frame size of 3 is 14.

Peterson’s solution is a software-based algorithm for achieving mutual exclusion in a shared memory environment. It was developed by Gary Peterson in 1981 and is based on two processes that share a common resource. The solution is based on the idea of using two flags, one for each process, to enforce mutual exclusion.

The Peterson’s solution works as follows:

1. Each process has a flag variable that indicates whether it is interested in entering the critical section or not. Initially, both flags are set to false.
2. When a process wants to enter the critical section, it sets its flag to true and then sets the turn variable to the other process.
3. The process then enters a busy-wait loop, checking the other process’s flag and turn variables. If the other process is not interested in entering the critical section or if it is its turn, then the process proceeds to the critical section.
4. Once a process is done with the critical section, it sets its flag to false and passes the turn to the other process.

The code for Peterson’s solution is as follows:

int turn;
bool flag[2];

void P0()
{
    flag[0] = true;
    turn = 1;
    while (flag[1] && turn == 1) {
        // busy wait
    }
    // critical section
    flag[0] = false;
}

void P1()
{
    flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0) {
        // busy wait
    }
    // critical section
    flag[1] = false;
}

In this code, P0() and P1() are the two processes that share a critical section. The flag array indicates whether each process is interested in entering the critical section, and the turn variable indicates which process should go first. The busy-wait loop ensures that both processes cannot enter the critical section at the same time.

Peterson’s solution is simple and effective, but it suffers from the problem of busy-waiting, which wastes CPU cycles and can lead to starvation. Also, it is susceptible to race conditions when implemented in multiprocessor environments.

A process is a program that is being executed by the operating system. During its lifetime, a process can hold different states, each of which corresponds to a specific phase of its execution. The different states a process can hold are:

1. New: In this state, the process is being created by the operating system, and the necessary resources are being allocated to it.
2. Ready: In this state, the process is waiting to be assigned to a processor by the operating system. It has all the necessary resources and is waiting for its turn to execute.
3. Running: In this state, the process is being executed by the processor. It is currently using the processor’s resources, and its instructions are being executed.
4. Blocked: In this state, the process is waiting for an event to occur, such as an I/O operation or a semaphore signal, before it can continue executing. The process cannot proceed until the event occurs.
5. Terminated: In this state, the process has finished executing, and its resources are being released by the operating system.

The different events that can lead to each state transition for a process are:

1. New to Ready: The process is created by the operating system, and all the necessary resources are allocated to it.
2. Ready to Running: The operating system assigns the processor to the process, and the process begins executing.
3. Running to Blocked: The process encounters an event, such as an I/O operation, that requires it to wait for some external condition to occur before it can continue executing.
4. Running to Ready: The process voluntarily relinquishes the processor, such as by calling a wait function, and goes back to the ready state.
5. Blocked to Ready: The event that the process was waiting for occurs, and the process can continue executing.
6. Running to Terminated: The process finishes executing, and its resources are released by the operating system.

With a page size of 512 bytes, the logical address of 16 bits can be split into a page number and an offset as follows:

• Page number: The first 9 bits of the logical address represent the page number, as 2^9 = 512.
• Offset: The remaining 7 bits represent the offset within the page, as the page size is 512 bytes.

Therefore, for the given logical address 0000010001111101, the page number is 000001000, and the offset is 1111101.

If the frame address corresponding to the computed page number is 15, then the physical address can be calculated as follows:

• The frame address is 15, which is represented by the binary number 1111.
• The offset is 1111101, which represents the byte offset within the page.
• Therefore, the physical address is 1111 1111101 in binary, which is equal to 0xFD in hexadecimal notation.

The following elements uniquely characterize a process while a program is executing:

1. Process ID (PID): A unique identifier that distinguishes the process from other processes in the system.
2. Program counter (PC): A register that contains the memory address of the next instruction to be executed in the program.
3. Process state: The current state of the process, such as ready, running, blocked, or terminated.
4. Memory management information: The memory allocation and usage information for the process, including the virtual memory address space, page table, and memory allocation/deallocation information.
5. CPU registers: The values stored in the CPU registers for the process, such as the general-purpose registers, stack pointer, and status register.
6. I/O status: The status of any I/O operations associated with the process, including the devices being used and the state of any pending I/O requests.
7. Priority: The priority of the process relative to other processes in the system, which determines the order in which the processes are scheduled for execution.

Multiprogramming is a technique that enables a computer system to execute multiple programs simultaneously. The handling of multiple non-interactive and interactive jobs in multiprogramming can be explained as follows:

1. Multiple Non-Interactive Jobs: Non-interactive jobs are those that do not require user interaction and can run without user intervention. In multiprogramming, multiple non-interactive jobs are handled by allocating resources such as CPU time, memory, and I/O devices to each job. The system can switch between jobs based on the scheduling algorithm to ensure that each job gets a fair share of resources. The operating system assigns priorities to each job, and the scheduling algorithm determines which job to execute based on its priority level.
2. Multiple Interactive Jobs: Interactive jobs are those that require user interaction and input. In multiprogramming, multiple interactive jobs are handled by allocating resources such as CPU time, memory, and I/O devices to each job. The system can switch between jobs based on the scheduling algorithm to ensure that each job gets a fair share of resources. In addition, the operating system must provide a mechanism for user interaction, such as a command interpreter or a graphical user interface (GUI). The operating system must also provide a way to manage user input/output, such as managing input from the keyboard or output to the screen.

To handle multiple interactive jobs, the operating system must provide a way to switch between jobs quickly and efficiently to ensure that the user experiences minimal delay. The scheduling algorithm must take into account the interactive nature of the jobs and ensure that the user does not have to wait too long for a response. For example, the Round Robin scheduling algorithm can be used to ensure that each job gets a fair share of CPU time, while the Shortest Job First (SJF) algorithm can be used to prioritize jobs based on their execution time.

In summary, multiple non-interactive and multiple interactive jobs in multiprogramming are handled by allocating resources to each job and switching between jobs based on the scheduling algorithm. The operating system must also provide a mechanism for user interaction and input/output management to handle interactive jobs efficiently.

(i) Static allocation of memory refers to the allocation of memory during the compilation or assembly of a program, whereas dynamic allocation of memory refers to the allocation of memory during the execution of the program.

(ii) Swapping and paging are two memory management techniques used by operating systems. Swapping involves moving an entire process from main memory to secondary storage, while paging involves dividing the process into fixed-size pages and moving only the required pages to and from main memory.

(iii) In a paging memory management scheme, the process is divided into fixed-size pages, whereas in a frame memory management scheme, the physical memory is divided into fixed-size frames. A segment is a logical unit of a program, such as a procedure or a data structure, which can be of variable size. Segmentation is a memory management scheme in which a process is divided into variable-sized segments.

Equal size fixed partitions are a memory management technique in which the memory is divided into fixed-size partitions, and each partition is assigned to a process. While this technique has some advantages, it also has two significant difficulties:

1. Internal Fragmentation: When a process is assigned a partition that is larger than its memory requirement, the unused memory within the partition is called internal fragmentation. The unused memory cannot be used by any other process, and it is wasted. Over time, the internal fragmentation can become significant, leading to a waste of memory.
2. Limited Process Size: With equal size fixed partitions, the size of the largest process that can be accommodated is limited by the size of the partitions. If the largest process is larger than the partition size, it cannot be accommodated, even if there is enough memory available in the system. This can lead to inefficient use of memory, as larger processes may be left waiting for memory even when there is enough memory available in the system.

If the scheduling of processes is priority based, the Gantt chart for the given scenario would be:

| P2 | P1 | P3 | P4 | P1 | P1 | P1 | P1 | P1 | P1 | P1 |

The calculation of turnaround time and waiting time for each process is as follows:

Process P1: Turnaround Time = 10 – 0 = 10 Waiting Time = 1 Priority = 2

Process P2: Turnaround Time = 6 – 1 = 5 Waiting Time = 0 Priority = 1

Process P3: Turnaround Time = 5 – 2 = 3 Waiting Time = 0 Priority = 3

Process P4: Turnaround Time = 9 – 3 = 6 Waiting Time = 1 Priority = 4

The average turnaround time for the system is (10 + 5 + 3 + 6)/4 = 6 The average waiting time for the system is (1 + 0 + 0 + 1)/4 = 0.5.

Best Fit and Worst Fit are memory allocation strategies used in operating systems to allocate free memory blocks to processes requesting memory.

In Best Fit strategy, the OS searches for the smallest free block of memory that is larger than or equal to the size requested by the process. The idea behind this strategy is to minimize wastage of memory by selecting the smallest block that can accommodate the process. For example, if there are three free memory blocks of sizes 50KB, 100KB, and 75KB, and a process requests 70KB of memory, then the Best Fit strategy will allocate the 75KB block to that process.

In Worst Fit strategy, the OS searches for the largest free block of memory available and allocates it to the process. This strategy aims to maximize the utilization of memory by selecting the largest available block, even if it is much larger than the process size. For example, if there are three free memory blocks of sizes 50KB, 100KB, and 75KB, and a process requests 70KB of memory, then the Worst Fit strategy will allocate the 100KB block to that process.

Both strategies have their advantages and disadvantages. Best Fit can lead to smaller blocks of free memory, which can be used to accommodate smaller processes, but it can also cause more fragmentation. Worst Fit, on the other hand, can lead to larger blocks of free memory, which can be used to accommodate larger processes, but it can also cause more wastage of memory.

To check whether the system is in a safe state, we can use the Banker’s algorithm. In this algorithm, we check whether there exists a safe sequence of processes that can complete their execution. If such a sequence exists, then the system is in a safe state.

Let’s calculate the need matrix for the given processes.

Processes Max Alloc Need

R1 R2 R3 R1 R2 R3 R1 R2 R3

1 5 6 3 2 1 3 5 3

2 8 5 6 3 2 5 3 3

3 4 9 2 3 0 1 9 0

4 7 4 3 3 2 4 2 0

5 4 3 3 1 0 3 3 0

Now, let’s calculate the available resources for each resource type.

Available = Total – (Allocated by P1 + Allocated by P2 + Allocated by P3 + Allocated by P4 + Allocated by P5) = 31 – (2 + 3 + 6 + 2 + 1) = 17 of R1 = 8 – (1 + 2 + 0 + 2 + 0) = 3 of R2 = 8 – (0 + 3 + 2 + 0 + 1) = 2 of R3

Next, we will create a work matrix that is initially set to the available resources.

Work = Available = (17, 3, 2)

Now, let’s create a boolean array of length 5 called finish, initialized to false.

finish = [false, false, false, false, false]

Next, we will look for a process that can be completed with the current available resources. We will check if the need of any process is less than or equal to the work. If such a process exists, we will allocate its resources to it, mark the process as finished, and add it to the safe sequence.

For the given system, we can follow the below steps:

1. From process P3, we can allocate (1, 0, 2) resources, and mark it as finished. Work = (18, 3, 4) finish = [false, false, true, false, false] safe sequence = [P3]
2. From process P4, we can allocate (3, 2, 0) resources, and mark it as finished. Work = (21, 5, 4) finish = [false, false, true, true, false] safe sequence = [P3, P4]
3. From process P1, we can allocate (2, 4, 3) resources, and mark it as finished. Work = (23, 9, 7) finish = [true, false, true, true, false] safe sequence = [P3, P4, P1]
4. From process P5, we can allocate (1, 3, 0) resources, and mark it as finished. Work = (24, 12, 7) finish = [true, false, true, true, true] safe sequence = [P3, P4, P1]

Linux VServer is a virtualization solution that allows for multiple isolated virtual environments to run on a single Linux kernel. It provides a lightweight, secure and efficient way to create and manage virtual private servers.

The architecture of Linux VServer is based on a concept called “Virtual Private Server” (VPS), which is a virtual machine that behaves like a dedicated server. In Linux VServer architecture, the kernel is modified to support the concept of “context” or “context ID”, which is a unique identifier for each virtual environment. Each context runs as a separate entity, isolated from other contexts on the same physical server.

The Linux VServer architecture consists of the following components:

1. The Host Operating System: The host operating system is the Linux kernel with some modifications to support virtualization. It provides the necessary system resources and manages the virtual environments.
2. The Virtual Environments: The virtual environments are isolated instances of the operating system that are created and managed by the host operating system. Each virtual environment has its own file system, processes, memory, and network resources.
3. The Context Management System: The context management system is responsible for managing the virtual environments. It provides the necessary tools to create, start, stop, and manage the virtual environments.
4. The Resource Management System: The resource management system is responsible for allocating system resources such as CPU, memory, and disk space to the virtual environments. It ensures that each virtual environment gets a fair share of the resources and prevents one virtual environment from hogging all the resources.

In the producer-consumer problem, a shared buffer is used to communicate between two processes, the producer and the consumer. The producer generates items and puts them in the buffer, while the consumer takes items out of the buffer and processes them. A race condition occurs when the producer and the consumer try to access the buffer at the same time, leading to inconsistent behavior.

To solve the producer-consumer problem using semaphores, we can use two semaphores, empty and full, and a mutex. The empty semaphore keeps track of the number of empty slots in the buffer, while the full semaphore keeps track of the number of full slots in the buffer. The mutex ensures that only one process can access the buffer at a time.

The producer and the consumer follow the following steps:

Producer:

1. Wait for the empty semaphore to become positive.
2. Acquire the mutex.
3. Add an item to the buffer.
4. Release the mutex.
5. Signal the full semaphore.

Consumer:

1. Wait for the full semaphore to become positive.
2. Acquire the mutex.
3. Remove an item from the buffer.
4. Release the mutex.
5. Signal the empty semaphore.

The solution using message passing involves creating two processes, the producer and the consumer, and passing messages between them. The producer sends a message containing an item to the consumer, who then processes the item and sends an acknowledgement message back to the producer. The producer can continue generating items and sending them to the consumer as long as the buffer is not full. If the buffer becomes full, the producer must wait until the consumer has processed some items and created some space in the buffer.