Lab 2 Solution

Description

In this lab you will implement priority based thread scheduling for Pintos.

As supplied, Pintos implements a first-come-first-served (FCFS) ready queue with a periodic interrupt to implement a round-robin (RR) style of scheduler.

NOTE: We have not covered the FCFS or RR scheduling algorithms in the lectures yet, neither have we covered Semaphores and Condition Variables, but we will be doing so soon. The concept or a prioritized ready queue is not hard to grasp, so I strongly recommend you make a start on this lab immediately.

There are three increasingly complex dependent parts to this lab:

• Implementing the prioritized ready queue

• Handling priority in concurrency primitives

• Implementing priority donation between threads interacting with each other through these concurrency primitives.

This lab is worth 15% of your final grade.

Submissions are due NO LATER than 23:59, Wednesday May 2, 2018 ( three weeks )

Setup

SSH in to one of the two CMPS111 teaching servers using your CruzID Blue password:

Or	$ ssh	<cruzid>@noggin.soe.ucsc.edu	( use Putty http://www.putty.org/ if on Windows )
	$ ssh	<cruzid>@nogbad.soe.ucsc.edu

Authenticate with Kerberos:

$ kinit <cruzid>@CATS.UCSC.EDU

Authenticate with AFS:

$ aklog

Create a suitable place to work: ( only do this the first time you log in )

$ mkdir –p ~/CMPS111/Lab2

$ cd ~/CMPS111/Lab2

Install the lab environment: ( only do this once )

$ tar xvf /var/classes/CMPS111/Spring18/Lab2.tar.gz

Build Pintos:

Accessing the teaching servers file systems from your personal computer

Follow the instructions from Lab 1:

https://classes.soe.ucsc.edu/cmps111/Spring18/SECURE/CMPS111-Lab1.pdf

Background Information

(1) Priority Based Ready Queues

Thread priorities range from PRI_MIN (0) to PRI_MAX (63). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest.

The initial thread priority is passed as an argument to thread_create(). If there’s no reason to choose another priority, consumer code should use PRI_DEFAULT (31) when creating a thread.

1. • When a thread is added to the ready list at creation, if this new thread has a higher priority than the currently running thread, the current thread must immediately yield the processor to the new thread.

1. • When thread priority is raised or lowered via thread_set_priority(), you may need to reorder the ready queue, and take appropriate action (known as “preempting”) if a thread with higher priority that the currently executing thread is now waiting.

2. Priority and Concurrency

When threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be woken up first.

2. • Pintos locks use semaphores, so once your implementation for semaphores is working, it will, or at least, should also be working for locks.

2. Priority Donation

One issue with priority scheduling is “priority inversion”.

Consider high, medium, and low priority threads H, M, and L, respectively.

If H needs to wait for L (because, for example, L holds a lock H would like to acquire), and M is on the ready list, then H will not get the CPU because the low priority thread L will never get scheduled ahead of M.

A partial fix for this problem is for H to “donate” its priority to L while L is holding the lock, then recall the donation once L releases (and thus H acquires) the lock.

Priority donation implementations need to account for a number of different situations in which priority donation is required:

• Multiple Donations: Multiple priorities are donated to a single thread.

• Nested & Chained Donations: If H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H’s priority.

University of California Santa Cruz Baskin School of Engineering CMPS111 Spring 2018 Lab 2 Copyright © 2017-2018 David C. Harrison. All rights reserved.

Requirements

Basic:

• Change the supplied FCFS ready queue into a priority based ready queue

• Pass the following tests:

15. alarm-priority o priority-preempt o priority-change

15. priority-fifo

Advanced:

• Implement priority waiting for locks, semaphores, and condition variables

• Pass the following tests:

15. priority-sema

15. priority-condvar

Stretch:

• Implement single-level priority donation, including multiple donations

• Pass the following tests:

15. priority-donate-single o priority-donate-one o priority-donate-lower

o priority-donate-multiple o priority-donate-multiple2 o priority-donate-sema

15. priority-donate-condvar

Extreme:

• Implement nested and chained priority donation

• Pass the following tests:

15. priority-donate-nest

15. priority-donate-chain

What to submit

In a command prompt:

$ cd ~/CMPS111/Lab2/pintos/src/threads

$ make submit

This creates a gzipped tar archive named CMPS111-Lab2.tar.gz in your home directory.

UPLOAD THIS FILE TO THE APPROPRIATE CANVAS ASSIGNMENT.

In addition to submitting modified and new source files, you are required to write a short report (no more than two pages) on your work.

This report should contain at least:

• A defense of the rationale behind your design

• Details of tests your submission fails and what investigations you undertook to try and find out why

If you keep a simple journal as you work your way through this lab, writing the report will be easy – it’s essentially a tidied up version of your journal.

SUBMIT YOU REPORT TO CANVAS IN THE SAME ASSIGNMENT AS YOUR CODE ARCHIVE.

Note that the report WILL NOT BE READ unless plagiarism is detected in your submission.

University of California Santa Cruz Baskin School of Engineering CMPS111 Spring 2018 Lab 2 Copyright © 2017-2018 David C. Harrison. All rights reserved.

What steps should I take to tackle this?

Come to the sections and ask.

How much code will I need to write?

A model solution that satisfies all requirements adds approximately 200 lines of executable code.

Grading scheme

The following aspects will be assessed:

1. (100%) Does it work?

a.	Basic Requirements	(40%)
b.	Advanced Requirements	(30%)
c.	Stretch Requirements	(20%)
d.	Extreme Requirements	(10%)

2. (-100%) Did you give credit where credit is due?

2. 1. You submission is found to contain code segments copied from on-line resources and you failed to give clear and unambiguous credit to the original author(s) in your source code (-100%)

2. 2. You submission is determined to be a copy of another past or current CMPS111 student’s submission (-100%)

§

University of California Santa Cruz Baskin School of Engineering CMPS111 Spring 2018 Lab 2 Copyright © 2017-2018 David C. Harrison. All rights reserved.