Scheduling Algorithms in Operating Systems

Scheduling and Priority Mechanisms

• Priority Inversion: The rationale behind scheduling algorithms can fail if a high-priority thread is unable to run due to a lower-priority thread holding a resource.
• Priority Ceiling Protocol: Assigns a high priority to mutexes, ensuring that any thread holding it has priority above threads needing the mutex, thus preventing priority inversions.
• Priority Inheritance Protocol: Temporarily boosts the priority of a low-priority thread that holds a mutex needed by a higher-priority thread, allowing swift mutex release while maintaining system priorities.
• Random Boosting: Mechanism that randomly increases the priority of mutex holders to expedite critical section completion; used by Windows operating systems to mitigate priority inversions.

Supporting Concurrency

• Three essential considerations for concurrency support:
  • Processes must communicate effectively.
  • Ensuring threads operate without interference.
  • Synchronizing thread behavior.

Inter-Process Communication (IPC)

• Shared Address Space: Threads within the same process can share memory, simplifying information exchange.
• Message Acknowledgment: Messages typically include sequence identifiers to manage received messages and detect duplicates.
• Authentication: Ensures proper identification of processes during communication to prevent interactions with unauthorized entities.
• Performance Costs: Message passing can incur overhead from multiple copies of messages and context switching between user and kernel modes.

Sockets

• Sockets are special files in UNIX that bind to network interfaces, providing a tailored API for message passing and network communication.
• They enable data exchange via buffers and variables, aiding communication between isolated processes.

Message Passing

• Basics: Operates on send and receive primitives implemented as system calls.
  • send(destination, &message): Sends a message to a specified destination.
  • receive(source, &message): Receives a message from a specified source.
• Communication can occur between local processes or over a network through sockets.
• Synchronizing Semantics: Message passing inherently incorporates synchronization due to its communication nature.

Message Passing: Buffers

• No Buffering: The sender blocks until the message is received with no intermediate storage.
• Buffered Communication: The kernel maintains a limited queue of messages, allowing senders to transmit without blocking until the buffer is full.

Message Passing: Limitations

• Data Loss: When communicating over networks, messages may get lost; acknowledgments can help confirm receipt and trigger retransmission if necessary.
• Security Risks: Increased vulnerabilities when handling messages over networks, necessitating robust communication protocols.

Signals

• Signal Mechanism: Asynchronous notifications sent between processes that invoke a signal handler based on signal numbers (e.g., KILL, STOP).
• Sending Signals: Executed through the kill(pid_t pid, int sig_nr) function.
• Signal Handling: Processes manage signals via defined signal handlers, which can be modified using functions like signal() or sigaction().
• Synchronicity: Signals operate asynchronously; they can be triggered at any time, usually upon interrupts or system calls.
• Signal Count: Processes cannot track the number of signals received before handling, as they are represented only in a bitmask.

Deadlocks

• Mutual Exclusion: Access to shared resources must be controlled, permitting only one thread at a time to avoid deadlocks.

This quiz covers key concepts in scheduling algorithms, focusing on priority ceiling and priority inheritance mechanisms. Understand how these methods help prevent priority inversions and manage thread priorities effectively. Test your knowledge on the implications of mutexes in real-time systems.