Locking Protocol for concurrency control

Two way phase locking 2PL

guarantees conflict serializability
may be subjected to deadlocks
doesnot guarantees cascading rollbacks
In expanding phase, number of locks can only increase
In shrinking phase locks only released

2PL is superset of SS2PL(rigourness)

Strict 2PL
For any two transactions T1, T2, if a write operation precedes a conflicting operation of T2 (either read or write), then the commit event of T1 also precedes that conflicting operation of T2.

Any strict schedule is cascadeless, but not the converse. Strictness allows efficient recovery of databases from failure.

//http://en.wikipedia.org/wiki/Schedule_%28computer_science%29#Strict
Release exclusive lock only after end of transaction that is unlock happens only after commit or abort
guarantees serialiability and recoverable schedule too
read locks can be released
S2PL class of schedule is (2PL intersection Strictness)
release its write locks only after it has ended
read locks are released regularly during phase 2
we need to know the phase 1 end seperate from transaction end


Transaction can be in following states

Running its executing
Ready its programs execution has ended and its waiting to be Ended
Ended or completed It is either commited or Aborted de





SS2PL Strong Strict 2PL (Rigorous )
release both locks only after END
has actully one phase only, no phase 2
SS2pL enforce both conflict serializability and strictness


Deadlock in 2PL


Other enforcing mechanism for serializability
Time stamp ordering


Correctness of database transaction is defined by its
serializability or isolation and its recoverability

relaxing the serializability criteria isolation levels


view and conflict serializability











Problem 1

Determine whether
1)schedule is serializable or not
2)schedule can be produced by 2PL
3)schedule can be produced by Strict 2PL

Schedule S1

T1	T2	T3
		r(D)
w(A)
	r(B)
w(B)
	r(D)
		w(D)

Solution

1) To check the serializability we draw the precedence graph of the schedule

http://www-stud.uni-due.de/~selastoe/?mdl=dbms&mode=precedence

T2--------->T1
 |
 |
 v
T3

Since the graph is acyclic, so its serializable

2)
Non-serializable schedules can not be 2PL or strict 2PL.
Subset of serializable schedules can be 2PL or strict 2PL

2PL protocol says for a transaction all locks should be requested before releasing any lock

T1	T2	T3
		Ls(D)
		r(D)
Lx(A)
w(A)
	Ls(B)
	r(B)
	Ls(D) U(B)
Lx(B)
w(B)
U(A) U(B)
	r(D)
	U(D)
		Lx(D)
		w(D)
		U(D)

 Fig. showing how 2 phase locking protocol works for this schedule


Here  transaction requested shared lock for read and exclusive lock for write
Shared locks on data item are compatible like here T2 requested shared lock on data item D which was shared locked by T3.

If we look at only the transaction lock requests we can see that for each transaction we first requested all the
locks before releasing any

T1	T2	T3
		Ls(D)
Lx(A)
	Ls(B)
	Ls(D) U(B)
Lx(B)
U(A) U(B)
	U(D)
		Lx(D)
		U(D)

 Fig showing only the lock request and lock release for all transactions



Ls = shared lock
Lx = Exclusive lock
 U = Unlock



converting shared lock to exclusive lock is part of growing phase while
converting exclusive lock to shared lock is part of shrinking phase

Problem read to write lock and write to read lock conversions
Solution A read lock can be converted to write lock if no other readers, this converion happens by first unlocking the data item and then acquiring the write lock, if the request are already queued by some other processes for write lock might not get lock instantly
write to read is always possible.

If transaction Ti has shared lock and transaction Tj request exclusive lock on same item first transaction Ti has to release the lock and then transaction Tj can acquire the lock

Problem consider schedule  S =T1 R(x), T2:R(Y) ,T1:W(z) , T1:commit, T3:R(y) , T3:r(z) ,T2 w(y), T3: w(x),T2:commit , T:commit

2PL
T1           T2            T3
Ls(x)
r(x)
               Ls(y)
               r(y)
Lx(z)
w(z)
U(x)U(z)
commit;
                                Ls(y)
                                 r(y)
                                Ls(z)
                                 r(z)
                                 Lx(x) U(y)
                 Lx(y)
                 w(y)
                 U(y)
                commit;
                               w(x)
                               U(x)
                              commit;

Strick 2PL would require that T2 gets the Lx(y) while T3 has shared lock on y but T3 commits after T2 request so it cannot get the Lx(y)

