Simulation Questions.doc

LOVELY PROFESSIONAL UNIVERSITY Academic task- 3 Name: Parminder Singh Course Code : CSE316

Course Title: Operating System

Important Points 1.This assignment is a compulsory CA component. 2.The assignment is to be done on individual basis (no groups) 3.The assignment submission mode is Online only. Student has to upload the assignment on orbefore the last date on UMS only. No submission via e-mail or pen-drive or any media will be accepted. 4.Non-submission of assignment on UMS till the last date will result in ZERO marks. 5.The student is supposed to solve the assignment on his/her own. If it is discovered at any stagethat the student has used unfair means like copying from peers or copy pasting the code taken frominternet etc. ZERO marks will be awarded to the student. 6.The student who shares his assignment with other students (either in same section or differentsection) will also get ZERO marks. Programming Scenarios: 1. Develop a scheduler which submits the processes to the processor in the following scenario, and compute the scheduler performance by providing the waiting time for process, turnaround time for process and average waiting time and turnaround time.Considering the arrival time and the burst time requirement of the processes the scheduler schedules the processes by interrupting the processor after every 3 units of time and does consider the completion of the process in this iteration. The schedulers than checks for the number of processes waiting for the processor and allots the processor to the process but interrupting the processor after every

6 units of time and considers the completion of the process in this iteration. The scheduler after the second iteration checks for the number of processes waiting for the processor and now provides the processor to the process with the least time requirement to go in the terminated state. The inputs for the number of requirements, arrival time and burst time should be provided by the user. Consider the following units for reference. Process Arrival time Burst time P1 0 18 P2 2 23 P3 4 13 P4 13 10 2. Considering the arrival time and burst time requirement of the process the scheduler schedules the processes by interrupting the processor after every 6 units of time and does consider the completion of the process in this iteration. The scheduler than checks for the number of process waiting for the processor and allots the processor to the process but interrupting the processor every 10 unit of time and considers the completion of the processes in this iteration. The scheduler checks the number of processes waiting in the queue for the processor after the second iteration and gives the processor to the process which needs more time to complete than the other processes to go in the terminated state. The inputs for the number of requirements, arrival time and burst time should be provided by the user. Consider the following units for reference. Process Arrival time Burst time P1 0 20 P2 5 36 P3 13 19 P4 26 42 3. Consider a scheduler which schedules the job by considering the arrival time of the processes where arrival time if given as 0 is discarded or displayed as error. The scheduler implements the shortest job first scheduling policy, but checks the queue of the processes after the every process terminates and time taken for checking and arranging the process according to the shortest job is 2 time unit. Compute the waiting time, turnaround time and average waiting time and turnaround time of the processes. Also compute the total time taken by the processor to compute all the jobs.

The inputs for the number of requirements, arrival time and burst time should be provided by the user. Consider the following units for reference. Process Arrival time Burst Time 1 0 6 2 3 2 3 5 1 4 9 7 5 10 5 6 12 3 7 14 4 8 16 5 9 17 7 10 19 2 4. Consider the scenario, there are 3 student processes and 1 teacher process. Students are supposed to do their assignments and they need 3 things for that-pen, paper and question paper. The teacher has an infinite supply of all the three things. One students has pen, another has paper and another has question paper. The teacher places two things on a shared table and the student having the third complementary thing makes the assignment and tells the teacher on completion. The teacher then places another two things out of the three and again the student having the third thing makes the assignment and tells the teacher on completion. This cycle continues. WAP to synchronise the teacher and the students. ● Two types of people can enter into a library- students and teachers. After entering the library, the visitor searches for the required books and gets them. In order to get them issued, he goes to the single CPU which is there to process the issuing of books. Two types of queues are there at the counter-one for students and one for teachers. A student goes and stands at the tail of the queue for students and similarly the teacher goes and stands at the tail of the queue for teachers (FIFO). If a student is being serviced and a teacher arrives at the counter, he would be the next person to get service (PRIORITYnon preemptive). If two teachers arrive at the same time, they will stand in their queue to get service (FIFO). WAP to ensure that the system works in a non-chaotic manner. ● If a teacher is being served and during the period when he is being served, another

