Problem Statement The Linux Kernel, the massive program responsible for low-level hardware and management operations, is difficult to debug because of its nature. The KDUAL project aims to simplify the task of kernel development and debugging by providing an implementation of some of the core kernel code that functions in userspace. This library will precisely mimic the Linux Kernel Application Programming Interface (API). Code developed to be part of the kernel can be compiled against this library for testing purposes. This will result in a user-space program that will be much easier and safer to debug than an actual kernel. Once the code under development is completely debugged, it can be compiled against the actual kernel with no changes, producing a working Linux Kernel. Concurrency, the existence of multiple threads of control at one time, is a key feature of modern operating systems. In a concurrent system, multiple threads of control can potentially attempt to access the same data simultaneously, resulting in data corruption and program failures. These problems are avoided by locking algorithms, which associate access to resources with a single item called the lock. Unfortunately, poorly designed code can result in a situation known as deadlock. Deadlock occurs when several processes each are waiting to take resources held by each other in such a way that no process can obtain the resource it seeks without giving up a resource it already has. The KDUAL locking implementation will include a deadlock detection scheme which will identify deadlock situations and inform the user, aiding in debugging. Methods Deadlock detection will be accomplished by a dedicated thread that monitors the dependencies of other threads. The detection thread relies on a structure called a Wait-For-Graph (WFG). The nodes of the WFG are processes in the system, and the (directed) edges of the graph are dependencies between processes, indicating that one process is waiting for another to give up a resource. If there is a deadlock, it will be detectable in the WFG as a cycle: a path from a node to itself. The definition of deadlock is that the process is waiting on a resource that it cannot obtain until it releases a resource it already holds; this will necessarly result in a cycle in the WFG, because the process must (through some number of intermediaries) depend on itself. The reverse is also true: a cycle in the WFG always indicates a deadlock situation: because a process is dependant on itself, it is necessarily involved in deadlock and requires outside intervention. This means that checking for cycles in the WFG will detect all deadlocks without ever identifying non-deadlock situations as deadlocks (false positives); thus it is a reliable method for detection. Results This is the text output of the lock_test program compiled with the option '-DKC_LOCK_DEBUG=1' to enable debugging messages. The number at the start of each line is the ID of the thread printing the message; the lines marked '**DEBUG**' are printed from within the 'lock.c' code. Lines reading ''getting ready to wait'' indicate that the thread had to wait to obtain a lock. This output is from three threads attempting to complete the same series of locking operations. 16386: Attempting to take locks one and two seperately 16386: Calls succeeded, checking status of both locks 16386: Both locks appear locked 16386: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 16386: Calls succeeded, checking status of both locks 16386: Both locks appear unlocked 16386: Attempting to take locks one and two in one call 16386: Call succeeded. Checking lock status 16386: Both locks appear locked 16386: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 16386: Calls suceeded. Checking lock status 16386: Both locks appear unlocked 16386: Attempting to take lock1 twice (recursively) **DEBUG**:The lock was not unlocked; getting ready to wait **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 2 in call to kc_lock_unlock() **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock Completed test 49156: Attempting to take locks one and two seperately 49156: Calls succeeded, checking status of both locks 49156: Both locks appear locked 49156: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 49156: Calls succeeded, checking status of both locks 49156: Both locks appear unlocked 49156: Attempting to take locks one and two in one call 49156: Call succeeded. Checking lock status 49156: Both locks appear locked 49156: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 49156: Calls suceeded. Checking lock status 49156: Both locks appear unlocked 49156: Attempting to take lock1 twice (recursively) **DEBUG**:The lock was not unlocked; getting ready to wait **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 2 in call to kc_lock_unlock() **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock Completed test 32771: Attempting to take locks one and two seperately 32771: Calls succeeded, checking status of both locks 32771: Both locks appear locked 32771: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 32771: Calls succeeded, checking status of both locks 32771: Both locks appear unlocked 32771: Attempting to take locks one and two in one call 32771: Call succeeded. Checking lock status 32771: Both locks appear locked 32771: Attempting to release locks one and two **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock 32771: Calls suceeded. Checking lock status 32771: Both locks appear unlocked 32771: Attempting to take lock1 twice (recursively) **DEBUG**:The lock was not unlocked; getting ready to wait **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 2 in call to kc_lock_unlock() **DEBUG**:Reached kc_lock_unlock **DEBUG**:Checked to make sure we own the lock Lock count is 1 in call to kc_lock_unlock() **DEBUG**:Unlocked the lock Completed test This demonstrates that the basic locking algorithms are correctly implemetned; processes can take (and wait on), release, and check the status of locks. Research Summary Projects implementing portions of kernel code in user-space have been attempted before (Daytona, Alpine). While most of these projects are sometimes aimed at providing a maximum efficiency solution for a specific set of conditions, it is usually impossible for user-space code to compete with the kernel for speed. Thus, most of these projects are, like KDUAL, designed primarily for testing purposes, and thus emphasize transparency and equivalency with the standard kernel over speed and specificity. The primary scheme for deadlock detection is the Wait-For-Graph. Although this technique has been adapted for various situations (e.g. deadlock detection in distributed system usually uses multiple local WFGs and message passing), the basic principle of detecting cycles in the dependencies remains standard.