In the 2PL we are allowed to read or write even after some unlock only condition is no lock can come after first unlock

In S2pL all exclusive lock unlocks comes at the end after commit or abort

Dealing with Deadlock
Deadlock Prevention
A transaction locks all data item it refers to before execution this prevents deadlocks since transaction never has to wait
Another approach is to impose ordering on all the data items and to require that transactions lock data items only in sequence consistent with ordering  example tree protocol

Conservative 2PL uses this approach

Deadlock detection and resolution
wait for graph,created using lock table, is kept which is used to detect the  cycle  and then one of the transaction is rolled back
transactions are added to wait for graph as they get blocked

Deadlock Avoidance
some avoid deadlock by not letting the cycle to  complete, if discovers that blocking a transaction is likely to create a cycle it rollback the transaction
wound wait and wait die algorithms use timestampt to avoid deadlock by rolling back victim

Starvation
particular transaction never gets a chance to proceed further

 Timestamp Protocol
selects ordering among transaction in advance instead at time of execution

timestamp monotonically increasing
timestamp is assigned by system before transaction starts
timestamp for transaction determines serializability order thus if Ti < Tj then system must ensure that Ti appears before transaction Tj in schedule

we associate with each data item Q two timestamps
W-timestamp(Q) largest timestamp of any transaction that executed write (Q) successully
simliarly R-timestamp(Q) for read

Timestamp ordering Protocol
ensures conflict serializability
ensures freedom  from deadlock since no transaction ever waits , its just killed
possibility of starvation
can generate schedules not recoverable but can be guaranteed in several ways

1) when transaction T issues write(X)  check if
read_TS(X) > TS(T) or write < TS then some younger transaction has already read the data item X so abort
and rollback T
when transaction issues read(X)
if younger  transaction has already written to the data item X abort and rollback T
ensures that any conflicting operations are executed in timestamp order

Strict Timestamp Ordering
ensures strict schedule along with conflict serializable
instead of writing when transaction has higher timestamp then on data item it waits until transaction that wrote value of data item commits or aborts

Thomas write Rule
does not ensures conflict serializability
1)IF read_ts(X) >TS(T) that is some younger transaction read the data item before T
abort and rollback T and reject operation
2)write_ts(x) > ts(T) donot execute the write but continue and will be detected in 1)

Cache memory - Direct mapped, Set Associative, Associative ,Performance

 Direct mapped Cache

Mapping function 

Each main memory block can be mapped to only single cache line like ,
 each 0, m,2m ... block can be assigned to cache block 0
 each m+1, 2m+1, 3m+1 ... block can be assigned to cache block 1

cache line number  = (main memory block number) mod number of cache lines
                            = (main memory address / Block size) mod number of cache lines
                            = (M_d/B) mod m

Problem 1

A two dimensional byte array A[50][50] is stored in main memory starting address 0x1100 in row major order. Direct mapped cache is used with 32 line.
If array is accessed in following order

for (int i=0;i< M; i++)
 for (int j= 0;j
    A[i][j] = 0

1)Find number of cache miss assuming cache is empty initially.
2)consider same code to run again, one more time after first scenario then find total cache miss.
3) If the size of array element is t Bytes  then find total cache miss for single array access.
4) What difference would it make if we had fully associative cache.

Solution 1.1

Array is accessed in order


A[0][0], A[0][1] ....  A[0][N-1] .... A[M-1][0],A[M-1][1] ...A[M-1][N-1]

First element A[0][0] is stored at address (0x1100)_H = (1048576)_d in decimal

Cache line to which element A[0][0] will be mapped
  = (main memory block number) mod number of cache lines
  = (main memory address / Block size) mod number of cache lines
  = (1048576 / 64) mod 32 = 0



so first element is mapped to first cache line and complete block of 64 bytes are moved
i.e elements A[0][0] to A[0][49] and A[1][0] to A[1][13](64th element of two dimensional array) will be moved in cache line zero

Next reference to A[0][1] will be a hit and so till A[1][13](64rd element of array)

Fig. shows organization of main and cache memory

Each Bth(block size) element will be miss because first element in every new memory block will not be present in cache.


i.e number of miss will be ceil(MN/B) for array A[M][N] for this case

= ceil(50x50 / 64) = 40

Fig shows state of cache memory

number of blocks that will be overwritten on first array access is ceil(MN/B) - m

= 40-32
= 8

Solution 1.2

On first run of function we had 40 cache miss  and first 8 blocks were overwritten.


