Homework #2 solution

Describe the differences among short-term, medium-term and long-term scheduling?

For each:

Short-term scheduling - also called "CPU scheduler", allocates CPU time to processes in memory
Medium-term scheduling - swaps processes out of memory and reinstates them, to be run, at a later time, as in a time-sharing system
Long-term scheduling - also called "job scheduler"

A common difference, other than their defined tasks, is also how frequently each scheduler is called.

Problem 5.3

What are two differences between user-level threads and kernel-level threads? Under what circumstances is one type better than the other?

A couple differences:

User threads are built using a library and are unknown or undifferentiated by the kernel.
Kernel threads require more operating system resources because they are managed by the kernel.

A user thread is more appropriate for low-level tasks, whereas a kernel thread is better for high-priority tasks that should get high priority to system resources.

Problem 5.6

What resources are used when a thread is created? How do they differ from those used when a process is created?

When created, a thread requires an ID, a register set, a stack and program counter.

Threads are smaller than processes. In addition to the thread information, each process creates its own Process Control Block (PCB), containing a code section, data section, and O/S resources. Threads reference these items from their creating or parent process.

Problem 6.3

Consider the following set of processes, with the length of the CPU-burst time given in milliseconds.

a) Draw Gantt charts for each of the following: FCFS scheduling, SJF scheduling, priority scheduling, and Round Robin scheduling

FCFS scheduling

P1	P2	P3	P4	P5
10	11	13	14	19

SJF scheduling

P2	P4	P3	P5	P1
1	2	4	9	19

Priority scheduling

P2	P5	P1	P3	P4
1	6	16	18	19

Round Robin scheduling

P1	P2	P3	P4	P5	P1	P3	P5	P1	P5	P1	P5	P1	P5	P1
1	2	3	4	5	6	7	8	9	10	11	12	13	14	19

b) What is the turnaround time of each process for each of the scheduling algorithms in part a?

Turnaround times are:

Turnaround Times
	FCFS	SJF	Priority	RR
P1	10	19	16	19
P2	11	1	1	2
P3	13	4	18	7
P4	14	2	19	4
P5	19	9	6	14

c) What is the waiting time of each process for each of the scheduling algorithms?

Waiting times:

Waiting Times
	FCFS	SJF	Priority	RR
P1	0	9	6	9
P2	10	0	0	1
P3	11	2	16	5
P4	13	1	18	3
P5	14	4	1	9

Let's see:

FCFS: (0+10+11+13+14) / 5 = 48 / 5 = 9.6
SJF: (9+0+2+1+4) / 5 = 16 / 5 = 3.2
Priority: (6+0+16+18+1) / 5 = 41 / 5 = 8.2
RR: (9+1+5+3+9) / 5 = 27 / 5 = 5.4

The shortest average wiating time is Shortest Job First (SJF) at an average wait of 3.2 milliseconds.

Threading Comparison Problem

From Chapter 5, please describe three "important" facts/properties of the implementation of threads on a) Solaris, b) Windows 2000, c) Linux, and d) Java operating systems.

These are my favorites, other answers are certainly possible:

a) Solaris

Four scheduling classes or priorites: real time, system, time sharing, and interactive
Scheduling approach is a preemptive multilevel feedback queue
Threads run on the CPU until: an I/O block, it uses its time slice, or it is pre-empted by a higher priority thread

b) Windows 2000

32 levels of priorities in two general groups: variable class (0-15) and real-time class (15-31).
Scheduler is called the "dispatcher" and again uses a preemptive multilevel feedback queue for scheduling.
Foreground processes (current window) get higher priority than background processes.

c) Linux

Two separate scheduling algorithms: one for time-sharing, one for real-time.
Real-time scheduling is still "soft" because the kernel threads cannot be interrupted "willy-nilly".
The scheduling algorithm is "credit-based" to enforce priority and prevent starvation.