Memory Management - Paging, Swaping, Partitioning

Bring process into main memory from input queue

Fix Partitioning

1. If using equal size partitions, main memory is divided into fix size partitions initially

• A process whose size <= partition can only be loaded in it. 
• If program large than partition size program has to design it with overlays reduces the OS overhead.
• Could lead to internal fragmentation for small size process
• Process can be loaded into any free partition.

2. If using unequal size partitions, main memory is divided into some unequal partitions initially.

• so a big process can be allocated the large size partitions and for a small size process we can allocate small partition reducing the internal fragmentation
• Process can be loaded in the smallest partition within which it fits.
• A scheduling queue is required for each different size partition which helps swapped out process.
• It minimizes the wasted memory from internal frag.
• But could lead to wastage when the large space remains unused because process will be queued for the other partitions that are smallest fit.

Fix partitioning leads to limit on multiprogramming that is active process in the system

Dynamic Partition

Dynamic partition leads to external fragmentation where portion of memory outside the variable size partition are fragmented.
Solution to external fragmentation problem is compaction to move the free space together.Its time consuming process and complete overhead. Processes must be dynamically relocatable for moving them around in memory
If we are to avoid compaction we can make intelligent assignment of process to memory so as to reduce the external fragmentation
Best fit First Fit and Next Fit. First fit is usually best and fastest.
First fit may lead to holes in the front end of memory. More the fragments in the front end more scanning for first fit



Next fit may lead to more external fragmentation leaving the need for compaction.
Best fits leads to many smaller memory holes leading to more frequent compaction.

Buddy System

compromise between two partitioning

Swapping

Consider at t0 we have some n process taking up the complete memory and at time t1 new process with priority higher than all the n process arrives.And we are using some priority scheduling then this process should get the CPU and should be brought in the main memory but since there is no space we need to swap out some process and bring high priority process in memory and then after its finished or some other swaps out we should swap that low priority process in .

Observations

Swapping was used in the old time sharing systems where memory was enough to load only single process so at end of each time quantum new process was brought in memory by swapping present process.
context switch time would be sum of swapping out and again swapping in process or part of it from backing store.
For efficient utilization of CPU each process execution time should be greater than the overhead i.e swap time.
Swapping is very expensive compared to instruction execution.
Swap time is dependent majorly on the transfer time, so if we move only that much portion of main memory which process is actually using, it would reduce the swap time.
We never swap the process with pending I/O or we execute I/O operations into operating system buffers only
Unix uses a variant of swapping, Demand Paging .

Paging

Allows physical address space of the process to be non contagious
Memory is divided into fixed small size chunks called frames and process into pages
Memory wasted in paging is only due to internal fragmentation and that only fraction in  last page of process.
Differs from fixed partitioning in that
 small partitions
 process can be allocated more that one partition
 non contagious allocation for process is possible
In simple partitioning logical address is location relative to beginning of the program and processor translates logical address to physical address
If Page size is decided as 2^n then remaining bits in the relative address of the process would decide the maximum number of pages allowed in page

In case of paging special hardware is used for logical address to physical address translation.Hardware looks up the logical address in the page table to find the physical address

Fig. logical address divided into offset and page number

Page table

stores mapping between logical address and physical address.
Contains one entry for each page of the process
operating system maintains a copy of page table for each process
Context switch time will increase as page table references need to be changed
If a page table entry is 4 byte long that is 32 bits it can address 2^32 physical page frames and if each frame is 4kb then we can address( 2^32)(2^12) = 2^44 bytes

Fig. lookup for virtual address in page table

Page Table Entry PTE

Each page table entry contain page frame address and property bits like a present bit, a dirty or modified bit, address space or process ID information.
Assuming 32-bit physical address with page size of 2^8, we  use 4 bytes for PTE (24 bit physical page number with 8 bits left for control.)

Sharing and Protection
Reentrant code, non self modifying code can be shared between different process
we map the re-entrant portion of code for each process into same physical frames.
the protection bits in the PTE helps perform certain validation like process is not trying to modify the read only page, that each reference to memory is valid.

Types of Page table

 Multilevel Page table

Since each process can occupy a huge amount of virtual memory that is it can have large number of pages that much entry for each process would be too high.To overcome this we store page table in virtual memory rather than real memory that is page table is divided into pages and when a process is running a part of its page table must be in memory including page that is executing

Fig. two level page table organization

All level page table are actually frames stored in the memory
Each entry in the page table is page frame address of size of  PTE


The format for multilevel page table specifies the offsets for each level page table


Consider  three level page table the logical address is divided into four part
1.offset into page directory or fist level page table.each entry points to page frame containing second level entries
2.offset into page middle directory or second level page table
3.offset into third level page table which specifies page frame
4.offset into page frame.

