COMP1521 Revision 11 Sample Solutions

Revision Exercise: Print file contents (PS)

write a c program show_file so that, given a single command line argument containing the path to a file, it reads and prints the contents of that file to standard output. For example:

cat sample.txt
Hello, world!
./show_file sample.txt
Hello, world!
cat three_lines.bin
one
two
three
./show_file three_lines.bin
one
two
three

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest show_file

Sample solution for show_file.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
    // check for errors
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <file>\n", argv[0]);
        exit(1);
    }

    // open the file
    FILE *f = fopen(argv[1], "r");
    if (f == NULL) {
        perror(argv[1]);
        exit(1);
    }

    //serially, read in bytes and output them to the stdout.
    int c;
    while ((c = fgetc(f)) != EOF) {
        fputc(c, stdout);
    }

    fclose(f);

    return 0;
}

Revision Exercise: Copy File (PS)

Write a C program copy_file so that, given two command line arguments — the first being the path to a source file to be read, and the second being the path to a destination file — it copies the contents of the source file to the destination file.

If the destination file already exists, it should be overwritten.
If the destination file does not exist, it should be created.

For example:

echo "Hello, world!" > sample.txt
cat sample.txt
Hello, world!
./copy_file sample.txt copy.txt
cat copy.txt
Hello, world!

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest copy_file

Sample solution for copy_file.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <source> <destination>\n", argv[0]);
        return 1;
    }

    FILE *source = fopen(argv[1], "r");
    if (source == NULL) {
        perror(argv[1]);
        return 1;
    }

    FILE *destination = fopen(argv[2], "w");
    if (destination == NULL) {
        perror(argv[2]);
        fclose(source);
        return 1;
    }

    int c;
    while ((c = fgetc(source)) != EOF) {
        if (fputc(c, destination) == EOF) {
            perror("fputc");
            fclose(source);
            fclose(destination);
            return 1;
        }
    }

    fclose(source);
    fclose(destination);
    return 0;
}

Revision Exercise: Print the type of a file (PS)

Write a C program file_type so that, given one command line argument — the path to a source file. print out whether the file is a regular file, a directory, or a symbolic link.

For example:

echo "HIIII" > sample.txt
./file_type sample.txt
file
mkdir some_directory
./file_type some_directory
directory
ln -s sample.txt some_symlink
./file_type some_symlink
symbolic link

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest file_type

Sample solution for file_type.c

#include <stdio.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
    struct stat fileStat;
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s <file>\n", argv[0]);
        exit(1);
    }

    //use lstat instead of stat
    if (lstat(argv[1], &fileStat) < 0)
    {
        perror("lstat");
        exit(1);
    }

    //check if reg
    if (S_ISREG(fileStat.st_mode))
    {
        printf("file\n");
    }

    //check for directory
    else if (S_ISDIR(fileStat.st_mode))
    {
        printf("directory\n");
    }
    
    //check for symlink
    else if (S_ISLNK(fileStat.st_mode))
    {
        printf("symbolic link\n");
    }

    return 0;
}

Revision Exercise: Remove the first half of a file (PS)

Computer viruses are pieces of code that infect computers and can corrupt data and replicate themselves. An example of this would be a virus that deletes the first half of files. For educational purposes only you'll be writing a c program to do this.

Write a C program halving_virus so that, given one command line argument, a path to a file, it removes the first half of the file. That is to say, if the source file is four bytes long, bytes 2, 3 should be kept in the file and bytes 0, 1 should be removed from the file.
Odd file sizes are to be rounded such that a source file that has 5 bytes should only keep bytes 3, 4, 5.

If the size of the source file is less than or equal to one byte, your program should remove all contents of the file.

For example:

echo "Hello, world!" > sample.txt
cat sample.txt
Hello, world!
./halving_virus sample.txt
Halved sample.txt
cat sample.txt
world!
echo 1234 > five_bytes.txt
cat five_bytes.txt
1234
./halving_virus five_bytes.txt
Halved five_bytes.txt
cat five_bytes.txt
34
echo 123 > four_bytes.txt
cat four_bytes.txt
123
./halving_virus four_bytes.txt
Halved four_bytes.txt
cat four_bytes.txt
3

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest halving_virus

