CSE2302 CMG-2003-10

Tutorial Sheet 4

Synchronization and CPU Scheduling

1. Objectives and Outcomes

1.1 Objectives

  1. To review material covered in the lectures (chapters 7 and 5);
  2. To confirm understanding of concepts such Process, Process Control Block Process States, Scheduler, Process Queues, Context Switch, Process Creation, Process Termination, Interprocess Communication, Critical-Section, Atomic Transactions, Semaphores and Monitors;
  3. To answer questions arising from lectures during the next few weeks;

1.2 Outcomes

  1. You should be able to describe the purpose of various Process Management and CPU Scheduling concepts;
  2. You should be able to explain in detail the sequence of tasks performed by the Operating-System components during process management and scheduling of processes; and
  3. You should be able to explain the need for these components to support Modern Operating Systems.

2. Review Lecture Material

  1. What is the difference between pre-emptive and non-pre-emptive? (The word pre-emption comes from two Latin words pre, before, and emptio, a purchase: hence its current meaning of "anticipative".)
  2. Identify and explain the four transitions in the process state diagram in terms of pre-emptive and non-pre-emptive scheduling.
  3. Explain how the Gantt chart is constructed (this is part of assignment 2).
  4. What are the three conditions necessary for critical regions? Discuss them, paying particular attention to those that you find difficult.

3. Discussion of Assignment

  1. (Students to raise issues of concern: tutors will explain these issues, but not give the answers to the assignment!)

4. Deadlocks and Final Review Synchronisation

  1. Why is the test and set instruction useful? Explain how it can be used to implement mutual exclusion.
  2. Why can't you use a test and set (T&S) instruction in place of a semaphore? Hint: compare the semantics of T&S versus semaphores. Explain what else is needed to realise a semaphore using the T&S instruction.
  3. Explain how semaphores are used in the bounded buffer problem to implement both mutual exclusion and synchronization.
  4. What is the difference between deadlock prevention, deadlock avoidance, and deadlock detection?
  5. One way to avoid deadlock is to restrict the creation of circular wait situations. A method of doing this is to only allocate resources in some arbitrarily imposed ordering, and require that processes always request their required resources in this order. Explain how this prevents deadlock from occuring.
  6. A problem with this method is that it may lead to inefficient use of resources, since the lowest numbered ones always have to be allocated first. A process might make progress if it can allocate some higher numbered ones first, that are not being used by other processes. It is therefore proposed to modify the method by ordering resources in a circular fashion, such that that lowest numbered resource may be requested after the highest numbered resource, provided that the lowest (in the original sense) resource is requested after other processes have completed all their resource requests. Will this method work? Why?

5. Any Other Issues