teacher comes, then that teacher would get the service next. This process might continue leading to increase in waiting time of students. Ensure in your program that the waiting time of students is minimized. 5. Consider a scheduling approach which is non pre-emptive similar to shortest job next in nature. The priority of each job is dependent on its estimated run time, and also the amount of time it has spent waiting. Jobs gain higher priority the longer they wait, which prevents indefinite postponement. The jobs that have spent a long time waiting compete against those estimated to have short run times. The priority can be computed as : =1+ / Using the data given below compute the waiting time and turnaround time for each process and average waiting time and average turnaround time. Process Arrival time P1

0

P2

5

P3

13

P4

17

6. IndianRail has decided to improve its efficiency by automating not just its trains but also its passengers. Each passenger and each train is controlled by a thread. You have been hired to write synchronization functions that will guarantee orderly loading of trains. You must define a structure struct station, plus several functions described below. When a train arrives in the station and has opened its doors, it invokes the function station_load_train(struct station *station, int count) where count indicates how many seats are available on the train. The function must not return until the train is satisfactorily loaded (all passengers are in their seats, and either the train is full or all waiting passengers have boarded). When a passenger arrives in a station, it first invokes the function station_wait_for_train(struct station *station) This function must not return until a train is in the station (i.e., a call to station_load_train is in progress) and there are enough free seats on the train for this passenger to sit down. Once this function returns, the passenger robot will move the passenger on board the

train and into a seat (you do not need to worry about how this mechanism works). Once the passenger is seated, it will call the function station_on_board(struct station *station) to let the train know that it's on board. Create a file IndianRail.c that contains a declaration for struct station and defines the three functions above, plus the function station_init, which will be invoked to initialize the station object when IndianRail boots. In addition: You must write your solution in C using locks and condition variables: ● lock_init (struct lock *lock) ● lock_acquire(struct lock *lock) ● lock_release(struct lock *lock) ● cond_init(struct condition *cond) ● cond_wait(struct condition *cond, struct lock *lock) ● cond_signal(struct condition *cond, struct lock *lock) ● cond_broadcast(struct condition *cond, struct lock *lock) Use only these functions (e.g., no semaphores or other synchronization primitives). ● You may not use more than a single lock in each struct station. ● You may assume that there is never more than one train in the station at once, and that all trains (and all passengers) are going to the same destination (i.e. any passenger can board any train). ● Your code must allow multiple passengers to board simultaneously (it must be possible for several passengers to have called station_wait_for_train, and for that function to have returned for each of the passengers, before any of the passengers calls station_on_board). ● Your code must not result in busy-waiting. 7. Sudesh Sharma is a Linux expert who wants to have an online system where he can handle student queries. Since there can be multiple requests at any time he wishes to dedicate a fixed amount of time to every request so that everyone gets a fair share of his time. He will log into the system from 10am to 12am only. He wants to have separate requests queues for students and faculty. Implement a strategy for the same. The summary at the end of the session should include the total time he spent on handling queries and average query time. 8. Design a scheduler that uses a preemptive priority scheduling algorithm based on dynamically changing

priority. Larger number for priority indicates higher priority. Assume that the following processes with arrival time and service time wants to execute (for reference): ProcessID P1 P2 P3 P4

Arrival Time Service Time 0 4 1 1 2 2 3 1

