MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 18

Scheduling, Concurrency and Deadlock

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 22 marks. Total 32 marks.

Name

Class

Date

Mark  / 32

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What is a context switch?1
    1. AMoving a file from one folder to another
    2. BChanging the screen resolution
    3. CSwitching the processor off to save power
    4. DSaving the state of the running process and loading the state of the next
  2. 2Which scheduling algorithm gives each process a fixed time slice in turn?1
    1. ARound robin
    2. BFirst come first served
    3. CShortest job first
    4. DPriority scheduling
  3. 3What is a disadvantage of shortest job first scheduling?1
    1. ALong processes may be starved, and burst times must be known in advance
    2. BIt cannot run more than one process
    3. CIt needs more than one processor
    4. DIt always has the longest average waiting time
  4. 4A process arrives at time 2 and needs 5 units. It finishes at time 14. What was its waiting time?1
    1. A5
    2. B7
    3. C9
    4. D12
  5. 5What is the effect of making the quantum in round robin very large?1
    1. AIt makes the processor idle
    2. BIt gives the best response time
    3. CIt behaves like first come first served
    4. DIt increases the number of context switches
  6. 6What is a race condition?1
    1. AA fault where the result depends on the timing of tasks sharing data
    2. BA loop that never ends
    3. CA program that runs faster than expected
    4. DTwo programs competing to open the same file name
  7. 7What does a lock provide?1
    1. AA faster way to read data
    2. BA way to encrypt shared data
    3. CMutual exclusion: only one task at a time in a critical section
    4. DA way to run tasks in parallel
  8. 8Which of these is one of the four conditions needed for deadlock?1
    1. AStarvation
    2. BThrashing
    3. CTime slicing
    4. DCircular wait
  9. 9How can deadlock be prevented in a program that needs several locks?1
    1. AUse more locks
    2. BMake every task acquire the locks in the same order
    3. CRelease every lock after a random delay
    4. DRun every task at the same priority
  10. 10Amdahl's law says that 80% of a program can run in parallel. What is the greatest possible speed-up, however many processors there are?1
    1. A80 times
    2. B5 times
    3. C2 times
    4. D1.25 times

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1DescribeDescribe how a round robin scheduling algorithm works.3
  2. 2CalculateThree processes, P1, P2 and P3, all arrive at time 0. They need 5, 3 and 1 units of processor time respectively. Calculate the average waiting time when they are scheduled using (a) first come first served, in the order P1, P2, P3 and (b) shortest job first. State which gives the lower average.4
  3. 3ExplainExplain what is meant by a race condition, and how it can be prevented.4
  4. 4ExplainTwo processes each need exclusive use of both a printer and a scanner before they can continue. Process 1 has been allocated the printer and Process 2 has been allocated the scanner. Explain why this situation is a deadlock, and describe one way in which deadlock could be prevented.5
  5. 5DiscussA photo editing program applies a filter to a very large image. Discuss the use of parallel processing to make it faster.6

Mark scheme

Section A

1D2A3A4B5C6A7C8D9B10B

Section B

1 Describe how a round robin scheduling algorithm works. 3

One mark for each of the following, to a maximum of 3.

  • Each process is given a fixed amount of processor time (a time slice or quantum)
  • When the time is used up the process is pre-empted and put at the back of the queue
  • The next process in the queue then runs, and processes that finish leave the queue

Model answer. Each process in the ready queue is allowed to use the processor for a fixed amount of time called a time slice or quantum. When the time slice is used up, the process is pre-empted and placed at the back of the queue, and the process at the front of the queue is given the processor next. A process that finishes before the end of its time slice leaves the queue.

2 Three processes, P1, P2 and P3, all arrive at time 0. They need 5, 3 and 1 units of processor time respectively. Calculate the average waiting time when they are scheduled using (a) first come first served, in the order P1, P2, P3 and (b) shortest job first. State which gives the lower average. 4

