Skip to Content

Is lottery scheduling preemptive?

By: Author Olin Wade (Remodel or Move Stuff)

Lottery scheduling is a probabilistic scheduling algorithm primarily used in operating systems to schedule processes. The key question is whether lottery scheduling allows preemption or not. In this article, we will explore lottery scheduling in detail and analyze whether it can be considered a preemptive scheduling algorithm.

What is Lottery Scheduling?

Lottery scheduling assigns each process a number of lottery tickets upon arrival. The scheduler then randomly selects tickets to determine which process runs next. Processes with more tickets have a higher chance of being selected and thus receiving CPU time. Lottery scheduling aims to provide probabilistic fairness and prevent starvation.

The key aspects of lottery scheduling are:

  • Each process is assigned a certain number of lottery tickets on arrival.
  • The scheduler randomly selects lottery tickets using a probabilistic algorithm.
  • The process holding the selected ticket gets to run on the CPU.
  • Processes with more tickets have a higher chance of selection.

Lottery scheduling is particularly useful in large-scale shared systems with multiple users. It prevents single users from monopolizing resources. It also adapts allocations based on dynamic ticket assignments.

Key Properties of Lottery Scheduling

Some key properties of lottery scheduling are:

  • Probabilistic fairness – Each process has a probability of selection proportional to its tickets. There is no deterministic guarantee of fairness.
  • Prevents starvation – Solutions like giving new processes more tickets prevent indefinite postponement.
  • Dynamic ticket allocation – Tickets can be adjusted dynamically based on factors like user priority.
  • Scalable – Lottery scheduling is suitable for large-scale parallel systems with multiple processes.

These properties make lottery scheduling particularly useful for modern shared infrastructure like public clouds. The probabilistic nature provides loose fairness guarantees while preventing starvation.

Is Lottery Scheduling Preemptive?

Preemptive scheduling allows the scheduler to forcibly preempt a currently running process based on factors like priority. A key question is whether lottery scheduling allows preemption or if processes run until completion once scheduled.

Standard lottery scheduling is generally non-preemptive. Once a process is selected from the lottery, it runs until completion or it blocks. The scheduler does not preempt the process once it starts running.

However, there are preemptive variants of lottery scheduling as well. In these variants, the scheduler continues to hold lotteries at periodic intervals. If a higher priority process wins the lottery, the scheduler can preempt the currently running process.

Examples of Preemptive Lottery Scheduling

Some examples of preemptive lottery scheduling algorithms include:

  • Stride scheduling – The scheduler holds lotteries at fixed intervals or strides. Winning tickets can preempt running processes.
  • Thread scheduling in GNU/Linux – The completely fair scheduler uses lottery scheduling with preemption.
  • Dynamic lottery scheduling – Ticket allocations change dynamically, allowing preemption based on updated priorities.

These algorithms allow preemption of running processes based on factors like priority by holding repeated lotteries. Preemption itself may have an associated cost, so the frequency of lotteries needs to be balanced.

When is Preemptive Lottery Scheduling Used?

Preemptive lottery scheduling is best suited for environments where priorities can change dynamically. For example:

  • Scheduling interactive processes where UI responsiveness is critical.
  • Real-time systems where higher priority processes arrive unpredictably.
  • Servers where workload varies dynamically over time.
  • Cloud environments where quality of service depends on priorities.

The probabilistic nature of lottery scheduling makes it suitable for such dynamic systems. Preemption further allows reallocating resources based on priority changes.

Challenges with Preemptive Lottery Scheduling

Some challenges with preemptive lottery scheduling include:

  • Preemption overhead – Context switching has an associated computational cost which increases with preemption frequency.
  • Starvation – Buggy implementations can still cause indefinite starvation of low priority processes.
  • Priority inversion – A high priority process may get blocked by a low priority lock holder.
  • Livelock – Processes can repeatedly preempt each other without progress.

These challenges can reduce performance and increase response times. Therefore, great care should be taken to optimize preemption frequency and address issues like starvation.

Conclusion

In summary:

  • Standard lottery scheduling is generally non-preemptive but preemptive variants exist.
  • Preemptive lottery scheduling introduces overhead but adapts to dynamic priorities.
  • It is best suited for environments with fluctuating workloads and priorities.
  • Implementation challenges like livelock must be addressed.

Lottery scheduling provides probabilistic fairness and dynamism. Making it preemptive adds responsiveness, but also complexity. The suitability for a specific use case needs careful analysis of the trade-offs involved. But it is a useful technique for shared, heterogeneous environments with fluctuating demands.

Example Analysis

Here is a hypothetical example to illustrate the use of preemptive lottery scheduling:

Environment

A multi-user system with 3 types of processes:

  • Interactive apps (highest priority)
  • Batch jobs (medium priority)
  • Background services (low priority)

