程序代写代做代考 go algorithm cache C graph Carnegie Mellon

Carnegie Mellon
15-213/513/613: Final Exam Review Kashish & Ishita

Carnegie Mellon
Final Exam Logistics
¡ö Cheat sheets – 2 double sided 8.5 x 11 in.
¡ö Join Zoom, turn on video AND microphone.
¡ö Show ID and cheatsheet to TA on video.
¡ö You will receive an email with the link to the zoom call,
the exam time, and more detailed logistics soon.
¡ö 8 categories of questions:
¡ö Malloc, VM, Processes, Signals, IO, Threads,
ThreadSync, Multiple Choice (pre-midterm)

Carnegie Mellon
Virtual Memory

Carnegie Mellon
Virtual Memory Virtual Address – 18 Bits
Physical Address – 12 Bits Page Size – 512 Bytes
TLB is 8-way set associative Cache is 2-way set associative
Final S-02 (#5)
Lecture 18: VM – Systems

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset
(B) VPN: Virtual Page Number
(C) TLBI: TLB Index
(D) TLBT: TLB Tag

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset – Location in the page
Page Size = 512 Bytes = 29 ¡ú Need 9 bits

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset
(B) VPN: Virtual Page Number – Everything Else

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset
(B) VPN: Virtual Page Number
(C) TLBI: TLB Index – Location in the TLB Cache

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset
(B) VPN: Virtual Page Number
(C) TLBI: TLB Index – Location in the TLB Cache 2 Indices ¡ú 1 Bit
TLBI

Carnegie Mellon
Virtual Memory
Label the following:
(A) VPO: Virtual Page Offset
(B) VPN: Virtual Page Number
(C) TLBI: TLB Index
(D) TLBT: TLB Tag – Everything Else
TLBT TLBI

Carnegie Mellon
Virtual Memory
Label the following:
(A) PPO: Physical Page Offset
(B) PPN: Physical Page Number
(C) CO: Cache Offset
(D) CI: Cache Index
(E) CT: Cache Tag

Carnegie Mellon
Virtual Memory
Label the following:
(A) PPO: Physical Page Offset

Carnegie Mellon
Virtual Memory Label the following:
(A) PPO: Physical Page Offset – Same as VPO
AAAAAAAAA

Carnegie Mellon
Virtual Memory
Label the following:
(A) PPO: Physical Page Offset – Same as VPO (B) PPN: Physical Page Number – Everything Else
BBBAAAAAAAAA

Carnegie Mellon
Virtual Memory Label the following:
(A) (B) (C)
PPO: Physical Page Offset – Same as VPO PPN: Physical Page Number – Everything Else CO: Cache Offset – Offset in Block
BBBAAAAAAAAA

Carnegie Mellon
Virtual Memory Label the following:
(A) (B) (C) (D)
PPO: Physical Page Offset – Same as VPO PPN: Physical Page Number – Everything Else CO: Cache Offset – Offset in Block
CI: Cache Index
BBBAAAAAAAAA
CO

Carnegie Mellon
Virtual Memory
Label the following:
(A) PPO: Physical Page Offset – Same as VPO
(B) PPN: Physical Page Number – Everything Else
(C) CO: Cache Offset – Offset in Block
(D) CI: Cache Index
(E) CT: Cache Tag – Everything Else
BBBAAAAAAAAA
Cache Tag CI CO

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4 1. Write down bit representation
1 = 0001 A = 1010 9 = 1001 F = 1111 4 = 0100
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0x?? TLBI: 0x?? TLBT: 0x?? TLB Hit: Y/N? Page Fault: Y/N? PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x?? TLBT: 0x?? TLB Hit: Y/N? Page Fault: Y/N? PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x00 TLBT: 0x?? TLB Hit: Y/N? Page Fault: Y/N? PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x00 TLBT: 0x6A TLB Hit: Y/N? Page Fault: Y/N? PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x00 TLBT: 0x6A TLB Hit: Y! Page Fault: Y/N? PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x00 TLBT: 0x6A TLB Hit: Y! Page Fault: N! PPN: 0x??
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. Write down bit representation
2. Extract Information:
VPN: 0xD4 TLBI: 0x00 TLBT: 0x6A TLB Hit: Y! Page Fault: N! PPN: 0x3
011010100111110100

Carnegie Mellon
Virtual Memory
Now to the actual question!
Q) Translate the following address: 0x1A9F4
1. 2. 3.
Write down bit representation
Extract Information
Put it all together: PPN: 0x3, PPO = 0x??
011

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
CO: 0x?? CI: 0x?? CT: 0x?? Cache Hit: Y/N? Value:0x??
011111110100

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
1. Extract more information
CO: 0x00 CI: 0x?? CT: 0x?? Cache Hit: Y/N? Value:0x??
011111110100

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
1. Extract more information
CO: 0x00 CI: 0x01 CT: 0x?? Cache Hit: Y/N? Value:0x??
011111110100

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
1. Extract more information
2. Go to Cache Table
CO: 0x00 CI: 0x01 CT: 0x7F Cache Hit: Y/N? Value:0x??
011111110100

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
1. Extract more information
2. Go to Cache Table
CO: 0x00 CI: 0x01 CT: 0x7F Cache Hit: Y Value:0x??
011111110100