Sample solution for halving_virus.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
        exit(1);
    }

    FILE *file = fopen(argv[1], "r");
    if (file == NULL)
    {
        fprintf(stderr, "Error: Unable to open file %s\n", argv[1]);
        exit(1);
    }

    FILE *tmp_file = fopen("temp", "w");
    if (tmp_file == NULL) {
        perror("tmp file");
        exit(1);
    }

    struct stat st;
    if (stat(argv[1], &st) == -1)
    {
        fprintf(stderr, "Error: Unable to get file size\n");
        exit(1);
    }

    long size = st.st_size;
    if (size > 1) {

        long half = size / 2;
        // printf("size=%ld,half=%ld\n", size,half);

        fseek(file, half, SEEK_SET);

        int c;
        while ((c = fgetc(file)) != EOF) {
            fputc(c, tmp_file);
        }
    }

    fclose(file);
    fclose(tmp_file);
    rename("temp", argv[1]);

    printf("Halved %s\n", argv[1]);


    return 0;
}

Revision Exercise: Extract File Permissions (PS)

Write a C program extract_permissions so that, given one command line argument — the path to a source file. Print out the equivalent octal number of the permission, it's bitwise representation, and the formatted permissions string.

To get For example:

# copy and run the following commands to make some example files
mkdir examples; touch examples/000.s examples/777.c examples/sample.txt
chmod 000 examples/000.s
chmod 777 examples/777.c
ls -l examples
total 0
---------- 1 z5555555 z5555555 0 Apr 29 12:27 000.s
-rwxrwxrwx 1 z5555555 z5555555 0 Apr 29 12:27 777.c
-rw-r--r-- 1 z5555555 z5555555 0 Apr 29 12:27 sample.txt

./extract_permissions ./examples/sample.txt
Octal: 664, Bitwise: 110110100, String: rw-r--r--
./extract_permissions ./examples/000.s
Octal: 0, Bitwise: 000000000, String: ---------
./extract_permissions ./examples/777.c
Octal: 777, Bitwise: 111111111, String: rwxrwxrwx

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest extract_permissions

Sample solution for extract_permissions.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <file>\n", argv[0]);
        return 1;
    }

    struct stat file_stat;
    if (stat(argv[1], &file_stat) == -1) {
        perror("stat");
        return 1;
    }

    // get the permissions string
    char permissions[10];
    permissions[0] = (file_stat.st_mode & S_IRUSR) ? 'r' : '-';
    permissions[1] = (file_stat.st_mode & S_IWUSR) ? 'w' : '-';
    permissions[2] = (file_stat.st_mode & S_IXUSR) ? 'x' : '-';
    permissions[3] = (file_stat.st_mode & S_IRGRP) ? 'r' : '-';
    permissions[4] = (file_stat.st_mode & S_IWGRP) ? 'w' : '-';
    permissions[5] = (file_stat.st_mode & S_IXGRP) ? 'x' : '-';
    permissions[6] = (file_stat.st_mode & S_IROTH) ? 'r' : '-';
    permissions[7] = (file_stat.st_mode & S_IWOTH) ? 'w' : '-';
    permissions[8] = (file_stat.st_mode & S_IXOTH) ? 'x' : '-';
    permissions[9] = '\0';

    int octal = file_stat.st_mode & 0777;
    int bitwise = octal;

    printf("Octal: %o, Bitwise: ", octal);
    for (int j = 8; j >= 0; j--) {
        printf("%d", (bitwise & (1 << j)) ? 1 : 0);
    }
    printf(", String: %s\n", permissions);

    return 0;
}

Revision Exercise: Hackerman (CR-DN)

Write a C program hackerman so that, given one command line argument — the directory to be searched, hackerman recursively searches through the directory and it's sub-directories to find passwords.

The password will always be the contents of a file named "password", although the file's extension may vary. (e.g. password.bin, password, password.txt are all valid password files!!)

For security purposes, the admins have limited your ability to access certain files and directories, however passwords may be hidden behind these security measures and they will need to be found anyways. You should try to change the permissions of files and directories you find to gain access. To do this you can use chmod(2) to make the file public and group readable.

If the password is found, print the password to stdout along with the filename where it was found.
If the password cannot be found, your program should print "Passwords not found\n" and then exit(3) with status 0

Use the following command to get a directory to test your program with

