Operating Systems Issues

Main Page Intel Curriculums

Introduction to the Course

Introduction to Multicore Architectures

Projects

Multicore Architectures

Introduction to Compilers for HPC

Compiler Optimizations

Loop Optimization

Operating Systems Issues

SC01-OMP-Intro-Tutorial

SC01-OMP-Tutorial-Advanced

 

Contents

Multi-core computing: Multi-processor Scheduling

Introduction

•Design issues in system with multiple processors

  • •Tightly coupled or loosely coupled.
  • •Message passing, shared memory or both.

•Several new issues are introduced into the design of scheduling functions.

•Loosely coupled systems are easier to handle.

  • •Not an OS issue but an application issue
  • •Several message passing systems are available (such as MPI)

•We will examine these issues and the details of scheduling algorithms for tightly coupled multi-processor systems.

Issues with Multi-processor computations

•Granularity of computation

  • •Fine grain
  • •Coarse grain
    • •Various shades of coarseness.

•Design issues

  • •Assignment of processes to processors
  • •Multiprogramming on individual processors
  • •Actual dispatching of a process

Granularity

•The main purpose of having multiple processors is to realize ????

•Applications exhibit parallelism at various levels with varying degree of granularity.

Fine grain parallelism: Inherent parallelism within a single instruction stream.

  • •High data dependency ....high frequency of high frequency of

synchronizations required between processes.synchronizations required between processes.

  • •Dynamic Scheduling/Superscalar architectures exploit

this kind of parallelism.

Fine Grain Parallelism

•Given a sequence of instructions the issue logic will look at the dependencies between multiple instructions in a window.

  • •Dependencies: Data or Control dependency.
  • •Dependencies: False or true.
  • •Consider add R1, R2 followed by add R3, R4.
  • •Consider div R1, R2 followed by div R3, R4
  • •Consider load X followed by load Y

•Independent instructions can be executed in parallel if structural resources are available.

Granularity

Medium grain parallelism: Parallelism of an application can be implemented by multiple threads in a single process.

  • •Usually programmers have to “use”threads in the design.
  • •Threads are scheduled by user (e.g. pthreads) or by OS (kernel threading).

Coarse grain parallelism: Parallelism in a system by virtue of several concurrent processes

  • •Need to synchronize using semaphore or other synchronization objects.
  • •Example: Server side threads for web servers. FTP servers etc.

Very coarse grain: When synchronization needs are not high among parallel processes.

  • •Processes can even be distributed across network.
  • •Example: CORBA standard for distributed system.

Independent parallelism: Multiple unrelated processes.

  • •All independent processes can run in parallel.

Design Issues

•Where does the OS run?

•Mapping processes to processors.

  • •Static or dynamic

•Use of multiprogramming on individual processors.

•Actual dispatching of a process.

Where does the OS run?

Master/slave assignment: Kernel functions always run on a particular processor. Other processors execute user processes.

  • •Advantage: Resou rce conflict resolution simplified since single processor has control.
  • •Single point of failure (Master).

Peer assignment: OS executes on all processors. Each processor does its own scheduling from the pool of available processes. Most OSesimplement this in an SMP environment.

Mapping Processes to Processors

•Largely an application issue.

•Applications may be written for a particular configuration of the machine.

  • •Application create threads of computations and channel of communication between these threads assuming a particular machine configuration.

•Applications may be generic in nature

  • •Create n threads of computations. These threads can execute on machines with 1, <n, n or >n processors.
  • •OS may assign any number of processors (1 to n) to this application.

Multiprogramming at each processor

•In a multi-processor system, CPU utilization is not all that important

  • •As long as some computation is being carried out, it is fine.

•Application efficiency are more important

  • •Turn around time
  • •application-related performance metrics.

•Assigning all threads to different processors may not always yield high performance.

Multiprogramming

•A multi-threaded application may require all its threads be assigned to different processors for good performance.

  • •If there are n threads and m processors (m > n), m-nprocessors may not have any thing to execute.

•If threads are dependent on each other and require heavy synchronization, assigning all to same processor may be beneficial

•Process allocation can be Static or dynamic.

Process dispatching

•After assignment, deciding who is selected from among the pool of waiting processes

  • •process dispatching.

•Single processor multiprogramming strategies may be counter-productive here.

•Priorities and process history may not be sufficient.

Process scheduling

•Single queue of processes or if multiple priority is used, multiple priority queues, all feeding into a common pool of processors.

•Multi-server queuing model: multiple-queue/single queue, multiple server system.

  • •Inference: Specific scheduling policy does not have much effect as the number of processors increase.

•Conclusion: Use FCFS with priority levels.

Thread scheduling

•An application can be implemented as a set of threads that cooperate and execute concurrently in the same address space. •Load sharing: pool of threads, pool of processors.

Gang scheduling: Bunch of related threads scheduled together.

Dedicated processor assignment: Each program gets as many processors as there are parallel threads.

