Scheduling Algorithm

in the context of potentially leaving low-priority processes waiting indefinitely:

(A) Shortest-Job-First (SJF) Scheduling:

• This algorithm selects the process with the shortest expected processing time first.
• Can potentially cause starvation for long jobs, especially low-priority processes.
• If continuous short jobs keep arriving, a long job might be perpetually postponed.
• Explanation: High potential for indefinite waiting of low-priority processes.

(B) Priority Scheduling:

• Processes are assigned priorities, and the highest priority process is executed first.
• Low-priority processes can experience starvation if high-priority processes continuously arrive.
• Without aging mechanism, low-priority processes might never get CPU time.
• Explanation: High potential for indefinite waiting of low-priority processes.

(C) First-Come, First-Served (FCFS) Scheduling:

• Processes are executed in the order they arrive in the ready queue.
• Generally fair, as processes are served based on arrival time.
• Less likely to cause indefinite waiting, as all processes get a chance to execute.
• Explanation: Low potential for indefinite waiting.

(D) Round-Robin (RR) Scheduling:

• Processes are given a fixed time quantum to execute.
• After the time quantum expires, the process is moved to the back of the queue.
• Provides fair time-sharing among all processes.
• Prevents any single process from monopolizing the CPU.
• Explanation: Lowest potential for indefinite waiting.

Answer: (A) and (B) are most likely to leave low-priority processes waiting indefinitely. The key concept here is "starvation" - a situation where a process is unable to get the required resources to proceed with its execution for an extended period.

Process Scheduling:

1. Performance Parameters
2. Scheduling Algorithms
3. FCFS (First Come First Served)
4. SJF (Shortest Job First)
5. Shortest Remaining Time Next Algorithm (SRTN)
6. Priority Based Non-Preemptive Scheduling

Performance parameters for process scheduling:

1. CPU Utilization
2. Throughput of the system
3. Average Turnaround
4. Average waiting time of a process
5. Response Time

Slide 6 discusses CPU Utilization, System Throughput, and Turnaround time as part of Process Scheduling:

• CPU Utilization: It is the average fraction of time during which the CPU is busy, executing either user programs or system modules. Higher CPU utilization is better.
• System Throughput: It is the average amount of work completed per unit time.
• Turnaround time: It is the total time elapsed from the time a job is submitted (or process is created) to the time the job is completed. The formula is: Turnaround Time = Process/job finish time - process/job Arrival Time.

Slide 7 discusses Waiting Time within Process Scheduling:

• Waiting Time: It is defined as the total time spent by a job while waiting in a suspended state or ready state, in a multiprogramming environment.
• The formula is: Waiting time of job/process = Turnaround time - actual execution time.
• Lower the average waiting time, the better it is.

Slide 8 explains Response Time, Pre-emption, and Non-Pre-emption within Process Scheduling:

• Response Time: This parameter has relevance for interactive-time sharing systems and for real-time systems. In interactive systems, response time is defined as the time elapsed from the moment the last character of a command line is typed by the interactive user, to the time when the first response to that command appears on the terminal. For real-time systems, it is defined as the time elapsed from the time an event is reported in the system, to the time when the first instruction is interrupted servicing routing (IsR) is executed to service the interrupt caused by the event.
• Pre-emption: Forcefully stoppage of job.
• Non-Pre-emption: Job will leave the CPU on its own.

Slide 9 lists various Scheduling Algorithms:

1. First Come First Served (FCFS) – Non-Preemptive
2. Shortest Job First (SJF) – Non-Preemptive
3. Shortest Remaining Time Next (SRTN) – Preemptive
4. Round Robin
5. Priority
6. Multi Level Queues (MLQ) Scheduling – Non-Preemptive
7. Multi-level Feedback Queue – Preemptive

Slide 10 explains First Come First Served (FCFS) scheduling:

• First Come First Served (FCFS): The processes are dispatched (scheduled to run) strictly in the same order as those have arrived in the system.
• Example: Includes a table with Process, Arrival Time (ms), Next Burst (ms), Finish Time (FT), Turnaround Time (TAT), and Waiting Time (WT) for processes P0, P1, P2, and P3.
• Average Turnaround Time = 14.25ms
• Average Waiting Time = 8.75

Slide 11 explains Shortest Job First (SJF) scheduling:

• Shortest Job First (SJF): The next job to be dispatched will be the one which happens to be the shortest amongst the pending lot of jobs.
• Example: Includes a table with Process, Arrival Time (ms), Next Burst (ms), Finish Time (FT), Turnaround Time (TAT), and Waiting Time (WT) for processes P0, P1, P2, and P3.
• Average Turnaround Time = 12.75ms
• Average Waiting Time = 7.25ms

I am unable to draw tables. However, I can provide the data from slides 10 and 11, which you can then use to create the tables yourself.

Slide 10: FCFS Example

• Average Turnaround Time = 14.25ms
• Average Waiting Time = 8.75ms

Slide 11: SJF Example

• Average Turnaround Time = 12.75ms
• Average Waiting Time = 7.25ms

