UCLA-COM-SCI-111-2022F-final

pdf

School

University of California, Los Angeles *

*We aren’t endorsed by this school

Course

111

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by tachyonphantom

UCLA Computer Science 111 final exam, fall 2022 180 minutes total, open book, open notes, closed computer. 1 minute = 1 point. Write answers on exam. Name:__________________________ Student ID:_____________ 1. The x86-64 HLT instruction (opcode 0xF4) halts the logical processor, so that it does nothing until the next external interrupt. If all logical processors in a physical package are halted, the entire package enters a low-power state to save energy. 1a (3 minutes). Briefly explain whether user-mode Linux code can HLT. 1b. (8 minutes). Explain whether and how the implementations of the Linux system calls pause() and sched_yield() should use HLT. 1c. (8 minutes). Linux uses preemptive scheduling. If sched_yield() and/or pause() uses HLT and then a clock interrupt is delivered, what should happen next and why?

[page 2] 2. Consider the following buggy C program, which is supposed to copy all data from a file ‘infile’ to a file ‘outfile’. 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <sys/fcntl.h> 4 #include <unistd.h> 5 6 void 7 error(void) 8 { 9 perror("I/O error"); 10 exit(1); 11 } 12 13 int 14 main (void) 15 { 16 char buf[1000]; 17 int ifd = open("input", O_RDONLY); 18 if (ifd < 0) 19 error(); 20 ssize_t insize = read(ifd, buf, sizeof buf); 21 if (insize < 0) 22 error(); 23 close(ifd); 24 int ofd = open("output", O_WRONLY|O_CREAT|O_TRUNC, 0666); 25 if (ofd < 0) 26 error(); 27 28 do { 29 if (write(ofd, buf, sizeof buf) < 0) 30 error(); 31 } while (0 < (insize = read(ifd, buf, sizeof buf))); 32 33 if (insize < 0) 34 error(); 35 close(ofd); 36 exit(0); 37 } [continued on next page]

[continued from previous page] [page 3] 2a (5 minutes). Here’s one example of buggy behavior. Briefly explain what went wrong, and say how you’d change the source code to fix this bug. Make your fix as short and simple as you can. $ echo x >input $ ./a.out $ ls -l input output -rw-r--r--. 1 eggert eggert 2 Dec 5 10:19 input -rw-r--r--. 1 eggert eggert 1000 Dec 5 10:19 output 2b (10 minutes). Here’s a different example of buggy behavior. Likewise, explain and fix this other bug simply. Assume bug (a) is already fixed. $ cp /etc/passwd input $ ./a.out I/O error: Bad file descriptor $ ls -l /etc/passwd input output -rw-r--r--. 1 root root 2771 Jun 15 2021 /etc/passwd -rw-r--r--. 1 eggert eggert 2771 Dec 5 10:27 input [continued on next page]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

[continued from previous page] [page 4] 2c (8 minutes). One rule of reliable programming is to always check the result of each system function or system call. Where was this rule broken in the original program, and what are the consequences of breaking the rule in each case where it was broken? 3 (15 minutes). Suppose you are implementing a file system for an NVMe device, and you are worried about how well the device will perform with applications that write data. The NVMe standard requires only three I/O commands: read, write, and flush. Explain how you could use these commands to improve overall system performance by using dallying or some other form of speculation in a Linux file system. Briefly explain the costs and benefits of your approach with typical apps.

[page 5] 4 (8 minutes). Cache invalidation (i.e., invalidating stale cache entries when the underlying data mutates) is a problem in distributed databases, which can have multiple caches on different nodes. Linux maintains a block level cache for file systems like ext2. Explain whether and how the Linux kernel deals with cache invalidation with this block level cache. When discussing any performance issues, assume Linux uses 4 KiB blocks and is running on a system with 64 cores (128 threads), with 4 MiB total L1 cache, 64 MiB total L2 cache, 256 MiB total L3 cache, and 512 GiB RAM. 5 (9 minutes). Suppose you are a black-hat hacker who is attempting to attack the professor’s applications on his laptop while he’s giving a lecture. Describe three attacks, one against privacy, one against integrity, and one against service.

[page 6] 6a (8 minutes). Explain why NFS has close-to-open consistency but not write-to-read consistency, whereas Linux’s ext4 file system has both close-to-open and write-to-read consistency. 6b (5 minutes). What effect on NFS’s performance would you expect if it had ext4’s consistency guarantees? 6c (5 minutes). What effect on ext4’s performance would you expect if we relaxed its consistency guarantees to those of NFS?

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