When the process starts execution (i.e. CPU assigned), priority for that process changes at the rate of m=1.When the process waits for CPU in the ready queue (but not yet started execution), its priority changes at a rate n=2. All the processes are initially assigned priority value of 0 when they enter ready queue for the first time . The time slice for each process is q = 1. When two processes want to join ready queue simultaneously, the process which has not executed recently is given priority. Calculate the average waiting time for each process. The program must be generic i.e. number of processes, their burst time and arrival time must be entered by user. 9. Design a scheduler with multilevel queue having two queues which will schedule the processes on the basis of pre-emptive shortest remaining processing time first algorithm (SROT) followed by a scheduling in which each process will get 2 units of time to execute. Also note that queue 1 has higher priority than queue 2. Consider the following set of processes (for reference)with their arrival times and the CPU burst times in milliseconds. ------------------------------------Process Arrival-Time Burst-Time ------------------------------------P1 0 5 P2 1 3 P3 2 3 P4 4 1 ------------------------------------Calculate the average turnaround time and average waiting time for each process. The input for number of processes and their arrival time, burst time should be given by the user. 10. Reena’s operating system uses an algorithm for deadlock avoidance to manage the allocation of resources say three namely A, B, and C to three processes P0, P1, and P2. Consider the following scenario as reference .user must enter the current state of system as given in this example : Suppose P0 has 0,0,1 instances , P1 is having 3,2,0 instances and P2 occupies 2,1,1 instances of A,B,C resource respectively.

Also the maximum number of instances required for P0 is 8,4,3 and for p1 is 6,2,0 and finally for P2 there are 3,3,3 instances of resources A,B,C respectively. There are 3 instances of resource A, 2 instances of resource B and 2 instances of resource C available. Write a program to check whether Reena’s operating system is in a safe state or not in the following independent requests for additional resources in the current state: 1. Request1: P0 requests 0 instances of A and 0 instances of B and 2 instances of C. 2. Request2: P1 requests for 2 instances of A, 0 instances of B and 0 instances of C. All the request must be given by user as input. 11. You have been hired by Coltrans Limited to automate the flow of traffic on a one-lane bridge that has been the site of numerous collisions. Coltrans Limited wants you to implement the following rules: ● Traffic can flow in only a single direction on the bridge at a time. ● Any number of cars can be on the bridge at the same time, as long as they are all traveling in the same direction. ● To avoid starvation, you must implement the “five car rule”: once 5 or more consecutive northbound cars have entered the bridge, if there are any southbound cars waiting then no more northbound cars may enter the bridge until some southbound cars have crossed. A similar rule also applies once 5 or more consecutive southbound cars have entered the bridge. You must implement the traffic flow mechanism in C by defining a structure struct bridge, plus five functions described below. When a northbound car arrives at the bridge, it invokes the function: bridge_arrive_north(struct bridge *b) This function must not return until it is safe for the car to cross the bridge, according to the rules above. Once a northbound car has finished crossing the bridge it will invoke the function: bridge_leave_north(struct bridge *b) Southbound cars will invoke analogous functionsbridge_arrive_southand bridge_leave_south. Use the next pages to write a declaration forstruct bridge and the four functions above, plus the functionbridge_init, which will be invoked to initialize the bridge You must write your solution in C using the functions for locks and condition variables: lock_init (struct lock *lock) lock_acquire(struct lock *lock) lock_release(struct lock *lock) cond_init(struct condition *cond)

cond_wait(struct condition *cond, struct lock *lock) cond_signal(struct condition *cond, struct lock *lock) cond_broadcast(struct condition *cond, struct lock *lock) Use only these functions (e.g., no semaphores or other synchronization primitives). You may not use more than one lock in each struct bridge. Your solution must not use busy-waiting. If your southbound functions are identical to the northbound functions except that north is replaced with south (and vice versa) in all identifiers, then you can omit the southbound functions and just circle this bullet point. 12. Ten students (a,b,c,d,e,f,g,h,i,j) are going to get there pictured clicked by university camera. Only one student can enter the camera room while the other students wait outside the room. The students are waiting in a queue to enter the room. To pass time the students start to play a game. In this game the students give candies to each other in a random manner (assume the students never run out of candies). They decide that the student with highest candies will be allowed to enter. When the student with highest amount of candies enter the room, the student starts the game again. Initially the students do not know if there is any body in the room and they start their game and the student with highest candies enter. Write and implement the algorithm to schedule such and compute the waiting and turnaround time. Consider the arrival time and burst time as given by the user. 13.You have been hired by the National council for Traffic Management to computerize traffic control at a 3-way intersection (pictured below).