Now array elements are accessed again from A[0][0]

Assuming it as first run then there would be ceil(MN/B) = 40 cache miss
But since we already have data from previous run in the cache memory of which we had overwritten first 8 blocks so
remaining 32 - 8 = 24 are still present in cache memory and we will have hit for that may elements
So number of cache miss will be 40-24 = 16

Therefore Total number of cache miss after two run of function would be 40 + 16 = 56

Solution 1.3

When transferring block to cache from main memory  we moved 64 elements earlier which lead to miss on every 65 element
Now in a block we can accommodate (B/t) elements Hence transfer would be for next B/t -1 elements along this one.  Hence every (B/t) will give result in a cache miss here


So we will have (MN/(B/t)) cache miss.

Associative Mapping

main memory block can be loaded in to any cache line
address is interpreted as just tag and word instead of line because which ever line is empty we put block into that
number of lines in cache is not determined by address format unlike as in Direct mapped

Set Associative Cache

cache is divided into v sets each consisting of k lines
k-way set associative mapping that is there are k possible lines in which the same mapped blocks can go.

cache line number  = (main memory block number) mod number of sets v
                            = (main memory address / Block size) mod (number of cache line/k)
                            = (M_d/B) mod m/k
memory address is interpreted as tag set and word
tag+set specify a block in main memory

when memory address is presented from CPU it indexes with set bits in cache to find set where would could be It then compares tag bits with every tag field of line in set and if there is match then it addresses the word in that line
number of cache lines
here tag comparison is only to k possible


Problem  A 64KB cache has 16 byte blocks. If addresses are 32 bits, how many
bits are used the tag, index, and offset in this cache?
a)if cache is direct mapped
Solution
number of bits for addressing word= 4bit
number of cache lines = size of cache / size of block = 64KB/16B = 4K = 12bits
remaining 16 bits for tag so  division of 32 bits is like
16bit  12bit  4bit


b)if cache is 4-way set associative
number of bits for addressing word are same 
number of lines/blocks in each cache set is 4 
so each cache set is 4*16B = 64B
number of cache sets = size of cache/size of cache set = 64KB/64B = 1K 
so 10 bits for cache set/index
so division of 32 bits is like 
18bit tag  10bit index  4bit word


c)for fully asscociative cache
number of index bits = 0 because any block can be stored in any line


Problem Consider following
cache size 8 byte, 
2-way set associative
2 byte block size with
LRU replacement
request for addresses
0110, 0000, 0010, 0001, 0011, 0100, 1001, 0000, 1010, 1111, 0111
determine address in cache and miss/hit
Solution 
number of lines/blocks in each set = 2
size of cache set = 2*2 B = 4B
number of cache set = 8B/4B = 2 
division of 4bits address
2bit tag  1bit index 1bit word


2 bytes(block) are moved for each address so next address would be also brought in cache 
here index maps directly into 0 or 1 cache set
if index is 1 its set 1 and if bit is 0 its set 0

1) for address 0110
index is 1 so it goes in  set 1
set 0  --------
         ---------
set 1 01------(address 0110 and 0111) 
       ----------
its compulsory miss because first reference of 0110
2)0000
index 0
set 0  00------(address 0000 0001)
         ---------
set 1 01------(address 0110 and 0111)
       ----------
its compulsory miss because first reference of 0000
3) similarly for 0010 its compulsory miss and placed in set 1 line 2 with next byte 0011
4), 0001 its hit because its in set0 line1
5)0011 hit
6)0100 compulsory miss mapped to set 0 line 2 with next byte 0101
7)1001 is first reference hence compulsory miss it will replace content of set 0 line based on LRU


set 0  (0000 0001)
         (0100 0101)
set 1  (0110 0111) 
         (0010 0011)
0000 is reference least recently so its replaced in line1
and line 1 would be now (1001 1010)
8)0000
it 0000 second reference and its miss so its conflict miss 
replaces with LRU its 0100 second line so now set 0 line 2 is 0000 0001
9)1010 compulsory miss mapped to set 1 line 1 because 0110 should be replaced 
now content of set1 line 1 is 1010 1011
10)1111 compulsory miss mapped to set 1 line 2
set 1 line 2 1111 0011
11)0111
we brought this block into cache but was replaced without use so
its capacity miss