cp -r  /web/cs1521/25T1/activities/hackerman/hackerman_examples .

For example:

# copy and run the following commands get a directory to test your program on
cp -r  /web/cs1521/25T1/activities/hackerman/hackerman_examples .
ls -l hackerman_examples
total 16
drwxrwxrwx 2 z5555555 z5555555 4096 Feb  5 22:49 empty
drwxrwxrwx 2 z5555555 z5555555 4096 Feb  5 22:32 inner_folder
-rwxrwxrwx 1 z5555555 z5555555    8 Feb  5 22:16 password.txt
drwxrwxrwx 2 z5555555 z5555555 4096 Feb  5 22:36 security_folder
cat hackerman_examples/inner_folder/password
prettier
./hackerman hackerman_examples/inner_folder
Password heheheha found in 1521/admins/passwords/password.txt
cat hackerman_examples/security_folder/password.bin
cat: hackerman_examples/security_folder/password.bin: Permission denied
./hackerman hackerman_examples/security_folder
Password "hidden behind a firewall!" found in hackerman_examples/security_folder/password.bin
cat hackerman_examples/password.txt
glazeeee
./hackerman hackerman_examples
Password prettier found in hackerman_examples/inner_folder/password
Password glazeeee found in hackerman_examples/password.txt
Password "hidden behind a firewall!" found in hackerman_examples/security_folder/password.bin
ls -l hackerman_examples/empty
total 4
-rwxrwxrwx 1 z5360323 z5360323 9 Feb  5 22:49 pword_in_body
./hackerman empty
Passwords not found

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest hackerman

Sample solution for hackerman.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>
#include <sys/stat.h>

#define MAX_PASSWORD_LENGTH 127
#define MAX_PATHNAME_LENGTH 1024

int recursive_search(char *dir);

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <directory>\n", argv[0]);
        exit(1);
    }

    chmod(argv[1], 0777);
    if (recursive_search(argv[1]) == 1) {
        printf("Passwords not found\n");
    };

    return 0;
}

int recursive_search(char *dir) {
    DIR *dp;
    struct dirent *entry;
    struct stat statbuf;
    char *new_path = malloc(MAX_PATHNAME_LENGTH);
    int found = 1;

    //open stats of the directory
    if ((dp = opendir(dir)) == NULL) {
        fprintf(stderr, "Cannot open directory %s\n", dir);
        return 1;
    }

    //search through current directory
    while ((entry = readdir(dp)) != NULL) {
        //append name onto file path.
        snprintf(new_path, MAX_PATHNAME_LENGTH, "%s/%s", dir, entry->d_name);
        //change permissions of file to ensure accessibility
        chmod(new_path, 0777);
        lstat(new_path, &statbuf);
        //recurse if directory
        if (S_ISDIR(statbuf.st_mode)) {
            if (strcmp(".", entry->d_name) == 0 || strcmp("..", entry->d_name) == 0) {
                continue;
            }
            int temp = recursive_search(new_path);
            if (temp == 0) {
                found = 0;
            }
        } else {
            //if file, check if filename matches format
            if (strstr(new_path, "password") != NULL) {
                found = 0;
                FILE *fp = fopen(new_path, "r");
                if (fp == NULL) {
                    fprintf(stderr, "Cannot open file %s\n", new_path);
                    return 1;
                    
                }

                char password[MAX_PASSWORD_LENGTH];
                if (fread(password, 1, MAX_PASSWORD_LENGTH, fp) == 0) {
                    fprintf(stderr, "Cannot read file %s\n", new_path);
                    return 1;
                }
                struct stat s;
                stat(new_path, &s);
                password[s.st_size] = '\0';
                printf("Password %s found in %s\n", password, new_path);
                fclose(fp);
            }
        }
    }

    free(new_path);
    closedir(dp);
    return found;
}

Revision Exercise: JSON decoder (CR)

Write a C program json_decoder so that, given two or more command line arguments — the first being the path to a source file to be read, and the rest being keys. your program should print the value of that key to stdout.

If the key is not found, print nothing.

as a reminder, JSON follows this generic format:
{ "key1": value1, "key2": value2, ... }

Run the following command to get an example JSON file to test your program with

cp /web/cs1521/25T1/activities/json_decoder/files.ln/months.json .

