CS111 Lecture 10 

Condition Variable, Semaphores, Deadlock, File System Performance

Professor Paul Eggert

Notes by Zhaoying Yao

Condition Variable

Condition variable is a boolean condition. When it is met, system will wake up the process.

To set up condition variable, we need:

1. a boolean condition that defining the variable (program's responsibility)

2. blocking mutex to protects the condition

3. a condition variable  of type condivar_t representing the condition

API for condition variable:

A. wait (condivar_t *c, bmutex_t *b)

• precondition: you have a  acquired blocking mutex.

• action: release b, then blocks until some other threads notify the  OS that condition is true.

B. notify (condivar_t *c)

• notifies all other threads that condition is true

• returns notification to everyone

Example:

 Writec implementation with condition variable

Semaphores

A semaphore is like a blocking mutex, except it protects N instances of a resource rather than only one.

e.g. create semaphore with N=5, resources available if N>0, out of resources if N=0.

Blocking mutex is when N=1. However, mutex is a locking mechanism in charge of synchronizing access to a resource. Semaphore is a signaling mechanism in charge of switching control of resource between threads.

Naming: in Dijkstra's implementation for semaphores he named:

prolaag p, for acquire 

verhood v, for release

Spinlock is the basics for condition variable and semaphores. Spin lock is using a pessimistic way, which leads to gaps between threads. We can use a optimistic way, which assumes no one is using the lock and we acquire it, then we have code that does the real work. In the end, we check if anyone has this lock. If someone does, we release it and the code that is doing real work will not execute.

Deadlock

Deadlock is when two threads are waiting on each other, in which case neither will wake up.

How to avoid Deadlock

1. Don't lock.
2. Don't allow more than 1 lock per process.
3. Lock ordering (assume some order, typically address). if you grab multiple locks, you acquire locks in ascendent order. If any lock is busy, you give up all the locks and start over.
4. Dynamic detection of cycles. (Linux uses this)

If it's Real Time, use 1, 2 or 3.

File System Performance Problem

Storage Hierarchy

• ALU (a few ns, 1 cycle)
• registers
• L1 Cache
• L2 Cache (8 cycles)
• DRAM (100 cycles)
• HardDisk

Why is hard disk slow?

Inside hard disk are disks coated with magnetic material. It physically rotates disks and a magnetic head to read and write date. A typical hard drive that puts data on same cylinder at 7200 rpm is running at 120 Hz, which is very slow compare to CPU's cycle time.

To grab random section off disk

1. Accelerate read head in direction of disk track
2. Decelerate
3. Listen for the correct track, settle down
4. Wait for data to come under head
5. Copy data out of a section
6. Transfer data from cache to CPU

Example Hard Drive:

Typical 1TB drive 

• 16MB cache, 7200 rpm , 8.33333 ms rotation time
• 4.16666 average latency (rotational)
• 8.5ms /9.5ms average read seek/write seek time
• 0.8ms/1.0ms track-to-track seek
• 1.29 Gb/s max internal transfer rate, max sustained transfer rate (the outer ring of the disc is faster for same angular velocity)
• 3Gb/s external transfer rate
• 512, 520, 524, 528 bytes/sector
• 12.5 W typical
• 9 W idle
• 1.2 million hours MTBF
• 0.73% AFR (annualized failure rate)
• 10^(-15) nonrecoverable sector read failure  (how to measure? Several drives at the same time? Look at statistics of other similar devices and guess)

Example SSD:

Corsair Force GT 60 GB

• 20W Max power consumption 

• 1000000 hours mean time before failure

• 1.74 GB/s 1.7 Gb/s read- write

• + No latency of rotation.

• + Flash wears out! Only so many writes.
• - Relatively expensive.

Hard Drive Time Example:

for(;;){

char c;

if (read (0, &c, 1)! = 1)

break;

process (c);

}

Time = average 4.16 ms(rotation)+8.5ms(read seek)+very small number

The time it takes is too long, we need to improve it. 

Performance Improvement Strategies

Methods to improve the performance of a file system

• BATCHING

Wait to see if there is more work can be done together instead of guessing what the application will do. This can be used for both Read and Write.

Advantage +: Do data in large batches, so control overhead is less per byte. This can improve performance by up to batching factor.

Disadvantage -: You need to  change your source code.

• PREFETCHING:

Operating system guesses future reads and saves if guesses are right. Read copies from the read ahead buffer.

• DALLYING (the kernel ) 

File system waits to see if the next task could be done at the same time. This is for Write and it's similar to Batching.

Advantage +:By delaying your work, you do your work more efficiently.

Next lecture: How to Design a File System.

Reference: http://www.cs.ucla.edu/classes/winter13/cs111/scribe/10b/

http://www.cs.ucla.edu/classes/winter13/cs111/scribe/10d/

http://www.cs.ucla.edu/classes/spring13/cs111/scribe/9a/

Hard drive image reference: http://www.pantherproducts.co.uk/index.php?pageid=whatisharddisk

Deadlock image reference: http://howtodoinjava.com/2012/10/16/writing-a-deadlock-and-resolving-in-java/