Process Planning and Scheduling in Operating Systems

Process Planning

Objectives

• Justice: Avoid favoring some processes over others.
• Maximum Number of Interactive Users: Focus on most time-sharing systems.
• Predictability: The strategy must enable the execution of processes.
• Minimizing Overhead: Minimize context switches.
• Balance in the Use of Resources: Resources must be used fairly and for as long as possible.
• Safety Priorities: Established priorities should be respected.
• Maximum Capacity of Execution: Minimize process changes.

Criteria

• Response Time: Speed with which the system responds to a request.
• Service Time: Response time minus time for I/O.
• Runtime: Service time minus timeout.
• Processor Time: Processor time occupation.
• Timeout: Waiting times in queues.
• Efficiency: Processor utilization.
• Yield: Number of jobs per unit time.

Metrics

• ti = Time of Executive Order
• t = Time of Execution
• tf = Time of End of Implementation
• T = Time of Service = tf - ti
• E = Wait Time = T - t
• I = Index Service = t / T

Policies

• Appropriate: Produce a process change with every change of context (Time Sharing, Real Time, etc.).
• Non-Appropriation: The processes are executed until their end (Batch Processing).
• FIFO (First In, First Out)
• SJN (Shortest Job Next)
• LIFO (Last In, First Out)
• LJN (Longest Job Next)
• RR (Round Robin)
• SRT (Shortest Remaining Time)
• Priority
• Multiple Queues

First In, First Out (FIFO)

• Also known as FCFS (First Come, First Served)
• It is a non-preemptive policy
• It is very predictable
• The index of the longer service improves the processes
• It does not have a very good performance

Shortest Job Next (SJN)

• It is a non-preemptive policy
• It is very predictable
• The service index is good for short processes
• It requires more information than other policies to decide on the next process to run (heuristic)

Last In, First Out (LIFO)

• Also known as LCFS (Last Come, First Served)
• It is a non-preemptive policy
• It is very predictable
• The index of the shorter service improves the processes
• It does not have a very good performance

Longest Job Next (LJN)

• It is a non-preemptive policy
• It is very predictable
• The service index is good for long processes
• It requires more information than other policies to decide on the next process to run (heuristic)

Round Robin (RR)

• Also known as cyclic allocation
• It is an appropriate policy
• It is unpredictable
• The index of service depends on the quantum (q), which is usually a value between 5 and 90 milliseconds
• RR tries to keep the index of service of short processes constant

Priorities

• Static: The value does not change during the lifetime of the process.
• Dynamic: The value may change during the lifetime of the process.
• Internal: The value depends on some characteristic of the process.
• External: The value depends on a property outside the process.

Interruptions

An interruption is an event that alters the sequence in which the processor executes instructions. The interruption is generated by the system hardware.

Interruptions Handling

1. Hardware passes control to the operating system.
2. The operating system saves the state of the interrupted process.
3. The operating system analyzes the interruption and transfers control to the appropriate routine.
4. The routine processes the interrupt.
5. The state of the process is restored, or the next process is executed.

Types of Interruptions

• Supervisor Calls (SVC): User requests to I/O.
• I/O: Started by hardware and I/O, such as a change of state (ready).
• External: Expiration of terms, interruption of another processor.
• Restart
• Program Verification: Division by zero, overflow of numbers, format error, invalid code.
• Machine Check