Operating Systems Interview Questions and Answers: 60 Questions from Easy to Hard

#include <stdio.h>
#include <sys/syscall.h>
#include <unistd.h>

int main(void) {
    long raw = syscall(SYS_getpid);    /* raw system call */
    pid_t lib = getpid();              /* libc wrapper */
    printf("%s, SYS_write = %d\n",
           raw == lib ? "same pid" : "different", SYS_write);
    return 0;
}

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

static atomic_flag busy = ATOMIC_FLAG_INIT;
static long counter = 0;

static void spin_lock(void) {
    /* set the flag and get its old value in one atomic step */
    while (atomic_flag_test_and_set_explicit(&busy,
                                             memory_order_acquire))
        ;                              /* spin */
}

static void spin_unlock(void) {
    atomic_flag_clear_explicit(&busy, memory_order_release);
}

static void *work(void *arg) {
    (void)arg;
    for (int i = 0; i < 1000000; i++) {
        spin_lock();
        counter++;
        spin_unlock();
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("%ld\n", counter);
    return 0;
}

#include <pthread.h>
#include <stdio.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
static int jobs = 0;

static void *worker(void *arg) {
    (void)arg;
    pthread_mutex_lock(&m);
    while (jobs == 0)                  /* re-check after every wakeup */
        pthread_cond_wait(&cv, &m);
    jobs--;
    pthread_mutex_unlock(&m);
    printf("worker took a job\n");
    return NULL;
}

int main(void) {
    pthread_t t;
    pthread_create(&t, NULL, worker, NULL);
    pthread_mutex_lock(&m);
    jobs++;                            /* change state under the lock */
    pthread_cond_signal(&cv);
    pthread_mutex_unlock(&m);
    pthread_join(t, NULL);
    printf("jobs left %d\n", jobs);
    return 0;
}

#include <pthread.h>
#include <stdio.h>

typedef struct {
    int id;
    long balance;                      /* in rupees */
    pthread_mutex_t m;
} Account;

static Account acc[2] = {
    {0, 1000000, PTHREAD_MUTEX_INITIALIZER},
    {1, 1000000, PTHREAD_MUTEX_INITIALIZER},
};

static void transfer(Account *from, Account *to, long amount) {
    /* always lock the lower id first: no circular wait */
    Account *first = from->id < to->id ? from : to;
    Account *second = from->id < to->id ? to : from;
    pthread_mutex_lock(&first->m);
    pthread_mutex_lock(&second->m);
    from->balance -= amount;
    to->balance += amount;
    pthread_mutex_unlock(&second->m);
    pthread_mutex_unlock(&first->m);
}

static void *zero_to_one(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++)
        transfer(&acc[0], &acc[1], 5);
    return NULL;
}

static void *one_to_zero(void *arg) {
    (void)arg;
    for (int i = 0; i < 100000; i++)
        transfer(&acc[1], &acc[0], 3);
    return NULL;
}

int main(void) {
    pthread_t x, y;
    pthread_create(&x, NULL, zero_to_one, NULL);
    pthread_create(&y, NULL, one_to_zero, NULL);
    pthread_join(x, NULL);
    pthread_join(y, NULL);
    printf("%ld %ld total %ld\n", acc[0].balance, acc[1].balance,
           acc[0].balance + acc[1].balance);
    return 0;
}

32-bit addresses, 4 KB pages, 4-byte entries:
  one level:  2^20 entries x 4 B = 4 MB per process
  two levels: 10 | 10 | 12 bits, each table 1024 x 4 B = 4 KB

x86-64, 48-bit virtual addresses, 4 KB pages, 8-byte entries:
  four levels: 9 | 9 | 9 | 9 | 12 bits, each table 512 x 8 B = 4 KB

EAT = (1 - p) x m + p x s

m = memory access time       = 80 ns
s = page-fault service time  = 6 ms = 6,000,000 ns
p = page-fault rate

#include <errno.h>
#include <signal.h>
#include <stdio.h>
#include <sys/wait.h>
#include <unistd.h>

static volatile sig_atomic_t reaped = 0;

static void on_child(int sig) {
    (void)sig;
    int saved = errno;
    while (waitpid(-1, NULL, WNOHANG) > 0)
        reaped++;                      /* one signal, many exits */
    errno = saved;
}

int main(void) {
    struct sigaction sa;
    sigemptyset(&sa.sa_mask);
    sa.sa_handler = on_child;
    sa.sa_flags = SA_RESTART | SA_NOCLDSTOP;
    sigaction(SIGCHLD, &sa, NULL);

    sigset_t block, old;
    sigemptyset(&block);
    sigaddset(&block, SIGCHLD);
    sigprocmask(SIG_BLOCK, &block, &old);
    for (int i = 0; i < 5; i++)
        if (fork() == 0)
            _exit(0);
    while (reaped < 5)
        sigsuspend(&old);              /* sleep, SIGCHLD unblocked */
    printf("reaped %d children\n", (int)reaped);
    return 0;
}

Inode block pointers (4 KB blocks, 4-byte block numbers):
  12 direct             -> 12 blocks
  1 single indirect     -> 1024 blocks
  1 double indirect     -> 1024 x 1024 blocks
  1 triple indirect     -> 1024 x 1024 x 1024 blocks