Fig. format of logical address for 3 level page table

Problem 1

Consider 32 bit Physical address 4KB pages, 4GB virtual address space
Number of pages in virtual address space 4GB/4KB = 2^20
Size of page table would be (PTE size) * (number of pages) = 4byte * 2^20 = 2^22 or 4MB
How many virtual pages would be required = (size of page table) / (size of page) = 4MB/4KB = 2^10
So, a top level page table would have 2^10 page table entries and total size would be = (2^10)(4bytes) = 2^12 i.e 4KB.Hence a two level page table would need 4KB more than single level page table. However, not all the second-level tables need to be resident in memory, and page tables are not needed for unmapped virtual memory. Thus the total usage is actually lower, and only the top-level table must be in memory at all times, requiring only 4KB (exactly one page) of physical memory per process.

Problem 2

consider a three level page table 36 bit physical address
2, 9, 9, 12 bits for first level second third and offset of page respectively
page frame size is 4KB and PTE is 4bytes
what will be number of bits required to address each next level table or page frame
Solution
First find Number of bits required to address a single page frame
Number of frames in the main memory =  (2^36/2^12) = 2^24
so we need 24 bits for addressing a page frame
Since each page table at each level is nothing but page frame addressed by PTE we need 24 bits to address each page frame
First level would be addressed by some process pointer after that each page table will have PTE to address next page frame.

Problem 3 consider a three level page table with
10,8,6,8 bits for first level second, third and offset of page respectively

1. What is the size of a page table for a process of 256K

Solution

Fig . three level page table organization for prob 3

Size of page table =(size of 3rd level table * number of third level page tables required + size of 2nd level        table *  number of second level page tables required + size of 3rd level table * number of first level page tables required)

Number of third level page table = (number of virtual pages) / (number of entries third level can hold)
To calculate number of third level page required we first find
how many pages are required by program or present in virtual address space
number of pages in virtual address space = (size of program ) / (page size)
                                                               = (256K)/2^8 = 2^10
so there should be 2^10 entries in the third level page table but each third level page table can hold 2^6 entries only so 2^10/2^6 =16 third level page table will be required

Number of second level page table = (number of third level page table)/(entries in each second level page    table)
                                                     =16/2^8 ~= 1

Number of first level page table = (number of second level page table)/(entries first level can hold)

                                                 = 1/1024 ~= 1
so size of page table = 1024*4*1+256*1+64*4*16

Note if different section are stored differently like data code stack, where two section could get same offset bits at second level then we need to store this in different page table. Number of second page table will change the first level will have three different entry for each section.

Problem 4 Consider system with 36 bit virtual address space and 8k page size with 4byte PTE.
If virtual address space of process is 8G analyze single two and three level page table organizations.
Solution
For first level page table number of page table
//pending

Inverted Page Table (IPT) with hashing
fixed size page table independent of number of processes and number of pages
entry for each physical frame in memory so if physical address is 32 bit with 8 bits for frame then there are 2^24 entries in the page table.
virtual address division = page number + offset but translation would be
page number portion is mapped into hash value which is pointer to inverted page table. since more than one virtual page number can give same hash value chaining technique is used
each page table entry holds page number,process identifier, control bits and chain pointer. Combination of pid and page identifies a page in virtual address space of a process. chain pointer may contains index value to address same table
system implementing IPT has difficulty implementing shared pages



http://www.cs.utexas.edu/users/dahlin/Classes/UGOS/hw/7bsol.html
http://www.ece.cmu.edu/~ece548/handouts/742sln1b.pdf

Process Synchronization in Operating System

Essential criteria to solve critical section problem

1.Mutual exclusion takes care of race condition.
2.Progress means that no process shall be kept from entering its critical section by another process that is stopped outside its critical section i.e if process j blocks in the remainder section it should not affect the entry of i in the critical section.
3.Bound waiting condition guarantees no starvation.If solution provides strict alternation then bounded waiting is inherently satisfied.If access to critical region is arbitrary then starvation is possible.



Mutual exclusion with Hardware 

1. Disabling the interrupts will ensure mutual exclusion but is not practiced for user processes and it is possible only in uniprocessor system. Disabling interrupt would ensure all 3 condition

2. Hardware provides special instruction that allows modification of a word or swap of words atomically
Test and set lock

• atomic(non interruptible) instruction used to write to a memory location 
• returns old value.
• no other process may begin test and set unless first is complete.
• guarantees mutual exclusion and progress but is prone to starvation. 
• starvation possible because access to critical region is in arbitrary fashion.  

initially set lock = false;

