Operating Systems Chp 2.6, 3 & 4

Chp 3 and 4 notes Chapter 3: Scheduling Chapter 4: Concurrency

Chapter 2.6 Threads

ON MIDTERM REVIEW

Thread Definition:

Chapter 2.6 Threads

ON MIDTERM REVIEW

Thread Definition:

Thread: A thread is an instance of executing a portion of a program within a process without incurring the overhead of creating and managing separate PCBs.

Chapter 2.6.2 Threads within a process

ON MIDTERM REVIEW

1)Multiple threads within a process _____.

A. will always execute the same sequence of instructions

B. must execute within disjoint parts of the shared program

C. may execute different sequences of instructions within any part of the shared program

C. may execute different sequences of instructions within any part of the shared program

Chapter 2.6.3: Threads vs processes

ON MIDTERM REVIEW

Using n threads within a single process is more efficient than using n separate processes because _____.

1) the threads share the same code and data

A. True

B. False

A. True

• The code and data do not have to be replicated n times.

Chapter 2.6.3: Threads vs processes

ON MIDTERM REVIEW

2) only the threads can take advantage of multiple CPUs

A. True

B. False

B. False

• Both processes and threads can take advantage of multiple CPUs.

Chapter 2.6.3: Threads vs processes

ON MIDTERM REVIEW

3) only threads can block independently from one another

A. True

B. False

B. False

• Both processes and threads can block independently from one another.

Chapter 2.6 The Thread Control Block

ON MIDTERM REVIEW

Thread Control Block Definition:

A thread control block (TCB) is a data structure that holds a separate copy of the dynamically changing information necessary for a thread to execute independently.

• Since each thread within a process is an independent execution activity, the runtime information held in the PCB and the execution stack must be replicated for each thread.

• The replication of only the bare minimum of information in each TCB, while sharing the same code, global data, resources, and open files, is what makes threads much more efficient to manage than processes.

Chapter 2.6.5: TCBs vs PCB

ON MIDTERM REVIEW

1) Threads are faster to create and destroy than processes.

A. True

B. False

A. True

• A TCB is a much simpler data structure than a PCB and thus is faster to manage.

Chapter 2.6.5: TCBs vs PCB

ON MIDTERM REVIEW

2)In a multi-threaded process the PCB is replaced by multiple TCBs.

A. True

B. False

B. False

• A PCB is still needed because much of the information is shared by all threads within the process and need not be replicated in the TCBs.

Chapter 2.6.5: TCBs vs PCB

ON MIDTERM REVIEW

3)Memory and other fields are not replicated in the TCBs because the data is not needed by threads.

A. True

B. False

B. False

• All fields are needed by threads but all fields other than the CPU_state and thread_state can be shared by all threads.

Exercise 2.6.1 Single-threaded vs multi-threaded computation

ON MIDTERM REVIEW

A server accepts and processes requests from clients. The server keeps the results of the most recent requests in memory as a cache.

• A new request arrives on average every 25 ms.

• The processing of each request takes 15 ms.

• If the requested result is not in the memory cache, additional 75 ms are needed to access the disk.

• On average, 80% of all requests can be serviced without disk access.

• The creation of a new thread takes 10 ms.

(a) Should the server be implemented as a single-threaded or a multi-threaded process? Justify your answer.

(b) What percentage of requests would have to be satisfied without disk access for the single-threaded approach to be feasible?

(a)Should the server be implemented as a single-threaded or a multi-threaded process? Justify your answer.

80% of all requests take 15 ms. The remaining 20% take 15 + 75 = 90 ms.
A single-threaded process blocks when the disk is accessed. Thus the average time for each request is 0.8 15 + 0.2 90 = 30.
The process is unable to keep up with the arrivals and thus an unbounded queue will form
A multithreaded process incurs the thread creation time for each request but does not block on disk access. Thus, the average CPU time for each request is 10 + 15 = 25, which is sufficient to keep up with the arrivals.
The multi-threaded approach is the better choice.

