代写Midterm - CMPSC 473 SU23 Results for Qianghe Gao代写留学生数据结构程序

2024.06.26 - 首页 >> Matlab编程

Midterm - CMPSC 473 SU23 Results for Qianghe Gao

Question 1

Suppose you get the following from running bt:

(gdb) bt

#0 0x0000555555555371 in tree_size (t=0x0) at

gdb_demo.c:63

#1 0x000055555555537d in tree_size (t=0x7fffffffe3e0) at

gdb_demo.c:63

#2 0x000055555555537d in tree_size (t=0x7fffffffe398) at

gdb_demo.c:63

#3 0x000055555555537d in tree_size (t=0x7fffffffe380) at

gdb_demo.c:63

#4 0x0000555555555507 in main (argc=1,

argv=0x7fffffffe528) at gdb_demo.c:84

What does 0x0000555555555371 represent?

The location of the current call stack's frame. in the stack

The address of the current assembly instruc!on

The return address of the current func!on

gdb's iden!fier for the current call stack

The address of the current func!on's local variables

Question 2

Suppose we are using a standard 64-bit x86_64 system, and we set

void** p = 0x2000

int* q = ((int*)(p + 5)) - 4

What is q in hexadecimal?

Question 3

Briefly explain your answer to the previous ques!on (i.e., show your work). Sta!ng irrelevant facts won't help your score, and sta!ng incorrect informa!on may reduce your score.

Question 4

Fill in the missing code pieces.

// Add all elements in array to existing value in ret

// Example: if array is [2, 3, 4] and ret contains 5

// then upon return, ret should contain 2+3+4+5=14

