CS 111 Lecture 10 Scribe Notes: File System Performance

prepared by Andre Hsu, Alex Guo, and Collin Yen for a lecture by Professor Paul Eggert on Nov 4th, 2013

A. Condition Variables

We need:
- A boolean condition that defines the variable
  - Programmer’s responsibility to define this condition, independent of the hardware
  - Variables are abstract, and can be described as “floating around.”
- Blocking mutex - used to protect the condition
- A condition variable that represents the condition
  - A new data type condvar_t that can be implemented with a little piece of memory.
  - Compared to Variables, a condition variable is a piece of storage that holds items.
API:
- wait(condvar_t* c, bmutex_t *b)
  - Precondition: You have acquired a blocking mutex b(Don't want to call this function unless safely in the protected area)
  - Action: Releases b. Then it blocks until some other process or thread notifies us that the condition is true; When the condition is true, it will reacquire b and then return c.
  - Notice that wait can take a long time.
- notify(condvar_t *c)
  - Notifies a particular thread that the wait conditions is true.
- notifyAll(condvar_t* c) - Notifies all threads
  Benefits of notifyAll:
  - If you have a system where the system wants to determine priorities of the applications then we use notifyAll, everyone wakes up, and they figure out what to do.
  - On the other hand, if you have something similar to pipes then you are better off just using notify.

Pipe Example:

struct pipe
{
	bmutext_t b;
	condvar_t nonfull, nonempty; //want to wait for if the pipe is not full so that people can write to it or if the pipe is nonempty so we know that we can read from it; non full for writers and nonempty for readers. 
	size_t r, w; //Store the read and write bytes
	char buf[N];

};


void writec(struct pipe* p, char c) 
{
	acquire(&p->b) //Acquire the spin lock and if we can't get it then we block
	while(p->w - p-> r == N) //While the pipe is full
		{

			wait(&p->nonfull, &p->b); //Condition variable function
		}
		p->buf[p->w++ %N]=c;
		release(&p->b);
		notify(&p->nonempty); //This does not guarantee to the other threads that the condition is true. All we are saying is that the condition might be true, so the other threads should wake up to check it.
}

Semaphores - A semaphores is like a blocking mutext except it protects n instances of a resource intend of just one.
- A blocking mutex is a binary semaphore.
- Resources in the semaphore are available if N>0 and we are out of resources if N =0.
- Example:
  - Create a semaphore with N = 5.
  - Resources are available if N > 0.
  - Out of resources if N =0.
- Primitives Functions E. W. Dijkstra
  - proloog P - like acquire (if resources are available, decrement resources otherwise wait.)
  - verhoog V -release
Hardware Lock Elision (HLE)
- One problem with spin locks is that they take up CPU time when the spin lock is trying to lock and unlock.
- We want to get the effect of spin locks without spin locks.
- Basic Idea:
  - Invent a new instruction prefix to the x86 architecture called xacquire.
  - Lock:
    - try: xacquire lock xchgl %eax, lockvar
      cmp $0, $eax
      jnz try
    - The xacquire prefix is an optimistic variant of the xchgl that says most of the time when you do this instruction you're going to do xchgl that works so don't wait for the lock to finish and just do it.
    - In the case that it doesn't work then try it again.
  - Unlock:
    - xrelease movl $0, lockvar
    - For unlock we check to see if we actually got the lock.
    - If we didn't get the lock we just say that all the actions that happened in between the lock and the unlock didn't execute so we undo all the actions and then go back to the beginning of the lock and try again.
- Spin locks are pessimistic because they assume that bad things are going to happen and then do the action.
- HLE's are optimistic in that they assume that the process will acquire the lock. Therefore, they don't wait to acquire the lock until the end, and if they didn't retrieve the lock they undo all the actions and try again.
- The goal is to get a locking primitive that has hundreds of threads trying to access the same resource at the same time and we don't want to have them wait for the unnecessary locking and unlocking times.
Deadlock
- Deadlocks can be tricky because they can come about in unanticipated ways.
- Example: Fast Cat
  - We want to make the cat program more efficient so that we don't have to copy all the data form userspace to kernel space back to userspace.
  - Better code:
```
//Copy primitive that allows us to copy everything at once
while(copy(0,1,40%) > 0)
	continue;
```
    - Deadlock problem arises because the 0 represents the stdin and 1 is the kernel space memory, and so for both of those you could have pipes.
    - What it does:
      - acquire 0's struct
      - acquire 1's struct
      - copy data
      - release 1
      - release 0
    - Deadlock situation occurs when you have copy(1,0…) at the same time, and so one thread will be waiting for the structure that the other thread holds.
- How to avoid deadlock?
  - Don't lock (no exclusion)
  - Don't allow more than 1 lock per process. Let process A lock one thing, but if you want to lock another item you must first release your lock.
  - Lock ordering
    - You assume that locks are in some order.
    - Acquire locks in ascending order.
    - If at any moment any lock is busy you give up all locks and start over.
    - In this method, all attempts at locking will be through TryAcquires.
  - Lab-Dynamic Detection of Cycles
    - Look to see if a newly created lock would create a cycle and if it would implement a method to avoid it.

B. File System Performance

Problem: We want to be able to get data from Flash and Harddisk storage as fast as possible

Hardisk:

The track is a circular path on the hard disk.
A sector is part of the track.
You have small dots on each of the disks that are called read heads.
We want to arrange our data so that it is all in the same cylinder.

To grab a random sector off the disk:

First we need to figure out which track the sector is in.
Then we need to accelerate the read heads in the direction of the desired track.
When we get about halfway there, we need to decelerate the read head.
When we get very close to the sector the read head needs to listen to the magnetic flux to determine the correct track.
Now we have to wait for the data to come under the head.
Then we copy the data out of the sector and into the cache of the disk controller.
Transfer data from the cache to the CPU or RAM.

Seagate Barracuda ES2 1TB
16 MiB	cache
7200 rpm	drive
8.333 ms	rotation time
4,166 ms	average latency - amount of time it will take for the data to come under the read head will be half of the rational time
8.5 ms	average read seek - if you choose two track numbers at random and measure how long it takes to accelerate and decelerate the heads from one track to another.
9.5 ms	average write seek - Takes longer because you are writing data as the head moves and write has to be a lot more accurate because if you are a little bit off you might leak and write data into the wrong track
0.8 ms/1.0ms	Track-to-track seek - If you are seeking in one track and you want to go to another track
1.29 Gb/s	Maximum internal transfer rate - rate at which data comes off the disk and onto the cache. If the data is closer to the edges then it is faster to transfer the data.
3 Gb/s	External transfer rate - Rate at which you transfer data from the disk controller cache to the bus
512, 520, 524, 528 bytes/sector	We can configure the disk drive to have a different number of bytes per sector. Standard is 512 bytes/sector
12.5 W	Will use 12.5 watts when it is running
9 W	Idle- Will use 9 watts if it is not doing anything and just staying idle
.73% AFR	annualized failure rate (24*7)- If you use the machine for a year straight then there is an .73% chance that it will crash and you will have to replace it.
10^-15 nonrecoverable read failure rate	Probability that the disk will lose the sector

Corsair Force GT (Flash Memory)
60 GB	Capacity
2.0 W	Capacity
1,000,000 hours	Mean time before failure
1.74 GB/s	read
1.7 Mb/s	write
0s	latency

Flash wears out, whereas hard disks do not.
Can only do a certain amount of writes to flash and then you can't do anymore.
Wear leveling - flash drive controller keeps track of how many times you write to a block of memory and if the controller realizes that you have been writing to a particular block over and over again, what the controller will do is it will move the block so that you don't wear out that piece of memory.
Will result in all of your flash memory failing at once rather than just part of it at a time.

Program that you might want to run on the disk:

Read from a file a byte at a time

for(;;)
{
	char c;
	if(read(0,&c,1) !=1) //Suppose this does all the steps above dealing with hard disks - Total read time will be long because the read time will be = 8.5(average read seek) + 4.16 ms(average latency) + (.0005 MB/100Mb/s) (max sustained transfer rate)
	break;
		process(c);

}

We care primarily about the average read seek and the latency.
Improvement Methods:
- Batching - If you want to do something over and over again then take the control part of that operation and do that once.
  - By reading in as much data as possible we are able to make the control overhead time less per byte.
  - Allows us to improve performance by up to the batching factor.
  - ```
  for(;;)
  {
  	char c;
  	if(read(0,&c,1024)!=1)
  		break;
  	process(c);//If the process takes a long time then batching won't have that much of an effect, but if the process is short then the run time will be increased by around 1000 times
  }
```
- Prefetching
  - Operating system guesses future reads and saves what it guesses will be read.
  - Read copies form this read ahead buffer.
  - Able to do the latency and the average read seek in parallel instead of just waiting.
- Dallying
  - The application will probably do another write in the same sector and by waiting you can just move them once because by delaying your work you work more efficiently.