CS 111: Lecture 11 Scrible Notes

Justin Yuan & Jiexi Luan

Part 1: Avoiding Race Conditions Continued CONDITION VARIABLES:
We would like to create a boolean condition in order to define a certain variable.
Keeping track of this will be the programmer's responsibility, therefore we need to think of when the variable is allowed to be changed, and by what process.
We need a blocking mutex to protect the condition.
Only processes that own the mutex can change the condition. This will prevent any race conditions.
Here is an example of how to implement a blocking mutex.

				1. typedef struct{
				2.	splinlock_t l;
				3.	proc_t *blocked_list;
				4.	bool acquired;
				5. } bmutex_t;
				6. 
				7. typedef struct{
				8. 	proc_t *next_blocked;
				9. } proc_t;
				10. 
				11. void acquire(bmutex_t *b){
				12. 	for(;;) {
				13. 		lock(&b->l);
				14.		current_process->blocked;	//current_process is a global variable that points to the current process
				15.		current_process->next_blocked = p->blocked_list;
				16.		p->blocked_list = current_process;
				17.		if(!b->acquired) break;
				18.		unlock(&b->l);
				19.		schedule();
				20.	}
				21.	b->acquired = 1;
				22.
				23.
				24.	
				25. void release(bmutex_b *b){
				26.	lock(&b->l);
				27.	for(proc=b->blocked_list;*proc; proc=proc->next_blocked){
				28.		proc->blocked=0;
				29.	}
				30.	b->acquired=0;
				31.	unlock(&b->l);
				32.  }

Below is the API:

					1.  wait(condvar_t *c, bmutex_t *b)
					2. 	//precondition: b is acquired
					3.	//releases b
					4.	//	-  asks until some other process notifies that condition may be true
					5.	//	- reacquires b
					6. 
					7.  notify(condvar_t *c)
					8.	//wakes up a thread waiting for condition to be true
					9. 
					10. notifyALL(. . . )
					11. broadcast(. . . )
					12. 	//notifies all threads
					13.

Semaphores:
A semaphore is like a mutex, except it protects N instances of a resource, not just one.
It is locked when int == 0, and unlocked when int > 0.
Implementation Example:

		1. struct pipe{
		2. 	char buf[N];
		3.	unsigned r,w;
		4.	bmutex_t b;
		5. }
		6. 
		7. char readc(struct pipe *p){
		8.	acquire(&p->b);
		9.	release(&p->b);
		10.	return c;
		11. }

Deadlock:
A deadlock occurs when two competing processes wait for each other to finish, therefore neither does.
Deadlocks cannot always be anticipated Example: Implementing a fast cat

		a | cat | b
		
		1. while((n=read(0,buf,sizeof buf))>0)
		2.	write(1,buf,n);
		3.	while(xfer(0,1,n)>0)
		4.		continue;
		5.	return c;
		6. }
		7.
		8. // The first pipe is waiting on the second pipe. Also the second pipe is waiting on the first pipe.
		9. // This cycle of dependency is known as a deadlock.

How we can avoid deadlocks entirely

Don't lock: Not enforcing exclusive access may not be the best approach, but it is simple and could work in some situations.
No more than one lock process: This is the next simplest approach, and will guarantee no two processes will compete with each other.
Lock ordering: Give the locks some sort of order. This is usually done by ascending address space. If any lock is busy, give up all locks and start over.
Dynamic detection: We can check if newly acquired locks have overlapping dependencies with any existing locks. If there is such a lock, then we reject it.

Part 2: Introduction to File System Performance

Problem: computers have a storage hierarchy in which the fastest storage mediums are limited by space.

Storage Hierarchy (by speed)

ALU (a few nanoseconds, ~1 cycle )
Registers
L1 Cache (~2 cycles)
L2 Cache (~4-8 cycles )
DRAM (~100 cycles )
flash
hard drive

How can we design a file system to be as efficient with storage as possible?

We will mostly focus on the flash and hard drive portions, since these are infinity slower compared to the other memory modules.

A hard disk is made up of one or many magnetic platters. Each platter has a magnetic head mounted on an arm that is able to move across the platter in order to read and write data. By the nature of the physical form of the platter, data is written in circular patterns.

A platter can be divided up into a number of tracks, concentric circles around the disk.

A track can be further divided up into a number of sectors, segments within each circle.

A cylinder is formed by several overlapping tracks from multiple platters.

Things to consider:

Reading from sequential sectors, or even an entire track will be ideal since the magnetic head will not need to be moved as much.

All reader heads must move in unison, so reading from a cylinder will also be ideal

Here is what actions a hard drive must undergo when grabbing a random sector off the disk:

accelerate read head in direction of desired track
decelerate read head when about half way there
when almost there "listen" for correct track
(the head may overshoot the track or even come up short)
when on the correct tract, wait for desired sector to come around
copy data out of sector and onto disk controller's cache
transfer data from cache to RAM or CPU via BUS

Typical Hard Disk Performance Specifications
measured from a Seagate Barracuda FS2

16MB cache

7200RPM

1.0TB capacity

8.333ms platter rotation time

4.166ms average latency (the head is on average half a full track away from desired sector)

8.5ms average read seek

9.5ms for write
The write time is slower than the read time because reads can be sloppy and in approximately the right area to get the correct data. Writes must be exactly on target so that all tracks and sectors have uniform spacing.

0.8-1.0 track to track seek time

1.29Gb/s max internal transfer rate (from disk to cache)
typically burst speeds are close to this rate since the read head does not have to move as much initially.

0.93Gb/s max sustained transfer rate
This is slower than the max internal transfer rate as the head may need to grab data from anywhere on the disk

3Gb/s external transfer rate
Often the advertised speed of hard drives.

512 bytes per sector
(this can be reconfigured to 520, 524, or 528 bytes per sector)

uses 12.5W, 9.0W at idle

1.2 million hours MTBF

For a comparison, below are some specifications for a solid state drive.

Typical SSD Performance Specifications
measured from a Corsair Force GT

1.74Gb/s read

1.70Gb/s write

(there is no read or write latency)

60GB capacity

uses 2.0W max

Immediately one can notice that SSDs have much faster read and write speeds, particularly they excel at random reads and writes.

It is important to note that the main drawback for SSDs are their limited read/write cycles
This is countered by wear levelling. Wear levelling checks the SSD for hot write spots, then swaps these sectors for lesser used sectors.
Hardware levelling should be able to account for drive partitioning, but software leveling may not.

Here is an example of reading from a hard disk.

		a | cat | b
		
		1. for(;;){
		2.	char c;
		3.	if(read(0,&c,1)!=1)
		4.		break;
		5.	process (c);
		6. }

Each read will take on average:

8.5ms (seek latency)+ 4.16ms (write latency) +0.005ms (time from cache to registers)
= 12.665ms

Naturally, the worst read condition is reading 1 byte from random locations.
There are some methods one can employ to improve average read times.

Batching:

Batching requires reading data in large batches so that control overheard is less per byte. Instead of reading just one byte we read entire sectors.

Depending on if process() is a bottleneck, batching may or may not improve read times.

Prefetching:

Prefetching has the OS guess future reads and saves them in cache.

Dallying:

Dallying delays writes to allow programs to possibly schedule more things to be written. It tries to fill a sector in one write cycle.

Although it may be counter-intuitive, it may be more efficient to do work by delaying it.