[Skip Navigation]
2018-03-21
User Icon

Mar 21 In-class Exercise Thread.

Post your solutions to the Mar 21 In-Class Exercise to this thread.
Best,
Chris
Post your solutions to the Mar 21 In-Class Exercise to this thread. Best, Chris
User Icon
-- Mar 21 In-class Exercise Thread
1. 1,0,1,2, 1,0,2
2. Cache = []
  R1: Cache = [1,]
  R2: Cache = [1,0]
  R3: Cache = [1,0]
  R4: Cache = [1,2] MISS
  R5: Cache = [1,2]
  R6: Cache = [0,2] MISS
  R7: Cache = [0,2]
3. Cache = []
  R1: Cache = [1,]
  R2: Cache = [1,0]
  R3: Cache = [1,0]
  R4: Cache = [1,2] MISS
  R5: Cache = [1,2]
  R6: Cache = [1,0] MISS
  R7: Cache = [2,0] MISS
4. Hk = 1 + 1/2 = 1.5
  Number of cache misses for LRU = 3
  Number of cache misses for LRU > Hk
(Edited: 2018-03-21)
1. 1,0,1,2, 1,0,2 2. Cache = [] R1: Cache = [1,] R2: Cache = [1,0] R3: Cache = [1,0] R4: Cache = [1,2] MISS R5: Cache = [1,2] R6: Cache = [0,2] MISS R7: Cache = [0,2] 3. Cache = [] R1: Cache = [1,] R2: Cache = [1,0] R3: Cache = [1,0] R4: Cache = [1,2] MISS R5: Cache = [1,2] R6: Cache = [1,0] MISS R7: Cache = [2,0] MISS 4. Hk = 1 + 1/2 = 1.5 Number of cache misses for LRU = 3 Number of cache misses for LRU > Hk
User Icon
-- Mar 21 In-class Exercise Thread
 1. let I = [I1,I2, I3]
    Round_1 = I2, I1,I2,I1,I3
    Round_2 = I3,I3,I2,I2,I2,I2,I1
 
 2. cache = [I1,I3]
    I2 - cache Miss eject I3, 
    I1 - cache = [I1,I2]
    I2 - cache = [I1,I2]
    I1 - cache = [I1,I2]
    I3 - cache Miss eject I1 cache = [I2,I3]
Round 1 -----
    I3 - cache = [I2,I3]
    I3 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I1 - cache Miss
end of Round 2 ____
3. cache = [I1,I3]
    I2 - cache Miss eject I1, 
    I1 - cache = [I2,I3] cache miss eject I2
    I2 - cache = [I1,I3] cache miss eject I3
    I1 - cache = [I1,I2]
    I3 - cache Miss eject I1 cache = [I2,I3]
end of Round 1 -----
    I3 - cache = [I2,I3]
    I3 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I2 - cache = [I2,I3]
    I1 - cache Miss eject I3
end of Round 2______ 
  LRU has 5 misses - 4 for the first sequence and 1 for the second sequence

 4. Hk = 1+ 1/2 = 1.5
    Number of cache misses for LRU = 5 > Hk
1. let I = [I1,I2, I3] Round_1 = I2, I1,I2,I1,I3 Round_2 = I3,I3,I2,I2,I2,I2,I1 2. cache = [I1,I3] I2 - cache Miss eject I3, I1 - cache = [I1,I2] I2 - cache = [I1,I2] I1 - cache = [I1,I2] I3 - cache Miss eject I1 cache = [I2,I3] Round 1 ----- I3 - cache = [I2,I3] I3 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I1 - cache Miss end of Round 2 ____ 3. cache = [I1,I3] I2 - cache Miss eject I1, I1 - cache = [I2,I3] cache miss eject I2 I2 - cache = [I1,I3] cache miss eject I3 I1 - cache = [I1,I2] I3 - cache Miss eject I1 cache = [I2,I3] end of Round 1 ----- I3 - cache = [I2,I3] I3 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I2 - cache = [I2,I3] I1 - cache Miss eject I3 end of Round 2______ LRU has 5 misses - 4 for the first sequence and 1 for the second sequence 4. Hk = 1+ 1/2 = 1.5 Number of cache misses for LRU = 5 > Hk
User Icon
-- Mar 21 In-class Exercise Thread
 1. I = {1,2,3}
    r1 = 2
    r2 = 3
    r3 = 1
    First round  : 2, 2, 1, 1,3
    Second round : 3, 3, 2, 1

 2. Initial Cache = {2,1}
    Round 1
   Cache = {2,1} for page request 2 (HIT)
 	 = {2,1} for page request 2 (HIT)
 	 = {2,1} for page request 1 (HIT)
 	 = {2,1} for page request 1 (HIT)
 	 = {2,1} for page request 3 (MISS)
 	 = {1,3} 
   Round 2
   Cache = {1,3} for page request 3 (HIT)
         = {1,3} for page request 3 (HIT)
 	 = {1,3} for page request 2 (MISS)
 	 = {1,2} for page request 1 (HIT)
 MIN had two misses as we replaced pages looking forward on what page would be 
 requested
 3. LRU Cache = {2,1}
    Round 1
    Cache = {2,1} for page request 2 (HIT)
 	 = {2,1} for page request 2 (HIT)
 	 = {2,1} for page request 1 (HIT)
 	 = {2,1} for page request 1 (HIT)
 	 = {2,1} for page request 3 (MISS)
 	 = {1,3} 
    Round 2
    Cache = {1,3} for page request 3 (HIT)
         = {1,3} for page request 3 (HIT)
 	 = {1,3} for page request 2 (MISS)
 	 = {3,2} for page request 1 (MISS)
 	 = {2,1}
  LRU had three misses(replaced least recently used page)   

 4. Hk = 1.5
   LRU cache misses = 3 (which is > than Hk)