Dynamic scheduling: More like demand scheduling.

Contents

< p>•Scheduling

  • •Traditional
  • •Real time
  • •Multi-processor

•Synchronization and synchronization objects

•Inter-process communication

•Security

 

Multi-core computing: CPU Scheduling

Scheduling

•To hide the effects of I/O Bursts and achieve higher CPU utilization

•To give a fair chance to all processes

•Short term scheduling

  • •CPU scheduling

•Long term scheduling

  • •Process admission policies

•Medium term scheduling

  • •Swap management

 

CPU Scheduling

•CPU scheduler selects a process from “Ready to run”queue

  • •Scheduling decision

•Allocates CPU to this process.

  • •Dispatch
    • •Context switching

•Queue is maintained by PCB pointers

•Pre-emptive scheduling

  • •When a running process may be removed and put back in the “ready to run”queue.

 

When to have CPU scheduling

•Process moves from running state to waiting state

  • •Due to an I/O request
  • •Due to a call to wait

•Upon Process Termination

•Expiration of time quota (preemptive)

•Upon any other time when OS is called

  • •Interrupts, System Calls

Scheduling Criteria

•CPU Utilization ( System centric)

  • •Keep CPU as much busy as possible

•Throughput ( System centric)

  • •Number of processes completed/time

•Turnaround time ( Process centric)

  • •Real time taken to complete a process

•Waiting time ( Process centric)

  • •How much time a process is in ready queue

•Response time ( Process centric)

  • •Factor for an interactive process

•Deadline ( Real time behavior)

  • •Time guarantee to schedule a task.

Scheduling Algorithms

•First Come First Serve (FCFS)

  • •Simplest implementation
  • •No preemption

•Shortest Job First (SJF)

  • •Optimal scheduling algorithm
  • •Minimum Average Waiting Time
  • •Difficulty: To know the time that it will take
  • •Batch systems: A good choice.

 

Example

ProcessArrival TimeCPU BurstWait TimeTurnaround
P1 0 6 0 6
P2 4 20 2 22
P3 5 1 21 22

Example (Contd.)

ProcessArrival TimeCPU BurstWait TimeTurnaround
P1 0 6 0 6
P2 4 20 3 23
P3 5 1 1 2

SJF

•Though optimal, not practical.

  • •No way to find the CPU burst.

•Scheduling techniques try to approximate SJF

  • •Guess/predict the next burst (t n: Predicted n th burst. t n: Actual n th burst)

t n+1 = at n + (1 - a)t n 0= a =1

t n+1 = t n when a= 1

t n+1 = t n when a= 0

t n+1 = at n + (1 - a)at n-1+……+ (1 - a) jat n-j+……+(1-a) n+1t 0

•Burst guess is obtained by exponentialaveraging.

•t 0 is a system wide scheduling constant.is a system wide scheduling constant.

•a is a weight factor.

 

Example of "Guessing"

CPU Burst 6 4 7 5 9 12 12 10
Guess (t 0=10, a=0.5) 10 8 6 6 5 7 9 10

 

Preemptive SJF

•When a new task arrives, the SJF is evaluated again and rescheduling can take place.

  • •aka Shortest-remaining-time-first (SRTF) scheduling

 

Example (SRTF)

ProcessArrival TimeCPU BurstWait TimeTurnaround
P1 0 8 1 9
P2 4 20 5 25
P3 5 1 0 1

 

Adding Priority (Priority scheduling)

•Simplest form is to add priority to a process.

  • •Select the highest priority job first
  • •Apply SJF/SRTF/FIFO/…scheduling only within a group of processes with the same priority

 

Priority scheduling + SJF

ProcessCPU BurstCPU BurstPriority
P1 8 2
P2 20 1
P3 1 3
P4 5 2

 

Issues with Priority

•Priority definition.

  • •How to define a priority?
    • •System policies: Charge, job quantum, I/O
    • •External or internal definition.

•Pre-emptive vs. non-preemptive

  • •When a process arrives, should we remove the running process? (e.g. SRTF + Priority)

•Starvation

  • •When high priority jobs come at a frequency that a low priority job is blocked.
  • •Solution: add “aging”.

 

Aging with Priority

•Each time a process is scheduled, •Increase the priority of each pending task by 1. (could even be periodic) •Priority: defined at admission time only. •In pre-emptive scheduling. •When a job is pre-empted, reset the priority. •Guaranteed “No starvation”.

 

Adding Time Quantum: Round

Robin Scheduling

•FCFS + Preemption •Each time a process is scheduled, a time quantum is given to this. •When time quota expires, process is moved to ready queue. •Job is entered at the end of the queue and scheduled from the beginning of the queue. •Round robin scheduling


To be continue...

 


<end of topic>

Read other topics in Mulit-Core Curriculums

For more complete information about compiler optimizations, see our Optimization Notice.
Categories: