Demand Paging Deadlock Guide

Introduction

A deadlock is when two or more processes have some resources, but not all of the resources required to execute. The resources that are required are held by the other processes, which in turn want the resources that are held by the initial processes. In this state, no process can execute.

The classic sign that a deadlock has occurred is that a collection of processes just appear to never do anything i.e. 'just hang'.

In the context of demand paging, the resource is a page of RAM that can be paged in or out. If one process wants data in a page of RAM that is paged-in or out by another process, then a potential deadlock condition can occur.

Deadlocks are only likely to occur if you are altering or interacting with one of the components used in paging in and out, such as media drivers or the paging sub-system. The majority of user-side code does not need to worry about deadlocks from paging.

This guide is most applicable to device side writers and other engineers writing kernel-side code.

Deadlock features

For a deadlock to occur, four necessary conditions must occur:

Mutual exclusion condition

A resource cannot be used by more than one process at a time.

Hold and wait condition

One process is holding one resource, but needs another before it can finish.

No preemption condition

The resources can only be relinquished by the process holding it.

Circular wait condition

One process is holding a resource and wants another resource that is held by another process, which in turn wants access to the resource held by the initial process.

Deadlock Prevention

Since the cause of deadlocks (as far as demand paging is concerned) is due to the paging in and out of RAM, the following points have to be considered:

• Make sure all kernel-side components are always unpaged.

• Pinning; new APIs have been added that allows a process to over-ride the demand paging rules as regards to how RAM pages are paged in and out the phone's memory. The name comes from that fact that the RAM page is fixed in the phone's RAM (as if a pin had been stuck into it) until a detached command is executed (unpinned). This is implemented by using the new DLogicalChannel::SendMsg() method.

• Mutex use in device drivers - if the nesting order is violated then deadlock can occur. To overcome this, make sure that all device driver operations that could cause a page fault don't use mutexes. In other words, any access to paged memory while holding a mutex has the potential to cause a deadlock.

• Code running in DFC Thread 1 must not access user memory. This DFC thread is used by the implementation of the system timer functionality, hence paging RAM in or out of the system by this thread could cause serious performance problems or a deadlock.

• For media drivers, make sure that when the media driver services page-in requests, that the thread that the driver runs in does not also make requests to page-in RAM pages. Because, if this was to occur, then the media driver will not be able to service the page in request and a dead lock would occur.