1. I = {1,2,3} r1 = 2 r2 = 3 r3 = 1 First round : 2, 2, 1, 1,3 Second round : 3, 3, 2, 1 2. Initial Cache = {2,1} Round 1 Cache = {2,1} for page request 2 (HIT) = {2,1} for page request 2 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 3 (MISS) = {1,3} Round 2 Cache = {1,3} for page request 3 (HIT) = {1,3} for page request 3 (HIT) = {1,3} for page request 2 (MISS) = {1,2} for page request 1 (HIT) MIN had two misses as we replaced pages looking forward on what page would be requested 3. LRU Cache = {2,1} Round 1 Cache = {2,1} for page request 2 (HIT) = {2,1} for page request 2 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 1 (HIT) = {2,1} for page request 3 (MISS) = {1,3} Round 2 Cache = {1,3} for page request 3 (HIT) = {1,3} for page request 3 (HIT) = {1,3} for page request 2 (MISS) = {3,2} for page request 1 (MISS) = {2,1} LRU had three misses(replaced least recently used page) 4. Hk = 1.5 LRU cache misses = 3 (which is > than Hk)
User Icon
-- Mar 21 In-class Exercise Thread
 Itemset: {a, b, c}
 Cache has: {a, b}

 1. Round 1: b,c,a,b  Round 2: b,a,a,b

 2. R1. {a,b}
   R2. {a,c} Miss
   R3. {a,c} 
   R4. {a,b} Miss
   
   R1. {a,b}
   R2. {a,b} 
   R3. {a,b}
   R4. {a,b}
   
 3. For LRU
   R1. {a,b}
   R2. {b,c} Miss
   R3. {a,c} Miss
   R4. {a,b} Miss
   
   R1. {a,b}
   R2. {a,b} 
   R3. {a,a} 
   R4. {a,a}
   
 4. Hk = 1+1/2 = 1.5
   LRU has 3 misses 
   Number of cache misses by LRU > Hk
Itemset: {a, b, c} Cache has: {a, b} 1. Round 1: b,c,a,b Round 2: b,a,a,b 2. R1. {a,b} R2. {a,c} Miss R3. {a,c} R4. {a,b} Miss R1. {a,b} R2. {a,b} R3. {a,b} R4. {a,b} 3. For LRU R1. {a,b} R2. {b,c} Miss R3. {a,c} Miss R4. {a,b} Miss R1. {a,b} R2. {a,b} R3. {a,a} R4. {a,a} 4. Hk = 1+1/2 = 1.5 LRU has 3 misses Number of cache misses by LRU > Hk
User Icon
-- Mar 21 In-class Exercise Thread
Round 1 : 0 2 1 Round 2 : 1 1 0 2 cache - []
1 Req: [0,] ; 2 Req: [0,2,]; 3 Req: [0,1,];4 Req: [0,2,] miss; next round 1 req: [1,] ; 2 Req: [ 1,1, ]; 3 Req [1,0] MISS; 4 Req [1,0,] 5 req [0,2] MISS, 6 Req [0,1, ]
Round 1 : 0 2 1 Round 2 : 1 1 0 2 cache - [] 1 Req: [0,] ; 2 Req: [0,2,]; 3 Req: [0,1,];4 Req: [0,2,] miss; next round 1 req: [1,] ; 2 Req: [ 1,1, ]; 3 Req [1,0] MISS; 4 Req [1,0,] 5 req [0,2] MISS, 6 Req [0,1, ]
2018-03-22
User Icon
-- Mar 21 In-class Exercise Thread
1. I = [4,5,6] round 1: 5,4,5,6, round 2: 5,4,6,5 2. initially Cache [5,4] Cache[5,4] Cache[5,4] Cache[5,6] MISS Cache[5,6] Cache[4,6] MISS Cache[4,6] MISS Cache[5,6] 3. Cache = [5,4] Cache = [5,4] Cache = [5,4] Cache = [5,6] MISS Cache = [5,6] Cache = [5,4] MISS Cache = [6,4] MISS Cache = [6,5] MISS 4. Hk = 1 + 1/2 + 1/3 = 1.83 Number of cache misses for LRU = 4 Number of cache misses for LRU > Hk
<nowiki> 1. I = [4,5,6] round 1: 5,4,5,6, round 2: 5,4,6,5 2. initially Cache [5,4] Cache[5,4] Cache[5,4] Cache[5,6] MISS Cache[5,6] Cache[4,6] MISS Cache[4,6] MISS Cache[5,6] 3. Cache = [5,4] Cache = [5,4] Cache = [5,4] Cache = [5,6] MISS Cache = [5,6] Cache = [5,4] MISS Cache = [6,4] MISS Cache = [6,5] MISS 4. Hk = 1 + 1/2 + 1/3 = 1.83 Number of cache misses for LRU = 4 Number of cache misses for LRU > Hk </nowiki>
2018-03-26
User Icon
-- Mar 21 In-class Exercise Thread
1.I = [1,2,3]
  round 1: 2,1,2,3
  round 2: 2,1,3,2