(b)What percentage of requests would have to be satisfied without disk access for the single-threaded approach to be feasible?

If n is the percentage of requests without disk access, then (1 - n) is the percentage with disk access. The average time must not exceed 25:
n 15 + ( 1 - n) 90 = 25
n = 0.8667
87% of requests must be satisfied without accessing the disk.

Chapter 3 Scheduling

3.1 Principles of Scheduling

ON MIDTERM REVIEW

Scheduling decisions are made at two different levels

Long-term Scheduling:

Short-term Scheduling:

Long-term Scheduling: decides when a process should enter the ready state and start competing for the CPU.

Short-term Scheduling: decides which of the ready processes should run next on the CPU.

Chapter 3.1.2

ON MIDTERM REVIEW

Long-term scheduling takes place ________ short-term scheduling.

A. more frequently than

B. Less frequently than

C. equally frequently as

B. Less Frequently than

• Long-term scheduling occurs only at process creation and when the OS suspends the process. These events are much less frequent than moving between the running, ready, or blocked states, which requires short-term scheduling.

Chapter 3.1

A process can move to the RL from different locations.

1)A process entering the RL from a list of new processes is subject to ________.

A. long-term scheduling

B. short-term scheduling

A. Long-term scheduling

• The OS must decide whether the process should be added to the current mix of processes to compete for the CPU.

Chapter 3

A process can move to the RL from different locations.

2)A process entering the RL from the suspended list is subject to ________.

A. long-term scheduling

B. short-term scheduling

A. Long-term scheduling

• The OS may wish to decide whether the process should be re-admitted to the current mix of processes to compete for the CPU.

• Short-term scheduling applies to the movement of processes between the RL and the CPU. A suspended process is moved back to the RL at the discretion of the OS, which may involve long-term scheduling.

Chapter 3

A process can move to the RL from different locations.

3) A process entering the RL from the waiting list is subject to ________.

A. long-term scheduling

B. short-term scheduling

B. Short-term Scheduling

• A blocked process is moved to the RL as soon as the needed resource becomes available and typically requires no scheduling decision. But once the process is back on the RL, short-term scheduling is again applied.

• Long-term scheduling applies to only new processes entering the RL for the first time and processes re-admitted form the suspended list.

Chapter 3

A process can move to the RL from different locations.

4)A process entering the RL from the CPU is subject to ________.

A. long-term scheduling

B. short-term scheduling

B. short-term scheduling

• Whenever a running process is not allowed to continue running, the process is moved back to the RL by the OS. The decision to stop and remove the process is subject to short-term scheduling. Similarly, moving the process back to the RL is a short-term scheduling decision.

• Long-term scheduling applies to new processes entering the RL for the first time and processes re-admitted form the suspended list.

Chapter 3

ON MIDTERM REVIEW

Preemptive vs non-preemptive scheduling

Non-preemptive Scheduling:

Preemptive Scheduling:

ON MIDTERM REVIEW

non-preemptive scheduling: algorithm allows a running process to continue until the process terminates or blocks on a resource.

preemptive scheduling: algorithm may stop the currently running process and choose another process to run. The decision is made whenever:

• A new process enters the ready list.

• A previously blocked or suspended process re-enters the RL.

• The OS periodically interrupts the currently running process to give other processes a chance to run.

Chapter 3.1.5 Scheduling Decisions under non-preemptive scheduling

ON MIDTERM REVIEW

A non-preemptive algorithm makes a scheduling decision whenever _____.

1)

a new process arrives in the RL

A. True

B. False

B. False

• A non-preemptive decision is made only when the currently running process terminates or blocks, not when a process enters the RL.

Chapter 3.1.5

ON MIDTERM REVIEW

A non-preemptive algorithm makes a scheduling decision whenever _____.

2)

