Final exam study guide: Spring, 2025 (CS 3650, Prof. Gene Cooperman) 1. TWO TOPICS FROM BEFORE THE MIDTERM (Please review for final) ostep.org and xv6: fd, open file table , v-node (inode, fd): https://stackoverflow.com/questions/5256599/what-are-file-descriptors-explained-in-simple-terms#answer-17741176 Section: "Hear it from the Horse's Mouth : APUE (Richard Stevens)." [ The relevant syscalls: open (the _only_ way to create a new entry in the open file table) fork (shallow copy), dup, dup2 pipe close ] Page tables for virtual memory: Chapter 18 of ostep.org: https://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf [ Keywords: virtual memory, physical memory page frame in RAM, page in swapfile ] In addition to ostep.org, another good review is at: https://www.geeksforgeeks.org/page-table-entries-in-page-table/ [ The CPU cache (direct-mapped, fully associative) will _not_ be on the final exam. ] 2. TRADITIONAL MULTITHREADING: [ ostep.org: Chapters 28 through 31; ALSO: https://course.khoury.northeastern.edu/cs3650/parent/thread-synch/ ] mutex - one resource, critical section (can be non-contiguous), global shared variables as parameters of resource pthread_mutex_lock, pthread_mutex_unlock, semaphore - multiple identical resources sem_init initializes the semaphore count (how many resources) semaphore count as an invariant: If count >= 0, it's the number of available resources If count < 0, it's the number of threads waiting for a resource sem_init, sem_wait, sem_post sem_wait atomically does two things: count--, and force sleep (waiting) if count < 0 sem_post atomically does two things: count++, and wake up exactly one thread if the count had previously been negative EXAMPLES: threadpool.c, producer-consumer.c, And Chapter 31.3 of ostep.org: Semaphores For Ordering (in Chapter 31) SEE ALSO: https://www.baeldung.com/cs/semaphore (but I prefer the above description) condition variable - user can define how many resources, and there can be multiple types of resources (e.g., permission to read; or permission to write) SEE: https://course.khoury.northeastern.edu/cs3650/parent/thread-synch/acquire-release.pdf MODEL: Acquire-Release ACQUIRE-RELEASE USING MUTEX One way to think about condition variables is to start with the very simple: pthread_mutex_lock; ...; pthread_mutex_unlock You can view this as simply: pthread_mutex_lock&lock); ...; pthread_mutex_unlock(&lock); OR: ACQUIRE(&lock); ...; RELEASE(&lock); The problem with the mutex version of ACQUIRE-RELEASE is (a) It only supports one resource (the lock) (b) If "..." involves a lot of work, then it will hold the lock for a _long_ time. So, if we want reader locks, a second reader must wait. ACQUIRE-RELEASE USING CONDITION VARIABLE ACQUIRE(&lock, &cond); ...; RELEASE(&lock, &cond); This version adds a condition variable. So, the programmer has full control of the policy for when a lock will be acquired and when a lock can be released. So, the lock can protect both reader and writer resources. For the exact code for ACQUIRE-RELEASE using condition variables, see: ostep.org (Chapter 30) or: the acquire-release.pdf shown above. ACQUIRE-RELEASE USING CONDITION SEMAPHORE Semaphores are unusual in that for a single semaphore, sem_wait and sem_post are executed by two different threads. Hence, we have: THREAD A: sem_wait(&sem) THREAD B: sem_post(&sem) OR (in acquire-release language), we can view it as: THREAD A: WAIT_TO_ACQUIRE(&cond) THREAD B: RELEASE_FROM_WAITING(&cond) CONCEPTS USED SPECICALLY IN THIS COURSE: 1. Resources (mutex/semaphore/condition variable is not about memorizing a pattern of code. It is used for an underlying concept: resources) ADVANCED (not on the final): Here is an advanced article describing resources in multithreaded programming. It presents much of what we saw in our course, but then goes on to advanced topics of how threads and resources are used for distributed systems. https://www.geeksforgeeks.org/threads-in-distributed-systems/ ADVANCED (not on the final): Here is an advanced article showing how resources can be futher generalized from threads to distributed processes across multiple computers: https://www.geeksforgeeks.org/resource-management-in-distributed-system/#best-architectures-for-resource-sharing-in-distributed-system NOTE: If these advanced topics appeal to you, consider CS 4730 – Distributed Systems https://bnrordsp.neu.edu/ssb-prod/bwckctlg.p_disp_course_detail?cat_term_in=202510&subj_code_in=CS&crse_numb_in=4730 2. Thread schedules: There are tools (McMini is one tool among many) that will examine all thread schedules of a program to find thread schedules that exhibit: deadlock, assert failure, crash (e.g., NULL pointer dereference), livelock, data races, etc. The exam will _not_ include livelock or data races. "Deadlock" is a situation where each thread is "Blocked" (for example, waiting on a mutex lock, or sleeping in the waiting room for a condition variable). Probably there is no time to do this, since our final is on the first day of Finals Week. But in a different world, you could read closely ostep.org: Chapter 30: Condition Variables where they exhibit many bugs. By adding "assert" statements to their code, you could then use McMini to directly analyze the several example "buggy" codes described in that chapter. NOTE: ostep.org home page also has a link to the code for Chapter 30: https://github.com/remzi-arpacidusseau/ostep-code/tree/master/threads-cv So, if the semester were longer, we could examine each of the "buggy" programs using McMini.