CMPSC 311 – Introduction to Concurrency (Study Notes)

Sequential Programming Paradigm

• Definition
  • Processing each client request in the exact order it arrives; the server handles one connection to completion before accepting the next.
• Canonical C Sketch

  listen_fd = Listen(port);
  while (1) {
      client_fd = accept(listen_fd);
      buf = read(client_fd);
      write(client_fd, buf);
      close(client_fd);
  }

• Benefits
  • Simple control flow; easy to reason about.
  • Minimal persistent state.
  • Few complex error cases.
• Disadvantages
  • Potentially poor performance.
  • A single slow client blocks every other client.
  • Under-utilises CPU and network resources.
• Real-world analogy
  • If an entire class (
    \approx 300 students) had to take a final sequentially, the exam would stretch to 25 days.

Motivation for Concurrency

• Goal: Serve multiple outstanding requests overlapping in time.
• Approaches discussed
  • Asynchronous, event-driven I/O: select() / epoll().
  • Multiple processes: fork() per connection.
  • Multiple threads: pthread_create() per connection.

Process-Based Concurrency (fork)

• Operational Flow
  • Parent blocks in accept().
  • On new connection:
  1. Parent calls fork().
  2. Child handles client; terminates with exit().
  3. Parent may call wait() to reap exited children (prevents zombies).
• Visual (slide depiction)
  • Parent ⇨ fork() ⇨ Child ⟹ handles client.
  • Multiple such child processes exist in parallel.
• Key System Calls
  • pid_t fork(void);
  • Returns 0 in child, >0 (child PID) in parent, <0 on error.
  • void exit(int status);
  • Ends the calling process immediately; passes status to parent.
  • pid_t wait(int *status);
  • Parent blocks until any child changes state; returns that child’s PID and fills in *status.
• Example Putting It Together

  int main(void) {
      printf("starting parent process\n");
      pid_t pid = fork();
      if (pid < 0) { perror("fork failed"); exit(EXIT_FAILURE);} 
      if (pid == 0) {
          printf("child processing\n");
          sleep(50);
          exit(19);              // child's exit status
      } else {
          printf("parent forked a child with pid = %d\n", pid);
          int status;
          wait(&status);
          printf("child exited with status = %d\n", WEXITSTATUS(status));
      }
      return 0;
  }

• Benefits
  • Near-sequential simplicity (code mostly identical).
  • True parallelism; good CPU/network utilisation.
  • Process isolation ⇒ better security (memory spaces don’t overlap).
• Drawbacks
  • Processes are heavyweight; fork() and context switches are expensive.
  • Inter-process communication (IPC) is non-trivial (pipes, sockets, shared memory, etc.).

Thread-Based Concurrency (pthreads)

• Concept
  • One process containing many independently schedulable threads.
  • Parent thread handles accept(); spawns a new thread per connection.
• Informal Definition of a Thread
  • “Independent stream of instructions” within a process that the OS scheduler may interleave or run in parallel.
  • Analogy: Multiple procedures of a program all executing concurrently.
• Process vs. Thread Memory Layout
  • Processes: each has distinct address space, stack, registers, heap.
  • Threads: share the same code & heap; each has a private stack + registers.
• POSIX Thread API Snippets
  • Create: int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg);
  • Join: int pthread_join(pthread_t thread, void **retval);
  • Exit: void pthread_exit(void *retval);
• Control Flow
  1. Main thread calls pthread_create().
  2. New thread starts at the supplied function pointer.
  3. Thread ends via return or pthread_exit().
  4. Main optionally synchronises with pthread_join().
• Caveats of Shared State
  • All file descriptors, global variables, and heap objects are visible to every thread.
  • Two pointers with equal value reference the same data.
  • Without explicit coordination, concurrent reads/writes ⇒ data races, deadlocks, undefined behaviour.

Demonstration: Data Race on a Shared Counter

• Code (buggy)

  static int counter = 0;
  void *func(void *arg) {
      for (int i = 0; i < 5000; ++i)
          ++counter;            // critical section
      return NULL;
  }
  int main(void) {
      pthread_t t1, t2;
      printf("counter = %d\n", counter);
      pthread_create(&t1, NULL, func, NULL);
      pthread_create(&t2, NULL, func, NULL);
      pthread_join(t1, NULL);
      pthread_join(t2, NULL);
      printf("both threads completed, counter = %d\n", counter);
  }

• Why Output Varies
  • Increment (++counter) expands to three assembly instructions:
  1. mov counter, %eax (load)
  2. add $0x1, %eax (modify)
  3. mov %eax, counter (store)
  • Each CPU instruction is atomic, but the entire read-modify-write sequence is not.
  • OS may context-switch between any two instructions ⇒ race condition.
• One Possible Interleaving (abridged)
  • Thread-1 executes load; scheduler pre-empts.
  • Thread-2 loads same old value, increments, stores.
  • Thread-1 resumes, increments its stale copy, stores — final count off by 1.

Eliminating Races: Mutual Exclusion

• Principle: Only one thread executes the critical section simultaneously.
• Lightweight Solution: Atomics

  #include <stdatomic.h>
  static atomic_int counter = 0;
  ... ++counter;               // now single atomic instruction

• General Solution: Mutex Locks

  static int counter = 0;
  pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
  void *func(void *arg) {
      for (int i = 0; i < 5000; ++i) {
          pthread_mutex_lock(&lock);
          ++counter;           // critical section
          pthread_mutex_unlock(&lock);
      }
  }

• Lock Pseudocode Template

  lock_t mutex
  lock(&mutex)
      critical section
  unlock(&mutex)

Benefits & Drawbacks Summary

• Process-Based
  • ✅ Simpler mental model; strong isolation; good utilisation.
  • ❌ Heavyweight creation; slower context switches; tough IPC.
• Thread-Based
  • ✅ Lower overhead; natural shared-memory communication; easy to spawn many threads (limited by OS).
  • ❌ Requires careful synchronisation; one faulty thread can crash entire process; weaker security isolation.

Connections & Further Study

• Event-driven servers (select, poll, epoll) offer concurrency without new processes/threads; covered in later lectures.
• Advanced synchronisation primitives (read-write locks, condition variables, semaphores, lock-free data structures) appear in CMPSC 473.
• Ethics & Practical Implications
  • Poorly synchronised concurrent code can cause data corruption, security issues, or catastrophic downtime.
  • Understanding concurrency is foundational for multicore performance, scalable network services, and responsive GUIs.