For example:

    cat months.json
    {
        "january": 1,
        "february": 2,
        "march": 3,
        "april": 4,
        "may": 5,
        "june": 6,
        "july": 7,
        "august": 8,
        "september": 9,
        "october": 10,
        "november": 11,
        "december": 12,
        "selected": "may"
    }    
    ./json_decoder months.json august
    8
    ./json_decoder months.json selected
    "may"
    ./json_decoder months.json january december
    1 12
    ./json_decoder months.json pluto
    this should print nothing!

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest json_decoder

Sample solution for json_decoder.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    size_t len = 1024;
    
    
    char *token;

    //fopen
    FILE *fp = fopen(argv[1], "r");
    if (fp == NULL)
    {
        printf("File not found\n");
        exit(1);
    }
    //print argc
    for (int i = 2; i < argc; i++)
    {
        char key[1024];
        sprintf(key, "\"%s\"", argv[i]);


        fseek(fp, 0, SEEK_SET);
        //search through for the key line by line
        char line[len];
        char copy[len];
        while (fgets(line, len, fp) != NULL)
        {
            //copy the line
            strcpy(copy, line);
            if ((token = strtok(copy, ":")) != NULL) {
                if (strstr(token, key) != NULL)
                {
                    
                    //set the file pointer correctly
                    fseek(fp, -1*strlen(line), SEEK_CUR);

                    //skip the key, the colon and the blank space.
                    fseek(fp, strlen(token) + 2, SEEK_CUR);
                    //read the byte by byte into a string until the comma
                    int byte;
                    while ((byte = fgetc(fp)) != EOF)
                    {
                        if (byte == ',' || byte == '\n')
                        {
                            break;
                        }
                        printf("%c", byte);
                    }
                    printf("\n");
                }
            } else {
                return 1;
            }
            
        }
    }


    fclose(fp);
    return 0;
}

Revision Exercise: Detect C Files (CR)

Run the following commands to get the files required for this question:

cp -n /web/cs1521/25T1/activities/detect_c_files/files.cp/detect_c_files.c detect_c_files.c
cp -n /web/cs1521/25T1/activities/detect_c_files/files.ln/check_c_file.c detect_c_file.c
cp -r /web/cs1521/25T1/activities/detect_c_files/detect_c_file_examples detect_c_files_examples

Add code to detect_c_files.c so that when given a list of pathnames as command line arguments, it checks each to see if it's a c file or not.

We have provided a c program check_c_file.c which takes a single pathname as a command line argument, and returns 1 if given a c file and 0 otherwise.

There are two parts to this question. First in the main function spawn a process to compile check_c_file.c.

Secondly, complete the spawn_programs function so that given a list of filenames, and the length of that list, you spawn processes to run ./check_c_file in parallel on each filename.

You should wait for each child process to return (see waitpid(3)), then use the return value to print whether the file is or is not c program.

