Weekly Note 3 - Week 8

13 February 2019

There will be no classes in week 9, due to constraints at work for Jacob (I’ll be in Macedonia). Thus no lecture February 26th or tutorials on February 28th. I’m sorry for the inconvenience this may cause.

Luckily, there is project work :) So you should be able to get far with the second project.

See you in week 10 where we will start the next big section of the course: Process Synchronization.

With this change, week 20 seems to be the last week with classes in DM510.

Lecture - Tuesday, February 19th.

16-19 in U82

We will cover chapter 5: CPU scheduling. This chapter will be the primary material for exam topic 3: "CPU scheduling".

The first projects have been handed in, so we will take a look at (annonymized) code snippets from the first round of the projects. We will be doing some code review and discussing style, naming etc., helping you become better in the fine craftmanship of programming.

We will have a small review of the previous lecture, so this time it will be chapter 3 and 4, and we might sneak in a Kahoot.

Tutorial session

Thursday February 20th. 8-10 in U31 or Friday February 21th. 12-14 in U155

Preparation:

Make a list of 10-15 keywords for a 10 min. presentation with the topic: "CPU scheduling"

Prepare at home to discuss:

  1. Why is it important for the scheduler to distinguish I/O-bound programs from CPU- bound programs?

  2. Discuss how the following pairs of scheduling criteria conflict in certain settings.

    1. CPU utilization and response time

    2. Average turnaround time and maximum waiting time

    3. I/O device utilization and CPU utilization

  3. Consider the following set of processes, with the length of the CPU burst time given in milliseconds:
    3 1
    The processes are assumed to have arrived in the order P1 , P2 , P3, P4 , P5 all at time 0.

    1. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1).

    2. What is the turnaround time of each process for each of the scheduling algorithms in part a?

    3. What is the waiting time of each process for each of these scheduling algorithms?

    4. Which of the algorithms results in the minimum average waiting time (over all processes)?

  4. Which of the following scheduling algorithms could result in starvation?

    1. First-come, first-served

    2. Shortest job first

    3. Round robin

    4. Priority

  5. Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.

    1. What would be the effect of putting two pointers to the same process in the ready queue?

    2. What would be two major advantages and disadvantages of this scheme?

    3. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

  6. Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. Describe is the CPU utilization for a round-robin scheduler when:

    1. The time quantum is 1 millisecond

    2. The time quantum is 10 milliseconds

  7. Explain the differences in how much the following scheduling algorithms discriminate in favor of short processes:

    1. FCFS

    2. RR

    3. Multilevel feedback queues

In class:

Use the first 30 minutes to work on those exercises:

  1. In this chapter, we discussed possible race conditions on various kernel data structures. Most scheduling algorithms maintain a run queue, which lists processes eligible to run on a processor. On multicore systems, there are two general options: (1) each processing core has its own run queue, or (2) a single run queue is shared by all processing cores. What are the advantages and disadvantages of each of these approaches?

  2. Consider the exponential average formula used to predict the length of the next CPU burst. What are the implications of assigning the following values to the parameters used by the algorithm?

    1. α = 0 and τ0 = 100 milliseconds

    2. α = 0.99 and τ0 = 10 milliseconds

  3. The following processes are being scheduled using a preemptive, round-robin scheduling algorithm. Each process is assigned a numerical priority, with a higher number indicating a higher relative priority. In addition to the processes listed below, the system also has an idle task (which consumes no CPU resources and is identified as Pidle). This task has priority 0 and is scheduled whenever the system has no other availableprocesses to run. The length of a time quantum is 10 units. If a process is preempted by a higher-priority process, the preempted process is placed at the end of the queue.
    3 2

    1. Show the scheduling order of the processes using a Gantt chart.

    2. What is the turnaround time for each process?

    3. What is the waiting time for each process?

    4. What is the CPU utilization rate?

  4. Consider a system implementing multilevel queue scheduling. What strategy can a computer user employ to maximize the amount of CPU time allocated to the user’s process?

  5. Consider a preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate α ; when it is running, its priority changes at a rate β . All processes are given a priority of 0 when they enter the ready queue. The parameters α and β can be set to give many different scheduling algorithms.

    1. What is the algorithm that results from β > α > 0?

    2. What is the algorithm that results from α < β < 0?

  6. Assume that two tasks A and B are running on a Linux system. The nice values of A and B are -5 and +5, respectively. Using the CFS scheduler as a guide, describe how the respective values of vruntime vary between the two processes given each of the following scenarios:

    1. Both A and B are CPU-bound.

    2. A is I/O-bound, and B is CPU-bound.

    3. A is CPU-bound, and B is I/O-bound.

Then spend the remaining time discussing your list of keywords, and the excercises prepared at home and in class.

  • Chapter 5 in Operating System Concepts, Enhanced eText, 10th Edition

Material (Slides, etc.)