boolean TSL (boolean &lock) {
 boolean tmp = lock;
 lock = True;
 return tmp;
}

process p0 code
while(TSL(lock));
CS
lock = false;

gets the present value of the lock and sets it to true
Conditions
1.At time t0 process  p0 checks the while condition, TSL(lock) return false as lock is false initially, and sets lock = true, so p0 enters critical section.
2.At time t1>t0 process p1 tries to enter the critical section on call to TSL(lock)  it return true and sets lock to true again, so p1 is not allowed to enter critical section unless p0 executes the lock= false condition in exit section.
3.At time t2>t1process p0 has executed the lock = false and TSL(lock) returns false and p1 enters CS.

Exchange instruction (swap)
swap instruction executes atomically 
initially lock=false
code for process p0
key=true
while(key) swap(lock,key)
cs
lock=false;

Disadvantages of hardware instructions busy waiting(wasting cpu resource) and starvation possible.

Mutual Exclusion with software
1. Using lock variable alone does not ensures mutual exclusion.

Fig. software lock solution

2. Turn variable only.

3. Peterson's Algorithm

Allows two process p0 and p1 to share a single resource without conflict

Fig. peterson solution

1. Mutual Exclusion condition requires us to prove that if both process are checking the last statement of beginning section, that is while loop, only one of the process would be able to enter the critical section.
 Since value of turn can be either 0 or 1, turn value is not changed in CS or in remaining section, if it is 0 process 0 will enter and p1 would still be waiting and similar for p1.

2. For Progress we need to check if process blocks in the remainder section it does not affect the entry of other process in its critical section. In peterson solution process j set the flag[j] = 0 before entering in to its remainder section.so if process j now blocks in its remainder section then also process i can proceed with its critical section unlike in dekker's solution where if process blocks in the remainder section no other process can proceed to critical section.

3. Bounded waiting we need to check if one of the process is waiting that is in the while loop then eventually it will break out of loop and enter critical section.

Problems
All this solution has problem of
1. Busy waiting wasting cpu resource, frequent testing and waiting in while loop.
2. priority inversion problem
consider process p0 has low priority than process p1 and when p0 is in its critical section p1 comes, scheduler assigns CPU to p1 as its high priority process now
p1 gets CPU but cannot proceed because p0 is already in critical section(mutual exclusion)  while
p0 now waits for CPU assigned to process p1
process p1 gets into waiting state, before cpu could be assigned to p0 another process p2 arrives with priority less than p1 but greater than p0 this process will get the cpu
after p2 finishes p0 get the cpu and executes until it exits the critical section then p1 will get cpu
giving us priority inversion, low priority  process running before high priority process.

//here goes wake and sleep and it sproblems

4. Semaphores
Semaphore solution includes a semaphore variable and two atomic operations P(s) and V(s) semaphore is integer number representing the number of available resources.
if it is 0 means no resource is available and process has to wait.
if it is n means n resource are available and can be allocated.
V(s) executes when resource is released to increment the semaphore value.
semaphore does not distinguishes resources.
prevents race condition and deadlock does not guarantees them.

P(s):
while(1){

if s >= n

  s= s-n;

  break;
}

//here goes semaphore with waiting queue and wake up, sleep

semaphore with waiting queue can result in deadlock and also starvation if queue is LIFO


References

http://www.disi.unige.it/person/DelzannoG/SO1/AA0607/peterson.htm
http://en.wikipedia.org/wiki/Peterson%27s_algorithm
www.arl.wustl.edu/~fredk/Courses/cse422/sp03/.../concurrency1.ppt

Process Scheduling - Operating System Notes

Parameters affecting Process Scheduling decisions

• CPU utilization decreases by overhead of context switching.

• Thoughput is number of completed process per unit time and would increase if shortest task are executed firsts

• Turnaround time is time between submission of process and its completion. Average turnaround time is minimized by executing shortest tasks first

• Waiting Time time spent in ready queue. It is also minimized when shortest tasks are executed first

• Response time is increased if context switching is infrequent.
• response time is the (time of first result from system  - time of process submission)
• if process is submitted at time t0 and it is scheduled at time tn for for time t then response time is (tn+t) - t0

• run time of process = Turnaround time - waiting time 

• cpu utilization for n process = 

                    sum(run time of n process)/{sum(run time of n process) + sum(all contextswitch)}

• Penalty Rate = turnaround time / run time of process

• When calculating the turnaround time, waiting time response time, context switching time should be added it may be little when there are fewer context switch but may be significant as context switch increases.
• So by running shortest jobs  following parameters are optimized .
• Throughput , turnaround time, waiting time and also CPU utilization because no reorganization of the process queue is required, scheduling overhead is minimal.

