Sketch of a solution to the TDIU11 exam from 2020-03-06. Problem 1: 1) Event tick running ready queue waiting queue - 0 - - p1,p2,p3,p4 e4 1 p4+r - p1,p2,p3 e1,e3 2 p3 p4+r p1,p2 - 3 p3 p4+r p1,p2 - 4 p3 p4+r p1,p2 - 5 p3 p4+r p1,p2 e2 6 p2 p3,p4+r p1 - 7 p2 p3,p4+r p1 - 8 p3 p4+r p1 - 9 p4+r - p1 - 10 p1+r p4 - - 11 p1 p4 - - 12 p4 - - - 13 - - - Waiting time: p1: 0 p2: 0 p3: 2 p4: 9 2) Describe how events such as e3 trigger an interrupt that gives control to a service routine and the kernel involving a context switch and what that means. 3) Indeed P1 would have spent 5 more ticks in the waiting queue. This is a priority inversion where P1 should not wait for P3 but because it waits for P4 to release the lock, and that P4 is preempted by P3, it practically waits for P3. 4) One way is to give P4 the same priority as P1 when it holds the radio (a ressource P1 needs P4 to release). This is called priority inheritance. 5) Event tick running ready queue waiting queue - 0 - - p1,p2,p3,p4 e4 1 p4+r - p1,p2,p3 e1,e3 2 p4+r p3 p1,p2 - 3 p1+r p3,p4 p2 - 4 p1 p4 p2 - 5 p3 p4 p2 e2 6 p2 p3,p4 - 7 p2 p3,p4 - 8 p3 p4 - 9 p3 p4 - 10 p3 p4 - - 11 p3 p4 - - 12 p4 - - - 13 - - - Waiting time: p1: 0 p2: 0 p3: 4 p4: 9 Problem 2: 1) The table has an entry for each logical block. table_size = 4B * number_logical_blocks ---> there should be at most 128x2^{20}/4 = 32x2^{20} logical blocks The disk is 2^{42}B so each logical block should be at least 2^{42}/(32x2^{20}) = 2^{17} B = 256 physical blocks. 2) Assuming the two disks are mounted and their FAT tables are in memory, the copying process will need to recursively open directories and files and to create/copy corresponding ones for the destination. This requires fetching both inodes and data for directories and files from the disk. Inodes are kept in the system wide open file table with corresponding entries in the process-local open file table. Data blocks and directory structures are cached in memory. This involves reading (from source) and writing (to destination) logical disk blocks. 3) 4 GiB = 2^{32}B = 2^{15} logical blocks (assuming a logical block is 2^{17}B from 1). Assuming half the blocks require a seek of 500 x 10^{-6}s, we get 32/2 x 1024 x 500 x 10^{-6} s ~ 8 seconds to access each block of the 4GiB, if these need as much time to be copied without possibility of parallelizing the work, then the copy would require about 16 seconds. Problem 3: Part A: 1) Explain: * reflects a logical view with different treatments (rd/wr/ex) of different segments (text, heap, stack...) * Less sensitive to external fragmentation as not everything needs to be contiguous. 2) Still suffers from external fragmentation. Total memory is 8 units. Process 1 needs a segment with 3 units 111..... Process 2 needs a segment with 1 unit 1112.... and so on until 11121221 Process 1 terminates and segments reclaimed. ...2.22. Process 3 needs 2 segments of two units each ... cannot be allocated even though there is a corresponding total space. Paging with solve this because it will use the same units for the pages ... so if Process 3 needs 2 segments of 2 units, i.e., 4 units, then it will be allocated. 33323223 Part B: 1) a) 13-19 gives 512KiB pages with 4B entries making each table exactly 2^13 x 4 = 2^13* 2^2= 2^15B=32KiB. Hence, each page table fits in a page. The 48 - 19 = 29 bits identify the frame number in each entry, leaves 3 bits for valid and other. Virtual or logical addresses are 32 bits long. Page numbers are 13 bits long and give 2^13 page entries, each with 4B = 32 bits long. A physical address is 48 bits long with 19 bits corresponding to the offset. The 19 bits for the offset are identical in the 32 bits virtual and the 48 bits physical addresses. So 48-19=29 bits correspond to the frame number and are concatenated to the 19 offset bits to give the 48bits physical addresses Virtual address |______13______|__________19___________| is 32 bits | 13 bits page number identifies entry in page table (PT) | Entry in PT |______________29__________________|_3_| is 4B=32 bits | 29 bits frame number identifies frame in RAM. 3 bits used for valid bit and other information | Physical address|______________29__________________|__________19___________| is 48 bits long: 29 for the frame and 19 for the offset. b) 10-22 gives 4MiB pages with 4B entries making each table 2^{10}x4=4KiB which fits in a page. The 48-22=26 bits identify the frame in each entry, leaves 6 bits for valid and other. Virtual address |______10______|__________22___________| is 32 bits | 10 bits page number identifies entry in page table (PT) | Entry in PT |______________26________________|__6__| is 4B=32 bits | 26 bits frame number identifies frame in RAM. 6 bits used for valid bit and other information | Physical address|______________26________________|____________22___________| is 48 bits long: 26 for the frame and 22 for the offset. 2) b has more bits for permissions and other info, but comes with more internal fragmentation 3) TLB stores the correspondance between page and frame number to avoid having to read the corresponding page entries. 4) Without translation, memory accesses would take T with translation, each memory access requires reading the table entry, so 2T Let h be the hit ratio. Effective time: h*T + (1-h)*2T = T*(h+2-2*h)=(2-h)*T Degradation ((2-h)*T-T)/T = 1-h <= 0.01 ---> h >= 0.99. Problem 4: 1) A possible scenario can be explained, example: if an attacker can write to some folder the user has access to, then it can write its own version of a command, say "ls", which if executed it can copy/delete/change with the user permission if executed. 2) To find a password whose hashing corresponds to a hash code, attackers typically precompute the hash of a huge number of entries to find collisions. Salt requires the regeneration of such tables since the same passwrods give different hash when combined with different hash. 3) a) The program should be executable by every user. Owned by the root with setuid. To promote "least-privilege: It should not be writable (could be modified) or readable (no need for reading a file to execute it). Special care must be paid for the abscence of bugs (e.g. overflow, out-of-bound) or dependancy on environment variables. The computed checksums should not be accessible to users and the program should only verify the checsums not give the actual checksums. A combination with capabilities would allow to drop the capability as soon as the file was read (better-need-to-know) b) without proper check on the size of the path and the buffer where the path is stored, a buffer overflow attack migh be mounted. Explain.