a process changes from the blocked state to the ready state

A. True

B. False

B. False

• A non-preemptive decision is made only when the currently running process terminates or blocks, not when a blocked process's request is satisfied.

Chapter 3.1.5

ON MIDTERM REVIEW

A non-preemptive algorithm makes a scheduling decision whenever _____.

3)

a process requests an unavailable resource

A. True

B. False

A. True

• When a process blocks and leaves the RL, a new process must be selected to run.

Chapter 3.1.5

ON MIDTERM REVIEW

A non-preemptive algorithm makes a scheduling decision whenever _____.

4)

a process terminates

A. True

B. False

A. True

• When a process terminates and leaves the system, a new process must be selected to run.

Chapter 3.1.6 Scheduling decisions under preemptive scheduling

ON MIDTERM REVIEW

A preemptive algorithm makes a scheduling decision whenever _____.

1) a new process arrives in the RL

A. True

B. False

A. True

• A new process may have higher priority than the currently running process and thus could preempt the current process.

Chapter 3.1.6

A preemptive algorithm makes a scheduling decision whenever _____.

ON MIDTERM REVIEW

2)a process changes from the blocked state to the ready state

A. True

B. False

A. True

• The unblocked process may have a higher priority than the currently running process and thus could preempt the current process.

Chapter 3

A preemptive algorithm makes a scheduling decision whenever _____.

ON MIDTERM REVIEW

3)a process requests an unavailable resource

A. True

B. False

A. True

• When a request cannot be satisfied, the requesting process leaves the RL and a new process must be selected to run.

Chapter 3

A preemptive algorithm makes a scheduling decision whenever _____.

ON MIDTERM REVIEW

4) a process terminates

A. True

B. False

A. True

• When the current process terminates and leaves the system, a new process must be selected to run.

Chapter 3

TABLE ON MIDTERM REVIEW

Chapter 3.1.7 Changes in the time-related parameters

ON MIDTERM REVIEW

1) For a process in the ready state, the ____keeps increasing.

A. arrival time

B. Attained CPU time

C. real time in system

D. total CPU time

C. real time in system

• The real time keeps increasing no matter which state the process is in.

The arrival time is the point in time when the process entered the RL. This time cannot change.

The process is not running and so the CPU times does not increase.

The total CPU time is the fixed amount of CPU time needed between the process's arrival and departure times.

Chapter 3.1.8 The meaning of the priority parameters

ON MIDTERM REVIEW

1)A weather forecasting application is an example of a system with a deadline.

A. True

B. False

A. True

• A weather forecast is useless after the date for which the prediction was made.

Chapter 3.1.8 The meaning of the priority parameters

ON MIDTERM REVIEW

2)A video streaming application is an example of a periodic process.

A. True

B. False

A. True

• Video frames are transmitted using packets, each of which must be delivered within a specific time interval to prevent freezing of the transmission or choppy playback.

Chapter 3.1.8 The meaning of the priority parameters

ON MIDTERM REVIEW

3)The external priority is recorded in a process's PCB.

A. True

B. False

A. True

• If an external priority is used, the priority value is supplied to the create process function and is stored in the PCB as part of the scheduling information.

Chapter 3.1.10 Arrival/departure vs creation/destruction

ON MIDTERM REVIEW

1)Arrival/departure times correspond to process creation/destruction in _________ scheduling.

A. short-term

B. long-term

C. both short and long-term

B. Long-term

• Under long-term scheduling, a process has a single arrival (time of creation) and a single departure (time of destruction).

Under short-term scheduling, arrival/departure refer to the points in time when the process enters/leaves the RL, not the times when the process enters/leaves the system.

Under short-term scheduling, arrival/departure refer to the points in time when the process enters/leaves the RL. Arrival/departure under short-term scheduling may occur many times during the process's lifetime, whereas create and destroy each occur only once.

Chapter 3.1.11: Attained and total CPU times under long-term and short-term scheduling.