Schedulers

• In Preemptive scheduling transitions from running to ready state .Special hardware is required for preemptive scheduling ,affects the design of kernel

• The scheduling algorithm in which there is  prioritization or are premptive may lead to starvation because a high priority process will always  hog the cpu.there wont be starvation in non premtive scheduling

First Come First Serve (FCFS) process scheduling

• cpu utilization is optimal because least possible context switch, on process completion only

• Throughput, turnaround time, average waiting time and response time not optimal as long process can hog the cpu.

Shortest  Job First (SJF) non premptive process scheduling

• CPU utilization is optimal

• Average waiting time is optimal among all non preemptive schedulings

• throughput is optimal in all non preemptive scheduling

Shortest Remaining Time First (SRTF) premptive SJF process scheduling

• includes overhead of more context switching and also to position the process in queue

• CPU utilization not optimal as context switch increases
• maximum throughput if correct estimates for cpu burst and if context switch negligible
• Average turnaround time is less than SJF as newly arrived short burst process would be executed first which reduces the waiting time of short burst process.
• Starvation is possible.

Round Robin (RR) scheduling

• High context switching hence low cpu utilization
• optimal response time
• thoughput between FCFS and SRT
• no starvation. 
• round robin is good for short jobs
• Average turnaround time is greater than in SJF  but average waiting time is less than in SJF
• If time quantum q is increased ,

•  Average Turnaround time will decrease

•  Average waiting time will increase

• FCFS is RRS with infinite time quantum

Observations about Round Robin scheduling
if we have process p1 with alternating burst of t1 for cpu and t2  for i/o the result of the computation will be visible only after the i/o is done that is response time would be t1+t2 and not t1
Response time if all n process are active then response time = n*(q+s) under certain conditions when q is greater than cpu burst
Two i/o operations of process p1 and p2 are performed in parallel if they wait for different resource, until specified otherwise , that is p2 does not have to wait



Problem 1  Consider n processes sharing the CPU in a round-robin scheduling.  Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but, at the same time, each process is guaranteed to get its turn at the CPU at least every t seconds (i.e., it is idle for no more than t seconds between time slices)?

Solution

next execution of the process should occur within t seconds

Each process runs for q period and if there are n process
p1 p2 p3 ..... pn p1 p2 ... then p1 turn comes again when it has completed time quanta for remaining process p2 to pn  i.e it would take at most (n-1)q time
So Each process in round robin gets its turn after <= (n-1)q time when we don't consider overheads
but if we consider over head(s) then it would be ns+(n-1)q
So we have ns + (n-1)q <= t
overhead will be reduced when time quantum is maximum allowable i.e,  q = (t-ns)/(n-1)

Problem 2 consider 10 identical process intiated at same time with 15 identical requests
Each request consumes 20 ms of CPU A request is followed by I/O that consumes 10ms The scheduling overhead is 2ms. Find response time for first and last request when
1) time quantum q >= 20ms and
2) time quantum q =10 ms
Solution
Gantt chart
p1 s p2 s p3 s .................p10 s p1 s p2 s ........p10 s p1 s
first requests                               second requests for each process
assuming output recieved after q+s
response time for first process first request = 20 + 2 = 22ms
response time for last process first request =  (20+2) *10 = 220ms
For second run each process first spends 10ms in the I/O wait then makes request
so time quantum q will be spent as
10msec i/o wait + 10 cpu
second request is made after 10ms i/o wait
and result of second request will occur on third run after completing the 10ms CPU
response time for first process second request = 10(on second run)+2+ 9(20+2) + 10(third run) = 10*(20+2)
similarly for all other processes also same time would be incurred

when q=10ms
that is even the first request will not complete on first run
(10+2)*10 // first completion
10+2  //now 20ms CPU for process 1 completes
that is 11*(12)ms for completion of first process first request
For last process it would be (10+2)*10+(10+2)*10 = 240ms
For subsequent request each has to spend one cycle in I/O and then similar way we have to add above time

//pending
link

Refrences
http://en.wikipedia.org/wiki/Scheduling_(computing)
http://read.cs.ucla.edu/111/notes/lec7?do=index
http://people.engr.ncsu.edu/efg/501/f97/solutions.html

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

Graph Theory Problem solutions links

www.geometer.org/mathcircles/graphprobs.pdf
http://www.mpi-inf.mpg.de/~pascal/graphtheory_exercises.html  --very good set of questions , with solutions
www.math.udel.edu/~lazebnik/papers/688hwsols.pdf    --graph theory and combinatorics part 1
http://www.math.udel.edu/~lazebnik/papers/689H1-4S.pdf  --graph theory and combinatorics part 2