MCS 043 Q-1 (2014) solution



There is document - MCS 043 Q-1 (2014) solution available here for reading and downloading. Use the download button below or simple online reader.
The file extension - PDF and ranks to the Documents category.


135

views

on

Extension: PDF

Category:

Documents

Pages: 1

Download: 39



Sharing files


Tags
Related

Comments
Log in to leave a message!

Description
Download MCS 043 Q-1 (2014) solution
Transcripts
Solution for Assignment 3 1 The following is a semaphore solution to the readers-writers problem: semaphore mutex = 1 semaphore wrt = 1 int variable: readcount = 0 0 Reader: P(mutex) 1 readcount = readcount + 1 2 if readcount == 1 then P(wrt) 3 V(mutex) 4 5 P(mutex) 6 readcount = readcount – 1 7 if readcount == 0 then V(wrt) 8 V(mutex) 9 Writer: P(wrt) 10 11 V(wrt) Assuming the following situations: 1) If there are no writers and you have first Reader executing code at line #2 and a second Reader shows up, explain what will happen to the second Reader Second reader will be blocked at line #0 with P(mutex) 2) If you have one Writer accessing the database at line #10 and a Reader shows up, explain what will happen to the reader Reader will block at line #2 with P(wrt) 3) If you have 5 Readers reading the database at line #4, and a Writer shows up, what will happen to the Writer? When will the Writer access the database? 1 Writer will block at line #9 with P(wrt) 2 Writer will be allowed to access database after the 5th reader finished reading at line #7 with V(wrt) 4) The above solution can cause a starvation problem Point out how this situation is possible If a writer shows up in the midst of stream of readers, writer must wait and may starve if more readers keep showing up 2 Round robin schedulers normally maintain a list of all runnable processes, with each process occurring exactly once in the list What would happen if a process occurred twice in the list? Can you think of any reason for allowing this? A process will get more quanta per scheduling cycles This is used to give more important process a larger share of the CPU 3 Most round robin schedulers use a fixed size quantum Give an argument in favor of a small Assignment 1 http://facultykfupmedusa/ICS/salah/092/ics431/assignments/solution3 1 of 4 24-04-2014 15:34 quantum Now give an argument in favor of a large quantum A large quantum is more efficient than a small one, since fewer process switches happen this way However, interactive response time suffers Interactive processes prefer smaller quantums 4 Define the difference between preemptive and nonpreemptive scheduling State why strict nonpreemptive scheduling is unlikely to be used in a computer center Answer: Preemptive scheduling allows a process to be interrupted in the midst of its exe-cution, taking the CPU away and allocating it to another process Nonpreemptive scheduling ensures that a process relinquishes control of the CPU only when it finishes with its current CPU burst 5 Consider the following set of processes, with the length of the CPU-burst time given in milliseconds: The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0 a Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF,a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling b What is the turnaround time of each process for each of the scheduling algorithms in part a? c What is the waiting time of each process for each of the scheduling algorithms in part a? d Which of the schedules in part a results in the minimal average waiting time (over all processes)? Assignment 1 http://facultykfupmedusa/ICS/salah/092/ics431/assignments/solution3 2 of 4 24-04-2014 15:34 6 Suppose that the following processes arrive for execution at the times indicated Each process will run the listed amount of time In answering the questions, use nonpreemptive scheduling and base all decisions on the information you have at the time the decision must be made a What is the average turnaround time for these processes with the FCFS scheduling algorithm? b What is the average turnaround time for these processes with the SJF scheduling algorithm? c The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit and then SJF scheduling is used Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase This algorithm could be known as future-knowledge scheduling Answer: a 1053 b 953 c 686 Remember that turnaround time is finishing time minus arrival time, so you have to sub-tract the arrival times to compute the turnaround times FCFS is 11 if you forget to subtract arrival time 7 Is it possible to have a deadlock involving only one single process? Explain your answer Answer: No This follows directly from the hold-and-wait condition 8 Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources Show that the system is deadlock free Answer: Suppose the system is deadlocked This implies that each process is holding one resource and is waiting for one more Since there are three processes and four resources, one process must be able to obtain two resources This process requires no more resources and, therefore it will return its resources when done 9 Consider the following allocation state table: Assignment 1 http://facultykfupmedusa/ICS/salah/092/ics431/assignments/solution3 3 of 4 24-04-2014 15:34 Is the system in a safe state? Yes We have a safe sequence of a Can a request(1,0,2) for P1 granted? Yes Results in a safe sequence of b Next, can request for (3,3,0) by P4 be granted? No Resources are not availablec Lastly, can request for (0,2,0) by P0 be granted? No Resulting state is unsafed 10 In distributed systems, why is there a need for a unique timestamp? Used in several topics to break a tie, eg, in DME and in deadlock prevention, etc 11 To ensure mutual exclusion in distributed systems, there are two approaches: centralized and fully distributed? Which approach you prefer and why? See class notes and textbook 12 What is a disadvantage of using total resource ordering for deadlock prevention in distributed systems? It is inflexible and requires each process to check for order before it requests If the request a process wants is out of order, it may require the process to release the held resources to and request them again in order to proceed This may cause it to experience starvation 13 To prevent starvation in preventing deadlock by breaking wait-for cycle, which scheme you prefer: wound-wait or wait-die? Justify your answer See class notes and textbook 14 What is the bully algorithm is used for in distributed system? How does it work? See class notes and textbook 15 Bully algorithm can have considerable overhead in exchanging messages The Ring algorithm minimizes this overhead Explain how By constructing the logical ring, less messages are sent No broadcast messages, and less interruption 16 What is a disadvantage of Ring algorithm over Bully algorithm? Difficulty in constructing and maintaining the logical ring, especially when one of the processes in the ring fail Assignment 1 http://facultykfupmedusa/ICS/salah/092/ics431/assignments/solution3 4 of 4 24-04-2014 15:34







Recommended
MCS 043 Q-1 (2014) solution

MCS 043 Q-1 (2014) solution

Rriocard Pollakowski

127 views

MIT 6041 2015 Pset 1

MIT 6041 2015 Pset 1

Aymer Shaffer

137 views

CW701 701 Presentation

CW701 701 Presentation

Karthik Ve

149 views

CLRS Solution 4

CLRS Solution 4

Juliana Biggeri

145 views

Quiz 3 Solutions

Quiz 3 Solutions

122 views

CSWIP Set Question

CSWIP Set Question

Adelina Viglionese

161 views

CQI-122014

CQI-122014

153 views

JPMS Kali 2 2014

JPMS Kali 2 2014

Donnie Yulikova

158 views