Slide 12 explains the Shortest Remaining Time Next Algorithm (SRTN):

• Shortest Remaining Time Next Algorithm (SRTN): This is a preemptive algorithm, where the next job to be dispatched will be the one that happens to be the shortest amongst the pending jobs at the time of making the decision.
• If a process arrives later whose next burst happens to be shorter than the remaining burst time of the currently running process, the currently running process will be preempted by the new process.

Slide 13 provides an example of the Shortest Remaining Time Next (SRTN) algorithm:

• Example (EX-3): Includes a table with Process, Arrival Time (ms), Next Burst (ms), Finish Time (FT), Turnaround Time (TAT), and Waiting Time (WT) for processes P1, P2, P3 and P4.
• Average Turnaround Time: - 10ms
• Average Waiting Time: - 4.5 ms

Here is the data in the table:

Slide 14 explains the Priority-Based Non-Preemptive Algorithm:

• Priority-Based Non-Preemptive Algorithm: More critical processes are assigned a priority higher than the less critical ones. At the time of scheduling, a process dispatched will be the one that has the highest priority amongst the processes waiting in the ready queue.

Slide 15 provides an example, EX-4, of Priority-Based Non-Preemptive Scheduling:

• Includes a table with Process, Arrival Time (ms), Next Burst (ms), Process Priority, Finish Time (FT), Turnaround Time (TAT), and Waiting Time (WT) for processes P1, P2, P3 and P4.
• Average TurnOver Time:- 13.25ms
• Average waiting Time:- 7.75ms

Here is the data in the table:

NOTE: WT & TAT of FCFS > SJF > SRTM Slide 16 contains information related to examples for how FCFS, SJF and SRTN scheduling algorithms work. It seems to depict scenarios or Gantt charts illustrating the execution of processes P1, P2, and P3 under these different scheduling methods. It also mentions "UGLNET". Slide 17 provides a summary of scheduling algorithms and includes additional examples:

• Lists preemptive and non-preemptive algorithms.
• Non-Preemptive: FCFS, SJF
• Preemptive: SRTN, Priority
• Examples with burst times and priorities for processes P1, P2, P3, P4, and P5 are provided, demonstrating priority scheduling methods. One seems to be Priority Non-Preemptive Method.

Slide 19 provides a 2-minute summary of scheduling algorithms, distinguishing between preemptive and non-preemptive types:

• Non-Preemptive: FCFS, SJF
• Preemptive: SRTN, Priority (presumably Priority scheduling with preemption)

Process Scheduling

1) Arrival Time

• What it is: Time when a process enters the ready queue/system.
• Key takeaway: Marks when the process becomes available for execution.
• Notation: (T_{\text{arrival}})

2) Burst Time

• What it is: Total CPU time required by a process to complete.
• What it measures: Pure processing time (no I/O waits).
• Notation: (T_{\text{burst}})
• Concept: Burst Time = Total CPU Execution Time

3) Completion Time

• What it is: Time at which a process finishes its entire execution.
• Key takeaway: Final moment of termination.
• Notation: (T_{\text{completion}})

4) Turnaround Time (TAT)

• What it is: Total time from process arrival to completion.
• Formula: [ \text{TAT} = T_{\text{completion}} - T_{\text{arrival}} ]
• Significance: Overall lifecycle measure; higher TAT means longer wait + execution.

5) Waiting Time

• What it is: Time a process spends in the ready queue awaiting CPU.
• Formula: [ W_{\text{time}} = \text{TAT} - T_{\text{burst}} ]
• Quick use: If you know arrival, burst, and completion, compute TAT first, then (W_{\text{time}}).

6) Throughput

• What it is: Number of processes completed per unit time.
• Quick rule: Higher throughput = more work done per unit time.

7) CPU Utilization

• What it is: Percentage of time the CPU is busy.
• Quick rule: Higher utilization indicates better efficiency (toward 100%).

8) Response Time

• What it is: Time from arrival to first response (not full execution).
• Quick rule: Important for interactive systems; aim to minimize.

Simple Example (to memorize the arithmetic)

• Arrival: (T_{\text{arrival}} = 0) ms
• Burst: (T_{\text{burst}} = 10) ms
• Completion: (T_{\text{completion}} = 15) ms
• [ T_{\text{TAT}} = T_{\text{completion}} - T_{\text{arrival}} = 15 - 0 = 15 \text{ ms} ]
• [ W_{\text{time}} = T_{\text{TAT}} - T_{\text{burst}} = 15 - 10 = 5 \text{ ms} ]

Performance Metrics (at a glance)

• Turnaround Time (TAT): ( \text{TAT} = T_{\text{completion}} - T_{\text{arrival}} )
• Waiting Time: ( W_{\text{time}} = \text{TAT} - T_{\text{burst}} )
• Throughput: number of processes completed per unit time
• CPU Utilization: fraction of time CPU is busy
• Response Time: time to first response after arrival

Scheduling Algorithms (Non-Preemptive, context for study)