dcc detect_c_files.c -o detect_c_files
./detect_c_files detect_c_files.c check_c_file.c
detect_c_files.c is a C file
check_c_file.c is a C file
./detect_c_files detect_c_files.c detect_c_file_examples/*
detect_c_files.c is a C file
detect_c_file_examples/a.txt is NOT a C file
detect_c_file_examples/b.txt is NOT a C file
detect_c_file_examples/hello.c is a C file
detect_c_file_examples/hello.txt is NOT a C file
detect_c_file_examples/nonsense.c is a C file
detect_c_file_examples/test.s is NOT a C file
detect_c_file_examples/trick.c is a C file

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest detect_c_files

Sample solution for detect_c_files.c

// Sample solution for COMP1521 exercises
//
// Detects C files in parallel
//
// Author: Jimmy Kirkpatrick <z5480564@unsw.edu.au>

#include <stdio.h>
#include <stdlib.h>
#include <spawn.h>
#include <sys/types.h>
#include <sys/wait.h>

#define DCC_PATH "/usr/local/bin/dcc"
#define CHECK_C_FILE_PATH "./check_c_file"


extern char **environ;

void spawn_programs(char *filenames[], int len);

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <file>\n", argv[0]);
        return 1;
    }

    // ADD CODE HERE TO COMPILE 'check_c_file.c'
    char *compile_args[] = {DCC_PATH, "check_c_file.c", "-o", "check_c_file", NULL};
    pid_t pid;
    posix_spawn(&pid, DCC_PATH, NULL, NULL, compile_args, environ);
    waitpid(pid, NULL, 0);

    spawn_programs(&argv[1], argc - 1);

    return 0;
}

// spawns processes to check (in parallel) whether each
// filename in filenames array is a c file by calling the
// ./is_c_file executable
void spawn_programs(char *filenames[], int len) {
    // array to store pids
    pid_t pids[len];

    // spawn all processes
    for (int i = 0; i < len; i++) {
        char *check_argv[] = {CHECK_C_FILE_PATH, filenames[i], NULL};
        posix_spawn(&pids[i], CHECK_C_FILE_PATH, NULL, NULL, check_argv, environ);
    }

    // wait for processes to finish
    for (int i = 0; i < len; i++) {
        int status;
        waitpid(pids[i], &status, 0);

        // check exit status of ./check_c_file
        if (WEXITSTATUS(status) == 0) {
            printf("%s is a C file\n", filenames[i]);
        } else {
            printf("%s is NOT a C file\n", filenames[i]);
        }
    }

}

Revision Exercise: Append Date to File (DN)

Download date_file.c, or copy it to your CSE account using the following command:


cp -n /web/cs1521/25T2/activities/date_file/files.cp/date_file.c date_file.c

Your task is to add code to this function in date_file.c:

void append_date_to_file(char *filename) {
    // TODO: complete this function

    return;

}

Add code to the function append_date_to_file so that given a filename, you append the current date to the end of the file.
For example:

echo "helllooooo" > hi.txt
cat hi.txt
helllooooo
./date_file hi.txt
Appended date to hi.txt
cat hi.txt
helllooooo
Mon Apr 28

To do this, you should use posix_spawn to run the date command, with the following format string:

date '+%a %b %d'
Mon Apr 28

You will need to use pipes with posix spawn to capture the output and redirect it into the file. The lecture example spawn_read_pipe.c is an example of how to do this.

To access and/or redirect the output of a spawned process, you will need to use pipe(2). The pipe(2) manual entry has an example at the bottom of how it can be used.
You will need to open the given file in append mode, then tell your spawned process to output to it. posix_spawn works with file descriptors, not file pointers (FILE *).
There are a few options here. You can use the open(2) syscall, which returns a file descriptor. You could instead use fopen(3) which returns a file pointer (FILE *), then use fileno(3) to get a file decriptor from it.
```
// OPTION 1: open()
int fd = open(filename, O_APPEND | O_WRONLY | O_CREAT);

// OPTION 2: fopen()
FILE *f = fopen(filename, "a");
int fd = fileno(f);
```

You will need to create a posix_spawn_file_actions_t object, and pass this to posix_spawn when you create your process. To create it, you will need to use posix_spawn_file_actions_init(3).
To redirect the input or output of your created process use posix_spawn_file_actions_adddup2(3).
To close a file descriptor related to the process use posix_spawn_file_actions_addclose(3).

Once your process has run, you should use posix_spawn_file_actions_destroy to destroy your file actions object.

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest date_file

Sample solution for date_file.c

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


extern char **environ;

#define DATE_PATH "/usr/bin/date"
#define STDOUT_NO 1

void append_date_to_file(char *filename);

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc; i++) {
        append_date_to_file(argv[i]);
    }
    return 0;
}

void append_date_to_file(char *filename) {
    // create a pipe
    int pipe_file_descriptors[2];
    if (pipe(pipe_file_descriptors) == -1) {
        perror("pipe");
        exit(1);
    }

    //pipe_file_descriptors[0] => read end of pipe
    //pipe_file_descriptors[1] => write end of pipe

    // use open to get file descriptor for appending to file
    FILE *append_f = fopen(filename, "a");
    if (append_f == NULL) {
        perror(filename);
        exit(1);
    }
    // get file descriptor for file we want to append to
    int append_fd = fileno(append_f);
    // set write end of pipe to be append_fd
    // i.e. send process output to file
    pipe_file_descriptors[1] = append_fd;

    // create a list of file actions to be carried out on spawned process
    posix_spawn_file_actions_t actions;
    if (posix_spawn_file_actions_init(&actions) != 0) {
        perror("posix_spawn_file_actions_init");
        exit(1);
    }

    // tell spawned process to close unused read end of pipe
    // without this - spawned process would not receive EOF
    // when read end of the pipe is closed below,
    if (posix_spawn_file_actions_addclose(&actions, pipe_file_descriptors[0]) != 0) {
        perror("posix_spawn_file_actions_init");
        exit(1);
    }

    // tell spawned process to replace file descriptor 1 (stdout)
    // with write end of the pipe (append_fd)
    if (posix_spawn_file_actions_adddup2(&actions, pipe_file_descriptors[1], 1) != 0) {
        perror("posix_spawn_file_actions_adddup2");
        exit(1);
    }

    pid_t pid;
    char *date_argv[] = {DATE_PATH, "+%a %b %d", NULL};
    if (posix_spawn(&pid, DATE_PATH, &actions, NULL, date_argv, environ) != 0) {
        perror("spawn");
        exit(1);
    }

    waitpid(pid, NULL, 0);

    // close unused write end of pipe
    // in some case processes will deadlock without this
    // not in this case, but still good practice
    close(pipe_file_descriptors[1]);

    posix_spawn_file_actions_destroy(&actions);

    fclose(append_f);

    printf("Appended date to %s\n", filename);
    return;

}

Revision Exercise: Robot Arms: threads and mutex (DN)

Download robot_arms.c, or copy it to your CSE account using the following command:


cp -n /web/cs1521/25T2/activities/robot_arms/files.cp/robot_arms.c robot_arms.c

In this question we are writing code to automate a robot manufacturing line. The robot we're making has four arms, each made using some of three components. To make robots as quickly as possible we're going to do it in parallel using threads.

You have been given robot_arms.c, which contains an empty main function, and four thread functions; arm1, arm2, arm3, and arm4. Each "assembles" a robot arm using a mix of components; component A, component B, and component C.

In main, you should create four threads to do the arm1, arm2, arm3, and arm4 in parallel.
You should wait until all four threads have finished before you return from main.

There are three components, A, B and C, each component can only be used to make one arm at a time. We use mutexes component_A_mutex, component_B_mutex, and component_C_mutex to represent them.

You should add code to lock and unlock each component mutex when the arm functions are using them. You should use pthread_mutex_lock(3) to lock the component before the arm acquires it, and pthread_mutex_unlock(3) once the arm is finished assembling.

Think about how you can avoid deadlock - a state where all arms are waiting for components held by others.

When your program is working, it should look like this:

dcc -pthread robot_arms.c -o robot_arms
./robot_arms
Arm 1 acquired Component A
Arm 2 acquired Component C
Arm 2 acquired Component B
Arm 2 is assembling
Arm 1 acquired Component C
Arm 1 is assembling
Arm 4 acquired Component A
Arm 4 acquired Component B
Arm 4 is assembling
Arm 3 acquired Component C
Arm 3 acquired Component A
Arm 3 is assembling

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest robot_arms

Sample solution for robot_arms.c

/*
    Idea: order of locking is important

    A robot has 4 arms:
        Arm 1 is made of component A and C
        Arm 2 is made of component C and B
        Arm 3 is made of component C and A
        Arm 4 is made of component B and A
*/

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

