2.5The OS and Middleware

FE/SG requires only a phenomenon-level understanding: "mutual exclusion is implemented with semaphores" and "deadlock can occur." AP requires a more structural understanding of why deadlock occurs and which conditions must hold, and how breaking one of those conditions avoids it. This section also organizes practical knowledge of middleware and OSS licenses.

2.5.1Comparing scheduling schemes

• SJF (Shortest Job First) is a scheduling scheme that prioritizes the task expected to have the shortest execution time, which has the property that it theoretically minimizes average wait time. In practice, though, accurately estimating execution time in advance is difficult, and it has the weakness that a task with a long execution time can suffer perpetual starvation, always being pushed to the back.
• The starvation common to both priority scheduling and SJF is a state where a task meeting a certain condition (low priority, long execution time, etc.) never gets allocated the CPU. A representative countermeasure is aging, which dynamically raises a task's priority the longer it has been waiting.

2.5.2The conditions for deadlock and how to avoid it

• For a deadlock to occur, the following four conditions must all hold simultaneously: (1) mutual exclusion (a resource can be used by only one task at a time); (2) hold and wait (a task holds a resource while waiting for another to free up); (3) no preemption (a resource held by another task cannot be forcibly taken away); and (4) circular wait (multiple tasks form a cycle, each waiting on a resource held by the next). Conversely, breaking even one of these four conditions prevents deadlock from occurring.
• Practical deadlock-avoidance strategies can be organized by which of the four conditions they break. "Standardizing the order in which all tasks acquire resources" is a representative strategy for breaking circular wait (4)—if you always decide to acquire resource 1 before resource 2, a circular wait structurally cannot form. "Timing out and releasing already-held resources to retry if acquisition does not succeed within a set time" breaks hold and wait (2). "Letting a higher-priority task forcibly preempt a resource held by a lower-priority task" breaks no preemption (3), though it has the side effect of complicating how the preempted task maintains consistency.

Let us apply the four deadlock conditions to a real scenario. In an online banking system, suppose a funds-transfer task A holds a lock on "account X" while waiting for a lock on "account Y" to free up, and simultaneously a second funds-transfer task B holds a lock on "account Y" while waiting for a lock on "account X." Here, all four conditions hold: (1) mutual exclusion (each account lock can be held by only one task); (2) hold and wait (both tasks hold one lock while waiting for the other); (3) no preemption (a lock held by the other task cannot be forcibly released); and (4) circular wait (A waits on B's resource and B waits on A's, forming a cycle)—this is a deadlock. The most practical countermeasure is to establish a standard rule that all funds-transfer tasks acquire the lock for the lower-numbered account first. If this rule is consistently enforced, both tasks will always attempt to acquire locks in the same order regardless of which account number is lower, so the circular wait described above (condition 4) can no longer structurally form, and breaking one of the four conditions avoids deadlock. It is also worth touching on the role of middleware. Middleware sits between the OS and applications, providing common functionality to reduce development burden—examples include the DBMS (database management system), which handles data persistence; the application server, which provides the execution environment for business logic; and the message queue, which passes messages asynchronously between systems (absorbing speed differences between the sender and receiver, so processing can resume later even if one side is temporarily paused). When using OSS, license differences also matter. GPL (GNU General Public License) imposes an obligation to publish the modified source code, also under GPL, if you modify and distribute the software (copyleft), whereas the MIT License places almost no restriction on modification, redistribution, or commercial use as long as the copyright notice is retained, making it easy to embed in a proprietary product. Embedding OSS without understanding this distinction risks unintentionally taking on an obligation to publish your own source code.

2.5.3Section summary

• The four deadlock conditions: mutual exclusion, hold-and-wait, no preemption, circular wait (occurs only when all four hold). Standardizing resource-acquisition order breaks circular wait, a representative avoidance strategy
• SJF theoretically minimizes wait time but risks starvation for long jobs (mitigated by aging). Middleware includes the DBMS, application server, and message queue
• GPL imposes an obligation to republish modifications (copyleft). The MIT License leaves modification and redistribution nearly unrestricted if the copyright notice is retained