CSC 139: Project 3 Quiz Flashcards

Flashcards for reviewing the Parallel Sort with Dynamic Work Queue assignment.

Chunking Strategy

In Project 3, Dividing the input file into chunks (64 KB or smaller) aligned with record boundaries to balance memory usage and parallelism.

pthreads

In Project 3, we used these to create worker threads dynamically based on available CPU cores.

Merge Sort

A stable sorting algorithm used by each thread to sort its assigned chunk, preserving the relative order of equal keys.

pthread_cond_signal

In Project 3, this was used to wake up one of the threads waiting for work after a new chunk is added to the work queue.

pthread_cond_broadcast

In Project 3, this was called to wake up all threads waiting on the condition variable when all chunks have been enqueued.

Spurious Wakeups

A phenomenon in multithreading where a thread wakes up without an explicit signal. This can lead to unnecessary resource consumption and requires checking conditions after waking.

Synchronization Mechanisms

Mutexes and condition variables that ensure correctness without introducing deadlocks or busy-waiting.

Dynamic Work Queue

An efficient method for distributing chunks among threads, ensuring efficient utilization of CPU cores.

pthread_mutex_t

In Project 3, this acts as a lock, allowing only one thread at a time to access a shared resource, preventing race conditions and ensuring data integrity in multithreaded applications. This is crucial for synchronizing threads.

pthread_cond_t

In Project 3 , this was a condition variable used in multithreading to block a thread until a particular condition is met, facilitating synchronization between threads.

Enqueue Operation

In Project 3, this involved adding a new chunk of work to the shared queue. This operation typically requires synchronization mechanisms such as mutexes to ensure that multiple threads can safely add work without causing race conditions.

Dequeue Operation

In Project 3, this involved retrieving a chunk of work from the shared queue by a worker thread. It uses mutexes and condition variables, to ensure that only one thread retrieves a chunk at a time and that threads block when the queue is empty.