void add(int* array, int length, int* ret) {

if (length > 0) {

length--;

[ Select ]

add(array, length, ret

);

[ Select ]

}

Question 5

In this problem, we will address mul!ple ques!ons rela!ng to the malloc data structure under the following assump!ons:

We always use headers and footers in all blocks, and they are equal to each other.

The headers/footers contain the size of the block including the size of the header and footer and user payload space

The headers/footers contain an alloc bit in the lowest bit to indicate if the block is allocated (1) or free (0)

We use a prologue header/footer with the size of the prologue

We use an epilogue header with a size of 0

The heap is ini!alized without any space between the prologue and epilogue (i.e., empty heap)

When adding space at the end of the heap in malloc, we add the minimum necessary space to fit the user request while accoun!ng for alignment issues

We use an implicit free list implementa!on (i.e., no explicit free list or segregated free list)

All memory returned from malloc must be 16-byte aligned

The heap starts at address 0x7efff7c7b010

Suppose we have a call to mm_init() followed by a call to malloc(25).

What is the address of the prologue? 0x7efff7c7b010

What is the address of the header for that malloc'd block? 0x7efff7c7b018

What is value is stored inside the header for that malloc'd block? 0x31

What is the address returned from malloc? 0x7efff7c7b028

What is the address of the footer for that malloc'd block? 0x7efff7c7b050

What is the address of the epliogue? 0x7efff7c7b058

Question 6

Indicate if the following are valid consistency checks for a malloc data structure with an explicit free list.

Check that calling free twice back to back with the same pointer is not allowed True

Check that blocks in the explicit free list are actually free False

Check that all blocks are within the heap area False

Check that malloc correctly updates the header True

Question 7

Suppose you are implemen!ng malloc on a system that requires 4-byte alignment. In allocated blocks, you set the header to

size | ALLOC

where ALLOC is defined as some fixed value. Of these choices, which is the largest possible value you can define for ALLOC?

Question 8

Suppose you are wri!ng a malloc implementa!on where instead of storing the size in the header, you instead store a pointer to the next adjacent block's header. Assuming that malloc returns 8-byte aligned pointers and that the lower header bits are used for flags (e.g., alloc bit), fill in the following code:

* getNextBlock - returns pointer to next block's heade

* p - pointer to a block's header

void* getNextBlock(void* p) {

return (void*)(~7 & *((size_t*)p)

);

}

* getSize - returns size of block including header

* p - pointer to a block's header

size_t getSize(void* p) {

return sizeof(size_t) * ((size_t)getNextBlock(p) - (s

ize_t)p)

;

}

Question 9

Suppose we're using a 16-bit system with 2 byte pointers. Suppose the system has 4KB pages with a single-level page table. How many entries are there in a page table? Express your answer as an integer in base 10.

Question 10

Briefly explain your answer to the previous ques!on (i.e., show your work). Sta!ng irrelevant facts won't help your score, and sta!ng incorrect informa!on may reduce your score.

Question 11

Suppose we're using a 16-bit system with 2 byte pointers. Suppose the system has 256 byte pages with a two-level page table. Assume the two-level split is such that each page table contains the same number of entries. Suppose a program is only using the following virtual addresses:

0x1000

0x2000

0xEF00

0xFF00

How much space is being used for this program's page table structures in bytes? Assume that page tables do not need to be page-aligned. Express your answer as an integer in base 10.

Question 12

Briefly explain your answer to the previous ques!on (i.e., show your work). Sta!ng irrelevant facts won't help your score, and sta!ng incorrect informa!on may reduce your score.

Question 13

Suppose we're using an 8-bit system with 16 byte pages and a two-level page table. Assume the two-level split is such that each page table contains the same number of entries. Suppose the following is a dump of physical memory:

00: 50 10 20 20 10 90 f0 50 e0 40 20 90 00 50 80 10 10: 90 00 c0 50 30 e0 30 00 f0 f0 60 20 10 d0 50 f0 20: 40 e0 40 f0 f0 00 f0 f0 a0 30 a0 f0 50 e0 40 f0 30: 50 00 f0 f0 90 e0 90 40 f0 10 d0 20 10 90 f0 50 40: 80 40 00 f0 40 90 e0 10 d0 90 30 00 f0 f0 90 e0 50: 60 40 f0 10 20 20 10 90 f0 30 b0 10 20 40 00 f0 60: 50 70 e0 50 f0 50 80 f0 60 20 90 d0 50 f0 80 40 70: 50 00 f0 d0 c0 f0 20 10 c0 f0 f0 60 60 30 50 40 80: 50 40 10 20 c0 50 f0 00 f0 f0 c0 90 20 30 f0 30 90: 70 50 f0 60 90 e0 90 00 60 20 50 50 00 00 70 c0 a0: 40 20 30 f0 20 e0 20 e0 50 00 10 40 40 30 30 50 b0: 60 00 20 10 40 f0 30 f0 40 50 00 f0 90 40 d0 f0 c0: a0 50 20 50 70 90 30 40 50 20 40 d0 30 c0 f0 e0 d0: 60 40 10 20 c0 50 00 30 70 90 80 30 80 40 20 c0 e0: 00 60 10 30 40 f0 20 90 10 c0 70 90 60 f0 50 80 f0: b0 d0 00 c0 50 00 30 40 40 90 e0 00 00 70 c0 90

Suppose we declare char* p = 0xda. What is *p, assuming the process's base page table register (e.g., cr3) contains 0xf0? Express your answer in hexadecimal.

0x20

Question 14

Briefly explain your answer to the previous ques!on (i.e., show your work). Sta!ng irrelevant facts won't help your score, and sta!ng incorrect informa!on may reduce your score.

Question 15

Pick ALL of the choices where the page fault handler is always triggered.

Reading from NULL pointer

Writing to NULL pointer

Reading from malloc'd memory

Writing to malloc'd memory

Reading from swapped out memory

Writing to swapped out memory

Reading from shared global variable

Writing to shared global variable

Reading from non-page aligned pointer

Writing to non-page aligned pointer

Reading from COW memory

Writing to COW memory

Question 16

Suppose you have a size 3 cache ini!ally containing items A, B, and C. Under the Belady OPT algorithm, what items are evicted in each step in the following access pa"ern:

D Evict A

A Evict B

E Evict C

C Evict D

B Evict A

A Evict E

D Evict C

E Evict B

D N/A (hit)

B Evict A

Question 17

Briefly explain your answer to the previous ques!on (i.e., show your work). Sta!ng irrelevant facts won't help your score, and sta!ng incorrect informa!on may reduce your score.

Question 18

When performing a syscall, the computer will switch from the user stack to the kernel stack. How does the computer know where the kernel stack is?

Determined based on thread id

Specified in kernel stack register

Always starts at a predefined loca!on

Loca!on is configured during bootup

Looked up in a kernel data structure

Question 19

What happens when context switching from thread A to thread B in a different process?

Thread A's registers are saved

Thread A's registers are restored

Thread B's registers are saved

Thread B's registers are restored

The user stacks of the threads are swapped in memory

Thread B's stack is loaded into memory

The base page table register is switched

The TLB is flushed

The kernel stack register is switched

The stack register is switched