Lecture 7: Scheduling Algorithms

Supporting atomic update in the persume of power failure

---

2 big ideas

• A commit record
• A journal

More generally, you implement an atomic action:

	BEGIN
	   pre-commit phase
	   commit
	   post-commit phase
	END
				

Two variants: write-ahead log and wirte-behind log

Commons:

• Main memory database
• Journal is on disk
• No cell data on disk but kept in RAM

Advantages:

• Access to cell data is fast
• No seeks when writing (it always writes to the same log)

Disadvantages:

• Chew up RAM
• Rebooting (recovering after crashes) is slow

Uncommons:

• Write-ahead log

  	log planned writes
  	commit
  	install new data
  									

  When recovery:

  Scan forward through log, looking for commited but not installed cells

  Advantages:

  • More likely to save the last action
  • Don't need to know old data
  
  
• Write-behind log

  	log old cell values
  	install new data
  	commit
  									

  When recovery:

  Scan backward through log and restore old uncommited cells

  Advantages:

  • More conservative
  • recovery tends to be faster
  
  

Another two variant: cascading aborts and compensating actions (necessary with complicated actions)

Motivation: High throughput

Cascading aborts: More automatable

Tell P2 the file size
P2 is later told that the file size is wrong
P2 aborts its transaction

Compensating actions: More feasible

Tell P2 the file size
P2 is later told that the file size is wrong
P2 adds compensating actions to make the last story correct

Unreliable programs have bad memory referrence

---

Solutions:

• Hire better programmers
• Help from the hardware and/or emulator (hardware is able to find bad referrence and report)

Advantage: Faster

• help from the compiler and/or runtime

Advantage: Debuggable

A simple implementation:


If referrence M doesn't satisfy P1_base <= M < P1_bound, report

Disadvantages:

• Require contiguous RAM for each program
• Hard to share between programs
• Can't have identical copies of program running

e.g. jmp 100038 (absolute address which can be accessed by one process can't be accessed by another)

Solution: Use relative address (Position Independent Code)

Disadvantage: A bit slower than absolute address

First step to virtual memory: Always add the base register

P1_base <= M + P1_base < P1_bound: M is the virtual address

Now, absolute address can be used via virtual address
Each process has 8 base-bound pairs:



Disadvantage: External fragmentation still exists which makes it hard to grow domains
Virtual address

Disadvantage: Segment sizes are limited

Paging

Early X86 had rw permissions but not x (r is used to imply x)
Nowadays, x is added to help detect buffer overruns

Page size = 2^12 = 4096 bytes
4 bytes in virtual memory table (an entry) represents 4096 bytes of virtual memory (a page)

With 1-level page table, 2^22 = 4 MB is needed for page table per process in X86, which is too large
So 2-level page table is applied




Program can use more than physical memory: Swap space in Linux

Disadvantages:
• Performance can be very bad
• Require locality of referrence to be practical, otherwise, you thrash (frequency of it depends on applications)

How does kernel treat page faults

At start, the process traps. The kernel must deal with the page fault

	// pfault(va, cp, atype): va is virtual address, cp is current process's pointer and atype is access type
	void pfault(void *va, struct proc *cp, int atype)
	{
		/* tell where this page should live on disk, return 0 if invalid
		 * otherwise address in swap space
		 * kernel maintains its own page table in a software-defined
		 */
		if (swapmap(va, cp) == 0)
			kill(cp, SIGSGSV);
		else
		{
		/*
		 *	vppn, vaa = removal_policy();
		 *	write out vppn to disk
		 *	record in desired page to save physical transaction
		 *	page_table[vaa] = 0;
		 *	page_table[va] = vppn;
		 */
		}
	}