This Is Not The Course Website You Are Looking For

This course website is from a previous semester. If you are currently in the class, please make sure you are viewing the latest course website instead of this old one.

This is a general outline of the key concepts (arranged by topic) that you should know for the Exam 03.

Format

The exam will have the following format:

A. Scripting

  1. Shell Scripting (multiple choice).

  2. Python Scripting (multiple choice).

  3. Unix Philosophy (multiple choice).

B. C

  1. Compiling and Building (multiple choice, fill-in-the-blank).

  2. Pointers, Arrays, Strings (multiple choice, fill-in-the-blank).

  3. Memory Allocations (multiple choice, fill-in-the-blank).

  4. Memory Management: (multiple choice, fill-in-the-blank).

C. System Calls

  1. File System (multiple choice, fill-in-the-blank).

  2. Networking (multiple choice, fill-in-the-blank).

  3. Processes (multiple choice, fill-in-the-blank).

  4. Programming: Write a C program that uses system calls (coding on the computer).

All portions of the exam will take place online. Parts A, B, and C. 1 - 3 will be an online quiz while Part C. 4 will require submitting code to your assignments repository.

Representative, but not Exhaustive

The final exam will be a comprehrensive assessment. This means that everything we have discussed this semester is considered fair game.

That said, the majority of the test will cover the last third of the class, as detailed below.

This check list is meant to be representative, rather than exhaustive (ie. there may be questions that show up on the exam that are not shown below).


Scripting

  1. What is Unix?

  2. What are the principles of functional programming?

  3. What is concurrency and what is parallelism?


Shell

How do you construct a unix pipeline to do the following:

  1. Extract a fields or characters.

  2. Search based on a pattern.

  3. Count the number of lines.

  4. Search a directory based on a pattern or file attribute.

  5. List the processes on the current machine.

Sample Question

Which of the following pipelines counts all the "Permission denied" errors encountered when recursively searching file names under the "/etc" directory?


Python

  1. How do you use map, filter, and lambda?

  2. How do you use list comprehensions?

  3. How do you use generator expressions?

  4. How do you split and join strings?

Sample Question

Given a list of integers called numbers, produce a new list called fives which consist only of the multiples of 5 by using filter and lambda.

Then, do the same thing using list comprehensions.

Exam 01 and 02

You may wish to review Exam 01 and Exam 02, along with previous quizzes assocated with those exams.


C

  1. Why bother with C? Why not just Python or C++?

  2. Why is C considered a systems programming language?

  3. What is C's relationship to Unix?


Compiling and Makefiles

  1. What is the compiler pipeline?

    • What exactly happens when you compile a program (ie. describe the compiler pipeline)?

    • What is the difference between a dynamic executable and a static executable?

    • What is the difference between a shared library and a static library?

  2. How do you write a Makefile that utilizes rules and variables for a program that consists of multiple files?

Sample Questions

  1. Why is it important to specify all the dependencies of a target in a Makefile rule?

  2. What is the difference between compiling and linking? What are some common errors that can occur in each phase?

  3. Write a Makefile for a project that outputs a shared library, a static library, a dynamic executable, and a static executable.


Pointers, Arrays, Strings

  1. What exactly is a pointer? array? string? How are they related?

  2. What does it mean to dereference a pointer?

  3. How do we get the address of a variable?

  4. What are multiple ways to access an element of an array or string?

  5. What is the difference between little-endian and big-endian?

Sample Question

Given the following code:

int main(int argc, char *argv[]) {  // | Label | Address | Value |
    int  n   = 16;                  // |       | 0xF     |       |
    int  a[] = {n};                 // | n     | 0xE     | 0x10  |
    int *p   = a;                   // |       | 0xD     |       |
    return 0;                       // |       | 0xC     |       |
}                                   // |       | 0xB     |       |

Assuming a little-endian 16-bit machine where each integer is 2 bytes, each character is 1 byte, and each pointer is 2 bytes, fill in the stack frame to the right by recording the location of the variables above and their values at the appropriate addresses.

The variable n is done for you; you need to add p and a to the stack frame.

Distinguish between the character 0 and the integer 0 by using hexadecimal for integers.


Memory Allocation

  1. What is the difference between a struct and a union?

  2. How much memory is allocated when we declare an int, float, double, char, array, string, or pointer?

  3. When we declare a variable, where is the data allocated (stack, heap, data, code)?

  4. How does word alignment influence the amount of memory allocated for structs and unions?

Sample Question

Given the following C program:

typedef struct
{
    char key;
    int  value;
} Pair;

int main(int argc, char* argv[])
{
    char    c = 'k';
    int     v = 2;

    Pair   p0 = {c, v};
    Pair  *p1 = malloc(sizeof(Pair));
    Pair  *p2 = calloc(v, sizeof(Pair));
    Pair **p3 = calloc(v, sizeof(Pair *));
    return 0;
}

How much memory was allocated on the stack, heap, and data for each of the variables in the main function?

Big Brain

Review Reading 10: Memory Management.


Memory Management

  1. How do we dynamically allocate memory? How do we deallocate that memory?

  2. When should we allocate on the stack? heap? data? What are the advantages and disadvantages of utilizing each memory segment?

  3. How do we detect and fix memory errors such as: segmentation faults, invalid reads, uninitialized memory, and memory leaks?

  4. What is singly-linked list?

  5. What is hash table?

