Loading learning content...
When multiple jobs compete for the same device, scheduling determines which runs first. This seemingly simple decision has profound implications for user experience, system throughput, fairness, and resource utilization.
Job scheduling in spooling systems shares concepts with CPU scheduling but has unique characteristics: jobs are typically non-preemptible (you can't pause a print halfway), job durations are often estimable, and priority requirements vary significantly between environments.
This page covers scheduling algorithms (FIFO, priority, fair share), priority management strategies, handling multiple queues and device pools, deadline scheduling, and optimization techniques. You'll understand how to configure and tune spooling systems for various workloads.
Before examining algorithms, we must understand what we're optimizing for. Different environments prioritize different objectives—often conflicting ones.
Primary Objectives:
The Fundamental Tradeoffs:
| Objective | Helps | Hurts | Best When |
|---|---|---|---|
| Strict priority | Urgent jobs | Low-priority wait time | Clear importance hierarchy |
| FIFO | Predictability, fairness | Urgent job response | Similar job sizes |
| Shortest job first | Average response time | Long job starvation | Variable job sizes |
| Round robin | Interactive response | Throughput (overhead) | Time-sharing needed |
| Fair share | User equity | Throughput, priority | Multi-tenant systems |
Unlike CPU scheduling, print jobs are typically non-preemptive. Once a job starts printing, it runs to completion—you can't pause mid-page to service a higher-priority job. This means scheduling decisions are made only when a device becomes free, making the initial ordering crucial.
First-In-First-Out (FIFO) is the simplest and most intuitive scheduling algorithm. Jobs are processed in the order they were submitted.
Advantages:
Disadvantages:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
/* Simple FIFO Scheduler Implementation */#include <stdio.h>#include <stdlib.h>#include <pthread.h> typedef struct job { int id; char *owner; size_t size; time_t submit_time; struct job *next;} job_t; typedef struct { job_t *head; job_t *tail; int count; pthread_mutex_t lock; pthread_cond_t not_empty;} fifo_queue_t; /* Add job to end of queue */void enqueue(fifo_queue_t *q, job_t *job) { pthread_mutex_lock(&q->lock); job->next = NULL; if (q->tail) { q->tail->next = job; } else { q->head = job; } q->tail = job; q->count++; pthread_cond_signal(&q->not_empty); pthread_mutex_unlock(&q->lock);} /* Remove and return job from front of queue */job_t *dequeue(fifo_queue_t *q) { pthread_mutex_lock(&q->lock); while (q->head == NULL) { pthread_cond_wait(&q->not_empty, &q->lock); } job_t *job = q->head; q->head = job->next; if (q->head == NULL) { q->tail = NULL; } q->count--; pthread_mutex_unlock(&q->lock); return job;} /* Estimate wait time for new job */int estimate_wait(fifo_queue_t *q, size_t bytes_per_sec) { pthread_mutex_lock(&q->lock); size_t total_size = 0; for (job_t *j = q->head; j; j = j->next) { total_size += j->size; } pthread_mutex_unlock(&q->lock); return total_size / bytes_per_sec;}The Convoy Effect:
FIFO's biggest weakness is the convoy effect. If a large job arrives first, all subsequent jobs—even tiny ones—must wait. Consider:
With FIFO, B, C, D wait nearly an hour for a 1-page printout. Their response time is dominated by A's job, not their own.
Despite this weakness, FIFO is often used as a baseline or when simplicity is paramount. Many systems use FIFO within priority classes.
Priority scheduling assigns importance levels to jobs and processes higher-priority jobs first. This is the most common approach in production systems.
Priority Sources:
CUPS Priority Model:
CUPS uses priorities 1-100 (default 50). Jobs with equal priority use FIFO. Priorities can be set per-job, per-user, or per-destination.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
/* Priority Queue Scheduler with Aging */#include <stdio.h>#include <stdlib.h>#include <time.h> typedef struct job { int id; int base_priority; /* Original priority (1-100) */ int effective_priority; /* After aging */ time_t submit_time; size_t size; struct job *next;} job_t; /* Priority queue (sorted by effective priority, then time) */typedef struct { job_t *head; int count; int age_seconds; /* Increase priority every N seconds */ int age_boost; /* Amount to increase */ int max_priority; /* Cap for aged priority */} priority_queue_t; /* Recalculate priorities based on wait time */void apply_aging(priority_queue_t *q) { time_t now = time(NULL); for (job_t *j = q->head; j; j = j->next) { int wait_time = now - j->submit_time; int aging_boost = (wait_time / q->age_seconds) * q->age_boost; j->effective_priority = j->base_priority + aging_boost; if (j->effective_priority > q->max_priority) { j->effective_priority = q->max_priority; } }} /* Insert job in priority order */void enqueue_priority(priority_queue_t *q, job_t *job) { job->effective_priority = job->base_priority; /* Find insertion point */ job_t **ptr = &q->head; while (*ptr && (*ptr)->effective_priority >= job->effective_priority) { /* Equal priority: FIFO ordering (after existing same-priority) */ ptr = &(*ptr)->next; } job->next = *ptr; *ptr = job; q->count++;} /* Get highest priority job */job_t *dequeue_priority(priority_queue_t *q) { apply_aging(q); /* Update priorities before selection */ /* Re-sort after aging (simplified - full re-sort) */ resort_queue(q); if (!q->head) return NULL; job_t *job = q->head; q->head = job->next; q->count--; return job;}Strict priority without aging can cause starvation—low-priority jobs never run if high-priority jobs keep arriving. Aging mitigates this by gradually boosting old job priorities. Configure aging parameters based on your maximum acceptable wait time.
| Priority | Level | Typical Use |
|---|---|---|
| 90-100 | Critical | Executive, customer-facing |
| 70-89 | High | Time-sensitive business |
| 40-69 | Normal | Regular user jobs |
| 20-39 | Low | Bulk, background |
| 1-19 | Minimal | Archive, non-urgent |
Fair share scheduling allocates device time proportionally among users or groups, preventing any single user from monopolizing resources.
Fair Share Principles:
Example Policy:
Next job selection: Engineering favored, Sales penalized.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
/* Fair Share Scheduler Implementation */#include <stdio.h>#include <stdlib.h>#include <string.h>#include <time.h> #define MAX_USERS 100#define HISTORY_WINDOW 3600 /* 1 hour history */ typedef struct { char *name; double target_share; /* Desired share (0.0-1.0) */ size_t bytes_printed; /* Bytes printed in window */ time_t window_start;} user_stats_t; typedef struct { user_stats_t users[MAX_USERS]; int user_count; size_t total_bytes;} fair_share_t; /* Calculate user's current share vs target */double deficit_ratio(fair_share_t *fs, const char *user) { for (int i = 0; i < fs->user_count; i++) { if (strcmp(fs->users[i].name, user) == 0) { if (fs->total_bytes == 0) return 1.0; /* No history */ double actual_share = (double)fs->users[i].bytes_printed / fs->total_bytes; double target = fs->users[i].target_share; /* Ratio > 1 means under quota (favored) */ /* Ratio < 1 means over quota (penalized) */ return (target + 0.01) / (actual_share + 0.01); } } return 1.0; /* Unknown user treated as neutral */} /* Select next job based on fair share */job_t *select_fair_share(fair_share_t *fs, job_t *pending) { job_t *best = NULL; double best_score = -1; for (job_t *j = pending; j; j = j->next) { /* Score combines priority and fair share deficit */ double deficit = deficit_ratio(fs, j->owner); double score = j->base_priority * deficit; if (score > best_score) { best_score = score; best = j; } } return best;} /* Record completed job */void record_usage(fair_share_t *fs, const char *user, size_t bytes) { for (int i = 0; i < fs->user_count; i++) { if (strcmp(fs->users[i].name, user) == 0) { fs->users[i].bytes_printed += bytes; fs->total_bytes += bytes; return; } } /* Add new user with default share */ add_user(fs, user, 1.0 / (fs->user_count + 1)); fs->users[fs->user_count-1].bytes_printed = bytes; fs->total_bytes += bytes;}Weighted Fair Share:
Not all users/groups need equal shares. Weight assignments reflect organizational needs:
[Shares]
Executive = 3
Engineering = 2
Sales = 1
Intern = 0.5
With these weights, Executives get 3/(3+2+1+0.5) = 46% of capacity.
Real systems often have multiple queues and devices. Scheduling must consider job routing, device capabilities, and load balancing.
Queue Classes:
Load Balancing Strategies:
| Strategy | Description | Best For |
|---|---|---|
| Round Robin | Rotate through devices | Identical devices |
| Least Loaded | Send to device with shortest queue | Variable job sizes |
| Fastest Available | Send to fastest idle device | Mixed device speeds |
| Capability Match | Match job requirements to device | Heterogeneous devices |
| Location Aware | Prefer nearby devices | Geographic distribution |
123456789101112131415161718192021222324252627282930313233343536373839404142434445
/* Device Selection for Job Routing */typedef struct { char *name; int speed_ppm; /* Pages per minute */ int jobs_queued; /* Current queue depth */ size_t bytes_queued; /* Total bytes in queue */ int has_color; int has_duplex; int has_stapler;} device_t; /* Capability matching */int device_supports_job(device_t *dev, job_t *job) { if (job->needs_color && !dev->has_color) return 0; if (job->needs_duplex && !dev->has_duplex) return 0; if (job->needs_stapling && !dev->has_stapler) return 0; return 1;} /* Select best device for job */device_t *select_device(device_t *devices, int count, job_t *job) { device_t *best = NULL; double best_score = -1; for (int i = 0; i < count; i++) { if (!device_supports_job(&devices[i], job)) continue; /* Estimate completion time */ double queue_time = devices[i].bytes_queued / (devices[i].speed_ppm * 1500.0); double job_time = job->size / (devices[i].speed_ppm * 1500.0); double total_time = queue_time + job_time; /* Score: inverse of completion time */ double score = 1.0 / (total_time + 0.1); if (score > best_score) { best_score = score; best = &devices[i]; } } return best;}Beyond basic algorithms, several optimization techniques can improve spooling system performance.
1. Job Coalescing: Combine similar jobs for efficiency. Multiple single-page jobs to the same printer can be merged into one multi-page job, reducing per-job overhead.
2. Deadline Scheduling: Jobs needing completion by specific times get priority that increases as deadline approaches.
3. Predictive Scheduling: Use historical data to predict job sizes, user patterns, and optimize accordingly.
4. Reservation Systems: Allow users to reserve device time for large jobs during off-peak hours.
1234567891011121314151617181920212223242526272829303132333435
/* Deadline-Based Priority Calculation */#include <time.h>#include <math.h> typedef struct { int base_priority; time_t deadline; /* 0 = no deadline */ time_t submit_time; size_t estimated_time; /* Estimated print seconds */} deadline_job_t; int calculate_effective_priority(deadline_job_t *job) { if (job->deadline == 0) { return job->base_priority; /* No deadline */ } time_t now = time(NULL); time_t slack = job->deadline - now - job->estimated_time; if (slack <= 0) { /* Already past deadline or will miss - maximum urgency */ return 100; } if (slack < 300) { /* Less than 5 minutes */ return 95; } else if (slack < 1800) { /* Less than 30 minutes */ return 80 + (1800 - slack) / 100; } else if (slack < 3600) { /* Less than 1 hour */ return 70 + (3600 - slack) / 200; } else { /* Plenty of time - use base priority */ return job->base_priority; }}Effective scheduling requires monitoring. Track metrics like average wait time, deadline miss rate, device utilization, and user satisfaction. Tune parameters (aging rates, priority weights, fair share windows) based on actual workload patterns.
This concludes our comprehensive exploration of spooling—from fundamental concepts through implementation details to optimization strategies.
You now have comprehensive knowledge of spooling systems in operating systems. These concepts apply not just to printing but to email, databases, message queues, and countless other systems that must manage asynchronous, persistent work queues. This fundamental pattern appears throughout computing—recognizing and applying it will serve you well in many contexts.