cpu-scheduling presentation for IT/CS.pptx

cpu-scheduling presentation for IT/CS

1. CPU SCHEDULING REPORT BY:ELFIE LAMPINAQUE DEXTERJAMES DEGAYO

2. BASIC CONCEPTS 1 SCHEDULING CRITERIA 2 SCHEDULING ALGORITHMS (FCFS, SJF, PRIORITY, ROUND ROBIN, ETC.) 3 MULTILEVEL QUEUE SCHEDULING 4 TABLE OF CONTENT

3. BASIC CONCEPTS CPU SCHEDULING IS A FUNDAMENTAL CONCEPT IN OPERATING SYSTEMS THAT DETERMINES WHICH PROCESS GETS TO USE THE CPU WHEN MULTIPLE PROCESSES ARE READY TO EXECUTE. THE STRUCTURE OF CPU SCHEDULING INCLUDES VARIOUS COMPONENTS AND SCHEDULING ALGORITHMS.

4. CPU SCHEDULING COMPONENTS 1.PROCESS STATES: >New → Ready → Running → Waiting → Terminated >The CPU scheduler selects processes from the Ready Queue for execution. 2.Process Control Block (PCB): >Stores process attributes like Process ID (PID), CPU registers, priority, program counter, etc.

5. 3.QUEUES USED IN SCHEDULING: >Job Queue: Contains all processes in the system. >Ready Queue: Contains processes ready to execute. >Waiting Queue: Contains processes waiting for I/O operations. 4.CPU Scheduler >Selects a process from the Ready Queue and assigns it to the CPU. 5.Dispatcher: Loads the selected process from the ready queue into the CPU for execution. Performs context switching and switching to user mode. CPU SCHEDULING COMPONENTS

6. TYPES OF CPU SCHEDULING ALGORITHMS CPU SCHEDULING CAN BE DIVIDED INTO PREEMPTIVE AND NON-PREEMPTIVE APPROACHES. A. Non-Preemptive Scheduling Algorithms 1.First Come First Serve (FCFS): >Processes are scheduled in the order they arrive. >Simple but can cause convoy effect (slow process delays faster ones). 2.Shortest Job Next (SJN) / Shortest Job First (SJF): >Process with the smallest burst time is selected first. >Optimal in minimizing waiting time but suffers from starvation (longer processes may never execute).

7. TYPES OF CPU SCHEDULING ALGORITHMS 3.PRIORITY SCHEDULING: Process with the highest priority is scheduled first. Starvation can occur if low-priority processes never get CPU time. B. PREEMPTIVE SCHEDULING ALGORITHMS ROUND ROBIN (RR): EACH PROCESS GETS A FIXED TIME QUANTUM BEFORE SWITCHING TO THE NEXT. REDUCES STARVATION BUT INCREASES CONTEXT SWITCHING OVERHEAD. 2.SHORTEST REMAINING TIME FIRST (SRTF): PREEMPTIVE VERSION OF SJF; A NEW PROCESS WITH A SMALLER BURST TIME CAN PREEMPT THE RUNNING PROCESS.

8. TYPES OF CPU SCHEDULING ALGORITHMS 3.PRIORITY SCHEDULING (PREEMPTIVE): The CPU is assigned to the highest-priority process, preempting lower-priority ones. 3.Multilevel Queue Scheduling: Divides processes into multiple queues based on priority (e.g., system, interactive, batch). 4.Multilevel Feedback Queue: Processes move between queues based on their behavior (e.g., interactive processes get higher priority).

9. TO EVALUATE CPU SCHEDULING ALGORITHMS, WE USE: Turnaround Time (TAT) = Completion Time - Arrival Time Waiting Time (WT) = Turnaround Time - Burst Time Response Time (RT) = First Response Time - Arrival Time Throughput = Number of processes executed per unit time CPU Utilization = Percentage of CPU time utilized PERFORMANCE METRICS

10. CPU SCHEDULING IN MULTIPROCESSOR SYSTEMS SYMMETRIC MULTIPROCESSING (SMP): EACH PROCESSOR HAS ITS OWN SCHEDULER. Asymmetric Multiprocessing (AMP): One processor handles scheduling for all others.

11. 2. SCHEDULING CRITERIA

12. SCHEDULING CRITERIA THE SCHEDULING CRITERIA STRUCTURE REFERS TO THE FACTORS USED TO EVALUATE AND PRIORITIZE PROCESSES IN A SCHEDULING ALGORITHM. THESE CRITERIA DETERMINE THE EFFICIENCY AND EFFECTIVENESS OF A SCHEDULING SYSTEM, ESPECIALLY IN OPERATING SYSTEMS AND TASK SCHEDULING.

13. COMMON SCHEDULING CRITERIA: >CPU UTILIZATION – THE PERCENTAGE OF TIME THE CPU IS ACTIVELY EXECUTING PROCESSES. A GOOD SCHEDULER MAXIMIZES CPU USAGE. >THROUGHPUT – THE NUMBER OF PROCESSES COMPLETED PER UNIT OF TIME. HIGHER THROUGHPUT MEANS BETTER PERFORMANCE.