Types of cache miss
Compulsory miss: when block is accessed for first time its called first reference miss, cold start miss or compulsory miss
Capacity miss: when blocks are discarded because cache cannot contain all blocks needed for program execution. when block is discarded before its use
Conflict miss: when several blocks are mapped to same cache set/block. Occurs in case of direct mapped and set associative cache




Cache performace
number of memory stall = number of miss  * miss penalty(cost per miss)
number of miss = IC * misses/instruction
miss/instruction =number of memory access/ instruction * miss rate






Problem Consider CPI = 1, only data access are load and store which makes 50% instructions 
miss penalty =25clock cycles, miss rate 2%
Solution 
number of memory access per instruction is 1 for instruction and .5 for data 
Memory stall cycle = IC * (1+.5)* .02*25 = .75*IC
cpu execution time = (cpu clock cycle + memory stall cycle) * clock cycle
with cpu with all cache hits its =  (IC*CPI ) * clock cycle
for cache its .2 miss rate ts  (IC*CPI +IC*.75) * clock cycle =1.75*IC * clock cycle
the computer with no cache miss is 1.75 times faster


Problem Consider CPI for ALU=1, Load/Store=1.5,  Branch=1.5, Jump=1. instruction mix of 40% ALU and  logical operations, 30% load and store, 20% branch and 10% jump instructions.
4-way set associative cache with separate data and instruction cache 
 miss rate of 0.20 for data and miss rate of  0.10 for instructions
miss penalty of 50 cycles for both . What is the effective CPU time (or effective CPI with memory stalls) and the average memory access time for this application with this Cache organization?
Solution
CPI ideal =(0.4*1)+(0.3*1.5)+(0.2*1.5)+(0.1*1) = 1.25.
memory stalls = number of memory access/ instruction * miss rate *miss penalty
.3 load/store data operations
1 instruction 
memory stall = .3*.2*50 + 1*.1*50 =8
Average memory access time = percentage of data accesses (hit time + data miss rate* miss penalty) +
percentage of inst. Accesses (hit time + inst.miss rate*miss penalty).
Therefore AMAT = (0.3/1.3)(1 + 0.2*50) + (1/1.3)(1+ 0.1*50).


b)Now consider a 2 level 4-way unified cache with a level l (L1) miss rate of 20% (0.20) and a
level 2 (L2) local miss rate of 30% (0.30). Assume hit time in L1 is 1 cycle, assume miss penalty
is 10 cycles if you miss in L1 and hit in L2 (i.e., hit time in L2 is 10 cycles), and assume miss
penalty is 50 cycles if you miss in L2 (i.e., miss penalty in L2 is 50 cycles). Derive the equation
for the effective CPU time (or effective CPI) and the average memory access time for the same
instruction mix as part (a) for this cache organization.

First note that the miss rate for L2 is given as the local miss rate. Average memory accesses per
instruction = 1.3 as noted earlier (0.3 for data and 1 for inst).


Cache miss penalty reduction
L2 cache second level cache
average memory access time = hit time(L1) + miss rate(L1) * miss penalty(L1)
miss penalty(L1) = hit time(L2) + miss rate(L2) * miss penalty(L2)
Local miss rate is total number of miss in cache divided by total number of access to cache
Global miss rate is total number of misses/ total number of CPU accesss
for L2 global miss rate is  miss rateL1 * miss rate L2
for L1 global and local miss rate is same

Write policy
write through written to both block in cache and to lower memory
write back written only to block in cache .Modified block is written to memory only when it is replaced. write occurs at speed of cache memory, less memory bandwidth required save intermediate writes. Read miss can result in writing the 
cpu wait during write through is called write stall. 
write allocate  a block is allocated on write miss that is a block is written in memory so next time it will be hit
no write allocate until read miss no block is allocated


www.seas.gwu.edu/~bhagiweb/cs211/homeworks/hw4-sol.pdf

References:

http://www.cs.lth.se/EDA115/    -- Cache memories Problem solutions

Multilevel index - Blocking factor

Why use Multilevel index?
In ordered sequential file number of block access required is log(2,b) where b is number of blocks to store the index file. Multilevel index were introduced to reduce the number of block access to access the record 

Number of block access required for multilevel index is log(bfr,b)
so number of access are less if bfr is greater than 2 for multilevel index than for ordered index file

Blocking factor

bfr  =  B/R =  (block size / record size)
blocking factor or fan out of multilevel index specifies number of records that can be accumulated in single block or records per block

Problem 1.1

Consider ordered data file with following parameters

r (number of records) = 16348
R (record size) = 32 bytes
B (block size) = 1024 bytes