2.Init Cache = [2,1]
  Cache = [2,1]
  Cache = [2,1]
  Cache = [2,3] MISS
  Cache = [2,3]
  Cache = [1,3] MISS
  Cache = [1,3] MISS
  Cache = [2,3]
3. LRU
 Cache = [2,1]
 Cache = [2,1]
 Cache = [2,1]
 Cache = [2,3] MISS
 Cache = [2,3]
 Cache = [2,1] MISS
 Cache = [3,1] MISS
 Cache = [3,2] MISS
4. Hk = 1.83
  Cache misses for LRU > Hk
(Edited: 2018-03-26)
1.I = [1,2,3] round 1: 2,1,2,3 round 2: 2,1,3,2 2.Init Cache = [2,1] Cache = [2,1] Cache = [2,1] Cache = [2,3] MISS Cache = [2,3] Cache = [1,3] MISS Cache = [1,3] MISS Cache = [2,3] 3. LRU Cache = [2,1] Cache = [2,1] Cache = [2,1] Cache = [2,3] MISS Cache = [2,3] Cache = [2,1] MISS Cache = [3,1] MISS Cache = [3,2] MISS 4. Hk = 1.83 Cache misses for LRU > Hk
2018-03-31
User Icon
-- Mar 21 In-class Exercise Thread
1. I = [a,b,c] round 1: b,a,b,c round 2: b,a,c,b 2. Initially, the cache would be: [b,a]
  Cache[b,a]
  Cache[b,a]
  Cache[b,c] Miss
  Cache[b,c]
  Cache[a,c] Miss
  Cache[a,c] Miss
  Cache[b,c]
3. Cache = [b,a]
 Cache = [b,a]
 Cache = [b,a]
 Cache = [b,c] Miss
 Cache = [b,c]
 Cache = [b,a] Miss
 Cache = [c,a] Miss
 Cache = [c,b] Miss
4. Therefore, H_k = 1 + 1/2 + 1/3 = 1.83
  Cache misses for LRU = 4
  Hence, cache misses for LRU > H_k
1. I = [a,b,c] round 1: b,a,b,c round 2: b,a,c,b 2. Initially, the cache would be: [b,a] Cache[b,a] Cache[b,a] Cache[b,c] Miss Cache[b,c] Cache[a,c] Miss Cache[a,c] Miss Cache[b,c] 3. Cache = [b,a] Cache = [b,a] Cache = [b,a] Cache = [b,c] Miss Cache = [b,c] Cache = [b,a] Miss Cache = [c,a] Miss Cache = [c,b] Miss 4. Therefore, H_k = 1 + 1/2 + 1/3 = 1.83 Cache misses for LRU = 4 Hence, cache misses for LRU > H_k
2018-04-01
User Icon
-- Mar 21 In-class Exercise Thread
 1. Round 1 = 2,3,1,3 Round 2 = 2,1,1,2
 2. R1 {2,}
 R2 {2, 3}
 R3 {2, 1} miss
 R4 {3, 1} miss
 
 R1 {2,}
 R2 {2, 1}
 R3 {2, 1}
 R4 {2, 1}
 
 3. R1 {2,}
 R2 {2, 3}
 R3 {1, 3} miss
 R4 {1, 3}
 
 R1 {2,}
 R2 {2, 1}
 R3 {2, 1}
 R4 {2, 1}
 
 4. Hk = 1 + 1/2 = 1.5
1. Round 1 = 2,3,1,3 Round 2 = 2,1,1,2 2. R1 {2,} R2 {2, 3} R3 {2, 1} miss R4 {3, 1} miss R1 {2,} R2 {2, 1} R3 {2, 1} R4 {2, 1} 3. R1 {2,} R2 {2, 3} R3 {1, 3} miss R4 {1, 3} R1 {2,} R2 {2, 1} R3 {2, 1} R4 {2, 1} 4. Hk = 1 + 1/2 = 1.5
[ Next ]
X

 

- Blog - Privacy - Terms - YioopBot - Developed at SeekQuarry -
(c) 2024 Yioop - PHP Search Engine
We use cookies to implement this site's user functionality, social media features, and traffic analytics. Privacy Policy Details. Allow Cookies