The M.G street street is one-way as pointed by the directional arrow. The B.S street is two-way. The rules for this intersection are:

1. Each car (process) arriving at the intersection will call a procedure Enter(inDir, outDir), where inDir and outDir are parameters whose value is one of the defined constants: NORTH, SOUTH, EAST, or WEST. The parameter inDir is the direction that you enter the intersection, and outDir is the direction that you will leave the intersection. This procedure returns only when it is safe to proceed through the intersection. 2. After leaving the intersection, the car (process) must call procedure Leave(outDir), where outDir is defined the same as above. 3. Cars can proceed straight or make legal turns. U turns are illegal. 4. If cars are waiting from both the north and east directions, they should proceed at the same time if they can safely do so. 5. If cars are waiting from both the north and east directions, and they cannot both safely proceed at the same time, they must alternate (this prevents starvation). 6. The east-west street has a single lane. The north-south street has two lanes - one in either direction. You are to write the code for the Enter() and Leave() methods. You can assume that you are supplied with (already written) a procedure called DriveThroughTheIntersection(). You have no idea how long this procedure takes to execute. The first program will be written using semaphores as the synchronization mechanism. Assume that car each is a process. You are to define the global variables (including semaphores) that are to be used, and how they are initialized. You are to then write the code that the cars will use. 14. A university computer science department has a teaching assistant (TA) whohelps undergraduate students with their programming assignments duringregular office hours. The TA’s office is rather small and has room for only one desk with a chair and computer. There are three chairs in the hallway outsidethe office where students can sit and wait if the TA is currently helping anotherstudent. When there are no students who need help during office hours, the TA sits at the desk and takes a nap. If a student arrives during office hoursand finds the TA sleeping, the student must awaken the TA to ask for help. If astudent arrives and finds the TA currently helping another student, the student