14. COMMON SCHEDULING CRITERIA: TURNAROUND TIME – THE TOTAL TIME TAKEN FROM PROCESS SUBMISSION TO COMPLETION, INCLUDING EXECUTION AND WAITING TIME. THE GOAL IS TO MINIMIZE TURNAROUND TIME. WAITING TIME – THE TOTAL TIME A PROCESS SPENDS WAITING IN THE READY QUEUE BEFORE EXECUTION. LOWER WAITING TIME IMPROVES SYSTEM RESPONSIVENESS.

15. RESPONSE TIME – THE TIME BETWEEN SUBMITTING A REQUEST AND THE FIRST RESPONSE (NOT COMPLETION). CRITICAL FOR INTERACTIVE SYSTEMS. FAIRNESS – ENSURING ALL PROCESSES GET A FAIR SHARE OF CPU TIME WITHOUT STARVATION.

16. DEADLINE ADHERENCE – IMPORTANT FOR REAL-TIME SYSTEMS WHERE TASKS MUST MEET STRICT DEADLINES. PRIORITY HANDLING – IF A PRIORITY-BASED SCHEDULING ALGORITHM IS USED, IT ENSURES HIGH-PRIORITY TASKS EXECUTE SOONER.

17. SCHEDULING ALGORITHMS (FCFS, SJF, PRIORITY, ROUND ROBIN

18. 1. FIRST COME FIRST SERVE (FCFS) DESCRIPTION: THE PROCESS THAT ARRIVES FIRST IS EXECUTED FIRST. TYPE: NON-PREEMPTIVE ADVANTAGES: SIMPLE AND EASY TO IMPLEMENT. DISADVANTAGES: CAUSES CONVOY EFFECT (LONG PROCESSES DELAY SHORTER ONES).

19. 3. PRIORITY SCHEDULING DESCRIPTION: PROCESSES ARE EXECUTED BASED ON PRIORITY (LOWER VALUE = HIGHER PRIORITY). TYPE: CAN BE PREEMPTIVE OR NON-PREEMPTIVE. ADVANTAGES: IMPORTANT TASKS GET EXECUTED FIRST. DISADVANTAGES: MAY CAUSE STARVATION (LOW-PRIORITY PROCESSES MAY NEVER EXECUTE). AGING CAN BE USED TO PREVENT THIS.

20. 2.SHORTEST JOB FIRST (SJF) DESCRIPTION: THE PROCESS WITH THE SHORTEST BURST TIME IS EXECUTED FIRST. TYPE: CAN BE PREEMPTIVE (SHORTEST REMAINING TIME FIRST - SRTF) OR NON-PREEMPTIVE. ADVANTAGES: MINIMIZES AVERAGE WAITING TIME. DISADVANTAGES: MAY CAUSE STARVATION FOR LONG PROCESSES

21. SCHEDULING ALGORITHMS ARE USED BY OPERATING SYSTEMS TO DETERMINE THE ORDER IN WHICH PROCESSES EXECUTE IN A CPU. THE GOAL IS TO OPTIMIZE CPU UTILIZATION, RESPONSE TIME, AND THROUGHPUT WHILE MINIMIZING WAITING TIME AND TURNAROUND TIME. SCHEDULING ALGORITHMS (FCFS, SJF, PRIORITY, ROUND ROBIN

22. 1. FIRST-COME, FIRST-SERVED (FCFS) SCHEDULING ✅ TYPE: NON-PREEMPTIVE ✅ SELECTION CRITERIA: PROCESSES ARE EXECUTED IN THE ORDER THEY ARRIVE. ✅ STRUCTURE: MAINTAIN A QUEUE (FIFO – FIRST IN, FIRST OUT). THE FIRST PROCESS IN THE QUEUE GETS CPU TIME UNTIL COMPLETION. NO SWITCHING UNTIL THE PROCESS COMPLETES.

23. ✅ ADVANTAGES: ✔ SIMPLE TO IMPLEMENT ✔ NO STARVATION ✅ DISADVANTAGES: ✖ HIGH WAITING TIME IF A LONG PROCESS COMES FIRST (CONVOY EFFECT) ✖ NOT SUITABLE FOR TIME-SHARING SYSTEMS

24. 2. SHORTEST JOB FIRST (SJF) SCHEDULING ✅ TYPE: CAN BE PREEMPTIVE (SHORTEST REMAINING TIME FIRST - SRTF) OR NON-PREEMPTIVE ✅ SELECTION CRITERIA: THE PROCESS WITH THE SHORTEST BURST TIME EXECUTES FIRST. ✅ STRUCTURE: SORT ALL PROCESSES BASED ON BURST TIME. THE PROCESS WITH THE LOWEST BURST TIME GETS CPU FIRST. IN PREEMPTIVE SJF (SRTF), IF A NEW PROCESS ARRIVES WITH A SHORTER BURST TIME, IT INTERRUPTS THE CURRENT PROCESS.

25. ✅ ADVANTAGES: ✔ MINIMIZES WAITING TIME AND TURNAROUND TIME ✔ EFFICIENT FOR BATCH PROCESSING ✅ DISADVANTAGES: ✖ REQUIRES KNOWING BURST TIME IN ADVANCE ✖ CAN LEAD TO STARVATION OF LONGER PROCESSES

26. 3. PRIORITY SCHEDULING ✅ TYPE: CAN BE PREEMPTIVE OR NON-PREEMPTIVE ✅ SELECTION CRITERIA: EACH PROCESS HAS A PRIORITY NUMBER; THE LOWER THE NUMBER, THE HIGHER THE PRIORITY. ✅ STRUCTURE: SORT PROCESSES BASED ON PRIORITY. THE HIGHEST-PRIORITY PROCESS EXECUTES FIRST. IN PREEMPTIVE PRIORITY SCHEDULING, A NEW HIGH-PRIORITY PROCESS INTERRUPTS THE RUNNING PROCESS.

27. ✅ ADVANTAGES: ✔ USEFUL FOR REAL-TIME SYSTEMS ✔ ENSURES URGENT TASKS GET CPU FIRST ✅ DISADVANTAGES: ✖ LOW-PRIORITY PROCESSES MAY STARVE (STARVATION PROBLEM) ✖ REQUIRES A MECHANISM (AGING) TO PREVENT STARVATION

28. 4. ROUND ROBIN (RR) SCHEDULING ✅ TYPE: PREEMPTIVE ✅ SELECTION CRITERIA: EACH PROCESS GETS A FIXED TIME SLICE (QUANTUM). ✅ STRUCTURE: EACH PROCESS IS GIVEN A TIME SLICE (E.G., 4MS). AFTER ITS TIME SLICE, THE PROCESS IS MOVED TO THE BACK OF THE QUEUE IF IT HASN’T FINISHED. THE CPU KEEPS SWITCHING BETWEEN PROCESSES IN A CYCLIC MANNER.

29. ✅ ADVANTAGES: ✔ FAIR FOR ALL PROCESSES ✔ GOOD FOR TIME-SHARING SYSTEMS ✅ DISADVANTAGES: ✖ CONTEXT SWITCHING OVERHEAD ✖ HIGHER TURNAROUND TIME FOR LONG PROCESSES IF THE QUANTUM IS TOO SMALL

30. MULTILEVEL QUEUE SCHEDULING

31. WHAT IS MULTILEVEL QUEUE SCHEDULING MULTILEVEL QUEUE (MLQ) SCHEDULING IS A CPU SCHEDULING ALGORITHM THAT DIVIDES PROCESSES INTO MULTIPLE QUEUES BASED ON THEIR CHARACTERISTICS (E.G., PRIORITY, PROCESS TYPE, OR MEMORY REQUIREMENTS). EACH QUEUE HAS ITS OWN SCHEDULING ALGORITHM, AND PROCESSES DO NOT MOVE BETWEEN QUEUES.

32. STRUCTURE OF MULTILEVEL QUEUE SCHEDULING ✅ KEY FEATURES: DIVIDES THE READY QUEUE INTO MULTIPLE QUEUES. EACH QUEUE HAS ITS OWN SCHEDULING ALGORITHM (E.G., FCFS, SJF, RR). A SCHEDULING POLICY DETERMINES HOW CPU TIME IS ALLOCATED BETWEEN QUEUES. ✅ TYPES OF SCHEDULING BETWEEN QUEUES: FIXED PRIORITY SCHEDULING: HIGHER-PRIORITY QUEUES ALWAYS EXECUTE FIRST. TIME-SLICE SCHEDULING: CPU TIME IS DIVIDED AMONG QUEUES.

33. TYPICAL QUEUES IN MLQ SCHEDULING

34. ADVANTAGES & DISADVANTAGES ✅ ADVANTAGES: ✔ PRIORITIZES CRITICAL TASKS (SYSTEM AND INTERACTIVE PROCESSES). ✔ EFFICIENT USE OF CPU BY ALLOCATING DIFFERENT SCHEDULING ALGORITHMS. ✔ GOOD FOR SYSTEMS WITH DIVERSE WORKLOAD TYPES. ❌ DISADVANTAGES: ✖ STARVATION CAN OCCUR IF LOWER-PRIORITY QUEUES GET LITTLE CPU TIME. ✖ PROCESSES ARE STUCK IN THEIR QUEUES (NO MOVEMENT BETWEEN QUEUES). ✖ COMPLEX TO IMPLEMENT.

35. WHEN TO USE MULTILEVEL QUEUE SCHEDULING? OPERATING SYSTEMS: SEPARATING SYSTEM PROCESSES, USER APPLICATIONS, AND BACKGROUND TASKS. CLOUD COMPUTING: ASSIGNING PRIORITY TO DIFFERENT WORKLOADS (REAL-TIME PROCESSING VS. BATCH JOBS). MULTIMEDIA SYSTEMS: GIVING REAL-TIME VIDEO/AUDIO PROCESSING HIGHER PRIORITY THAN BACKGROUND TASKS.

36. THANK YOU