Sample Questions

  1. Given the following C program:

    typedef struct Node
    {
        int value; 
        struct Node *next; 
    } Node;
    
    typedef struct {
        Node *head;
    } List;
    
    void list_fprint(List *l, FILE *stream)
    {
        for (Node *c = l->head; c; c = c->next)
            fprintf(stream, "%d\n", c->value);
    }
    
    bool list_remove(List *l, int v)
    {
        // TODO
    }
    
    int main(int argc, char *argv[])
    {
        List l;
        char buffer[BUFSIZ];
    
        while (fgets(buffer, BUFSIZ, stdin))
        {
            Node *next  = calloc(1, sizeof(Node));
            next->value = atoi(buffer);
            next->next  = l.head;
            l.head      = next;
        }
    
        list_fprint(&l, stdout);
        list_remove(&l, 42);
        return 0;
    }
    

    Given the linked list code above, implement the list_remove function which removes all nodes that contain the specified value.  Return whether or not any node was removed.

  2. Given the follow hash table (with linear probing) implementation at https://yld.me/raw/eRVG.c:

    /* hash_table.c */
    
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    /* Constants */
    
    #define DEFAULT_BUCKETS (1<<5)
    
    /* Structures */
    
    typedef struct
    {
        int    *data;
        size_t buckets;
    } Table;
    
    /* Functions */
    
    Table * table_create(size_t buckets)
    {
        Table *t = malloc(sizeof(Table));
        if (t)
        {
            t->buckets = (buckets ? buckets : DEFAULT_BUCKETS);
            t->data    = malloc(sizeof(int) * buckets);
        }
        return t;
    }
    
    void    table_delete(Table *t)
    {
        free(t);
    }
    
    bool    table_insert(Table *t, int value)
    {
        size_t hash = value;
    
        for (size_t offset = 0; offset < t->buckets; offset++)
        {
            size_t bucket = hash + offset;
            if (!t->data[bucket])
            {
                t->data[bucket] = value;
                return true;
            }
            if (t->data[bucket] == value)
            {
                return false;
            }
        }
    
        return false;
    }
    
    bool    table_search(Table *t, int value)
    {
        size_t hash = value;
    
        for (size_t offset = 0; offset < t->buckets; offset++)
        {
            size_t bucket = hash + offset;
            if (!t->data[bucket])
            {
                return false;
            }
            if (t->data[bucket] == value)
            {
                return true;
            }
        }
    
        return false;
    }
    
    /* Main Execution */
    
    int main(int argc, char *argv[])
    {
        int   d[] = {4, 6, 5, 5, 6, 0};
        Table  *t = table_create(0);
    
        for (int *p = d; *p; p++)
        {
            table_insert(t, p);
        }
    
        for (int i = 0; i < 10; i++)
        {
            printf("table_search(%d) = %s\n", i, table_search(t, i) ? "true" : "false");
        }
    
        table_delete(t);
        return EXIT_SUCCESS;
    }
    
    1. Compile and run the code using gdb. Where does the program segfault?

    2. Which line do you need to change to fix these errors?

    3. Compile and run the code using valgrind. What type of memory errors are there?

    4. Which line do you need to change to fix these errors?

    5. Compile and run the code using valgrind. What type of memory errors are there?

    6. Which line do you need to change to fix these errors?

    7. Compile and run the code using valgrind. What type of memory errors are there?

    8. Which line do you need to add to fix these errors?

    9. Both the table_insert and table_search do not compute the hash correctly. What is missing?

    10. Implement table_remove(Table *t, int value)


System Calls

  1. What exactly are system calls?

  2. What are some reasons why system calls related to files, processes, and networking would fail?

    • How do we check these failures?

    • How do we get the error message related to these failures?


Files

  1. What is the difference between open and fopen?

  2. What exactly is a file descriptor and what system calls can we do with one?

  3. How do we get the inode information for a file?

Sample Question

How would you use system calls in C to accomplish the following tasks:

Big Brain

Review Reading 11: using system calls to manipulate files and directories.


Networking

  1. What is networking?

  2. What is a URL and what are its components?

  3. How are sockets like files? How are they different?

  4. What is HTTP?

    • What system calls does a typical HTTP client perform? What messages does it send and receive?

    • What system calls does a typical HTTP server perform? What messages does it send and receive?

Sample Question

Modify http_client.c to implement a port scanner (ie. nc -z).

Big Brain

Review Reading 12: using sockets to connect to another machine.

Processes

  1. What is a process?

    • What attributes or components does it have?

    • What system calls can you do with them?

  2. What happens during the life cycle of a typical process?

    • After a fork, how does a process determine if they are the child or parent?

    • After a fork, who executes first: parent or child?

    • What happens when a process performs exec?

    • Why is it necessary to perform a wait?

    • What is the purpose of exit?

  3. How do we prevent a fork bomb?

    • How do we prevent zombies?

    • Why would we want to prevent these situations?

  4. What is a signal?

Sample Question

Given the following C code:

/* forking.c */

#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char *argv[])
{
    int status = 0;

    for (int i = 1; i < argc; i++)
    {
        pid_t pid = fork();

        if (pid < 0)
        {
            return EXIT_FAILURE;
        }

        if (pid == 0)
        {
            execlp(argv[i], "forkit", NULL);
        }
    }

    for (int i = 1; i < argc; i++)
    {
        int child_status;
        while (wait(&child_status) < 0)
        {
            status += child_status;
        }
    }

    return status;
}

Which of the following statements are true (select all that apply)?

  1. The execlp always succeeds.
  2. The execlp always fails.
  3. The execlp may succeed depending on the arguments.
  4. main will always return with success.
  5. main will always return with failure.
  6. main will may return with success depending on the arguments.
  7. At most one child process may run concurrently with the parent.
  8. Multiple child processes may run concurrently with the parent.
  9. This program has fork bomb potential.
  10. This program does not have fork bomb potential.
  11. This program always terminates gracefully.
  12. This program sometimes hangs indefinitely.

Big Brain

Review Reading 13: using fork, exec, and wait.