Homework answers / question archive / Computer Operating System Experiment Laboratory 6 CPU Scheduling and deadlock Objective: You will build a simulator of a simple operating system to learn more about operating systems in general and process schedulers in specific

Computer Operating System Experiment Laboratory 6 CPU Scheduling and deadlock Objective: You will build a simulator of a simple operating system to learn more about operating systems in general and process schedulers in specific

Computer Science

Share With

---

Computer Operating System Experiment

Laboratory 6

CPU Scheduling and deadlock

Objective:

50. You will build a simulator of a simple operating system to learn more about operating systems in general and process schedulers in specific.
50. You will write a banker algorithm program in a high-level language, and use the banker algorithm to simulate the allocation of resources and security checks.

Equipment:

VirtualBox with Ubuntu Linux

 

Methodology:

Program and answer all the questions in this lab sheet.

 

1. CPU Scheduling

CPU scheduling is the process by which a computer's operating system determines how, in what order, and for how long individual processes in a queue of processes are allowed to access the CPU. Input factors such as the chosen scheduling algorithm, the length of processes, and frequency of processes will have an influence on performance factors such as CPU utilization, average job waiting time, average job response time, and average job turn-around time. Depending on the application, the importance of some factors may weigh more heavily than others. For instance, a system that is designed for heavier human-computer-interaction may require lower average job response time in order to make the system appear more responsive.

 

In this Lab we will look at the following scheduling algorithms:

50. First Come First Served
50. Shortest Job First
50. Priority scheduling
50. Round Robin

You will observe the following output metrics:

50. Average Turnaround Time
50. Average Waiting Time

You will also vary our random sample of data by altering certain factors which will be discussed later.

The Process Scheduling Simulator will execute a collection of processes that demonstrate a scheduling algorithm of either First-Come/First-Served (FCFS), Shortest Job First (SJF), Priority, or Round Robin (RR) and will then generate visual aids along with statistics to explain the results. The typical scheduling queue is working as follows:

2. Experiments

2.1 Experiment 1: CPU Scheduling Simulator

Understanding the working of scheduling algorithms provides us with a knowledge of how to analyze the scheduling of processes, resource utilization, and performance in real-time applications. Various algorithms perform differently and have their unique set characteristics which are advantageous depending on the scenario and application. A simulator enables us to visualize these characteristics, working, and behaviors of scheduling algorithms. By automating the process of scheduling these tasks provided as input and displaying the output intuitively, which reduces the work on creating the schedule and focuses on analyzing the behaviors of the scheduling algorithms. This Lab focuses on the development of a web application that is machine and platform-independent, with the scope of illustrating multiple scheduling algorithms graphically to help one to draw comparisons and conclusions based on the results.

 

 

Implement a process scheduler with N processes executing concurrently. Each process is represented by a process control block (PCB). The process control block can contain the following information: process name, priority number, CPU burst time, used CPU time, process status, etc. The status of each process can be one of three states: ready W (Wait), running R (Run), or completed F (Finish). After the ready process gets the CPU, how long this process can run depends on the scheduling algorithm.

50. First-Come/First-Served (FCFS): The process ready queue is arranged in descending order of arrival time. According to processes’ arrival time, the processes can obtain their CPU burst with none-preemption.
50. Shortest Job First (SJF): according to processes’ arrival time and CPU burst, the shortest CPU burst will get their CPU burst.
50. Priority scheduling: The process ready queue is arranged in descending order of priority number and arrival time, and the first process of the chain is put in first.
50. Round Robin (RR): The process ready queue is arranged in descending order of arrival time. The program that implements processor scheduling by time slice rotation.

 

 