ON MIDTERM REVIEW

A process p starts running at time 0, becomes blocked at time 2, and starts running again at time 5.

1)p's attained CPU time under short-term scheduling at time 6 will be ______ time units.

1

• For short-term scheduling, arrival means entering the RL. p became ready (arrived) at time 5 and ran until time 6.

  
  

Chapter 3.1.11

ON MIDTERM REVIEW

A process p starts running at time 0, becomes blocked at time 2, and starts running again at time 5.

2)p's attained CPU time under long-term scheduling at time 6 will be ______ time units.

3

• For long-term scheduling, arrival is the time of creation of the process. p was created (arrived) at time 0, ran until time 2, and then again from time 5 to 6.

Chapter 3.1.11

ON MIDTERM REVIEW

A process p starts running at time 0, becomes blocked at time 2, and starts running again at time 5.

3)If p terminates at time 7, the total CPU time under long-term scheduling will be ______ time units.

4

• The total CPU time under long-term scheduling accumulates from process creation until process destruction: 2 units from 0 to 2 and 2 more units from 5 to 7.

Chapter 3.2 Scheduling of Batch Processes

ON MIDTERM REVIEW

Batch Process Definition:

batch process: performs a long-running and generally repetitive task that does not require any intervention from the user. Ex: Payroll, insurance claims processing, weather prediction, scientific calculations.

In the early days of computing, batch processing referred to submitting multiple computations, known as jobs, to be executed as a "batch" without manual intervention. In modern computing, any long-running computation that does not require interaction with a user is called a batch job or batch process.

Chapter 3.2 FIFO Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

1) Start of p1 ___

0

• p1 arrives at time 0. No other process is running and so p1 starts executing.

Chapter 3.2 FIFO Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

2) Start of p2 ___

9

• p2 arrived after p3 and needs to wait for both p1 and p3 to terminate.

Chapter 3.2 FIFO Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

3) Start of p3

5

• p3 arrived before p2 and starts when p1 terminates.

Chapter 3.2

ON MIDTERM REVIEW

SJF (Shortest Job First) algorithm Definition:

SJF (Shortest Job First) algorithm,: aka SJN (Shortest Job Next), schedules processes according to the total CPU time requirements. The shorter the required CPU time, the higher the priority. If multiple processes have the same CPU time requirement, then the arbitration rule can select a process based on the arrival times.

SJF is non-preemptive.

Chapter 3.2.4 SJF Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

1)Start of p1 ___

0

• p1 arrives at time 0. No other process is running and so p1 starts executing.

Chapter 3.2.4 SJF Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

2)Start of p2 ___

5

• p2 has a shorter total CPU time requirement than p3 and so p2 starts when p1 terminates, at time 5.

Chapter 3.2.4 SJF Scheduling

ON MIDTERM REVIEW

Determine the start times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

3)Start of p3___

6

• p3 starts when p2 terminates at time 6.

Chapter 3.2 SRT Scheduling Algorithm

ON MIDTERM REVIEW

SRT (Shortest Remaining Time) algorithm Definition:

ON MIDTERM REVIEW
SRT (Shortest Remaining Time) algorithm: schedules processes according to the remaining CPU time needed to complete the work. The shorter the remaining CPU time, the higher the priority. If multiple processes have the same remaining time requirement, then the arbitration rule can select a process based on the arrival times.

***SRT is the preemptive version of SJF.

Chapter 3.2.6: Determining the remaining time.

The remaining time of a process depends on _________.

1)arrival and departure times

A. True

B. False

B. False

• How much CPU time a process needs is independent of the process arrival or departure times.

Chapter 3.2

The remaining time of a process depends on _________.

2)total CPU time

A. True

B. False

A. True

• The remaining time is the difference between the total CPU time the process will need and the already attained CPU time.

Chapter 3.2

The remaining time of a process depends on _________.

3)real time in system

A. True

