CS 208 s21 — Learning Block #21

Table of Contents

1 Quick Checks

Which of the following is NOT a source of internal fragmentation?1

  1. Placement policy (e.g., returning a larger block than requested)
  2. Padding for alignment purposes
  3. Pattern of future requests
  4. Memory added to blocks in order to maintain heap data structures

Which of the following statements is FALSE?2

  1. Temporary arrays should not be allocated on the heap
  2. malloc returns the address of a block that is filled with arbitrary data
  3. Memory utilization is affected by both internal and external fragmentation
  4. An allocation failure will cause your program to stop

2 Practice

Assume the heap starts at address 0x1000 with no allocated blocks. brk is at 0x1100. The requests below arrive in the order they are given. The system will allocate a 16-byte aligned block in the first available space after the start of the heap. For each request, give the block size and the address returned to the application.3

  1. malloc(18)
  2. malloc(24)
  3. malloc(10)
  4. malloc(32)
  5. malloc(33)

Does the system need to call sbrk at any point?

3 Working on Lab 4

The problems that follow will help reinforce your understanding of how caches work. Assume the following:

  • The memory is byte addressable.
  • Memory accesses are to 1-byte words (not to 4-byte words).
  • Addresses are 13 bits wide.
  • The cache is two-way set associative (E = 2), with a 4-byte block size (B = 4) and eight sets (S = 8).

The contents of the cache are as follows, with all numbers given in hexadecimal notation.

practice-cache.png

The following figure shows the format of an address (1 bit per box). Indicate (by labeling the diagram) the fields that would be used to determine the following:

  • CO. The cache block offset
  • CI. The cache set index
  • CT. The cache tag

cache-address.png

  1. Suppose a program running on a machine with the above cache references the 1-byte word at address 0x0D53. Indicate the cache entry accessed and the cache byte value returned in hexadecimal notation. Indicate whether a cache miss occurs. If there is a cache miss, enter "—" for "Cache byte returned."4
    • Cache block offset (CO) 0x______
    • Cache set index (CI) 0x______
    • Cache tag (CT) 0x______
    • Cache hit? (Y/N)
    • Cache byte returned 0x______
  2. Repeat for memory address 0x0CB45
    • Cache block offset (CO) 0x______
    • Cache set index (CI) 0x______
    • Cache tag (CT) 0x______
    • Cache hit? (Y/N)
    • Cache byte returned 0x______
  3. Repeat for memory address 0x0A316
    • Cache block offset (CO) 0x______
    • Cache set index (CI) 0x______
    • Cache tag (CT) 0x______
    • Cache hit? (Y/N)
    • Cache byte returned 0x______

Footnotes:

1

The pattern of future requests is not a source of internal fragmentation

2

The false statement is an allocation failure will cause your program to stop. When malloc fails, it doesn't crash, but returns NULL. It is the program's job to check this return value and act accordingly.

3
  1. Block size of 32, returns 0x1000
  2. Block size of 32, returns 0x1020
  3. Block size of 16, returns 0x1040
  4. Block size of 32, returns 0x1050
  5. Block size of 48, returns 0x1070

All of these fit below 0x1100, so a call to sbrk is not needed.

4

cache-address1.png

  • Cache block offset (CO) 0x3
  • Cache set index (CI) 0x4
  • Cache tag (CT) 0x6A
  • Cache hit? (Y/N) No
  • Cache byte returned —
5

cache-address2.png

  • Cache block offset (CO) 0x0
  • Cache set index (CI) 0x5
  • Cache tag (CT) 0x65
  • Cache hit? (Y/N) No
  • Cache byte returned —
6

cache-address3.png

  • Cache block offset (CO) 0x1
  • Cache set index (CI) 0x4
  • Cache tag (CT) 0x51
  • Cache hit? (Y/N) No
  • Cache byte returned —