Carnegie Mellon
Virtual Memory
Q) What is the value of the address?
1. Extract more information
2. Go to Cache Table
CO: 0x00 CI: 0x01 CT: 0x7F Cache Hit: Y Value:0xFF
011111110100

Carnegie Mellon
Virtual Memory

Carnegie Mellon
Threads

Carnegie Mellon
Threads
Given this code, what variables do you think are shared?

Carnegie Mellon
Threads (Contd.)
Which variables can be shared by multiple threads simultaneously in this program?
(A) i
(B) balance
(C) instance
(D) cnt
(E) None of the above

Carnegie Mellon
Threads (Contd.)
Which variables can be shared by multiple threads simultaneously in this program?
(A) i
(B) balance
(C) instance
(D) cnt
(E) None of the above
Answer: B

Carnegie Mellon
Threads (Contd.)
(A) i is a local variable so it isn¡¯t shared.
(B) balance is a global variable so it¡¯s shared.
(C) instance is local to threadA() so it isn¡¯t shared.
(D) cnt is a static variable, so it retains its value even outside the scope in which it was defined, so it isn¡¯t shared.

Carnegie Mellon
Threads (Contd.)
Given the withdraw() and deposit() functions, what are the possible outputs? (balance = 10 initially)

Carnegie Mellon
Threads (Contd.)
What can be the value of balance?
(A) balance: 0
(B) balance: -3
(C) balance: 14
(D) balance: 6
(E) balance: 17
(F) balance: 4

Carnegie Mellon
Threads (Contd.)
What can be printed at the indicated line?
(A) balance: 0
(B) balance: -3
(C) balance: 14
(D) balance: 6
(E) balance: 17
(F) balance: 4
Answer: ABDF

Carnegie Mellon
Threads (Contd.)
The following is one interleaving that leads to output 0:
¡ö Thread A executes deposit(4), balance = 14
¡ö Thread B executes withdraw(6), balance = 8
¡ö Thread B executes deposit(3), balance = 11
¡ö Thread A executes withdraw(11), balance = 0
¡ö Thread B executes withdraw(7), balance = 0

Carnegie Mellon
Threads (Contd.)
The following is one interleaving that leads to output -3:
¡ö Thread A executes deposit(4), balance = 14
¡ö Thread A starts to execute withdraw(11) and
enters the if condition
¡ö Thread B executes withdraw(6), balance = 8
¡ö Thread A computes RHS for withdraw(11) = -3
¡ö Thread B executes deposit(3), balance = 11
¡ö Thread A completes withdraw(11), balance = -3
¡ö Thread B executes withdraw(7), balance = -3

Carnegie Mellon
Threads (Contd.)
The following is one interleaving that leads to output 6:
¡ö Thread A executes deposit(4), balance = 14
¡ö Thread A executes withdraw(11), balance = 3
¡ö Thread B executes withdraw(6), balance = 3
¡ö Thread B executes deposit(3), balance = 6
¡ö Thread B executes withdraw(7), balance = 6

Carnegie Mellon
Threads (Contd.)
The following is one interleaving that leads to output 4:
¡ö Thread B executes withdraw(6), balance = 4
¡ö Thread A executes deposit(4), balance = 8
¡ö Thread A executes withdraw(11), balance = 8
¡ö Thread B executes deposit(3), balance = 11
¡ö Thread B executes withdraw(7), balance = 4

Carnegie Mellon
Synchronization

Carnegie Mellon
Thread Synchronization
How many potential deadlock situations are present?

Carnegie Mellon
Thread Synchronization (Contd.) Situation 1:
tid1 executes V(&add_sem) and V(&rem_sem). Then, tid2 executes P(&rem_sem) and P(&add_sem). In this situation, tid1 can never execute P(&add_sem) since the value of add_sem = 0. As a result, this is a deadlock, since after the execution of thread 2, thread 1 can¡¯t resume. Thus, there¡¯s a deadlock.

