CSCI-UA.0202 Spring 2015 Homework 5

Handed out Monday, March 2, 2015
Due 10:00 AM, Monday, March 9, 2015

Homework 5

These problems should be done on your own. However, in a departure from our usual policy, you can post public questions about code to Piazza, provided that you do not post solutions or code excerpts of more than, say, two lines. You can and should answer each other's questions (again following the guidelines). The high-level point here is to facilitate conscientious collaboration through Piazza.

As usual, we're not going to grade these strictly (we'll mainly look at whether you attempted them). But they reinforce knowledge and skills that the remaining labs will assume, so you ought to work through them carefully.

If you are not yet fully comfortable with C, this homework may take more time than the others; please plan accordingly and please use Piazza as a resource. As usual, you must write code on your own.

Scheduling

This question is open-ended; there are many possible answers. You don't have to type very much, and you can think about these questions even when you are not in front of a computer.

There are many metrics that a scheduler has to balance: turnaround time, response time, throughput, and various definitions of fairness. We will consider the following types of systems in this question:

A high-performance computer used for large number crunching tasks (genetic sequencing, graphics rendering...)
A multimedia computer (video games, movies...)
A smartphone
A general-purpose computer on the CIMS network

For each of the system types above, which metrics do you think are the most important, and why? Some things to consider: How many users does the system have? Are user processes typically interactive? How long is a user willing to wait? What frustrations will users have if certain metrics are ignored? (There are many possible answers to this question.)
Taking into consideration your answers above, propose a scheduling policy (FIFO, etc.) for each system above.
For each of the systems above, what is the scheduling policy that would most completely undermine the purpose of the system?

C exercises

This part of the homework will exercise your C programming skills. First of all, if you have not yet done it, do the reading assignment on pointers.

Next, we will quickly walk through how to write and compile a program in C, and then you will write and compile several programs of your own.

Using a text editor, create a file called fun.c. In this file, type:

#include <stdio.h>

int main(int argc, char** argv)
{
    char* first_arg; 
    char* second_arg; 

    /* this checks the number of arguments passed in */
    if (argc != 3) {
        printf("usage: %s <arg1> <arg2>\n", argv[0]);
        return 0;
    }

    first_arg = argv[1];
    second_arg = argv[2];

    printf("My program was given two arguments: %s %s\n",
           first_arg, second_arg);

    return 0;

}

This is a C program. The #include at the top tells the compiler to use the header files of "standard I/O" (the standard input/ouput functions of the C library; these functions include printf). Also, argc contains the number of arguments passed to the program (including the program name itself) while argv[0] contains the name of the program that was invoked.

You can compile this program using:

$ gcc -g -Wall -o fun fun.c

You can now run this program using:

$ ./fun

You should see:

usage: ./fun <arg1> <arg2>

You can also do:

$ ./fun abc def
My program was given two arguments: abc def

Note the pattern here:

you create a C file and compile it with
```
$ gcc -g -Wall -o <output-file-name> <input-file-name>
```
(We are not using makefiles for the time being.)
You run your program using whatever was after the -o flag.
Inside the program, you gain access to the arguments using the argv array. (Remember how exec() takes an argv array? The OS takes that array and passes it to the new program's main() function.)

You will use this pattern in the exercises below; these exercises ask you to write several programs from scratch.

Write, from scratch, a C program that takes two arguments (strings) and prints out their concatenation. (Start with the program and pattern above.)
Write, from scratch, a C program that takes two arguments and prints the first three characters of each string. If either of the two arguments has fewer than three characters, print an error message. (You can use the function strlen to help; if you do that, then #include <string.h> at the beginning of the program.)
Write, from scratch, a C program that takes two arguments and supplies them to a function that you write:
```
int my_strcmp(char* a, char* b)
```
and then prints out the output of this function. my_strcmp should return 1 if a and b are not the same string and 0 if they are equal. You should implement my_strcmp without calling the standard C function strcmp! (You may thank us later; potential employers have been known to ask this question, or variants of it, in interviews.) To do this problem, remember that C strings end with a NULL character (the byte 0).

A common bug in C coding

Consider the following code:

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

// A box. Each box has an ID and a pointer to the box that resides inside
// of it. If the box has nothing inside of it, inner_box should be equal
// to NULL.
struct box {
    int id; 
    struct box *inner_box;
};

// Insert box: places the box "inner" inside of the box "outer".
// Since "outer" is being modified, we pass a pointer to "outer".
// Since "inner" is not being modified, we pass in "inner" directly.
void insert_box(struct box* outer, struct box inner) {
    printf("insert box: placing id %d inside id %d\n", inner.id, outer->id);
    outer->inner_box = &inner;
}

// Print box: prints a box and the box inside of it. This function
// is recursive and will end once a box is empty.
void print_box(struct box* first, int level) {
    int i;
    if (!first) 
        return;

    for (i=0; i < level; ++i) {
        printf("- ");
    }       
    printf("id: %d\n", first->id);
    print_box(first->inner_box, level+1);
}

int main() {
    // Create three boxes.
    struct box box1 = { .id = 37, .inner_box = NULL };
    struct box box2 = { .id = 12, .inner_box = NULL };
    struct box box3 = { .id = 19, .inner_box = NULL };

    // The box ordering should be box1 -> box2 -> box3
    insert_box(&box1, box2);
    insert_box(&box2, box3);
    
    // Print the boxes starting from the outside box.
    print_box(&box1, 0);

    return 0;
}

Using the program and the comments, describe at a high level what this code is intended to do. What output did the programmer expect the program to generate?
What happens when the program is run? (Copy/paste it into a file called box.c, compile it, and run it.)
What is the error in the programmer's reasoning?
Change this program to produce the intended output.

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