What is the ARIES Recovery Algorithm ?

'Algorithms for Recovery and Isolation Exploiting Semantics', or ARIES is a recovery algorithm designed to work with a no-force, steal database approach; it is used by IBM DB2, Microsoft SQL Server and many other database systems.

Three main principles lie behind ARIES:
- Write ahead logging: Any change to an object is first recorded in the log, and the log must be written to stable storage before changes to the object are written to disk.
- Repeating history during Redo: On restart after a crash, ARIES retraces the actions of a database before the crash and brings the system back to the exact state that it was in before the crash. Then it undo the transactions still active at crash time.
- Logging changes during Undo: Changes made to the database while undoing transactions are logged to ensure such an action isn't repeated in the event of repeated restarts.

The ARIES recovery procedure consists of three main steps :
- Analysis : It identifies the dirty (updated) pages in the buffer and the set of transactions active at the time of crash. The appropriate point in the log where REDO operation should start is also determined.
- REDO phase : It actually reapplies updates from the log to the database. Generally the REDO operation is applied to only committed transactions. However, in ARIES, this is not the case. Certain information in the ARIES log will provide the start point for REDO, from which REDO operations are applied until the end of the log is reached. Thus only the necessary REDO operations are applied during recovery.
- UNDO phase : The log is scanned backwards and the operations of transactions that were active at the time of the crash are undone in reverse order. The information needed for ARIES to accomplish its recovery procedure includes the log, the transaction table, and the dirty page table. In addition, checkpointing is used.

DATA STRUCTURES USED IN ARIES RECOVERY ALGORITHM :
Log records contain following fields :
- LSN
- Type (CLR, update, special)
- TransID
- PrevLSN (LSN of prev record of this txn)
- PageID (for update/CLRs)
- UndoNxtLSN (for CLRs)
* indicates which log record is being compensated
* on later undos, log records upto UndoNxtLSN can be skipped
- Data (redo/undo data); can be physical or logical.

Transaction Table :
- Stores for each transaction:
* TransID, State.
* LastLSN (LSN of last record written by txn).
* UndoNxtLSN (next record to be processed in rollback).
- During recovery:
* Initialized during analysis pass from most recent checkpoint.
* Modified during analysis as log records are encountered, and during undo.

Dirty Pages Table
- During normal processing :
* When page is fixed with intention to update
"Let L = current end-of-log LSN (the LSN of next log record to be generated).
" if page is not dirty, store L as RecLSN of the page in dirty pages table.
* When page is flushed to disk, delete from dirty page table.
* Dirty page table written out during checkpoint.
* (Thus RecLSN is LSN of earliest log record whose effect is not reflected in page on disk).
- During recovery :
* Load dirty page table from checkpoint.
* Updated during analysis pass as update log records are encountered.

Checkpoints :
- Begin_chkpt record is written first.
- Transaction table, dirty_pages table and some other file mgmt information are written out.
- End_chkpt record is then written out.
* For simplicity all above are treated as part of end_chkpt record.
- LSN of begin_chkpt is then written to master record in well known place on stable storage.
- Incomplete checkpoint.
* if system crash before end_chkpt record is written.
- Pages need not be flushed during checkpoint
* They are flushed on a continuous basis.
- Transactions may write log records during checkpoint.
- Can copy dirty_page table fuzzily (hold latch, copy some entries out, release latch, repeat).

First-Come-First-Served (FCFS) Scheduling

First-Come-First-Served algorithm is the simplest scheduling algorithm is the simplest scheduling algorithm. Processes are dispatched according to their arrival time on the ready queue. Being a non-preemptive discipline, once a process has a CPU, it runs to completion. The FCFS scheduling is fair in the formal sense or human sense of fairness but it is unfair in the sense that long jobs make short jobs wait and unimportant jobs make important jobs wait.
FCFS is more predictable than most of other schemes since it offers time. FCFS scheme is not useful in scheduling interactive users because it cannot guarantee good response time. The code for FCFS scheduling is simple to write and understand. One of the major drawback of this scheme is that the average time is often quite long.

CHARACTERISTICS :
o Non-preemptive.
o Ready queue is a FIFO queue.
o Jobs arriving are placed at the end of queue.
o Dispatcher selects first job in queue and this job runs to completion of CPU burst.

Advantages:
- Simple.
- Low overhead.
Disadvantages:
- Inappropriate for interactive systems.
- Large fluctuations in average turnaround time are possible.

Example :
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3.
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17

Suppose that the processes arrive in the order P2 , P3 , P1.
Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case.

Overview Of Mutual Exclusions in Operating Systems

A way of making sure that if one process is using a shared modifiable data, the other processes will be excluded from doing the same thing.
Formally, while one process executes the shared variable, all other processes desiring to do so at the same time moment should be kept waiting; when that process has finished executing the shared variable, one of the processes waiting; while that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed. In this fashion, each process executing the shared data (variables) excludes all others from doing so simultaneously. This is called Mutual Exclusion.
Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code where a process or thread accesses a common resource. The critical section by itself is not a mechanism or algorithm for mutual exclusion. A program, process, or thread can have critical section in it without any mechanism or algorithm, which implements mutual exclusion.
Examples of such resources are fine-grained flags, counters or queues, used to communicate between code that runs concurrently, such as an application and its interrupt handlers. The problem is acute because a thread can be stopped or started at any time.

How Mutual Exclusion is Done ?
We need to stop the two threads from working on the same data at the same time. The most common way to do this today is by using locks. A lock can be either locked or unlocked. As long as you do not forget to lock or unlock the door, this algorithms guarantees mutual exclusion and protects the so called critical region.
C:
1. omp_set_lock (&my_lock);
2. i++;
3. omp_unset_lock (&my_lock);
Actually, the lock needs to be initialized beforehand and destroyed sometime afterwards as well, but that's not too difficult either.
C:
1. #pragma omp critical
2. {
3. i++;
4. }
Or even simpler, like this:
C:
1. #pragma omp atomic
2. i++;
This basically does the same thing, except you do not need to worry about initialization and destruction of the lock and you cannot forget to unlock the mutex accidentally.