One mark for each of the following, to a maximum of 4.

  • FCFS: waiting times of 0, 5 and 8 for P1, P2 and P3
  • FCFS average = 13 / 3 = 4.33
  • SJF order P3, P2, P1 gives waiting times of 0, 1 and 4, with an average of 5 / 3 = 1.67
  • Shortest job first gives the lower average

Model answer. With first come first served, P1 runs from 0 to 5 so waits 0, P2 runs from 5 to 8 so waits 5, and P3 runs from 8 to 9 so waits 8. The average is (0 + 5 + 8) / 3 = 13 / 3 = 4.33 units. With shortest job first the order is P3, P2, P1. P3 waits 0, P2 waits 1 and P1 waits 4, so the average is (0 + 1 + 4) / 3 = 5 / 3 = 1.67 units. Shortest job first gives the lower average waiting time.

3 Explain what is meant by a race condition, and how it can be prevented. 4

One mark for each of the following, to a maximum of 4.

  • Two (or more) processes or threads access shared data (the same variable)
  • The result depends on the order or timing in which they run (they interleave)
  • For example, one task reads a value, another changes it, then the first writes back, so an update is lost
  • It can be prevented by mutual exclusion: a lock (mutex or semaphore) so only one task is in the critical section at a time

Model answer. A race condition happens when two or more processes or threads access the same shared data and the result depends on the order or timing in which they run. For example, one thread may read a balance, then another thread updates it, and then the first writes back its result, so that the second update is lost. It can be prevented using mutual exclusion: the code that uses the shared data is made a critical section, protected by a lock (mutex or semaphore), so that only one thread can be in it at any time.

4 Two processes each need exclusive use of both a printer and a scanner before they can continue. Process 1 has been allocated the printer and Process 2 has been allocated the scanner. Explain why this situation is a deadlock, and describe one way in which deadlock could be prevented. 5

One mark for each of the following, to a maximum of 5.

  • Process 1 is waiting for the scanner, which is held by Process 2
  • Process 2 is waiting for the printer, which is held by Process 1
  • Neither can release what it holds until it has both, so neither can ever continue (circular wait)
  • Prevention: require resources to be requested in the same fixed order
  • Or: a process must request all of its resources at once (or release what it holds), so there is no hold and wait

Model answer. Process 1 holds the printer and is waiting for the scanner, and Process 2 holds the scanner and is waiting for the printer. Each is waiting for a resource that the other holds, and neither can release what it holds until it has both, so neither can ever continue. This circular wait is a deadlock. It could be prevented by making every process request resources in the same fixed order, for example the printer before the scanner, so that a circular wait cannot form. Alternatively a process could be required to request everything that it needs at the same time, so that it never holds one resource while waiting for another.

5 A photo editing program applies a filter to a very large image. Discuss the use of parallel processing to make it faster. 6

One mark for each of the following, to a maximum of 6.

  • The image can be divided into sections, each processed on a separate core (or processor) at the same time
  • The work on each section is independent, so the speed-up could be close to the number of cores
  • There is overhead in splitting up the image and combining the results
  • Some parts cannot be run in parallel, such as loading and saving the file, which limits the speed-up (Amdahl's law)
  • The software must be written to use several cores, and the computer must have them
  • A reasoned conclusion: worthwhile for a large image because the filter can be shared out, but gains tail off as more cores are added

Model answer. The image can be divided into sections, with each section processed by a separate core at the same time. Because the filter is applied to each pixel independently, the work can be shared out very evenly and the speed-up could be close to the number of cores. There is some overhead, though, in splitting up the image and combining the results, and some parts of the program, such as loading and saving the file, cannot be done in parallel, which limits the overall speed-up as described by Amdahl's law. The software must be written to use several cores, and the computer must have them. Overall, parallel processing is worthwhile for a very large image because the filter can be shared out easily, but the gains tail off as more cores are added, because the part that cannot be parallelised takes up a bigger share of the total time.