SWAP: A Scheduler With Automatic Process Dependency Detection

Haoqiang Zheng, Jason Nieh

Department of Computer Science, Columbia University Technical Report , CUCS-005-03, April 2003


Cooperating processes are increasingly used to struc- ture modern applications in common client-server comput- ing environments. This cooperation among processes often results in dependencies such that a certain process cannot proceed until other processes finish some tasks. Despite the popularity of using cooperating processes in applica- tion design, operating systems typically ignore process de- pendencies and schedule processes independently. This can result in poor system performance due to the actual scheduling behavior contradicting the desired scheduling policy. To address this problem, we have developed SWAP, a system that automatically detects process dependen- cies and accounts for such dependencies in scheduling. SWAP uses system call history to determine possible re- source dependencies among processes in an automatic and fully transparent fashion. Because some dependencies can- not be precisely determined, SWAP associates confidence levels with dependency information that are dynamically adjusted using feedback from process blocking behavior. SWAP can schedule processes using this imprecise depen- dency information in a manner that is compatible with existing scheduling mechanisms and ensures that actual scheduling behavior corresponds to the desired scheduling policy in the presence of process dependencies. We have implemented SWAP in Linux and measured its effective- ness on microbenchmarks and real applications. Our ex- periment results show that SWAP has low overhead and can provide substantial improvements in system perfor- mance in scheduling processes with dependencies.



Columbia University Department of Computer Science