Planning

You need to make a planning to determine what will be the programs that are supported in the system

Types of planning

• Long term planning: Decision to add processes to set of processes to run
• Medium term planning: Decision to add processes to set of processes that are partially or fully in memory
• Short term planning: Decision on which available process/thread will be executed on the processor

Long term planning

Determines which programs are supported on the system. You must make two decisions:

• When you can create a new process
• What will be the next process to support. Combine processes with higher processor load and processes with higher I/O load

Controls the degree of multiprogramming. The more processes that are created, the lower the percentage of time each process can run

Medium term planning

Part of the function of exchange

It is based on the need to control the degree of multiprogramación

If virtual memory is not used, you should consider the memory needs of the process

Short term planning

CPU Usage Planning: Manage CPU Sharing Between Processes/Threads Ready to Run

The goal of the scheduler is to divide the processor time among the processes/threads that can run

You should consider factors such as:

• Equity: spread out the CPU usage
• Efficiency: avoid time idle CPU
• Performance: to maximize the number of requests

Planning mechanisms

The scheduler consists of three logical components:

• Queue: When a process changes to the Ready state, the gluer places it in a queue-type data structure
• Context Switch: When a process is to be evicted from the CPU, the context switch saves the contents of the CPU logs in the process BCP
• Distributor: The dealer selects one of the processes in the queue of Ready and assigns the CPU

Criteria of the planning

Criteria for comparing the performance of the various planning algorithms:

• Time of service (T_s) Estimated time of execution
• Time of return (T_r) Elapsed time from the time it arrives at the system until it ends
• Waiting time (T_w) Sum of times that the process is not running
• Return time normalized (\frac{T_r}{T_s}) Return time divided by the time of the service

Use of priorities

The planner will select always to a process of higher priority before than the lower priority

Uses multiple queues of Ready-to-represent each level of priority

Lower priority processes can be starved (never chosen)

A solution to starvation is to allow a process to change its priority based on its age or execution history

Planning policies

They rely on a selection function to determine which process, from among the Ready, is chosen to execute

The function can be based on priorities, resource needs, or process execution characteristics

There are two kinds of algorithms depending on the decision mode (instant the selection function is applied):

• No expulsion (non-appropriation or non-preferred): Once the process goes into the Execution state, it continues to run until it terminates or crashes waiting for an I/O (burst)
• With expulsion (appropriate or preferred): The process that is currently running can be interrupted and passed to the Ready by Operating System state. They allow to give a better service since they prevent a process from monopolizing the processor for a long time

Planning algorithms

Algorithms without ejection:

• FIFO (First-come First-served): First to arrive, first to be served
  • Select to run the process the more ancient of the queue of Ready
  • Easy-to-implement
  • Average waiting time very high
  • Penalizes short processes on the long-term processes
  • Favors the processes with CPU load of the processes with I/O load
  • It is often used combined with priorities
• SPN (Shortest Process Next): First, the short process
  • Selects the process with the shortest time of service
  • Difficulty in estimating the expected time of execution for each process
  • Minimizes the average waiting time
  • It penalizes those processes over the short processes
  • Possibility of starvation for long processes

Algorithms with ejection:

• Round Robin (RR)
  • Uses a time quantum that is a fraction of the time that allows each process to use the CPU
  • Ejects the process that has consumed its quantum of time and happens to occupy the last place of the queue of Ready
  • There are difficulties in choosing the size of the quant (less than 80% of CPU bursts)
  • Favors the processes with CPU load of the processes with I/O load
  • The large timeout, but ensures a CPU distribution with good response times
• FB (Feedback): Feedback multilevel
  • Divide the Ready queue into a queue hierarchy: RQ_0, \cdots, RQ_n, each with a priority level
  • Uses a time quantum, and a dynamic mechanism of priorities
  • The processes fall by RQ_0 and in each execution burst descend to the next queue
  • FIFO is used in each queue, except for the lower priority that is treated with a rotating shift
  • Favors short processes in front of the most old and long
    • Short processes will end quickly, without descending too low in the queue hierarchy
    • The long-term processes will be gradually brought down
  • There is a great number of variations of this scheme
  • To avoid starvation of long processes can be varied as a function of each queue

  Planning on POSIX

  Each planning policy has an associated range of at least 32 priority levels

  The scheduler will select the process with the highest priority

  When a process is ejected by a higher-priority process, the process becomes the first in the queue associated with its priority

  Three planning policies coexist in the planner:

  • SCHED_FIFO: It is an expulsion planning policy based on static priorities, in which processes with the same priority are served on the first come, first-served basis (FIFO queue). This policy will have at least 32 priority levels
  • SCHED_RR: This policy is very similar to SCHED_FIFO, but it uses a round-robin method to plan processes of the same priority. It also has at least 32 priority levels
  • SCHED_OTHER: It is a policy of planning defined by the implementation

  Services POSIX for process planning

  The three scheduling policies are defined in the header file

  <sched.h>

  Change the planning parameters of a process:

  int sched_setparam(pid_t pid, const struct sched_param *param);
  int sched_scheduler(pid_t pid, int policy, const struct sched_param *param);

  Obtain the planning parameters of a process:

  int sched_getparam(pid_t pid, const struct sched_param *param);
  int sched_getscheduler(pid_t pid);
  int sched_get_priority_min(int policy);
  int sched_get_priority_max(int policy);