• FCFS: First Come First Served
• SJF: Shortest Job First
• SRTN: Shortest Remaining Time Next (preemptive variant)
• Priority-Based Non-Preemptive

Quick Recall Tips

• Always start with arrival and burst: derive ( \text{TAT} = T_{\text{completion}} - T_{\text{arrival}} ), then ( W_{\text{time}} = \text{TAT} - T_{\text{burst}} ).
• For multiple processes, compute per-process values, then average for comparisons.
• Focus on minimizing idle time (increase CPU Utilization) and maximizing completed work per unit time (Throughput).

If you want, share a small sample with multiple processes (arrival times and burst times, and optionally completion times), and I’ll walk you through computing all metrics step-by-step.

Process Scheduling Terms: Interconnection

Relationship Matrix

Mathematical Relationships

Turn Around Time (TAT)

$$TAT = T_{completion} - T_{arrival}$$

Waiting Time

$$W _{time} = TAT - T_{burst}$$

Process Lifecycle Stages

1. Process Arrival
   • Enters ready queue
   • Timestamp recorded
2. Waiting Stage
   • Process queued
   • Awaiting CPU allocation
3. CPU Execution
   • Active processing
   • Burst time consumed
4. Completion
   • Task finished
   • Resources released

Performance Metrics

• Throughput: Processes completed per unit time
• CPU Utilization: Percentage of time CPU is active
• Response Time: Time from arrival to first response

Example Scenario

Arrival Time: 0 ms Burst Time: 10 ms Completion Time: 15 ms Turn Around Time: 15 - 0 = 15 ms Waiting Time: 15 - 10 = 5 ms

Key Observations

• Terms provide comprehensive process execution analysis
• Help optimize scheduling algorithms
• Enable performance measurement and improvement

Process State Diagram and Schedulers:

• LTS (Long-Term Scheduler)
• MTS (Medium-Term Scheduler)
• STS (Short-Term Scheduler)

(Reproduced from the hand-drawn note on the recap slide: Simple arrowed list.)

Process State Diagram and Schedulers ↓ LTS ↓ MTS ↓ STS

Topics for Lecture 2

• Process Scheduling: Part 1

Content Outline

1. Performance Parameter
2. Scheduling Algorithm
3. FCFS (First Come First Served)
4. SJF (Shortest Job First)
5. Shortest Remaining Time Next Algorithm (SRTN)
6. Priority Based Non-Preemptive Scheduling

(Note: The provided slides cover up to performance parameters in detail; algorithms like FCFS, SJF, etc., are listed but not expanded in the images. The PDF may have more pages with those details.)

Performance Parameters

The following are key metrics used to evaluate scheduling algorithms:

1. CPU Utilization
2. Throughput of the system
3. Average Turnaround
4. Average waiting Time of a process
5. Response Time

Detailed Explanations of Performance Parameters

1. CPU Utilization: It is the average fraction of time during which the CPU is busy, executing either user programs or system modules. Higher the CPU utilization, better it is.
   • Hand-drawn elements: Underlines on "executing either user programs or system modules" and "Higher the CPU utilization". No complex sketch here, just emphasis arrows.
2. System Throughput: It is the average amount of work completed per unit time.
   • Hand-drawn sketch reproduction: A simple note on "Amount of work done in a unit time." (No diagram, but emphasized with a wavy underline.)
3. Turnaround Time: It is the total time elapsed from the time the job is submitted (or process is created) to the time the job is completed.
   • Formula: Turnaround Time = Process/job finish time - process/job Arrival Time
   • Hand-drawn sketch reproduction: A timeline showing job submission to completion. Here's an ASCII version mimicking the horizontal arrowed line:

Amount of Work done in a unit time. Job Submit → t1 (Arrival) ----------------→ t2 (Completion) ↑ ↑ Job Arrival Job Complete

Rendering diagram…

1. Average Waiting Time: The average time a process spends waiting in the ready queue (not detailed further in the provided slides).
2. Response Time: The time from when a request is submitted until the first response is produced (not detailed further in the provided slides).

Additional Notes

• The lecture emphasizes optimizing these parameters through scheduling algorithms to improve system efficiency.
• Hand-drawn elements across slides include underlines, arrows, and simple boxes/arrows for emphasis (e.g., circling numbers or pointing to key terms like "Higher the CPU utilization").
• Homework/Revision: Likely involves revising these parameters and practicing calculations for turnaround time, throughput, etc., based on typical crash course structure.
• 2-Min Summary:
  1. Recap of process states and schedulers (LTS, MTS, STS).
  2. Introduction to performance parameters for evaluating scheduling.
  3. Detailed breakdown of CPU utilization, throughput, and turnaround time.
  4. Overview of upcoming non-preemptive algorithms (FCFS, SJF, SRTN, Priority).

This lecture builds on Lecture 1 by diving into how processes are scheduled efficiently, focusing on non-preemptive methods. Diagrams are essential for understanding timelines—refer to the reproductions above for clarity. If the PDF has additional pages beyond these slides, provide more details for further extraction.