Carnegie Mellon
Thread Synchronization (Contd.) Situation 2:
tid1 executes V(&add_sem) and V(&rem_sem). Then, tid2 executes P(&rem_sem). Next, tid1 executes P(&add_sem). Thread 2 wants to execute P(&add_sem) but it can¡¯t since add_sem has value 0. Thread 1 wants to execute P(&rem_sem) but it can¡¯t since rem_sem has value 0. Thus, there¡¯s a deadlock.

Carnegie Mellon
Thread Synchronization (Contd.)
For lengths 0-6, indicate the number of outcomes of that length that can be produced.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 0: None
This is because at least ¡®R¡¯ must get printed due to the call to remove() in thread1(). Even if there is a deadlock, at least that statement gets executed by tid1 before any sort of deadlock from the above situations.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 1: 1 (R)
In the deadlock scenario 2, where thread 1 executes P(&add_sem) and thread 2 executes P(&rem_sem), neither of the threads can proceed past that. Thus, no print statements are executed in either thread after that point. The only print statement that gets executed is due to the call to remove() before the calls to P() in thread 1.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 2: None
We noticed that ¡®R¡¯ due to the call to remove() in thread1() gets printed no matter what. From the code, we notice that it¡¯s not possible for only one other print statement to get executed.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 3: 2 (RAR, ARR)
This happens due to deadlock scenario 1 above, where thread2() executes completely but thread1() can¡¯t execute P(&add_sem) and the statements after that.
¡ö RAR: Thread 1 executes remove(), followed by thread 2 executing add() and remove().
¡ö ARR: Thread 2 executes add(), followed by any ordering of the 2 calls to remove() by threads 1 and 2.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 4: None
For any length greater than 3, it means that there was no deadlock, since thread 2 could run to completion and thread 1 could get past the calls to P(), which means it would run to completion as well. Thus, no responses of length greater than 3 and less than 6 are possible.

Carnegie Mellon
Thread Synchronization (Contd.) Response length 5: None
For any length greater than 3, it means that there was no deadlock, since thread 2 could run to completion and thread 1 could get past the calls to P(), which means it would run to completion as well. Thus, no responses of length greater than 3 and less than 6 are possible.

Carnegie Mellon
Thread Synchronization (Contd.)
Response length 6: 4
(RARAAR, RARARA, RAARRA, RAARAR)
Since there are no deadlocks, it means that the initial calls to V() and P() get executed by thread 1. Thus, ¡®R¡¯ and ¡®A¡¯ definitely get printed. After this, the calls to V() get executed by thread 1 and then, thread 2 can execute its calls to P(). After this, based on the interleavings between the threads, there are 4 possible outputs.

Carnegie Mellon
Thread Synchronization (Contd.)
¡ö RARAAR: Thread 1 executes remove(), threads 1 and 2 execute the add() statements in any order, and then thread 2 executes remove().
¡ö RARARA: Thread 1 executes remove(), thread 2 executes add() and remove(), then thread 1 executes add().

Carnegie Mellon
Thread Synchronization (Contd.)
¡ö RAARRA: Thread 2 executes add(), threads 1 and 2 execute the remove() statements in any order, and then thread 1 executes add().
¡ö RAARAR: Thread 2 executes add(), thread 1 executes remove() and add(), then thread 2 executes remove().

Carnegie Mellon
Good luck!

Carnegie Mellon
Processes
1. Logical control flow
2. Private address space
Important system calls 1. Fork
2. Execve
3. Wait
4. Waitpid

Carnegie Mellon
Processes
Draw a Process Graph!!! (it does not have to be like mine)

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
What is printed?
Assume printf is atomic, and all system calls succeed.
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
How many processes?
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
How many processes? Parent: forks child
Parent and child: each fork another child
Total: 4 processes
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
What does the process diagram look like?
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
What does count look like?
Parent: pid1 != 0 and pid2 != 0 Child1: pid1 == 0 and pid2 != 0 Child2: pid1 != 0 and pid2 == 0 Grandchild: pid1 == 0 and pid2 == 0
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
What does count look like?
Parent: pid1 != 0 and pid2 != 0 ¡ñ count = 3
Child1: pid1 == 0 and pid2 != 0 ¡ñ count = 2
Child2: pid1 != 0 and pid2 == 0 ¡ñ count = 0
Grandchild: pid1 == 0 and pid2 == 0 ¡ñ count = 2
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
int main() {
int count = 1;
int pid1 = fork();
int pid2 = fork();
if(pid1 == 0)
count++;
else{
if(pid2 == 0)
Given the process diagram, what are the different permutations that can be printed out?
}
count–;
else
count += 2;
printf(¡°%d¡±, count);
}