pthread_mutex_t component_A_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t component_B_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t component_C_mutex = PTHREAD_MUTEX_INITIALIZER;

// Arm 1 must get component A and component C
void* arm1(void* arg) {
    pthread_mutex_lock(&component_A_mutex);
    printf("Arm 1 acquired Component A\n");

    pthread_mutex_lock(&component_C_mutex);
    printf("Arm 1 acquired Component C\n");

    printf("Arm 1 is assembling\n");

    pthread_mutex_unlock(&component_C_mutex);
    pthread_mutex_unlock(&component_A_mutex);
    return NULL;
}

// Arm 2 must acquire component C and component B
void* arm2(void* arg) {
    pthread_mutex_lock(&component_B_mutex);
    printf("Arm 2 acquired Component B\n");

    pthread_mutex_lock(&component_C_mutex);
    printf("Arm 2 acquired Component C\n");

    printf("Arm 2 is assembling\n");

    pthread_mutex_unlock(&component_C_mutex);
    pthread_mutex_unlock(&component_B_mutex);
    return NULL;
}

// Arm C must acquire component A and component C
void* arm3(void* arg) {
    pthread_mutex_lock(&component_A_mutex);
    printf("Arm 3 acquired Component A\n");

    pthread_mutex_lock(&component_C_mutex);
    printf("Arm 3 acquired Component C\n");

    printf("Arm 3 is assembling\n");

    pthread_mutex_unlock(&component_C_mutex);
    pthread_mutex_unlock(&component_A_mutex);
    return NULL;
}