B. False

B. False

• How much CPU time a process needs is independent of the time the process has been in the system.

Chapter 3.2

The remaining time of a process depends on _________.

4)arrival and departure times

A. True

B. False

A. True

• The remaining time is the difference between the total CPU time the process will need and the already attained CPU time.

Chapter 3.2.7 SRT Scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

1)Start of p1 ___

0

• p1 arrives at time 0. No other process is running and so p1 starts executing.

Chapter 3.2.7 SRT scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

2)End of p1 ___

6

• p1 is interrupted at time 3 by p2. Thus p1's real time is extended by 1 unit, terminating at time 6.

Chapter 3.2.7 SRT Scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

3)Start of p2 ___

3

• Upon arrival, p2 has a shorter remaining CPU time than the running process p1. Thus p2 preempts p1 at time 3.

Chapter 3.2.2.7 SRT Scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

4)End of p2___

4

• p2 started at 3 and thus terminates one unit later at 4.

Chapter 3.2.7 SRT Scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

5)Start of p3 ___

6

• When p2 terminates, p1 has a shorter remaining CPU time than p3 and is allowed to continue. When p1 terminates at time 6, p3 starts.

Chapter 3.2.7 SRT Scheduling

ON MIDTERM REVIEW

Determine the start and end times of the following processes:

Process	Arrival time	Total CPU time
p1	0	5
p2	3	1
p3	2	4

6)End of p3 ___

10

• p3 starts at time 6 and runs uninterrupted until time 10.

Chapter 3

ON MIDTERM REVIEW

Performance of Algorithms:

The main objective in scheduling batch processes is to maximize the number of processes completed per unit of time. The order in which processes are executed cannot reduce the total CPU times of the individual processes but can reduce the waiting times.

Chapter 3

ON MIDTERM REVIEW

Turnaround time Definition:

turnaround time of a process is the time between arrival and departure, and is the sum of the total CPU time and the waiting time.

Chapter 3

ON MIDTERM REVIEW

average turnaround time (ATT) Definition:

average turnaround time (ATT) for a set of n processes is the mean of the n individual turnaround times.

Chapter 3

ON MIDTERM REVIEW

Starvation Definition:

Another important objective is to guarantee fairness. Starvation is the indefinite postponement of a process while other processes are allowed to proceed. Both SJF and SRT can lead to starvation.

Chapter 3.2.1 Scheduling of batch Processes

Challenge Activity ON MIDTERM REVIEW

Chapter 3.2.1 Scheduling of batch processes

Challenge Activity ON MIDTERM REVIEW

Exercise 3.2.1 Scheduling with FIFO, SJF, and SRT

ON MIDTERM REVIEW

(a)

For the 5 processes described below, draw a timing diagram showing when each process executes under FIFO, SJF, and SRT.

Process	p1	p2	p3	p4	p5
Arrival time	0	2	4	6	8
Total CPU time	3	6	4	5	2

(b)

Determine the ATT for each scheduling algorithm for the 5 processes.

(a) (b)

Chapter 3.3.6 Order of process execution under ML

ON MIDTERM REVIEW

Process p is in the queue at level N-3, followed by process q at the same level. Queues at levels N through N-2 are empty. The quantum size is 1 time unit.

1)If p needs 2 units of CPU time and q needs 1 unit of CPU time, process _________ will terminate first.

A. p

B. q

B. q

• p starts, executes for 1 unit, and goes back behind q. q needs only 1 time unit and terminates before p.

Chapter 3.3.6

ON MIDTERM REVIEW

Process p is in the queue at level N-3, followed by process q at the same level. Queues at levels N through N-2 are empty. The quantum size is 1 time unit.

2)When p starts executing, a new process r with a CPU time requirement of 3 units arrives at level N. The 3 processes will terminate in the order _________.

A. r, p, q

B. r, q, p

C. p, r, q

B. r,q,p