sits on one of the chairs in the hallway and waits. If no chairs are available, thestudent will come back at a later time. Using POSIX threads, mutex locks, and semaphores, implement a solutionthat coordinates the activities of the TA and the students. 15. Assume that a finite number of resources of a single resource type mustbe managed. Processes may ask for a number of these resources and willreturn them once finished. As an example, many commercial softwarepackages provide a given number of licenses, indicating the number ofapplications that may run concurrently.When the application is started,the license count is decremented.When the application is terminated, thelicense count is incremented. If all licenses are in use, requests to startthe application are denied. Such requests will only be granted whenan existing license holder terminates the application and a license isreturned. The following program segment is used to manage a finite number ofinstances of an available resource. The maximum number of resourcesand the number of available resources are declared as follows: When a process wishes to obtain a number of resources, it invokes thedecrease count() function: /* decrease available resources by count resources */ /* return 0 if sufficient resources available, */ /* otherwise return -1 */ int decrease count(int count) { if (available resources
The preceding program segment produces a race condition. Do thefollowing: a. Identify the data involved in the race condition. b. Identify the location (or locations) in the code where the racecondition occurs. c. Using a semaphore or mutex lock, fix the race condition. It ispermissible to modify the decrease count() function so that thecalling process is blocked until sufficient resources are available. 16.A barrier is a tool for synchronizing the activity of a number of threads.When a thread reaches a barrier point, it cannot proceed until all otherthreads have reached this point as well. When the last thread reachesthe barrier point, all threads are released and can resume concurrentexecution. Assume that the barrier is initialized to N—the number of threads thatmust wait at the barrier point: init(N); Each thread then performs some work until it reaches the barrier point: /* do some work for awhile */ barrier point(); /* do some work for awhile */ Using synchronization tools like locks, semaphores and monitors, construct a barrierthat implements the following API: • intinit(int n)—Initializes the barrier to the specified size. • int barrier point(void)—Identifies the barrier point. All threads are released from the barrier when the last thread reaches this point. 17.Jurassic Park consists of a dinosaur museum and a park for safari riding. There are m passengers and n single-passenger cars. Passengers wander around the museum for a while, then line up to take a ride in a safari car. When a car is available, it loads the one passenger it can hold and rides around the park for a random amount of time. If the n cars are all out riding passengers around, then a passenger who wants to ride waits; if a car is ready to load but there are no waiting passengers, then the car waits. Using synchronization tools like locks, semaphores and monitorssynchronize the m passenger processes and the n car processes. 18. This problem demonstrates the use of semaphores to coordinate three types ofprocesses.6 Santa Claus sleeps in his shop at the North Pole and can only be wakenedby either (1) all nine reindeer being back from their vacation in the South Pacific, or(2) some of the elves having difficulties making toys; to allow Santa to get some sleep,the elves can

only wake him when three of them have problems.When three elves arehaving their problems solved, any other elves wishing to visit Santa must wait forthose elves to return. If Santa wakes up to find three elves waiting at his shop’s door,along with the last reindeer having come back from the tropics, Santa has decidedthat the elves can wait until after Christmas, because it is more important to get hissleigh ready. (It is assumed that the reindeer do not want to leave the tropics, andtherefore they stay there until the last possible moment.) The last reindeer to arrivemust get Santa while the others wait in a warming hut before being harnessed to thesleigh. Using synchronization tools like locks, semaphores and monitorsprovide a solution to this problem. 19. A barbershop consists of a waiting roomwith n chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer entersthe barbershop and all chairs are occupied, then the customer leaves theshop. If the barber is busy but chairs are available, then the customer sitsin one of the free chairs. If the barber is asleep, the customer wakes upthe barber. Write a program to coordinate the barber and the customers.Using synchronization tools like locks, semaphores and monitorsprovide a solution to his problem. 20.A new shop opened recently on Lovely Street. It is extremely popular and you have been asked to help organize how the shoppers can enter and leave the shop. You must use semaphores as your synchronization mechanism for this problem. Before a shopper can enter, they must call EnterShop(), and this function blocks until it is ok to enter the shop. To enter the shop, the shopper then calls ShopForAWhile(). This function is already written and provided to you; it returns when you are done shopping. To indicate to the rest of the world that they are done shopping, a shopper must call LeaveShop(). You will write the EnterShop() and LeaveShop() functions. So, a left-handed shopper would call these functions in this way: EnterShop(LEFT); ShopForAWhile(); LeaveShop(LEFT); The shopkeeper is a bit peculiar and has some strange rules that you must enforce: 1. Shoppers can only enter the shop in pairs (groups of 2). Each group must have one lefthanded person and one right-hand person. You must wait

outside until you have found a pair. This means that both EnterShop() and LeaveShop() are called with a parameter of LEFT or RIGHT. 2. At most one pair of shoppers can be in the store at the same time. 3. Shoppers can leave the shop one at a time, but both shoppers must leave before the next pair can enter. 21. You are asked to design and implement a new synchronization primitive that will allow multiple processes to block on an event until some other process signals the event. When a process signals the event, all processes that are blocked on the event are unblocked. If no processes are blocked on an event when it is signaled, then the signal has no effect. Implement the following using C functions.

   

intdoeventopen(); Creates a new event, returning event ID on success, -1 on failure. intdoeventclose(inteventID); Destroy the event with the given event ID and signal any processes waiting on the event to leave the event. Return number of processes signaled on success and -1 on failure. intdoeventwait(inteventID); Blocks process until the event is signaled. Return 1 on success and -1 on failure. intdoeventsig(inteventID); Unblocks all waiting processes; ignored if no processes are blocked. Return number of processes signaled on success and -1 on failure.