Loading presentation...

Present Remotely

Send the link below via email or IM


Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.



No description


on 7 May 2014

Comments (0)

Please log in to add your comment.

Report abuse


Project Motivation

Scheduling is a critical part of an OS since it directly affects performance of a multitasking Operating System.
In particular, Linux and Android were chosen since they are open source and are widely used In embedded applications.


CPU vs IO Bound Process
I/O bound processes spend most of its time submitting and waiting on I/O requests.
Processor bound processes spend most of its time executing code.
The scheduling policy in Linux tends to favor explicitly I/O bound processes
Linux favors I/O bound processes to provide good interactive response and desktop performance.

Linux scheduler history
Changing Scheduling Priority
First determine the range of priority values and then the levels of priority based on min and max priorities.

Setting Linux Scheduling Policy
Processes can manipulate scheduling policy via sched_getscheduler() and sched_setscheduler()

#include <sched.h>
int sched_getscheduler (pid_t pid)
Int sched_setscheduler (pid_t pid, int policy, const struct sched_param *sp)

NOTE: “pid” is the process ID. A value of 0 refers to the invoking process’s scheduling plolicy.

Threads can manipulate scheduling as follows:

#include <pthread.h>
pthread_attr_getschedpolicy(&attr, &policy)
pthread_attr_setschedpolicy(&attr, SCHED_FIFO)

Problems in previous Scheduler
Traditional algorithm
Does not support Multiprocessor

O(1) scheduling
Supports SMP system and Processor affinity
Provides load balancing between cores or processors.
Based on Big-O Notation. It means the scheduler can work
in constant time regardless of the input.
But poor response time for interactive processes because it did
not favor I/O processes.

CMPE 180-194

Nitesh Majji 009422894
Julio Fuentes 008137844
Dibhanshi Dwivedi 009424051

Real Time

A process runs until it relinquishes control or it is preempted by a higher priority process.
A process runs until its time slice expires within its class. It can be preempted by a higher priority process.

Normal (non-real time)

This is the default scheduling class which uses the CFS scheduling algorithm.
Tasks at the same priority are round-robined.

Scheduling Priorities
A FIFO or RR classed process will always run if it is the highest priority process. It will immediately preempt a normal process.
The scheduler assigns the RR process a timeslice. When the timeslice expires, the scheduler moves it to the end of the list of processes with the same priority.

#include <sched.h>
int sched_get_priority_min (int policy);
int sched_get_priority_max (int policy) ;

Struct sched_param sp;
Int policy, max ;
policy = sched_getscheduler (pid) ;
max = sched_get_priority_max (policy);

Memset (&sp, 0, sizeof (struct sched_param)) ;
Sp.sched_priority = max ;

Other examples:
min, (max-min)/2

Precautions with Real-Time Processes
If there is no higher-priority process on the system, a CPU-bound loop will run until completion, without interruption. If the loop is infinite, the system can become unresponsive.
If a real time process busy-waits for a resource held by a lower priority process, the real time process will busy wait forever.
Special attention must be paid to real-time process and their CPU time requirements to avoid starving the system.
Red and Black Tree in CFS
Insertion and deletion operation in O(log N) where N is the number of processes.
Integrated into the Linux 2.6.23 release
Assigns a portion of CPU processing time to each task based on the nice value .
CFS records how long each task has run by managing the virtual run time variable
vruntime .
=actual running time+ decay factor where decay factor= +ve for lower priority task -ve for high priority task
IO bound task vruntime< CPU bound task vruntime

Completely Fair Scheduler (CFS)
Uses the red-black binary tree data structure to search next process to run based on the
Used by non-real time processes with the SCHED_OTHER Class
As red black tree is balanced, navigating it to discover the leftmost node will require O(logN) operations(N=number of nodes).
For better efficiency, the linux scheduler caches this value in a variable, and thus to determine which task to run next just require retrieving cached value.

Based on linux 2.6 kernel and uses CFS scheduling for normal task
Priorities of processes

Android Scheduling
Android Scheduling...
Android uses two different scheduling classes
Background class is low priority and can maximum utilize ~5% of the CPU
Foreground task has better priority and can utilize ~95% of the CPU.
We can change the priority by calling
that is part of the standard Java API and contains a value from MIN_PRIORITY(1) to MAX_PRIORITY(10).

Both Android and Linux use the Linux 2.6.23 kernel scheduling.
Real time processes always get higher priority than normal processes.
Processor affinity is critical for load balancing the scheduler and take care to of performance critical applications.
As Android is mainly used in smart phones, their priority depends mainly on whether it is a foreground process or not.
Processor Affinity
Processor affinity can be used to instruct the scheduler with processes to run on each CPU of a multi-processor system. The functions to set the processor affinity are:

#include <sched.h>
int sched_setaffinity (pid_t pid, size_t setsize, const cpu_set_t *set);
int sched_getaffinity (pid_t pid, size_t setsize, cpu_set_t *set);

The scheduler is not always able to schedule a process in favor of another because the process may be running in Kernel critical region. This may not be acceptable for a real time process deadline.
If there is more than one processor or core. One can be dedicated to real time processes.
program can be modified as follows:
Clear variable to set CPUs or cores
Get all available cores
Forbid the use of CPU or core to be used by real time processes.
Set real time process to run on dedicated CPU or core.

CPU Affinity and Real Time Processes
#include <sched.h>
typedef struct cpu_set_t;
Cpu_set_t set ;
Int ret;
Void CPU_ZERO (cpu_set_t *set) ;
Void CPU_SET (unsigned long cpu, cpu_set_t *set) ;
Void CPU_CLR (unsigned long cpu, cpu_set_t *set);

CPU_ZERO (&set) ;
/* clear variable */
ret= sched_getaffinity (0, sizeof (cpu_set_t), &set) ;
/* get allowed processors */
If (ret == -1) {perror (“sched_getaffinity error”);
return 1; }
CPU_CLR (1, &set);
/* forbid CPU #1 */
Ret = sched_setaffinity (0, sizeof (cpu_set_t), &set);
If (ret == -1) {perror (“sched_setaffinity error”);
return 1; }

---------------------------------- Code for real time process ------------------------------------------------
CPU_ZERO (&set) ;
/* clear variable */
CPU_SET (1, &set);
/* allow CPU #1 */
Ret = sched_setaffinity (0, sizeof (cpu_set_t, &set);
If (ret == -1) { perror (“sched_setaffinity”) ; return 1; }

Scheduling Classes (Policy)
Full transcript