Sketch of possible answers for TDIU11's exam of June 9th 2020. Assume (D1,D2,D3,D4)=(5,0,7,0) Problem 1: (a,b,c,d)=(2,4,1,3). Giving: t1: 6 ticks t2: 2 ticks t3: 8 ticks t4: 4 ticks 1. Round Robin with time quantum = 3 ticks. 1.a: Event tick running ready queue - 0 none none t1 arrives 1 t1(6) none t2 arrives 2 t1(5) t2(2) t3 arrives 3 t1(4) t2(2), t3(8) t4 arrives 4 t2(2) t3(8), t1(3), t4(4) - 5 t2(1) t3(8), t1(3), t4(4) - 6 t3(8) t1(3), t4(4) - 7 t3(7) t1(3), t4(4) - 8 t3(6) t1(3), t4(4) - 9 t1(3) t4(4), t3(5) - 10 t1(2) t4(4), t3(5) - 11 t1(1) t4(4), t3(5) - 12 t4(4) t3(5) - 13 t4(3) t3(5) - 14 t4(2) t3(5) - 15 t3(5) t4(1) - 16 t3(4) t4(1) - 17 t3(3) t4(1) - 18 t4(1) t3(2) - 19 t3(2) none - 20 t3(1) none - 21 none none 1.b: waiting times: t1: 5 ticks t2: 2 ticks t3: 9 ticks t4: 11 ticks 2.a Preemptive SJF: Event tick running ready queue - 0 none none t1 arrives 1 t1(6) none t2 arrives 2 t2(2) t1(5) t3 arrives 3 t2(1) t1(5), t3(8) t4 arrives 4 t4(4) t1(5), t3(8) - 5 t4(3) t1(5), t3(8) - 6 t4(2) t1(5), t3(8) - 7 t4(1) t1(5), t3(8) - 8 t1(5) t3(8) - 9 t1(4) t3(8) - 10 t1(3) t3(8) - 11 t1(2) t3(8) - 12 t1(1) t3(8) - 13 t3(8) none - 14 t3(7) none - 15 t3(6) none - 16 t3(5) none - 17 t3(4) none - 18 t3(3) none - 19 t3(2) none - 20 t3(1) none - 21 none none 2.b wiating times: t1: 6 ticks t2: 0 ticks t3: 10 ticks t4: 0 ticks 3. Suppose a schenario where t1(6) arrives at tick 0 and a task requiring 2 ticks arrives at each odd tick. t1 would starve. t1 would not starve in Round Robin. 4. Here, one could remedy to starvation by using aging, i.e., the priority p_t of a task t is regularly increased the longer the task waits. Problem 2: Recall D4=0 1) n = 2 x 2^{D4 % 3} = 2 logical blocks are 2 x 2^9 B = 2^10 B = 1 KiB each. 2) 4Bytes=32bits pointers can point to 2^32 logical blocks. #possible_blocks x size_of_a_logical_block = 2^32 x 2^10 B = 2^42B Maximum size of disk is then 2^42 Bytes 3) Indexed allocation: 12 direct, 1 indirect, 1 double indirect, 1 triple indirect logical block: 2^10 B pointers per block given a pointer is 4 B: 2^10 B / 4 B = 2^8 pointers direct: 12 x 2^10B indirect: 1 x 2^8 x 2^10B double indirect: 1 x 2^8 x 2^8 x 2^10B triple indirect: 1 x 2^8 x 2^8 x 2^8 x 2^10B max size file: 12x2^10 + 2^18 + 2^26 + 2^34 B ~ 2^34 B 4) double indexing: See explanation in earlier question: logical block: 2^10 B and 2^8 pointers per block. With double index, each pointer in a 2^8 pointers index block points to a 2^8 pointers index block that points to a 2^10 B data block. Hence, double indexing can point to 2^16 data blocks of 2^10 each. With triple indexing, each pointer in a 2^8 pointers index block points to a 2^8 pointers index block where each pointer points to a 2^8 pointers block where each pointer points to a 2^10 B data block. Hence, triple indexing can point to 2^24 data blocks. Each of the two indexings would be able to point to more than 2^11 blocks. 5) The data blocks of each of the 5000 files will be completely filled except for the last block. Assume in average the last data block of each file is half full. Internal fragmentation would result in 5000 (number of last datablocks) x 1/2 (half full) x 2^10 (size of a data block) ~ 2^21 Bytes. 6) We only account for seeks resulting from looking for the datablocks. Indices already in memory. No transfer: A file of 4 GiB = 2^32B = 2^22 x 2^10B would require 2^22 logical blocks. Half of them (i.2., 2^21) will require a seek. 2^21 (number of seeks) x 500 x 10^(-6) sec (cost of a seek) ~ 1049 seconds. Problem 3: Recall D4 = 0 n = 2 + (D4 % 3) = 2. 1) 2 level paging. For each level, the page table should have an entry for each page number at that level. Here the entries are 4 Bytes = 2^2 Bytes. Each page table has to fit in a page. 32 bits logical addresses. 2 levels. level 1: first 10 bits ---> 2^10 entries in level 1 table level 2: second 10 bits ---> 2^10 entries in each level 2 table offset : 12 last bits ---> page size: 2^12 B 2) physical addresses are 32 bits. 12 of them are used for the offset in a frame (frames and pages have the same size, in this case 2^12 bits). The remaining 20 bits can be used to identify a frame. so at most 2^20 frames. 3) Each of level 1 and level 2 uses 10 bits and results in tables with 2^10 entries, each entry is 4B so a page table, whether in level 1 or level 2, is 2^12B. One page of data needs to be indexed with 2 page tables: one for level 1 and another with level 2. So a minimum of 2 x 2^12 B = 2^13B. 4) logical: [level 1][level 2][offset] = [0000 0000 00][00 0000 0000][0000 0000 0000] the the entry number [level 1]=[0000 0000 00] gives the frame where to find the level 2 table. the entry number [level 2]=[0000 0000 00] at the level 2 table give the frame of the data page. This frame number will be concatenated with the offset [0000 0000 0000] to give the physical address [1111 1111 1111 1111 1100][0000 0000 0000] where the first 18 bits [1111 1111 1111 1111 1100] or the frame number stored at entry [0000 0000 00] of the page table of level 2 pointed to by the entry [0000 0000 00] of page level 1. 5) The system may use more pages than frames as the sum of the virtual memories of the process may exceed the available number of frames in physical memory. Fifo replacement only needs to update its information (a queue if by process, an index if global replacement) only when replacing, not at each page access like for LRU. 6) TLB caches the mapping from the page number (here the first 20 bits corresponding to the two levels) the content of the corresponding page table (importantely, a frame number and protection flags). The "identifier associated to a process" identifies the memory space (i.e., identifies the mapping itself) avoiding having to flush the TLB at a context switch. Problem 4: * pw is the "main password" * n = 2 + (0%3) = 2 * hash(x) is a one way hash function. It can cheaply compute the hash of an input. It is expensive and slow to deduce an input for a given output. One way to share n passwords beteen user and system given they share pw: let the ith password be concat(pw, string_of(i)). The passwords are then sent hashed from user to system. System expects hash(concat(pw, string_of(i))). The password is only valid once, then system expects concat(pw, string_of(i+1)). Attacker cannot reverse hash, and hence cannot deduce the hash(concat(pw, string_of(i+1))) just because it intercepted hash(concat(pw, string_of(i))) A problem with this way as that an attacker may be able to reverse hash after some time and if the passwrod pw is still in use then it can easily generate future passwords. A more robust scheme is to use hash^{n-i}(pw) as the ith password. This way, if the is obliged to reverse hash for each password, and not once for all passwords.