Priorities can change dynamically as users run apps. The goal is low latency for interactive apps.

Lottery Scheduling Setup

  • Interactive apps get 100 tickets.
  • Batch jobs get 10 tickets.
  • Background services get 1 ticket.

The scheduler holds a lottery every 200ms and selects a winning ticket. The process holding that ticket preempts any lower priority running process.

Benefits

  • Interactive apps get low latency due to high ticket allocation.
  • Batch jobs make progress without starvation.
  • Background services get minimal resources as desired.
  • Priorities are adapted dynamically as users run apps.

Frequent lotteries and preemption ensure responsiveness. Priority changes are handled probabilistically avoiding starvation. The overall outcome is optimal user experience.

Potential Issues

  • Too high preemption frequency can have high overhead.
  • Bugs may still cause starvation in some cases.
  • Priority inversion must be handled.

Careful tuning and testing is required to optimize the lottery interval. Priority inheritance can address inversion. Overall this demonstrates the strengths and weaknesses of preemptive lottery scheduling.

Comparative Analysis

Here is a comparative analysis of preemptive lottery scheduling vs shortest job first scheduling:

Metric Preemptive Lottery Shortest Job First
Fairness Probabilistic Deterministic
Starvation handling Good Poor
Context switches Frequent Few
Throughput Moderate High
Responsiveness Excellent Poor
Scalability Excellent Moderate

Key observations:

  • Lottery provides good probabilistic fairness and starvations handling but lower throughput.
  • SJF has high throughput but poor responsiveness and starvation handling.
  • Lottery scheduling scales better to large systems.

Neither algorithm is ideal and the choice depends on the specific environment. But lottery scheduling provides responsiveness while preventing starvation which is desirable.

When is Non-preemptive Scheduling Preferred?

Non-preemptive lottery scheduling is preferred in environments where:

  • Priorities do not change once set.
  • Preemption overhead must be avoided.
  • Starvation prevention is not critical.
  • Predictability is important.

For example, scientific computing workloads where jobs run unchanged for long periods. The minimal preemption provides predictability and avoids overhead.

Non-preemptive scheduling may also be preferred on simpler embedded systems. The simplicity can make analysis and certification easier in safety-critical domains.

Design Choices and Tradeoffs

Some key design choices and tradeoffs with preemptive lottery scheduling include:

  • Lottery frequency – Frequent lottery draws provide responsiveness but have higher overhead.
  • Ticket allocation – Static allocations are predictable but dynamic allocations adapt better.
  • Preemption handling – Low level preemption mechanisms impact overhead and state corruption.
  • Starvation avoidance – Techniques like dynamic ticket boosting may be needed.

Hybrid policies can balance these tradeoffs. For example, having dynamic ticket allocations but performing lottery draws only occasionally. Overall, there are no silver bullet solutions and extensive analysis is required.

Sample Pseudocode

Here is some sample pseudocode to illustrate preemptive lottery scheduling logic:

// Scheduling algorithm

const TICKET_BOOST = 10; // New process boost 

function allocate_tickets(process) {
  if (process.priority == INTERACTIVE) {
    return 100
  } else if (process.priority == BATCH) { 
    return 10 
  } else if (process.priority == BACKGROUND) {
    return 1
  }
}

function lottery_scheduler() {
  
  while (true) {
    
    // Allocate tickets
    for each (process in processes) {
      process.tickets = allocate_tickets(process) 
    }
    
    // Boost new processes
    for each (new_process in new_processes) {
      new_process.tickets += TICKET_BOOST 
    }
    
    // Select winning ticket
    winner = randomly_select(processes, tickets)
    
    // Preempt if needed
    if (winner.priority > current.priority) {
      preempt(current, winner) 
      current = winner
    }
    
    // Wait some time
    wait(LOTTERY_INTERVAL) 
  }
}

// Preemption logic

function preempt(current, next) {

  if (current.state == RUNNABLE) {
    // Save context safely
    save_context(current)
    
  } else {
    // Direct switch
    current = next
    
  }

  // Switch to next process
  restore_context(next)

}

This demonstrates a simple implementation with ticket allocation, random selection, priority-based preemption, and context switching logic.

Conclusion

In summary,

  • Standard lottery scheduling is non-preemptive but preemptive variants exist.
  • Preemptive lottery scheduling provides responsiveness and adaptation to dynamic priorities.
  • It works best for environments with fluctuating workloads and changing priorities.
  • Key design choices include preemption frequency, ticket allocation, and starvation handling.
  • There are always significant tradeoffs to be analyzed for optimal results.

Lottery scheduling aims to balance fairness and throughput. Adding preemption capabilities enhances it to handle environments with changing priorities and guarantees. It provides probabilistic fairness, responsiveness, and starvation prevention in heterogeneous workloads.