CSCI-UA.0202 Spring 2015 Homework 2

Handed out Thursday, February 5, 2015
Due 10:00 AM, Monday, February 9, 2015

Homework 2

These problems should be done on your own. We're not going to be grading them strictly (we'll mainly look at whether you attempted them). But they will be reinforcing knowledge and skills, so you should totally work through them carefully.

Processes and threads

In this question, assume a standard system with isolation and memory protection (this is in contrast to MiniprocOS). Further assume that the thread abstraction is implemented by the operating system. That is, thread_create() is a system call.
  1. What do you think are the differences between the implementation of thread_create(func) and the implementation of fork()? (here, func is the address of the function that the thread should begin at).
  2. What do you think are the key differences between the OS’s “process” data structure (process_t, in MiniProcOS) and whatever data structure it uses to implement a thread?

Linked lists

You need to understand linked lists in order to do lab 2. This question will provide some practice (you may thank us during job interview season: linked lists are common subjects of interview questions).

In the code below, we specify a data structure node_t: 

    struct node_t {
        int id;
        char name[10];
        struct node_t *next;
    };
A linked list consists of a list of these structures, connected via the next field, which is a pointer to another node_t. Given the head of a linked list (a pointer to the first element), the program can traverse the linked list by following the next pointers (you will do that in the exercise below). The last element in a linked list (assuming the list has been set up correctly) has its next field set to NULL.

We wish to write code that stores a list of students, each with an id and a name. We also will arrange to keep all elements keep sorted by student ids. The skeleton is below. You will fill it in. 

    /* Iterate through the sorted list (by node_t::id), and find the position after
     * which the new 'node' should be inserted in the list. Ensure that the list
     * is kept sorted. Return the element just before the newly inserted one.
     * If the new 'node' should be inserted at the beginning, return NULL.
     */
    node_t *
    find_insert_pos(node_t *head, node_t *node)
    {
        if (head == NULL) return NULL;

        node_t *ret = NULL;

        // 2.1 your code here

        return ret;
    }

    /* insert a new 'node' into the list 'head', return the new head of the list.
    node_t *
    insert(node_t *head, node_t *node)
    {
        if (head == NULL) return node;

        // find the proper position to insert this node pair.
        node_t *pos = find_insert_pos(head, node);

        // 2.2 your code here

        return head;
    }

    int
    main(void)
    {
        node_t *student_list = NULL;

        // init first student Alice
        node_t *student_1 = (node_t *)malloc(sizeof(node_t));
        student_1->id = 1002;
        strcpy(student_1->name, "Alice");
        student_1->next = NULL;

        // init second student Bob
        node_t *student_2 = (node_t *)malloc(sizeof(node_t));
        student_2->id = 1000;
        strcpy(student_2->name, "Bob");
        student_2->next = NULL;

        student_list = list_insert(student_list, student_1);
        student_list = list_insert(student_list, student_2);

        // now we should have a student list:
        //    <1000, Bob> -> <10002, Alice> -> NULL

        ... free resources ...

        return 0;
    }

  1. Traverse the list; return the insertion position.
  2. Insert node in the list head; make sure the return value is correct.

Shell

State the output (or behavior) of each of the following commands. 
        i.      echo  echo hello $world
        ii.     echo 'echo hello $world'
        iii.    echo "echo hello $world"
        iv.     echo `echo hello $world`
        v.      echo (echo hello $world)

        i.      echo 'hello world' |    cat
        ii.     echo 'hello world' >    cat
        iii.    echo 'hello world' 2>   cat

        i.      echo a &&   echo b
        ii.     echo a ;    echo b
        iii.    echo a &    echo b

There is a file 'members.txt'. Assume it is in the following form: 

        Name:John
        NetId:j22
        email:john@nyu.edu
        Name:Amy
        NetId:a123
        email:amy@nyu.edu
        ...
Try to use a pipeline (a shell command that uses a pipe) for each of the following tasks:

To output the first 100 names in this file. (Hint: you may want to compose the following commands: grep "^Name:[a-zA-Z']\+$", head -n100, cut -d':' -f 2)

To identify the first 100 names by alphabetical order, and then (in one command) output them (as above) and write them to a file called 'names.txt'. (Hint: you may want to use: sort, tee names.txt.)

Concurrency

Based on the following code:

    int i = 0; /* updated to fix bug of non-initialized i*/

    void
    foo(void *)
    {
        int n = i;
        i = i + 1;
        printf("foo: %d\n", n);
    }

    void
    boo(void *)
    {
        int n = i;
        i = i + 1;
        printf("boo: %d\n", n);
    }

    int
    main(void)
    {
        create_thread(foo);
        create_thread(boo);

        // wait for threads to finish
        join_thread(foo);
        join_thread(boo);

        printf("main: %d\n", i);
        return 0;
    }
  1. What are the possible outputs of this program?
  2. How could you avoid the race conditions?
  3. What are the possible outputs, after you apply your solution to the prior question?

Handing in the homework

Use NYU Classes; there's an entry for this homework.

Last updated: Mon May 04 11:24:46 -0400 2015 [validate xhtml]