// arm 4 must acquire component A and component B
void* arm4(void* arg) {
    pthread_mutex_lock(&component_A_mutex);
    printf("Arm 4 acquired Component A\n");

    pthread_mutex_lock(&component_B_mutex);
    printf("Arm 4 acquired Component B\n");


    printf("Arm 4 is assembling\n");

    pthread_mutex_unlock(&component_B_mutex);
    pthread_mutex_unlock(&component_A_mutex);
    return NULL;
}

int main() {
    // Create four threads to assemble each arm
    pthread_t thread_id1;
    pthread_t thread_id2;
    pthread_t thread_id3;
    pthread_t thread_id4;
    pthread_create(&thread_id1, NULL, arm1, NULL);
    pthread_create(&thread_id2, NULL, arm2, NULL);
    pthread_create(&thread_id3, NULL, arm3, NULL);
    pthread_create(&thread_id4, NULL, arm4, NULL);

    // Wait for all four threads to finish
    pthread_join(thread_id1, NULL);
    pthread_join(thread_id2, NULL);
    pthread_join(thread_id3, NULL);
    pthread_join(thread_id4, NULL);

    return 0;
}

Revision Exercise: Implement a least-recently-used replacement algorithm

Your task is to simulate least-recently-used (LRU) replacement of virtual memory pages.

Write a C program, lru.c, which takes two arguments, both integers.

This will be respectively the size in frames of simulated physical memory and and the size in pages of simulated virtual memory.

lru.c should then read integers from stdin until EOF.

Each integer will be the number of a virtual page being accessed.

lru.c should print one line of output for indicate what action occurs with a physical memory with a given number of frames.

dcc lru.c -o lru
./lru 4 6
Simulating 4 frames of physical memory, 6 pages of virtual memory
5
Time 0: virtual page 5 loaded to physical frame 0
3
Time 1: virtual page 3 loaded to physical frame 1
5
Time 2: virtual page 5 -> physical frame 0
3
Time 3: virtual page 3 -> physical frame 1
0
Time 4: virtual page 0 loaded to physical frame 2
1
Time 5: virtual page 1 loaded to physical frame 3
2
Time 6: virtual page 2  - virtual page 5 evicted - loaded to physical frame 0
2
Time 7: virtual page 2 -> physical frame 0
3
Time 8: virtual page 3 -> physical frame 1
5
Time 9: virtual page 5  - virtual page 0 evicted - loaded to physical frame 2

The provided code includes an array containing a data structure mapping each physical frame to a virtual page, as well as its last access time. This is known as an inverted page table.

For each access this function is called:

INTERNAL ERROR MISSING FILE: "./activities/lru/activities/lru/files.cp/lru.c"

Note that the fourth argument, struct ipt_entry *ipt, is a pointer to the inverted page table. It can be effectively indexed as an array, e.g. ipt[0] is the first entry.

You can complete the lab by adding code to this function (you are also free to write your own program from scratch if you prefer).

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest lru

Sample solution for lru.c

// Simulate LRU replacement of page frames

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define PAGE_FREE -1

// represent an entry in a simple inverted page table

typedef struct ipt_entry {
    int virtual_page;        // == -1 if physical page free
    int last_access_time;
} ipt_entry_t;


void lru(int n_physical_frames, int n_virtual_pages);
void access_page(int virtual_page, int access_time, int n_physical_frames, struct ipt_entry *ipt);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <n-physical-frames> <n-virtual-pages>\n", argv[0]);
        return 1;
    }
    lru(atoi(argv[1]), atoi(argv[2]));
    return 0;
}


