CS111 Lecture 10:
File System Performance

UCLA Spring 2014
Professor Paul Eggert
May 5, 2014

Scribed by Andrew Wong & Eddie Yan

I. Deadlock

a. Wait-For Graph Solution

b. Lock Ordering Solution

II. Quasi-Deadlock

a. Priority Inversion

b. Receive Livelock

III. Aside: Hardware Lock Elision

IV. Aside: Event-Driven Programming

V. File Systems

a. Performance Ideas

b. Performance Metrics

c. Example Device

Deadlock

While the general idea of deadlock has already been established (i.e. a state in a program at which nothing can happen), a more formalized list of conditions required for deadlock is as follows:

1. Circular waiting: If one process is waiting for a second process that is waiting for the first process, the result will be a circular wait loop in which no process can move forward.

2. Mutual exclusion: While one process is running with its resource, another process cannot be running with that same resource. Without mutual exclusion, there would be no deadlocks.

3. No preemption of locks: If a process has a lock, it cannot be forcibly revoked from the process, otherwise a deadlock would be easily avoided just by revoking the lock held by the problematic process.

4. Hold and wait: A process must be able to hold a lock and be in a waiting state for deadlock to occur. Deadlock will occur if a process is locking some resource while waiting for another condition that will never come true.

Every one of these conditions must be true for deadlock to occur. Thus, to avoid deadlock, just one of these conditions needs to be guaranteed false. Attacking the first condition, circular waiting, is a popular choice.

Wait-For Graph Solution

A method of avoiding circular waits involves maintaining a "Wait-For-Graph."

If a cycle were to appear in the graph, it would be possible for deadlock to occur. If, however, we check for loops in our graph before trying to acquire a resource, as shown below, there would be no way for a circular wait to happen.

This is a valid solution, and it will work, but what is its runtime? Every time we want to acquire something, we would have to check through the entire graph to see if the request would add a cycle, and with a large number of process and resources, this could be costly, depending on the size of the graph, perhaps reaching O(P * R). If possible, we would want something to run much faster, O(1) if possible, especially if we're doing something as trivial as adding one to a bank account (See Lecture 8).

Lock Ordering Solution

Another possible solution will grant us this desired speed: lock ordering. The idea is to impose an order of locking (e.g. ordered based on machine address of locked resource). A process that locks more than one resource must lock the resources in a fixed order. The process will keep locking the resources until one of them is busy, at which point, it will give up all of the locks and start over. The benefit to this is that it eliminates the possibility of the "hold and wait" condition necessary for deadlock to occur, in O(1) time, just by checking if the resource was available or not.

But this runtime comes at a price. This method depends on all of the processes behaving properly e.g. only obtaining locks in the specified order. Thus, this approach is much less convenient than our original, slower, Wait-For Graph method, for developers who might want to use the resources.

Quasi-Deadlock

Quasi-deadlock is like deadlock, but instead of hanging and doing nothing, the CPU is doing nothing useful, or not performing the intended task.

Priority Inversion

One type of quasi-deadlock is priority inversion, which killed off the Mars Pathfinder in 1997. Fundamentally, priority inversion is problematic because it prevents critical processes i.e. those with high priority from acquiring the CPU. It is tricky to debug because the parts, when examined individually, are fine, but once they are put together, there is a small chance for failure.

Priority inversion can only occur in a system that uses a preemptive scheduler with priority. Additional conditions must also be met (everything must go wrong in precisely the right way) for priority inversion to occur. For example, say we have three priorities: low, medium, and high, where the low priority task is runnable and the other two are waiting. The low priority task, since it currently has the highest priority among runnable tasks, will run and acquire some resource. Next, something causes the high priority task to become runnable. This will cause a context switch to the high priority task, but since the desired resource is locked, it will wait and return control to the highest-priority runnable task.

If, immediately after the context switch, the medium priority task switches to the runnable state, it will be next in line to run. The high priority task will hand control to the medium priority task and be stuck waiting for the resource used by the low priority task. However, since the high priority task is waiting on a resource held by T_low, whatever important task T_high needs to accomplish is stuck waiting, even though things are still happening (T_med is running).

The solution: when a high priority task is waiting for a lower priority task, lend the high priority to the low priority task, so the low priority task is guaranteed to finish and grant the high priority task control of the resource.

More info on the Mars Pathfinder incident

Receive Livelock

Another case of quasi-deadlock is called receive livelock and it works as follows. Suppose we have a bounded buffer of requests. When a request is received, the CPU has to stop its activity, follow an interrupt service routine to put the request into the buffer. This task of handling requests is high priority, so the CPU will stop its normal work routine to acknowledge these requests. This can lead to some strange behavior when processing a large number of requests, as illustrated in the figure below.

Ideally, the performance curve would asymptotically approach 100% CPU capacity. The problem occurs when the bounded buffer is full and requests keep coming in. This will happen when there is a large load of requests coming in at once. The CPU will spend all of its time handling interrupts without actually adding requests to the buffer, preventing the CPU from doing anything useful.

The solution: if the buffer is say 95-100% full, disable interrupts until it's at a more passable capacity (say 50%). This will allow the CPU to focus on actual work when the request buffer is too full.

Aside: Hardware Lock Elision (HLE)

Another problem we encounter when we deal with locking is that a lot of time is spent busy-waiting. So, as we've done throughout the course, we can try calling the hardware guys at AMD. Their solution: Hardware Lock Elision.

The idea is to give users the effect of having the lock without actually getting it. The CPU charges ahead without acquiring the lock, and only at the very end does it commit to memory. An example of this functionality is shown:

Locking:

movl $1, %eax

try: xacquire lock xchgl %eax, global_lock

cmp $0, %eax

jmp try

ret

Unlocking:

xrelease movl $0, global_lock

ret

The xacquire keyword tells the CPU to go ahead and execute commands, but to not write anything to memory just yet. Only at xrelease does the CPU try to commit its data. This frees the CPU from all the busy-waiting it would do otherwise if it were locking as usual.

More info on how Intel does HLE

Hardware Lock Elision is an example of speculation, whereby instructions are executed without confirming that a task should or need to be performed. If the prediction was correct, then speculation can improve performance.

Aside: Event-Driven Programming

"Data races are evil."

With this entire discussion of locking, the fundamental problem is that we want 2+ threads running at any time. If we could find a way to not use multiple threads, all of these problems caused by races would vanish. So a natural thought might be to just use one thread. We still want to be able to wait for events, as long we don't have the data races. To accomplish this, we use something called event-driven programming, which has a general single-threaded structure as follows:

while(true) {

wait_for_some_event e;

/* Note that this is the only wait that happens */

e->handler(e);

}

From this general framework, it is clear to see that there are no locks, and therefore, no bugs due to locking, and therefore, no deadlock. On the other hand, handlers are restricted to being fast in order to prevent any CPU hold-up. Thus, large jobs may need to be broken into multiple handlers. Additionally, things cannot be scaled via multithreading since there is no way to manage critical sections. However, it can be argued that it is inevitable that some applications need to scale using multiple processes anyway, so we can just cut out the middleman and scale using multiprocessing, keeping things simple for software engineers. Node.js is an example of a software framework designed with Event-Driven Programming principles.

File System Considerations

These are just a few ideas to improve file system performance. Lecture 11 will cover actual implementations of file systems.