CPU Scheduling Concepts Quiz
45 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

In the exponential averaging formula for predicting CPU burst length, what does the parameter α represent?

  • The length of the previous CPU burst.
  • The length of the most recent CPU burst.
  • The weight given to the past history.
  • The relative weight of recent and past history. (correct)

    • If α = 1 in the exponential averaging formula, then only the most recent CPU burst matters when predicting the next CPU burst length.

    True (A)

    What is another name for preemptive SJF scheduling?

    shortest-remaining-time-first scheduling

    When using exponential averaging, if $\alpha = 0$, then $\tau_{n+1}$ = ____.

    <p>$\tau_n$</p> Signup and view all the answers

    Match the value of alpha (α) with its effect on the prediction of the next CPU burst using exponential averaging:

    <p>α = 0 = Recent history has no effect on the predicted value. α = 1 = Only the most recent CPU burst matters in the prediction. α = 1/2 = Recent and past history are equally weighted. 0 &lt; α &lt; 1 = Each successive term has less weight than its predecessor.</p> Signup and view all the answers

    What type of context switch occurs when a process blocks for I/O?

    <p>Voluntary context switch (B)</p> Signup and view all the answers

    A nonvoluntary context switch happens when a process completes its time slice.

    <p>True (A)</p> Signup and view all the answers

    What is the conceptual range for CPU utilization?

    <p>0 to 100 percent</p> Signup and view all the answers

    The time it takes for a process from submission to completion is known as the ______ time.

    <p>turnaround</p> Signup and view all the answers

    Which of these is NOT directly affected by a CPU-scheduling algorithm?

    <p>Time spent executing on the CPU (B)</p> Signup and view all the answers

    Throughput is measured in the number of processes completed per second and so it is only applicable to short transactions.

    <p>False (B)</p> Signup and view all the answers

    What is the term for the amount of time a process spends waiting in the ready queue?

    <p>waiting time</p> Signup and view all the answers

    Match the scheduling criteria with their definitions:

    <p>CPU utilization = The percentage of time the CPU is busy. Throughput = The number of processes completed per time unit. Turnaround time = The time from submission to completion of a process. Waiting time = The time a process spends in the ready queue.</p> Signup and view all the answers

    What happens if a process's CPU burst is longer than one time quantum in Round Robin scheduling?

    <p>The process is preempted and moved to the end of the ready queue. (C)</p> Signup and view all the answers

    Round Robin scheduling is a non-preemptive algorithm.

    <p>False (B)</p> Signup and view all the answers

    In Round Robin scheduling, if there are 'n' processes in the ready queue and the time quantum is 'q', how much CPU time does each process get?

    <p>1/n of the CPU time in chunks of at most q time units.</p> Signup and view all the answers

    A _______ switch occurs when a process is preempted in Round Robin scheduling.

    <p>context</p> Signup and view all the answers

    Consider three processes P1, P2, and P3 with burst times 24, 3, and 3 milliseconds respectively. If the time quantum is 4 milliseconds, what is the waiting time of process P1?

    <p>6 milliseconds (B)</p> Signup and view all the answers

    Match the following terms with their description:

    <p>Time Quantum = Duration for which a process can run before being preempted Preemptive Scheduling = A process can be interrupted before its completion Ready Queue = A queue of processes ready to execute Context Switch = Saving the state of one process and loading the state of another</p> Signup and view all the answers

    In a Round Robin scheduling algorithm, if a process has a CPU burst equal to the time quantum, what happens when the time quantum expires?

    <p>The process is preempted and moved to the back of the ready queue. (C)</p> Signup and view all the answers

    In round robin scheduling, what happens after a running process’s time quantum has expired?

    <p>A context switch occurs where the current running process is moved to the tail of the ready queue and the next process in the queue gets to run.</p> Signup and view all the answers

    What does the PTHREAD_SCOPE_SYSTEM scheduling policy do on many-to-many systems?

    <p>It creates a dedicated LWP for each user-level thread. (A)</p> Signup and view all the answers

    The function pthread_attr_setscope() is used to retrieve the current contention scope.

    <p>False (B)</p> Signup and view all the answers

    What are the two possible values that can be passed to pthread_attr_setscope() to set the contention scope?

    <p><code>PTHREAD_SCOPE_SYSTEM</code> and <code>PTHREAD_SCOPE_PROCESS</code></p> Signup and view all the answers

    The pthread_attr_getscope() function receives a pointer to an ______ value that is set to the current value of the contention scope.

    <p>int</p> Signup and view all the answers

    Match the following functions with their primary actions:

    <p>pthread_attr_setscope = Sets the contention scope policy pthread_attr_getscope = Retrieves the contention scope policy pthread_attr_init = Initializes a thread attribute object pthread_create = Creates a new thread</p> Signup and view all the answers

    In the provided code example, what contention scope is set for the threads?

    <p><code>PTHREAD_SCOPE_SYSTEM</code> (B)</p> Signup and view all the answers

    The code example initializes a thread, sets the scope to PTHREAD_SCOPE_SYSTEM, and then creates five threads, effectively setting all 5 threads to this specified scope.

    <p>True (A)</p> Signup and view all the answers

    What does the code in Figure 5.10 do after retrieving the existing scope?

    <p>It sets the scope to <code>PTHREAD_SCOPE_SYSTEM</code>.</p> Signup and view all the answers

    What is a primary consideration when sharing resources within a physical core?

    <p>The resources, such as caches and pipelines, must be shared among hardware threads. (A)</p> Signup and view all the answers

    A multithreaded, multicore processor requires only one level of scheduling.

    <p>False (B)</p> Signup and view all the answers

    What is the primary focus of the first level of scheduling in a multithreaded, multicore processor?

    <p>Choosing which software thread to run on each hardware thread.</p> Signup and view all the answers

    At the second level of scheduling, a simple ______ algorithm can be used to schedule hardware threads to the processing core.

    <p>round-robin</p> Signup and view all the answers

    How does the Intel Itanium prioritize hardware threads for execution?

    <p>Based on a dynamically assigned urgency value. (B)</p> Signup and view all the answers

    The two different levels of scheduling in a multithreaded, multicore processor are mutually exclusive.

    <p>False (B)</p> Signup and view all the answers

    According to Figure 5.15, what are the two levels of scheduling for a dual-threaded core? Answer with a comma-separated list.

    <p>software threads, hardware threads</p> Signup and view all the answers

    Match the following scheduling levels with the appropriate action:

    <p>Level 1 Scheduling = Chooses software thread to run on each hardware thread Level 2 Scheduling = Core decides which hardware thread to run Operating System Scheduler = May choose any scheduling algorithm Itanium Thread Selection = Uses a dynamic urgency value</p> Signup and view all the answers

    In rate-monotonic scheduling, what determines the priority of a process?

    <p>The period of the process (A)</p> Signup and view all the answers

    Rate-monotonic scheduling always guarantees that all processes will meet their deadlines.

    <p>False (B)</p> Signup and view all the answers

    What is the worst-case CPU utilization for rate-monotonic scheduling with an infinite number of processes?

    <p>approximately 69 percent</p> Signup and view all the answers

    With rate-monotonic scheduling, if a process has a shorter period, it is assigned a ______ priority.

    <p>higher</p> Signup and view all the answers

    If two processes have a combined CPU utilization of 75%, what can be said about their schedulability using rate-monotonic scheduling?

    <p>They are guaranteed to meet their deadlines (D)</p> Signup and view all the answers

    Rate-monotonic scheduling is able to maximize CPU resources fully.

    <p>False (B)</p> Signup and view all the answers

    Match the following terms with their description in the context of rate-monotonic scheduling:

    <p>Period = The interval between process invocations CPU Utilization = The percentage of CPU time spent executing processes Deadline = The point in time when a process must complete its execution</p> Signup and view all the answers

    What is the bounded CPU utilization for two processes using rate-monotonic scheduling?

    <p>Approximately 83 percent (A)</p> Signup and view all the answers

    Study Notes

    CPU Scheduling

    • CPU scheduling is fundamental to multiprogrammed operating systems, allowing the system to switch between processes and increase productivity.
    • Modern operating systems schedule kernel-level threads instead of processes; the terms are often used interchangeably.
    • A core is the basic computational unit of a CPU, and processes execute on CPU cores.

    Chapter Objectives

    • Describe various CPU scheduling algorithms.
    • Assess CPU scheduling algorithms based on criteria such as CPU utilization, throughput, turnaround time, waiting time, and response time.
    • Explain issues related to multiprocessor and multicore scheduling.
    • Explain various real-time scheduling algorithms.
    • Describe the scheduling algorithms of Windows, Linux, and Solaris.
    • Demonstrate modeling/simulation to evaluate CPU scheduling algorithms.
    • Design a program to implement different CPU scheduling algorithms.

    Basic Concepts

    • In a system with a single CPU core, only one process can run at a time, others wait until the CPU is free, and get rescheduled.
    • Multiprogramming aims to keep the CPU busy by alternating processes.
    • CPU burst is when the process is being executed by the CPU.
    • I/O burst is when the process is waiting to perform I/O.
    • Processes alternate between CPU bursts and I/O bursts.

    CPU-I/O Burst Cycle

    • Process execution alternates between CPU execution and I/O wait.
    • CPU burst durations typically vary widely, with many short bursts and fewer long bursts.

    CPU Scheduler

    • The CPU scheduler selects a process from the ready queue to execute.
    • The ready queue can be implemented as a FIFO queue, priority queue, or a tree, or a similar structure.

    Scheduling Criteria

    • CPU utilization: Keeping the CPU busy as much as possible (0-100%).
    • Throughput: Number of processes completed per time unit.
    • Turnaround time: Time from submission to completion for a particular process, including waiting in the ready queue, CPU execution, and I/O.
    • Waiting time: Sum of periods spent waiting in the ready queue.
    • Response time: Time from submission to first response for interactive systems.

    Scheduling Algorithms

    • First-Come, First-Served (FCFS): Processes are executed in the order they arrive. It can result in significant waiting times if longer processes arrive early.
    • Shortest Job First (SJF): Processes with shortest next CPU burst are scheduled first. It minimizes average waiting time, but predicting the next CPU burst is challenging (Optimal algorithm if CPU burst values were known).
    • Round Robin (RR): Each process gets a small time quantum (e.g., 10-100 milliseconds). If a process's burst is longer than the time quantum, it's preempted and moved to the tail of the ready queue.
    • Priority Scheduling: Processes are assigned priorities with higher-priority processes being served first. If multiple processes have the same priority an algorithm like FCFS is used, can cause indefinite blocking/starvation for low-priority processes.
    • Multilevel Queue Scheduling: Processes are sorted into different queues based on priority (or other criteria) with different scheduling algorithms applied to each queue.
    • Multilevel Feedback Queue Scheduling: Processes can move between queues based on their behavior (e.g., high CPU burst).

    Multiprocessor Scheduling

    • Multiprocessor systems support multiple physical or multiple cores on a chip.
    • Load balancing is crucial to utilize multiple processors efficiently. Load balancing strategies include pull and push.
    • Processor affinity is the tendency of a thread to run on the same processor to take advantage of a warm cache.

    Real-Time CPU Scheduling

    • Soft real-time systems provide no guarantees about completing tasks by deadlines.
    • Hard real-time systems require strict deadline adherence for critical operations.
    • Event latency (the time between an event and its service) is crucial in real-time systems.
    • Interrupt and dispatch latency impact real-time system performance.

    Priority-Based Scheduling

    • Priorities are associated with processes, and higher-priority processes are given preference in scheduling.
    • Indefinite blocking/starvation can be a problem when low-priority processes wait indefinitely.
    • Aging is a technique to gradually increase the priority of processes waiting for a long time, preventing starvation.

    Thread Scheduling

    • Scheduling in multi-threaded systems can involve user-level or kernel threads
    • Some systems offer process contention scope (PCS) in which a thread only competes with other processes' threads
    • System contention scope (SCS) means a thread competes against other threads of the entire system
    • Pthread API can be used to set/get contention scope

    Evaluating Scheduling Algorithms

    • Deterministic modeling: Evaluating algorithms under a specific workload, offering exact values for comparison.

    • Queueing models: Modeling systems with fluctuating workloads. Evaluating average waiting times, utilizing mathematical formulas and probability distributions

    • Simulations: Simulating a complete system to evaluate how algorithms perform under realistic scenarios

    Studying That Suits You

    Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

    Quiz Team

    Related Documents

    Operating System Concepts - CPU Scheduling PDF

    Description

    Test your knowledge on CPU scheduling algorithms, including exponential averaging and preemptive SJF scheduling. This quiz covers key concepts such as CPU burst prediction, types of context switches, and CPU utilization. Challenge yourself with various questions related to CPU scheduling techniques.

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser