Test Two Review

Test Two Overview

In this section, I address key details regarding Test Two, including timing, format, materials allowed, and coverage topics.

Test Dates

  • Test Dates: April 15th to April 17th.
  • Format: Online and proctored through Honor Lock. The format will mirror Test One.

Allowed Materials

  • Note Sheet: One double-sided note sheet is permitted; it can contain anything that the student feels would be useful.

Topics Covered in Test Two

This exam focuses primarily on scheduling and resource management. Unlike Test One, this is not a cumulative exam; however, foundational concepts (like blocked processes and ready processes) from prior material may be referenced.

Scheduling and Resource Management

Key Concepts
Objective of Multitasking
  • Understand the objective of multitasking discussed in previous sessions.
Scheduler Organization
  • Ready Queue: A data structure where processes that are ready to run are held.
  • Device Queue: A queue that manages processes waiting for device access.
  • Blocked Process: A process that cannot continue because it is waiting for some external event.
  • Schedulers: Different types of schedulers exist:
      - Autonomous Scheduler: Operates independently.
      - Shared Scheduler: Must share resources or CPU time.
Process States

  • Process State Transitions: Key states to know include:
      - Ready: The process is ready to run.
      - Running: The process is currently executing.
      - Blocked: The process is unable to proceed due to waiting on an event.

  • Long-term vs. Short-term Schedulers: Know the differences and specific roles in process scheduling.

Scheduling Algorithms
Desirable Features
  • There are eight desirable features of scheduling algorithms. Students should know all these terms and understand conflicts:
      - Example Conflict: Fairness vs. Efficiency
      - Example Conflict: Efficiency vs. Response Time
Types of Scheduling Algorithms
  1. First-Come, First-Served (FCFS): A non-preemptive scheduling algorithm where processes are attended in the order they arrive.
  2. Shortest Job Next (SJN): Another non-preemptive scheduling algorithm focusing on the shortest burst time.
  3. Preemptive Schedulers:
       - Shortest Remaining Time First (SRTF): preemptive version of SJN.
       - Round Robin (RR): Preemptive scheduler where each process gets a fixed time (time quantum) to execute.
       - Multi-Level Feedback Queue: Prioritizes processes based on their behavior and needs.
Performing Algorithms
  • Be prepared to calculate based on given scenarios; examples provided are crucial. For instance:
      - If given a situation with processes P0 (5 units), P1 (2 units), P2 (7 units) arriving at times 0, 1, and 2, know how to compute average wait time, particularly with FCFS and RR paradigms.
Pros and Cons of Scheduling Algorithms
  • Be prepared to discuss the advantages and disadvantages of each scheduling algorithm:
      - Example: Discuss potential process starvation in the multi-level feedback queue or exploitation of round-robin scheduling.
Linux Fair Scheduler
  • Understand the concepts of active and expired queues, and how processes are managed to ensure fairness in scheduling.
  • Knowledge of the Big-O complexity of the scheduler (i.e., O(1), denoting constant time) and the reasoning behind it is key.

Resource Management

Deadlocks

Definition and Identification
  • Deadlock: Define and understand the circumstances that can lead to deadlocks. While a strict definition may not be requested, students will need to recognize and analyze scenarios for potential deadlocks.
Deadlock Detection
  • Resource Allocation Graph: Be able to visually interpret a graph to determine system deadlocks.
  • Deadlock Detection Algorithm: Understand how to manually perform the deadlock detection algorithm, regardless of coding specifics.
  • Recognize the significance of request, allocation, and resource vectors in detection scenarios.

Deadlock Recovery Techniques

  • Familiarize with two primary recovery methods: Process Termination and Resource Preemption. Understand the implications of each method regarding system stability and resource management.
Pros and Cons of Deadlock Approaches
  • Evaluate the advantages and disadvantages of detection and recovery strategies, recognizing that while detection may be resource-efficient, it requires periodic checks to maintain system performance. Discuss why overhead concerns are minimal.
Deadlock Prevention Techniques
  • Identify deadlock conditions and articulate methods to mitigate or eliminate these conditions in a system design.
Deadlock Avoidance Techniques
  • Familiarize with the deadlock avoidance algorithm, utilizing state analysis to categorize system states as safe or unsafe. Understand key matrices:
      - Max Claim Matrix: Maximum resources claimed by each process.
      - Allocation Matrix: Currently allocated resources to processes.
      - Calculate the Need Matrix: Can be derived from Max Claim Matrix minus the Allocation Matrix.

Integration of Deadlock Strategies

  • Lastly, recognize that strategies for deadlock management and scheduling may intersect and provide avenues for a comprehensive approach to process management.

Exam Preparation Tips

  • Given that the exam has a smaller material scope than Test One but involves complex problem-solving, practice with matrices, algorithms, and scenarios ahead of the test to gain confidence.

  • Practice Problems: Engage in self-made problems to assess understanding and abilities regarding wait time calculations and algorithm performance, ensuring readiness for potential exam challenges.

  • Text Submission: For any test answers, students must write original solutions in provided text fields; copying from external resources is strictly prohibited.

Conclusion

  • Encourage students to reach out with any questions and utilize office hours effectively leading up to the exam. Prepare efficiently to maximize performance on Test Two.