• r arrives at a higher level than p and q and thus preempts p, which goes behind q. When r terminates, q starts and terminates within 1 time unit, followed by p.

Chapter 3.3.7 ML Scheduling

1)ML is prone to starvation.

A. True

B. False

A. True

• ML relies on the fact that queues are empty at certain times. If a stream of processes continues arriving at some priority level k, then no process at any level below k will be able to run, leading to starvation of all processes at levels below k.

Chapter 3.3.7

2)Instead of using RR, a different algorithm (Ex: FIFO, SJF, or SRT), could effectively be used at each level for interactive processes.

A. True

B. False

B. False

• None of the three algorithms is suitable for the scheduling of interactive processes because adequate response time cannot be guaranteed.

Challenge Activity Chapter 3.3.1 Scheduling of interactive processes

ON MIDTERM REVIEW

Exercise 3.3.1 Turnaround time under RR scheduling

ON MIDTERM REVIEW

Three processes, p1, p2, p3, arrive at the same time and start executing using RR scheduling.
p1 starts first, followed by p2, and then p3.
The respective total CPU times of the 3 processes are 8, 3, 5 time units.
The context switching time is negligible.

(a) Determine the average turnaround time, ATT, when the quantum is Q = 1 time unit.

(b) Determine the average turnaround time, ATT, when the quantum is Q = 3 time units.

Chapter 3.4.2 Execution under RM

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

1)Process _________ starts first.

A. p1

B. p2

A. p1

• RM uses the process period as the priority. p1 has a shorter period and thus a higher priority.

Chapter 3.4.2 Execution under RM

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

2)Process p2 starts running at time _________ .

A. 3

B. 6

C. 8

D. 10

A. 3

• p1 starts first and needs 3 time units to complete. p2 follows immediately at time 3.

Chapter 3.4.2 Execution under RM

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

3)Process _________ will be running between times 8 and 9.

A. p1

B. p2

A. p1

• Under RM, p1 always has a higher priority than p2 and interrupts p2 as soon as it is available at time 8.

Chapter 3.4.4 Execution under EDF

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

1)p1's first deadline is _________.

8

• p1 arrives at time 0 and has a period of 8. Thus p1's deadline is the end of the first period.

Chapter 3.4.4 Execution under EDF

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

2)p2's first deadline is _________.

10

• p2 arrives at time 0 and has a period of 10. Thus p2's deadline is the end of the first period.

Chapter 3.4.4 EDF

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

3)Process _______ starts first.

p1

• p1 has a shorter deadline than p2.

Chapter 3.4.4 EDF

ON MIDTERM REVIEW

Processes p1 and p2 with the following characteristics arrive at time 0:

Process	Period	Total CPU time
p1	8	3
p2	10	6

4)Process______ will be running between times 8 and 9.

p2

• p1 has a new deadline of 16. p2's deadline is still 10. Thus p2 continues at time 8.

Chapter 3.4 Performance of the algorithms

ON MIDTERM REVIEW

A schedule is feasible if the deadlines of all process can be met.

The CPU utilization (U) is the sum of the individual fractions of CPU times used by each process.

If U = 1 then the CPU is utilized 100%

Challenge Activity Chapter 3.4.1 Real-Time Scheduling

ON MIDTERM REVIEW

Challenge Activity Chapter 3.4.1 Real-Time Scheduling

ON MIDTERM REVIEW

Exercise 3.4.1 Real-time scheduling under EDF and RM

ON MIDTERM REVIEW

Three periodic processes with the following characteristics are to be scheduled:
(D is the period and T is the total CPU time)

	D	T
p1	20	5
p2	100	10
p3	120	42

(a) Determine if a feasible schedule exists.

(b) Determine how many more processes, each with T = 3 and D = 20, can run concurrently under EDF.

(c) Determine how many more processes, each with T = 3 and D = 20, can run concurrently under RM.

(a) Determine if a feasible schedule exists.

5/20 + 10/100 + 42/120 = .25 + .1 + .35 = .7

.7 < 1 and thus a feasible schedule exists

(b) Determine how many more processes, each with T = 3 and D = 20, can run concurrently under EDF.

The CPU fraction used by each new process is 3/20 = .15

Thus 2 more such processes can run concurrently under EDF without exceeding the maximum CPU utilization, U = 1

(c) Determine how many more processes, each with T = 3 and D = 20, can run concurrently under RM.

The CPU fraction used by the 3 processes p1 through p3 is already .7

Adding any more processes to the mix would likely result in an infeasible schedule

4.1.2 Incorrect Interleaving of Code

4.1.4 Possible values of the variables

1)

When p1 is in CS, the value of c1 can be 0.

A. True

B. False

B. False

• c1 must be set to 1 before attempting to enter the CS.

4.1.4 Possible values of the variables

2)

When p1 is in CS, the value of will_wait can be 0.

A. True

B. False

B. False

• will_wait can only be 1 or 2.

4.1.4 Possible values of the variables

3)

When p1 is in CS, the value of will_wait can be 1.

A. True

B. False

A. True

• If p2 is not attempting to enter the CS, p1 sets will_wait to 1 but proceeds into the CS because c2 is 0.

4.1.4 Possible values of the variables

4)

When p1 is in CS, the value of will_wait can be 2.

A. True

B. False

A. True

• When both p1 and p2 try to enter the CS simultaneously, will_wait determines which process enters. Since p1 is in the CS, will_wait must be 2, indicating that p2 is waiting

4.1.5 An Incorrect Solution 1

p1 executes the code: while (1) { while (turn==2) /*wait*/ CS turn = 2 ... }

p2 executes the code: while (1) { while (turn==1) /*wait*/ CS turn = 1 ... }

1)Assuming the variable turn is initialized to 1 or 2, which requirement is violated in the above solution?

A. Mutual exclusion not guaranteed.

B. Lockout is possible.

C. Starvation is possible.

D. Deadlock is possible.

B. Lockout is possible

• p1 and p2 must alternate in entering the CS. When p1 does not want to enter, turn remains 1 and p2 cannot enter repeatedly. The same is true for p2.

4.1.6 An Incorrect Solution 2

p1 executes the code: while (1) { c1 = 1 while (c2) /*wait*/ CS c1 = 0 ... }

p2 executes the code: while (1) { c2 = 1 while (c1) /*wait*/ CS c2 = 0 ... }

1)

Which requirement is violated in the above solution?

A. Mutual exclusion not guaranteed.

B. Lockout is possible.

C. Starvation is possible.

D. Deadlock is possible.

D. Deadlock is possible

• If both p1 and p2 execute in lock-step then both c1 and c2 will be 1 when the processes enter the respective while loops and will never exit.

4.1.8 Possible overlap between the producer and the consumer

1)

Which code segments could never be executing simultaneously?

A. "produce next data item" and "remove data from buffer"

B. "place data into buffer" and "process data"

C. "mark buffer as full" and "remove data from buffer"

C. "mark buffer as full" and "remove data from buffer"

• When the producer is marking the buffer as full, the buffer contains a new data item and thus the consumer could only be processing the previous data item or waiting for the buffer to be marked as full, but not accessing the buffer.

4.1.9 The Consumer-producer problem vs the critical section problem

1) The buffer is a critical section.

A. True

B. False

2) The code segments "place data into buffer" and "remove data from buffer" must not be interleaved because both access the shared buffer. Thus the software solution to the critical section problem could be used to solve the producer-consumer problem.

A. True

B. False

1) False

• A critical section is a segment of code. The buffer is a data structure.

2) False

• In addition to preventing simultaneous access to the shared buffer, the solution must also guarantee that, starting with the producer, the two processes strictly alternate in accessing the buffer.