index stored as key + pointer pair

key value = 10 bytes
block pointer = 6 bytes

Find the number of first level and second level blocks required for multilevel index on this

Solution:

Number of First level Blocks

Lets find Number of blocks in data file

Number of records that can be accumulated in block i.e
Blocking factor  bfr  = 1024/32 = 2^5
so, can have 32 records in a block

now how many such blocks are required for 16348 records

number of blocks required for data file =  (r/bfr)
                                                          = 16348/ 32  ~=  511

now we know we need 511 entries in the first level index

primary level of multilevel index and data file

Find 511 entries can be stored in how many blocks
i.e  how many blocks in first level of multilevel index will be required to store this much entries where each entry is of 16 bytes(key + pointer size)

R' = 16
B = 1024
bfr' = 1024/16 = 2^6

Blocking factor or fan-out for first level and its subsequent levels will be same because index entry is of same size

so number of blocks required for 512 entries would be  = r'/bfr'
                                                                                    = 511/64 = 2^3  ~= 8

secondary level index

Number of Second level Blocks

Its clear that only a single second level block would be required to store 8 entries
but lets calculate


Number of entries in second level = Number of blocks in the first level  = 8
Number of blocks in second level = (number of fist level blocks)/(bfr)
                                                    = r''/bfr'

blocking factor bfr' is same here as second level because here also we will be storing key + pointer pair
Number of records are now 8.

So, Number of blocks for second level = 8/64  ~= 1

Problem 1.2

For secondary index on unordered key data file
with same parameters

Solution:

In case of secondary index there is one index entry required for each data record in data file

Number  of First level blocks 

First level index will store index entries for all the records(16348)  in data file

Number of blocks needed for first level index = r/bfr = 16348 / 64 ~= 256
(bfr = 1024/(10+6) )

Number of second level blocks


Number of entries in second level = Number of blocks in first level = 256
bfr = 64 is same and r = 256
so Number of second level blocks = 256/64 = 4

Magnetic Disk Problem Set

Magnetic Disk
bit near center moves slow comparision to bit near end
increasing the spacing between bits in outer tracks so that head can move with CAV
disadvantage amount data in outer and inner track would be same , limited by amount of data that can be stored in inner track
so density increases moving to inner tracks
multiple zone recording
within a zone number of bits per track is constant
zones father from center contains more bits hence better utilization of space
As head moves from one zone to another along same track length of bits changes, causing change in timing for read and write
seek time
= initial startup time + time to traverse tracks
traversal time is not linear that is if it takes t seconds to reach track 4 then it would take 2t to reach track 8 is not the case that is
It also has startup time and settling time


Problem Consider disk with rotation 5400rpm, seek time 4+.05t msec  where t is number of track
1024 tracks,512sector/track,block size 512 bytes.DMA and disk controller read and write data at 4MB/sec
a) capacity of disk
1024*512*512
b)reading 16KB file where sector contagious on track. max and min throughput
maximum th
rotational latency = 1/5400m/rev = 60/5400 sec/rev
it means it takes 60/5400 sec to read a track or 512sectors
so it takes 60/(5400*512) sec =22micro sec to read a sector
In case of maximum throughput we donot have any rotational latency overhead or seek latency It only takes time to move over that many sectors to read
there 16K/512 = 32 sectors in file
so to read 32 sectors it will take 22*32 microsec =694microsec = .694msec
so it takes 694 microsec to read file from the disk
Now we need DMA transfer will take time 16KB/4MB/s = 3.9 msec

Total time is time to get disk from disk + time to transfer via DMA = .694+3.9


For minimum throughput
It has to go for maximum distance to get data that is it has to seek all 1024 tracks and a complete rotational delay to reach data
seek time + latency = 4+.05*1024 + 60/5400


In average case
if there are t tracks, r rpm then
average seek time = t/2 * (per track seek time)
Average rotational delay = 60/ 2r rpm

Worst case
seek time = t * (per track seek time) 
rotational delay 60/ 2r

To read contagious sectors of file
we work on track 
1) For first track we have avg seek time and avg rotational delay overhead
2)For rest of tracks we have track-track seek time

To read non contagious file
we caclulate data for a sector
1)for each sector overhead of avg seek time, avg rotational delay
2) we add the time for all sector for that much number of blocks in file

Cylinder
Both surface of platter and tracks on them form cylinder
if there are p platters and both surface of each platter is used then
A cylinder has 2*p tracks