void lru(int n_physical_frames, int n_virtual_pages) {
    printf("Simulating %d frames of physical memory, %d pages of virtual memory\n",
          n_physical_frames, n_virtual_pages);
    struct ipt_entry *ipt = malloc(n_physical_frames * sizeof *ipt);
    assert(ipt);

    for (int i = 0; i < n_physical_frames; i++) {
        ipt[i].virtual_page = PAGE_FREE;
        ipt[i].last_access_time = -1;
    }

    int virtual_page;
    for (int access_time = 0; scanf("%d", &virtual_page) == 1; access_time++) {
        assert(virtual_page >= 0 && virtual_page < n_virtual_pages);
        access_page(virtual_page, access_time, n_physical_frames, ipt);
    }
}


// if virtual_page is not in ipt, the first free page is used
// if there is no free page, the least-recently-used page is evicted
//
// a single line of output describing the page access is always printed
// the last_access_time in ipt is always updated

void access_page(int virtual_page, int access_time, int n_physical_frames, struct ipt_entry *ipt) {
    int physical_frame_to_use = 0;

    for (int pp = 0; pp < n_physical_frames; pp++) {
        if (ipt[pp].virtual_page == virtual_page) {
            physical_frame_to_use = pp;
            break;
        }

        if (ipt[pp].last_access_time < ipt[physical_frame_to_use].last_access_time) {
            physical_frame_to_use = pp;
        }
    }

    int vp = ipt[physical_frame_to_use].virtual_page;

    printf("Time %d: virtual page %d ", access_time, virtual_page);
    if (vp == virtual_page) {
        printf("->");
    } else if (vp == -1) {
        printf("loaded to");
    } else {
        printf(" - virtual page %d evicted - loaded to", vp);
    }
    printf(" physical frame %d\n", physical_frame_to_use);

    ipt[physical_frame_to_use].virtual_page = virtual_page;
    ipt[physical_frame_to_use].last_access_time = access_time;
}

Revision Exercise: Implement address translation

You have been provided a stub C program, addr_translation.c, as follows.

Your task is to add code to this function in addr_translation.c:

INTERNAL ERROR MISSING FILE: "./activities/addr_translation/activities/addr_translation/files.cp/addr_translation.c"

Add code to the function addr_translation so that, given a uint32_t virtual address, it returns the corresponding uint32_t physical address.

The code in addr_translation_main.c will read from a file containing page table entries, and will load these entries into a hash map data structure. You aren't required to understand how this works, but you will need to make use of the hashmap_get function defined in addr_translation.h in order to retrieve the page table entry for a given virtual page number.

The function will return a struct page_table_entry, also defined in addr_translation.h. This structure contains the physical frame number, and a boolean indicating whether the page is valid or not. If the page is not valid, the function should return INVALID_ADDRESS. If there is no entry in the page table for the given virtual page number, hashmap_get will return NULL, and you should also return INVALID_ADDRESS.

Virtual addresses are structured so that the top 20 bits are the virtual page number, and the bottom 12 bits are the offset within the page.

Physical addresses are structured identically, except the top 20 bits are the physical frame number instead of the virtual page number.

Your goal is to use bitwise operations to extract the virtual page number from the virtual address, and then use the page table to find the physical page number. You should then combine the physical frame number with the offset to form the physical address. For example:

unzip examples.zip
... extracting ...
dcc -o addr_translation addr_translation.c addr_translation_hashmap.c addr_translation_main.c
cat examples/page_table_small.vpt
0 0xcd5f8
1 0x7156f 0x43d5b
1 0x3506f 0x1d2a4
1 0xe33be 0xa8ba0
1 0x0cb02 0xda99b
0 0x698d4
./addr_translation examples/page_table_small.vpt
0x7156ffff
0x43d5bfff
0x7156efff
0x00000000
0xcd5f8340
0x00000000
0x0cb02e8a
0xda99be8a

When you think your program is working you can use autotest to run some simple automated tests:

1521 autotest addr_translation

Sample solution for addr_translation.c

#include <stdlib.h>
#include "addr_translation.h"

#define INVALID_ADDRESS 0x0
#define OFFSET_WIDTH    12
#define OFFSET_MASK     0xFFF

uint32_t translate_address(HashMap page_table, uint32_t virtual_address) {
    PageTableEntry *entry = hashmap_get(page_table, virtual_address >> OFFSET_WIDTH);
    if (entry == NULL || !entry->valid) {
        return INVALID_ADDRESS;
    }
    return (entry->frame << OFFSET_WIDTH) | (virtual_address & OFFSET_MASK);
}