[page 7] 7. Your boss has an idea to improve overall system performance by modifying Linux’s page replacement algorithm to be Least Recently Written (LRW). With LRW, when there’s a page fault and you need to choose a page to evict, you choose the page that has been in memory the longest without being written to. If a page has never been written to, LRW treats it as if it had been written just before its contents were put into RAM. Here are two possible objections to LRW. For each objection, either support or oppose the objection, and briefly justify your answer. 7a (10 minutes). “Because x86-64 hardware doesn’t have hardware support for LRW in its page tables, the software overhead will be too great.” 7b (10 minutes). “Even assuming we could fix (a) somehow (say by modifying the hardware), on typical applications the LRW algorithm will perform worse than the LRU algorithm does.”

[page 8] 8. When run on a GNU/Linux x86-64 platform, this program dumps core: 1 #include <stddef.h> 2 #include <sys/fcntl.h> 3 #include <sys/mman.h> 4 int main(void) 5 { 6 int zero = open("/dev/zero", O_RDONLY); 7 void *p = mmap(NULL, 1024*8, PROT_EXEC | PROT_READ | PROT_WRITE, 8 MAP_PRIVATE, zero, 0); 9 void (*f)(void) = (void (*)(void)) p; 10 f(); 11 } The last few lines of strace output are: openat(AT_FDCWD, "/dev/zero", O_RDONLY) = 3 mmap(NULL, 8192, PROT_READ|PROT_WRITE|PROT_EXEC, MAP_PRIVATE, 3, 0) = 0x7f779ab76000 --- SIGSEGV {si_signo=SIGSEGV, si_code=SEGV_ACCERR, si_addr=0x7f779ab78000} --- +++ killed by SIGSEGV (core dumped) +++ 8a (4 minutes). Why does the program dump core? 8b (12 minutes). The strace output has two hexadecimal numbers, 0x7f779ab76000 and 0x7f779ab78000, that disagree slightly. Explain what happened and why they disagree.

[page 9] 9. For each of the following restrictions on an ext2 file system, explain (1) whether the Linux ext2 code enforces that restriction, and (2) whether you can violate that restriction if you have direct access to the on-drive representation of an ext2 file system. 9a (4 minutes). A file name component cannot contain control characters like '\r' (CR) and '\n' (LF). 9b (4 minutes). Every file has a last-modified time that is an integer count of seconds ranging from 0 (representing 1970-01-01 00:00:00 UTC) to 2**32 - 1 (representing 2106-02-06 22:28:15 UTC). 9c (4 minutes). A file name component can contain at most 255 bytes. 9d (4 minutes). A directory D cannot contain a non-‘..’ directory entry that names D’s parent. 9e (4 minutes). Every inode marked as free in the inode bitmap is free.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

[page 10] 10. (4 minutes). What is the maximum number of distinct regular files that can exist in an ext2 file system? Briefly justify your answer based on how ext2 file systems are implemented. 11 (10 minutes). It’s a bit awkward that a newly-created ext2 file system always has a lost+found directory, even though it’s empty. Why wouldn’t it have been a good idea for the ext2 designers to arrange for this directory to be created only if needed to hold directory entries?

[page 11] 12. Here’s how pthread_spin_unlock is implemented in GNU/Linux x86-64: pthread_spin_unlock: movl $1, (%rdi) xorl %eax, %eax retq 12a (8 minutes). The POSIX spec for pthread_spin_unlock says “The results are undefined if the lock is not held by the calling thread.” In practice, can one violate that rule on x86-64 GNU/Linux? That is, can one thread use pthread_spin_unlock to unlock a spin lock that was locked by a different thread? Briefly explain. 12b (10 minutes). The POSIX description for pthread_mutex_unlock says that if a thread attempts to unlock a mutex that it has not locked, the behavior is undefined for normal mutexes. Would it be practical for a platform like GNU/Linux to allow pthread_mutex_unlock to successfully unlock a normal mutex, even if invoked from a thread other than the thread that locked the mutex? or would such generosity of implementation not make sense for normal mutexes? Briefly explain by appealing to how you would implement pthread_mutex_unlock.

UCLA-COM-SCI-111-2022F-final

Related Documents