typedef struct pcb{ struct pcb *next;                       //The next process control block pointer char process_name[20];                    //Process name int process_number;                          //Process number int process_start_moment;                    //Process start time int process_burst_time;                       //Required running time int process_time_slice;                       //Time slice int process_priority;                          //Priority number }PCB;

 

 

 

50. Initialize the process control block:

 

void init_pcb_table()

 

50. Display process queue:

void display_process_queue(PCB *queue)

 

50. Create process:

PCB *create_process()

 

 

50. First come first serve process scheduling algorithm:

void FCFS()

 

50. Priority scheduling:

 

void PS()

 

50. Round Robin (RR) scheduling algorithm:

void RR()

 

…

Requirements?

1. you can start to implement those scheduling algorithms with non-preemption.
2. detailed analysis of the scheduling algorithm, based on a careful analysis, completely understand the role of the main data structures and processes described and shown a flowchart of the main module of the main data structure is given.
3. Follow the prompts, write the function complete, the program became a run.
4. repeatedly run the program, the program execution result of the observation, verify the correctness of the analysis and the results of a given final operation performed by the calculated result and the weighted turnaround time turnaround time.

 

 

Input:

Process name:P0

Arrival time:0

CPU burst: 2

…

 

Output?

 

PROCESS         BURST TIME      WAITING TIME              TURNAROUND TIME

--------------------------------------------------------------------------------------------------

 P0                    2                         0                 2

 P1                    5                         2                 7

 P2                    6                         7                 13

 P3                    7                        13                        20

Average Waiting Time = 5.500000

     Average Turnaround Time = 10.500000

 

2.2 Experiment 2: Safety Algorithm Implementation

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes a safe-state check to test for possible activities, before deciding whether allocation should be allowed to continue.

Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource-allocation system. We need the following data structures, where n is the number of processes in the system and m is the number of resource types:

• Available. A vector of length m indicates the number of available resources of each type. If Available[j] equals k, then k instances of resource type Rj are available.

• Max. An n × m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj.

• Allocation. An n × m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource type Rj.

• Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process Pi may need k more instances of resource type Rj to complete its task. Note that Need[i][j] equals Max[i][j] − Allocation[i][j].

 

Safety Algorithm?

1.  Let Work and Finish be vectors of length m and n, respectively.  Initialize:

Work = Available

Finish [i] = false for i = 0, 1, …, n- 1

2. Find an i such that both:

     (a) Finish [i] = false

     (b) Need_i £ Work

     If no such i exists, go to step 4

3.  Work = Work + Allocation_i
      Finish[i] = true
      go to step 2

4. If Finish [i] == true for all i, then the system is in a safe state

 

Requirements?

1. Implement Safety Algorithm that can determine the system is in a safe state or not if you give the inputs.
2. If system is in the safe sate, please output the execute sequence of processes.

 

Input:

Enter No. of AVAILABLE Instances for each resource

 

Enter MAXIMUM instance for a Process & its corresponding resource

 

Enter instance ALLOCATED for a Process & its corresponding resource

 

 

Output:

The system is safe.

The Safe Sequence is P0, P3, P2, P1.

 

 

Suppose that, at time T0, the following snapshot of the system has been taken:

 

 

2.3 Experiment 3: Bankers Algorithm (optional)

For this Lab, you will write a multithreaded program that implements the banker’s algorithm. Several customers request and release resources from the bank. The banker will grant a request only if it leaves the system in a safe state. A request that leaves the system in an unsafe state will be denied. This programming assignment combines three separate topics: (1) multithreading, (2) preventing race conditions, and (3) deadlock avoidance.

The Banker

The banker will consider requests from n customers for m resources types. The banker will keep track of the resources using the following data structures:

 

/* these may be any values >= 0 */ #define NUMBER OF CUSTOMERS 5 #define NUMBER OF RESOURCES 3 /* the available amount of each resource */ int available[NUMBER OF RESOURCES]; /*the maximum demand of each customer */ int maximum[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES]; /* the amount currently allocated to each customer */ int allocation[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES]; /* the remaining need of each customer */ int need[NUMBER OF CUSTOMERS][NUMBER OF RESOURCES];

 

 

The Customers

Create n customer threads that request and release resources from the bank. The customers will continually loop, requesting and then releasing random numbers of resources. The customers’ requests for resources will be bounded by their respective values in the need array. The banker will grant a request if it satisfies the safety algorithm outlined in previous experiment. If a request does not leave the system in a safe state, the banker will deny it. Function prototypes for requesting and releasing resources are as follows:

 

 

int request resources(int customer num, int request[]); int release resources(int customer num, int release[]);

 

 

These two functions should return 0 if successful (the request has been granted) and –1 if unsuccessful. Multiple threads (customers) will concurrently. access shared data through these two functions. Therefore, access must be controlled through mutex locks to prevent race conditions. The use of Pthreads mutex locks are described in the project entitled “Producer–Consumer Problem”.

 

Implementation

You should invoke your program by passing the number of resources of each type on the command line. For example, if there were three resource types, with ten instances of the first type, five of the second type, and seven of the third type, you would invoke your program follows:

./banker 10 5 7

The available array would be initialized to these values. You may initialize the maximum array (which holds the maximum demand of each customer) using any method you find convenient.