Assignment Two

Please submit this homework to the email address: by July 16th 2013(Tuesday)

1.We have two processes P1 and P2. The process P1 has a period of p1=50 and a CPU bust of t1=20; the process P2 has a period of p2=100 and a CPU burst time of t2=35. The deadline for each process requires that it complete its CPU burst by the start of its next period. Now we have 100 time slices, please use the rate-monotonic algorithm to schedule these two process P1 and P2; point out whether these two processes complete their first tasks before their first deadline.

2. Here are four processes. If the processes arrive at the ready queue at the times shown and need the indicated burst times, please use preemptive priority algorithm to schedule these processes and compute the relative average waiting time.

Process / Arrival Time / Priority / Burst Time
/ 0 / 3 / 10
/ 1 / 1 / 7
/ 2 / 2 / 7
/ 3 / 4 / 12

3. If a system is in a safe statute, the deadlock will not happen. Please use the Safety Algorithm of the Banker’s Algorithm to check whether the sequence <P1, P3, P0, P2> is a safe sequence and give the algorithm processes.

Process / Allocation
ABC / Need
ABC / Available
ABC
P0 / 010 / 743 / 332
P1 / 200 / 122
P2 / 302 / 600
P3 / 211 / 011

Please indicate here that <P1, P3, P0, P2> is a safe or unsafe sequence.

Please complete the forms to show the process of the algorithm

Allocate resource to P1

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Release resource from P1

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Allocate resource to P3

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Release resource from P3

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Allocate resource to P0

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Release resource from P0

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Allocate resource to P2

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

Release resource from P2

Process / Allocation
ABC / Need
ABC / Available
ABC
P0
P1
P2
P3

4. Please explain the relationships among safe, unsafe and deadlock situations?

5. What are the differences between the First-Come First-Serve (FCFS)and Round-Robin (RR) Scheduling? Can we change the RR to FCFS?

6. There are user-level and kernel-level threads. In the many-to-one and many-to-many, we use two different schemes to scheduling them. One is process-contention scope(PCS); another is system-contention scope (SCS). Please indicate which scheme is for user-level thread and which scheme is for kernel –level thread.

7. A deadlock situation can arise if the four conditions hold simultaneously in a system. Please list and explain these four situations.

8. There are three ways to satisfy a request of size n from a list of free holes. Please list and explain them.

9. Please explain the concept internal fragment and external fragment.

10. What are the two parts of logical address space?

11. Segment table is used to map two-dimensional physical addresses; each table entry has two parts. Please list and explain this two parts.

12. Here is a figure about paging hardware. Please indicate which part is logical address which part is physical address.