Csc 331 Operating Systems

Front 1

Java Thread States

Back 1

1) new: new Thread

2) running: start()

3) blocked: sleep()

4) dead: exits run() method

Front 2

Kernel Threads

Back 2

The kernel has a thread table

Advantages

♦ A process having large number of threads can be given more time

♦ Good for applications that frequently block

Disadvantages

♦ Slow and inefficient

♦ Significant overhead and increased in kernel complexity

Front 3

User Threads

Back 3

Advantages

♦ Can be implemented on OS that does not support threads

♦ Modification to OS not required

♦ Simple Representation

♦ Simple Management

♦ Fast and Efficient

Disadvantages

♦ lack of coordination between threads and operating system kernel

♦ User-level threads requires non-blocking systems call i.e., a multithreaded kernel

Front 4

Java threads may be created by:

Back 4

♦ extends Thread class and overwrites its run() function

♦ Implementing the Runnable interface

Front 5

Thread libraries

Back 5

Provides the programmer with an API for creating and managing threads

Three main thread libraries in use today

♦ POSIX Pthreads

♦ Win32

♦ Java

Front 6

Thread

Back 6

Is a basic unit of CPU utilization

♦ Has thread ID, a program counter, a register set, and a stack

Shares with the other threads belonging to the same process

♦ Code section

♦ Data section,

♦ and other OS resources (such as open files and signals)

Front 7

Thread Cancellation

Back 7

Two general approaches:

♦ Asynchronous cancellation terminates the target thread immediately

♦ Deferred cancellation allows the target thread to periodically check if it should be cancelled

Front 8

Thread Pools

Back 8

Create a number of threads in a pool where they await work

Advantages:

♦ Usually slightly faster to service a request with an existing thread than create a new thread

♦ Allows the number of threads in the application(s) to be bound to the size of the pool

Front 9

CPU Scheduling

Basic Concepts

Back 9

CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait

An I/O bound program typically has many short CPU bursts

A CPU-bound program might have a few long CPU bursts

Front 10

CPU Scheduler

Back 10

CPU scheduling decisions may take place when a process:

1. Switches from running to waiting state

2. Switches from running to ready state

3. Switches from waiting to ready

4. Terminates

Scheduling under 1 and 4 has no choice in terms of scheduling, nonpreemptive

2 and 3 is preemptive

Front 11

Dispatcher

Back 11

Dispatcher module gives control of the CPU to the process selected by the short-term scheduler;

Front 12

Scheduling Criteria

Back 12

CPU utilization – keep the CPU as busy as possible

Throughput – # of processes that complete their execution per time unit

Turnaround time – amount of time to execute a particular process

Waiting time – amount of time a process has been waiting in the ready queue

Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

Front 13

First-Come, First-Served (FCFS) Scheduling

Back 13

Similar to the concept of FIFO.

Front 14

Process Scheduling

Convoy effect

Back 14

Short process behind long process

♦ All the other processes wait for the long process to get off the CPU

Front 15

Shortest-Job-First (SJF) Scheduling

Back 15

Two schemes:

♦ nonpreemptive : Once a process is given to the CPU it runs to completion

♦ preemptive : Policy that switches the CPU process to the shortest at that time.

SJF is optimal – gives minimum average waiting time for a given set of processes

Study the examples given in the lectures

Front 16

Priority Scheduling

Back 16

A priority number (integer) is associated with each process

The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority)

♦ Preemptive

♦ nonpreemptive

SJF is a priority scheduling where priority is the predicted next CPU burst time

Problem ≡ Starvation – low priority processes may never execute

Solution ≡ Aging – as time progresses increase the priority of the process

Front 17

Priority Scheduling Problems

Back 17

Problem ≡ Starvation – low priority processes may never execute

Solution ≡ Aging – as time progresses increase the priority of the process

Front 18

Round Robin (RR)

Back 18

Each process gets a small unit of CPU time (time quantum) to execute code then switches to the next process in the queue

Front 19

Multilevel Queue

Back 19

Ready queue is partitioned into separate queues:

Each queue has its own scheduling algorithm

Scheduling must be done between the queues

Front 20

Multilevel Feedback Queue

Back 20

A process can move between the various queues; aging can be implementedthis way

Multilevel-feedback-queue scheduler defined by the following parameters:

♦ number of queues

♦ scheduling algorithms for each queue

♦ method used to determine when to upgrade a process

♦ method used to determine when to demote a process

♦ method used to determine which queue a process will enter when thatprocess needs service

Front 21

Multiple-Processor Scheduling

Asymmetric multiprocessing

Back 21

Only one processoraccesses the system data structures, reducing the need for data sharing.

Front 22

Multiple-Processor Scheduling

Symmetric multiprocessing (SMP)

Back 22

Eachprocessor is self-scheduling. All processes may be in a common ready queue, oreach processor may have its own private queue of ready processes.

Front 23

Multiple-Processor Scheduling

Processor affinity

Back 23

Cache memory populated with data accessed recently bythe process in execution; one process should be kept on one processor

 Soft affinity – not guaranteed

 Hard affinity – guaranteed . e.g. Linux

Front 24

Multiple-Processor Scheduling

Load Balancing

Back 24

Attempts to keep the workload evenly distributed across all processors inan SMP system

Front 25

Load Balancing:

push migration andpull migration

Back 25

Push: a specific task periodically checks theload on each processor and—if it finds an imbalance—evenly distributes theload by moving (or pushing) processes from overloaded to idle or less-busyprocessors.

Pull: occurs when an idle processor pulls a waiting taskfrom a busy processor

Front 26

Process Synchronization:

Race Condition

Back 26

Whereseveral processes access and manipulate the same data concurrently and theoutcome of the execution depends on the particular order in which the accesstakes place

Front 27

Critical Section Solution must Satisfy

Back 27

1. Mutual exclusion. If process Pi is executing in its critical section, then noother processes can be executing in their critical sections.

2. Progress. If no process is executing in its critical section and someprocesses wish to enter their critical sections, then only those processesthat are not executing in their remainder sections can participate indeciding which will enter its critical section next, and this selection cannotbe postponed indefinitely.

3. Bounded waiting. There exists a bound, or limit, on the number of timesthat other processes are allowed to enter their critical sections after aprocess has made a request to enter its critical section and before thatrequest is granted.

Front 28

Peterson’s Solution:

Back 28

Requires the two processes to share two data items:

int turn; //for process i and j

boolean flag[2]; // flag[i] or flag[j]

process i sets flag[i] = true, however it

Loops a while condition (turn = j and flag[j]) which check when process j has completed. Once this condition is false then process i is ready to enter critical sections. After it is done process i sets flag[i] to false. (similar algorithm in process j)