Timer Devices and Scheduling

Timer Device and Timer Interrupt

• Relevant Sections:

  • Section 1.6.5: Timer and Timer Interrupts (Page 39)

  • Section 2.5: Schedulers, Scheduling Algorithms, Timer Interrupts (Pages 76, 77, 78)

    • Section 2.5.1: Round-Robin Scheduling

    • Section 2.5.2: Scheduling in Batch Systems

Interrupts

• Key Questions:

  • What (who) is interrupting what (who)?

  • Types of Interrupts:

  • Timer Interrupt

  • Disk Interrupt

  • Keyboard Interrupt

Timer Interrupts

• In the Nachos architecture, represented by the Alarm class and related implementation.

Timer Devices

• Functionality:

  • Interrupt CPU for services, i.e., must jump to a specific routine for task handling.

  • Handles:

  • Process context switching

  • Alarm generation

  • Accounting CPU usage

  • Other event management tasks

Importance of Timer Devices

• Timer devices are essential for:

  • CPU scheduling

  • Time management of processes and events.

CPU Interrupt Pin

• Components Involved:

  • CPU

  • Interrupt Pin specific to CPU

  • Timer Device

Scheduling Fundamentals

• Key Concepts:

  • Preemptive Scheduling

  • Allows a higher-priority process to preempt a currently running lower-priority process.

  • Non-Preemptive Scheduling

  • A running process cannot be preempted and must finish its current cycle.

  • Round-Robin Scheduling

  • Multi-Level Priority Queue

Round-Robin Scheduling Visualization

• Diagrammatic representation:

  • Example schedules showing current and next processes (Process A, B, D, F, G).

Nachos Scheduler Implementation

• Key Functions:

  • Scheduler::Scheduler:

  • Initializes a list of ready but not running threads.

  • Scheduler::~Scheduler:

  • Deallocates the list of ready threads upon destruction.

  • Scheduler::ReadyToRun:

  • Marks a thread as ready but not currently running; appends it to the ready list.

    • Code Example:
      cpp void Scheduler::ReadyToRun(Thread *thread) { DEBUG('t', "Putting thread %s on ready list.\n", thread->getName()); thread->setStatus(READY); readyList->Append((void *)thread); }

  • Scheduler::FindNextToRun:

  • Returns the next thread for scheduling; returns NULL if no ready threads available.

    • Code Example:
      cpp Thread * Scheduler::FindNextToRun () { return (Thread *)readyList->Remove(); }

• Timer Interrupt Handling:

  • Alarm::CallBack: Handles the timer device's software interrupts. Can be called periodically based on TimerTicks. This routine is called whenever there's a timer interrupt and interrupts are disabled.

  • Instead of calling Yield() directly (which would suspend the interrupt handler), a flag is set to yield once the interrupt handler completes execution. This ensures the context switch functions correctly.

    • Code Example:
      cpp void Alarm::CallBack() { Interrupt *interrupt = kernel->interrupt; MachineStatus status = interrupt->getStatus(); if (status != IdleMode) { interrupt->YieldOnReturn(); } }

Kernel Initialization

• Function:

  • Initializes various components required for scheduling, handling, and managing threads.

  • Code Example:
    cpp void Kernel::Initialize() { currentThread = new Thread("main"); currentThread->setStatus(RUNNING); stats = new Statistics(); interrupt = new Interrupt(); scheduler = new Scheduler(); alarm = new Alarm(randomSlice); machine = new Machine(debugUserProg); synchConsoleIn = new SynchConsoleInput(consoleIn); synchConsoleOut = new SynchConsoleOutput(consoleOut); synchDisk = new SynchDisk(); }

Thread Functionality Across Multiple Threads

• Example Implementation:

  • SimpleThread: Example function that demonstrates a thread's execution and yielding process.

  • Code Example:
    cpp void SimpleThread(int which) { int num; for (num = 0; num < 5; num++) { printf("*** thread %d looped %d times\n", which, num); kernel->currentThread->Yield(); } }

  • ThreadTest: Initializes threads and demonstrates forking functionality.

  • Code Example:
    cpp void ThreadTest() { Thread *t = new Thread("forked thread"); t->Fork((VoidFunctionPtr)SimpleThread, (void *)1); SimpleThread(0); }

Effects of Timer Alarm on Thread Execution

• With Timer Alarm On:

  • Threads exhibit controlled time-sharing. The outputs will demonstrate interleaved execution between multiple threads.

• With Timer Alarm Off:

  • Threads will run without interruption. The output indicates that each thread will complete its loop consecutively without yielding.

Multi-Level Priority Scheduling

• Structure Overview:

  • Hierarchy showcasing Runnable processes categorized by priority levels:

  • Priority 4 (highest)

  • Priority 3

  • Priority 2

  • Priority 1 (lowest)

• Operational Mechanism: Scheduling decisions depend on the priorities of the processes, thus ensuring that higher-priority processes get more immediate access to CPU resources.