No-Wait Scheduling for Locks
研究并行腔室锁的无等待调度问题，用图论方法刻画两腔室锁的可行性并给出线性时间算法，对同质腔室和一般情形也提供高效算法，适用于等待时间不可避免的实际场景。
We introduce and investigate the problem of scheduling a single lock with parallel chambers. Special cases of this problem are related to interval scheduling. We focus on the existence of no-wait schedules and characterize their feasibility for a lock consisting of two chambers using new graph-theoretical concepts. We obtain a linear time algorithm for this special case. We also provide an efficient algorithm for the case where all chambers of the lock are identical. Furthermore, we describe a dynamic programming algorithm for the general case with arbitrary chambers. Finally, we indicate how our methods for the no-wait case can be applied to practical settings where waiting time is unavoidable.