算法代写-Process Synchronization

CSE 2431 HOMEWORK 1 Autumn 2018

The purpose of Homework 1 is to review important concepts in chapter 5, 6, 7. This homework accounts for 5% of the total grades (5 pts).

All homework assignments must be edited using word or similar editors and uploaded as PDF files. The assignment must be submitted electronically online in Carmen Dropbox by 11:59 pm 10/18/18. Late penalty will be 25% per day. Although it is fine to talk with other students at a high-level regarding concepts related to the homework, the homework must be the student’s own individual work.

  1. Process Synchronization (1.5pts)

    1. Producer-Consumer Problem (0.5pt)

      Given the semaphore algorithm in the slides, answer the questions below:

      1. What is the function of the empty semaphore? Explain how empty is used by the Producer and/or the Consumer.
      2. What is the function of the full semaphore? Explain how full is used by the Producer and/or the Consumer.
      3. Suppose the mutex semaphore in Producer and Consumer is renamed mutex1 in Producer and mutex2 in Consumer. How will this impact the Producer- Consumer Problem, if at all? Justify your answer.
      4. Assuming that there is at least one Producer and at least one Consumer executing and that the amount of time to insert/remove something from the buffer is finite, is it possible to have starvation in this problem? Justify your answer.
    2. Readers-Writers Problem (0.5pt)

      Given the semaphore algorithm in the slides, answer the questions below:

      1. What is the purpose of readcount? Explain how it is used by the Reader and/or the Writer. Is it a semaphore, shared or local variable? Why does only the first reader check to see if a writer is writing? Explain.
      2. Why are two binary semaphores, mutex and wrt, needed? Explain how they are used by the Reader and/or the Writer.
      3. Suppose instead of mutex, mutex1 is used for the first critical section in Reader and mutex2 is used for the second critical section in Reader. What, if any, impact will these changes have? Justify your answer(s).
      4. Assuming that there is at least one Reader and at least one Writer and that the amount of time to read or write is finite, is it possible to have starvation in this problem? Justify your answer.
    3. Dining Philosophers Problem (0.5)

      Given the semaphore algorithm in the slides, answer the questions below:

      1. Suppose, for each philosopher, the two wait statements were reversed. Explain how this changes the problem. Does this impact whether or not there is deadlock? Justify your answer.
      2. Suppose, for each philosopher, that the signal statements are reversed but not

        the wait statements. Explain how this changes the problem. Does this impact whether or not there is deadlock? Justify your answer.

  2. CPU Scheduling (1.5pt)

    Analyze scheduling algorithms for the following five processes given the process burst (processing time), burst (lower number means higher priority) and arrival time.

    Processes

    Burst Time

    Priority

    Arrival Time

    P1

    16

    3

    0

    P2

    7

    4

    2

    P3

    10

    5

    4

    P4

    4

    1

    6

    P5

    18

    2

    8

    For each of the following scheduling algorithms draw a Gantt diagram, calculate the wait time for each process and calculate the average wait time.

    1. First Come First Served (FCFS)
    2. Non-preemptive Shortest Job First (NP-SJF)
    3. Preemptive Shortest Job First (P-SJF)
    4. Preemptive Priority Scheduling
    5. Non-preemptive Priority Scheduling
    6. Round Robin Scheduling (the time quantum is 5 time units) *Note: when a new process arrives, it is placed at the end of the ready queue; when the time slice of the executing process expires, it is also placed at the end of the queue.

    *Note: Arrival Times should be considered for each of the scheduling algorithms. It’s possible that the algorithms will not need all the information given in the table.

  3. Deadlock Detection (1pt)

    1. Is a cycle considered to be a necessary and/or a sufficient condition for deadlock? Explain. Is the answer dependent on any particular characteristic of the resource allocation graph being considered? Justify your answer.
    2. Suppose a system has 5 processes, P = {P1, P2, P3, P4, P5}, and 4 resources, R =

      {R1, R2, R3, R4}, where W = {2, 1, 3, 3}. The current state of the system is defined by the following requests and assignments;

      • P1 is requesting an instance of R3 and has been assigned R2

      • P2 is requesting an instance of R1 and has been an instance of assigned R3

    • P3 is requesting an instance of R4 and has been assigned an instance of R1 and an instance of R3

    • P4 is requesting an instance of R3

    • P5 is requesting R2 and has been assigned an instance of R4

    Is there deadlock in this system? Thoroughly justify your answer. If there is no deadlock your justification should contain a sequence of execution for the processes.

  4. Deadlock Avoidance (1pt)

Suppose a system has 4 processes, P = {P1, P2, P3, P4}, and 4 resource types, R = {R1, R2, R3}. The current state of the system is defined by the following requests and assignments:

allocation max

R1 R2 R3 R1 R2 R3

P1

3

0

2

7

2

4

P2

1

2

0

1

3

2

P3

0

1

2

2

1

3

P4

2

3

0

3

5

4

Available R1 R2 R3 2 0 3

  1. What is the total number of instances for each resource type.
  2. Using Banker’s algorithm, is the system currently in a safe state? If yes, show the sequence of processes that satisfy the safety criteria. If no, explain.
  3. If process P1 requests resources (0, 0, 1), is it safe to grant the request?