Give an advantage and a disadvantage of direct access cache compared to associative cache.
A: It is faster to search for a page in the cache, because we know exactly where to look for it.
D: We cannot have multiple pages with the same index in the cache, so we might have to remove a page from the cache even if it is still needed.
Give an advantage and a disadvantage of associative cache compared to direct access cache.
A: Associative cache allows any memory block to be placed in any cache line, offering more flexibility in block placement.
D: Associative cache requires additional hardware for performing the tag comparison across all cache lines simultaneously.
Give an advantage and a disadvantage of set-associative cache compared to associative cache.
A:
Given two set-associative caches, one with 2 sets of 4 pages and one with 4 sets of 2 pages, which would perform better for the sequence of page requests: 17, 2, 37, 6, 9
We have 2 caches.
Using set-associative caches, in order to place a page in cache:
First one with 2 sets of 4 pages. Lets say pages 0,1,2,3 are in set 0, pages 4,5,6,7 are in set 1.
17 mod 2 = 1 -> it could go on page 4
2 mod 2 = 0 -> it could go on page 0
37 mod 2 = 1 -> it could go on page 5
6 mod 2 = 0 -> it could go on page 1
9 mod 2 = 1 -> it could go on page 6
The second one has 4 sets of 2 pages. Lets say pages 0, 1 are in set 0; pages 2, 3 are in set 1; pages 4, 5 are in set 2; pages 6, 7 are in set 3;
17 mod 4 = 3 -> it could go on page 6
2 mod 4 = 2 -> it could go on page 4
37 mod 4 = 1 -> it could go on page 2
6 mod 4 = 2 -> it could go on page 5
9 mod 4 = 1 -> it could go on page 3
Neither cache runs out of space for a given set for these pages, so neither one is forced to first offload a page.
The first cache has 3 pages for which the first page was not free, while the second cache has 2 pages for which the first cache page was not free.
Thus, I think the second one would perform better in this case, but I don't think there would be a very big difference.
Given two set-associative caches, one with 2 sets of 4 pages and one with 4 sets of 2 pages, which would perform better for the following sequence of page requests: 20,9,18,27,20,9,18,27
First one with 2 sets of 4 pages. Lets say pages 0,1,2,3 are in set 0, pages 4,5,6,7 are in set 1.
20 mod 2 = 0 -> it could go on page 0
9 mod 2 = 1 -> it could go on page 4
18 mod 2 = 0 -> it could go on page 1
27 mod 2 = 1 -> it could go on page 5
20 mod 2 = 0 -> it could go on page 2
9 mod 2 = 1 -> it could go on page 6
18 mod 2 = 0 -> it could go on page 3
27 mod 2 = 1 -> it could go on page 7
The second one has 4 sets of 2 pages. Lets say pages 0, 1 are in set 0; pages 2, 3 are in set 1; pages 4, 5 are in set 2; pages 6, 7 are in set 3;
20 mod 4 = 0 -> it could go on page 0
9 mod 4 = 1 -> it could go on page 2
18 mod 4 = 2 -> it could go on page 4
27 mod 4 = 3 -> it could go on page 6
20 mod 4 = 0 -> it could go on page 1
9 mod 4 = 1 -> it could go on page 3
18 mod 4 = 2 -> it could go on page 5
27 mod 4 = 3 -> it could go on page 7
The second one because it has more sets (slots).
Cache 2 has more sets (4 sets) compared to Cache 1 (2 sets), which means it has a higher degree of associativity. Each set in Cache 2 can hold 2 pages.
For the given page request sequence, Cache 2 can accommodate more pages in parallel due to its higher associativity. The pages can be distributed across multiple sets, reducing the chances of collisions and increasing the cache hit rate.
On the other hand, Cache 1 has fewer sets (2 sets) with each set capable of holding 4 pages. It has lower associativity compared to Cache 2.
Schedule the jobs below (given as Name/Duration/Deadline) so that the sum of their delays is minimised: A/5/7 B/2/4 C/4/13 D/3/8
B: starts at 0, finishes at 2, delay = 0
A: starts at 2, finishes at 7, delay = 0
D: startS at 7, finishes at 10, delay = 2
C: start at 10, finishes at 14, delay = 1
Total delay = 3
Schedule the following jobs (given as NAME/DURATION/DEADLINE) so that they all meet their deadlines: A/22/27, B/2/15, C/4/5
0 + 4 = 4/5 ⇒ C
4 + 2 = 6/15 ⇒ B
6 + 22 = 28/27 ⇒ A
Schedule the following jobs (given as NAME/DURATION/DEADLINE) so that they all meet their deadlines: A/5/9, B/7/13, C/1/10
0 + 5 = 5/9 ⇒ A
5 + 1 = 6/10 ⇒ C
6 + 7 = 13/13 ⇒ B
Schedule the jobs below (given as Name/Duration/Deadline) so that the sum of their delays is minimized: A/3/8, B/10/15, C/3/5
C: starts at 0, finishes at 3, delay = 0
A: starts at 3, finishes at 6, delay = 0
B: start at 6, finishes at 16, delay = 1
Total delay = 1