Carnegie Mellon
Processes
Remember:
¡ñ Processes can occur in
any order
¡ñ Watch out for a wait or
a waitpid!
¡ð What if I included a
wait(NULL) before
I printed out count? ¡ñ Good luck!

Carnegie Mellon
File IO

Carnegie Mellon

Carnegie Mellon
File IO
foo.txt: abcdefgh…xyz
int main() {
int fd1, fd2, fd3;
char c;
pid_t pid;
fd1 = open(¡°foo.txt¡±, O_RDONLY);
fd2 = open(¡°foo.txt¡±, O_RDONLY);
fd3 = open(¡°foo.txt¡±, O_RDONLY);
read(fd1, &c, sizeof(c));
read(fd2, &c, sizeof(c));
dup2(fd2, fd3);
read(fd3, &c, sizeof(c));
read(fd2, &c, sizeof(c));
Main ideas:
¡ö How does read offset?
¡ö How does dup2 work?
// c = ? // c = ?
// c = ? // c = ?
¡ö What is the order of arguments?
¡ö Does fd3 share offset with fd2?

Carnegie Mellon
File IO
foo.txt: abcdefgh…xyz
int main() {
int fd1, fd2, fd3;
char c;
pid_t pid;
fd1 = open(¡°foo.txt¡±, O_RDONLY);
fd2 = open(¡°foo.txt¡±, O_RDONLY);
fd3 = open(¡°foo.txt¡±, O_RDONLY);
read(fd1, &c, sizeof(c));
read(fd2, &c, sizeof(c));
dup2(fd2, fd3);
read(fd3, &c, sizeof(c));
read(fd2, &c, sizeof(c));
¡ö ¡ö
// c = a // c = a
// c = b // c = c
How does read offset?
¡ö Incremented by number of bytes
read
How does dup2 work?
¡ö Any read/write from fd3 now happen from fd2
¡ö All file offsets are shared

Carnegie Mellon
File IO
read(fd1, &c, sizeof(c)); // a
read(fd2, &c, sizeof(c)); // a
dup2(fd2, fd3);
read(fd3, &c, sizeof(c)); // b
read(fd2, &c, sizeof(c)); // c
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
Main ideas:
¡ö ¡ö ¡ö
How are fd shared between processes?
How does dup2 work from parent to child?
How are file offsets shared between processes?

Carnegie Mellon
File IO
read(fd1, &c, sizeof(c)); // a
read(fd2, &c, sizeof(c)); // a
dup2(fd2, fd3);
read(fd3, &c, sizeof(c)); // b
read(fd2, &c, sizeof(c)); // c
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
What would this program print?
Just ignore the possible outcomes due to interleaving … try two simple cases :
1. First child executes to the end
2. First parent executes to the end.

Carnegie Mellon
File IO
read(fd1, &c, sizeof(c)); // a
read(fd2, &c, sizeof(c)); // a
dup2(fd2, fd3);
read(fd3, &c, sizeof(c)); // b
read(fd2, &c, sizeof(c)); // c
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
Possible output 1: c = b // in child c = d // in child
c = c // in child
c = d // in child
c = e // in parent c = e // in parent

Carnegie Mellon
File IO
read(fd1, &c, sizeof(c)); // a
read(fd2, &c, sizeof(c)); // a
dup2(fd2, fd3);
read(fd3, &c, sizeof(c)); // b
read(fd2, &c, sizeof(c)); // c
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
Possible output 2:
c = d // in parent c = b // in parent
c = c // in child from fd1
c = e // in child from fd3
c = d // in child c = e // in child

Carnegie Mellon
File IO
.
.
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
if (pid!=0) waitpid(-1, NULL, 0);
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
return 0;
}
What are the possible outputs now?

Carnegie Mellon
File IO
.
.
pid = fork();
if (pid==0) {
read(fd1,
printf(¡°c = %c\n¡±, c);
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
}
if (pid!=0) waitpid(-1, NULL, 0);
read(fd1, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
read(fd2, &c, sizeof(c));
printf(¡°c = %c\n¡±, c);
return 0;
}
Possible output:
c = b // in child c = d // in child
c = c // in child
c = d // in child
c = e // in parent c = e // in parent
&c, sizeof(c));

Carnegie Mellon
File IO
read(fd1, &c, sizeof(c)); // a
read(fd2, &c, sizeof(c)); // a
dup2(fd2, fd3);
read(fd3, &c, sizeof(c)); // b
read(fd2, &c, sizeof(c)); // c
pid = fork();
if (pid==0) {
read(fd1, &c, sizeof(c));
dup2(fd1, fd2);
read(fd3, &c, sizeof(c));
}
if (pid!=0) waitpid(-1, NULL, 0);
read(fd2, &c, sizeof(c));
read(fd1, &c, sizeof(c));
¡ö
Child creates a copy of the parent fd table
¡ö dup2/open/close in parent affect the child
¡ö dup2/open/close in child do NOT affect the parent
File descriptors across process share the same file offset.
¡ö

Carnegie Mellon
Malloc

Carnegie Mellon
Malloc
¡ö Fit algorithms – first/next/best/good ¡ö Fragmentation
¡ö Internal – inside blocks
¡ö External – between blocks ¡ö Organization
¡ö Implicit
¡ö Explicit
¡ö Segregated

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
#2
32a
32a
#3
32a
#4
#5
final-f01.pdf: Problem 10 Part A
#6

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
#2
32a
32a
32a
#3
32a
32a
#4
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
#2
32a
32a
32a
32a
#3
32a
32a
32f [0]
#4
48a
48a
#5
final-f01.pdf: Problem 10 Part A
#6

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
#2
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
#4
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
#2
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32f [0]
#4
48a
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
#4
48a
48a
48a
48a
#5
final-f01.pdf: Problem 10 Part A
#6

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
80a
#4
48a
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
32a
32f [0]
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
80a
80a
#4
48a
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation? ¡ö internal?
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
32a
32f [0]
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
80a
80a
#4
48a
48a
48a
48a
#5
#6

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation? ¡ö internal
¡ö (48-16) + (80-48) = 64
¡ö external?
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
32a
32f [0]
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
80a
80a
#4
48a
48a
48a
48a
#5
#6

Carnegie Mellon
Malloc – First fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation?
¡ö internal
¡ö (48-16) + (80-48) = 64
¡ö external
¡ö 32
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48a
48a
48a
48a
#2
32a
32a
32a
32a
32a
32a
32a
32a
32f [0]
#3
32a
32a
32f [0]
32f [1]
32f [0]
80f [0]
80a
80a
#4
48a
48a
48a
48a
#5
#6

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
#2
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
#4
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
#2
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
#4
48a
48a
48a
48a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
#2
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
#4
48a
48a
48a
48a
48f [0]
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
48f [0]
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
32a
#4
48a
48a
48a
48a
48f [0]
64a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align ¡ö coalesced
¡ö footerless
¡ö 32 min size
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
48f [0]
80f [0]
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
32a
32a
#4
48a
48a
48a
48a
48f [0]
64a
64a
#5
#6
final-f01.pdf: Problem 10 Part A

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation? ¡ö internal?
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
48f [0]
80f [0]
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
32a
32a
#4
48a
48a
48a
48a
48f [0]
64a
64a
#5
#6

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation? ¡ö internal
¡ö (32-16) + (64-48) = 32
¡ö external?
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
48f [0]
80f [0]
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
32a
32a
#4
48a
48a
48a
48a
48f [0]
64a
64a
#5
#6

Carnegie Mellon
Malloc – Best fit
¡ö 16 byte align
¡ö coalesced
¡ö footerless
¡ö 32 min size
¡ö fragmentation?
¡ö internal
¡ö (32-16) + (64-48) = 32
¡ö external
¡ö 80
a = malloc(32)
b = malloc(16)
c = malloc(16)
d = malloc(40)
e = malloc(16)
f = malloc(48)
free(c)
free(a)
free(d)
free(b)
#1
48a
48a
48a
48a
48a
48f [0]
48f [0]
48f [1]
48f [0]
80f [0]
#2
32a
32a
32a
32a
32a
32a
32a
32a
#3
32a
32a
32f [0]
32f [1]
32a
32a
32a
32a
#4
48a
48a
48a
48a
48f [0]
64a
64a
#5
#6

Carnegie Mellon
Signals
who would win?
several hundred lines of tshlab code
one asynchronous boi

Carnegie Mellon
Signals

Carnegie Mellon
Signals (Contd.)
¡ö Sending the same signal to the parent in all the calls to kill() may print 1 since there would be no queuing of signals.
¡ö We can guarantee printing 2 if we send precisely one SIGUSR1 and one SIGUSR2.
¡ö We can print 1-4 depending on the manner in which signals are sent and received.

Related Posts