CMPSC 311, Spring 2013, Midterm Exam 1, Sample questions for review

solutions

1.  True/False, circle T or F.  [1 point each]
 
  T  F  (a)  The Posix Standard describes only an interface to the operating system, as a set of functions callable from C.
 
  T  F  (b)  When a Unix process starts, the input and output streams stdin, stdout and stderr are opened.
 
  T  F  (c)  When a C or Unix library function fails, it sets the global variable errnum to indicate the reason for the failure.

  T  F  (d)  The assert() macro can be used to verify a boolean expression at runtime; if the expression evaluates to false, the program is terminated.
 
  T  F  (e)  Parameter-passing in C is always call-by-value (or, pass-by-value, which is the same thing).
 
  T  F  (f)  Reference parameters (from C++) can be approximated by pointer parameters in C.

Answers --
(a)  False.  The Posix Standard indeed describes an interface to the operating system, but it also describes data types and utility programs, and describes their behavior.
(b)  True.  At this point in the course it's not important exactly when this is done, as long as it's done before main() starts.  This would probably be done by the system-provided startup function.  It's also true of any operating system that supports C programs, not just Unix.
(c)  False.  errno, not errnum.  Anyway, this is not the only mechanism that is used.
(d)  True.  The expression could also be ignored (not evaluated) if NDEBUG was defined, but that doesn't make the statement false.
(e)  True.
(f)  True.  See the supplementary notes Pointer and Reference Parameters in C and C++ .

Do you enjoy arguing for points?
(b)  The names stdin, stdout, stderr, are common for C programs using <stdio.h>, and are also available in C++, but it's not necessary for a Unix program to be written in C or C++.  By whatever name, those three streams are indeed opened.
(d)  Actually, if assert() is triggered, it calls abort(), which sends a SIGABRT signal to the process,  The default signal handler for SIGABRT calls exit(), but you might have replaced that signal handler with your own function that doesn't call exit().  Hence, the process might not be terminated.


2.  Multiple Choice  [3 points each]
 
Choose only one of the four given answers in each part, by circling 1, 2, 3, or 4.  There is at least one correct answer given in each part, and there may be other correct answers.  Partial credit is possible for some incorrect answers.
 
(a) A file descriptor is
 
    (1)  a non-negative integer obtained from a call to open().
    (2)  a non-negative integer obtained from a call to fopen().
    (3)  a pointer obtained from a call to open().
    (4)  a pointer obtained from a call to fopen().

(b) Comparing system functions and library functions, ...
 
    (1)  system functions are provided with the operating system, while library functions are provided with the programming language.
    (2)  library functions are provided with the operating system, while system functions are provided with the programming language.
    (3)  there is no difference, they are both provided with the operating system.
    (4)  there is no difference, they are both provided with the programming language.

(c) An operating system would be expected to ...

    (1)  provide methods for connecting hardware and software components.
    (2)  manage resources.
    (3)  provide abstractions of the resources.
    (4)  map virtual resources to actual resources over time.

Answers --
(a) The best answer is (1), 3 points, then (3) or (4), 1 point.
(b) The best answer is (1), 3 points, then (2) or (3), 1 point.
(c) These are all correct.  Don't expect anything so easy on the actual exam.


3.  [20 points]  Design and write a function that will estimate the size of the largest single block of memory that can be successfully allocated with malloc().  Do this efficiently.  Pseudocode is acceptable as long as it's not "too pseudo".  It would help in assigning partial credit if you also give a diagram of memory allocation within a process address space, to help explain how your function works.

"Cheat sheet" info -  malloc() is given one argument, a number of bytes to allocate.  If there is enough space available in the process heap segment, malloc() returns a non-NULL pointer to that space, otherwise it returns NULL.  The function free() takes one argument, which is expected to be a return value from malloc(), and deallocates that space.  malloc() does not initialize the memory it allocates.

Answers --
  [5] for a diagram.
[10] Use linear search.  Write a loop with malloc(1), stop when the function first returns NULL.
[15] Use binary search. 
     Start with lower_bound = 0, upper_bound = SIZE_MAX (the largest size_t value).
     trial = (lower_bound + upper_bound) / 2  [this part can be improved]
     v = malloc(trial); free(v);
     If v is NULL, decrease upper_bound to trial.
     If v is not NULL, increase lower_bound to trial.
     Repeat until lower_bound, upper_bound are close enough.


4.  [8 points]  Consider the swap function

static inline void int_swap(int *a, int *b)
{ int t = *a; *a = *b; *b = t; }

Explain what is wrong with each of the following uses of swap().

(a)  int m, n; int_swap(&m, &n);
(b)  int_swap(m, n);
(c)  int_swap(&m, &3);  // assign 3 to m

Answers --
  (a)  uninitialized variables
  (b)  should pass addresses, as in (a)
  (c)  &3 is illegal


5.  [lots of points]  This problem has happened to several students.  The program seems to run but it produces no output.  Explain why.

Lots of different answers --
The most subtle answer is that the program was compiled as
    cc -o test ...
There is already a program named test that comes with Unix; it is either a builtin shell command or a separate program.  If your path variable does not indicate the current directory, or puts the current directory after the standard directories, then the test program that is being run is not yours.  The system's test program evaluates an expression and exits with 0 (success, true) or 1 (failure, false); it never prints anything.


6.  [10 points]  Write a simple version of the od program.

"Cheat sheet" info - See the Course Intro notes and the Project 2 and 3 descriptions for examples.  The actual test would include a short example, since od has several options, and we need to be definite about which one to use.

Some answers --
loop over getc(), use the input character as an index into a table of strings for printf().
loop over getc(), use isprint() to choose from putc() or printf("%x")
etc.


7.  [6 points]  Explain the errors and repair the code.

int size_intarray = ... some value from the input ... ;
int *intarray = malloc(size_intarray);
for (i = 0; i < size_intarray; i++)
  { total += intarray[i]; }

Answers --
malloc()'s parameter type is size_t, but its argument size_intarray is an int.  As long as the value of size_intarray is 0 or positive, there won't be a problem.  If size_intarray is negative, then malloc() will interpret it as a large positive value.  Verify that the input values are correct, or change the type of size_intarray.
malloc()'s argument is in units of bytes, not a number of array elements, as the loop seems to suggest.
malloc() could return NULL, and the code didn't check for that.
malloc() does not initialize anything.
total wasn't defined and initialized.  i wasn't defined.
Change to malloc(size_intarray*sizeof(int)).
Assign values to intarray[i].
Define and initialize total.  Define i.


8.  [8 points]  Explain the errors and repair the code.
pid_t pid;
int status;

if ((pid = fork()) = 0)
  { /* child */
    execlp("bin/ls", "bin/ls", NULL);
  }
else
  { /* parent */
    waitpid(pid, &status, 0);
  }
Answers --
Use /bin/ls instead of bin/ls .
Check for pid < 0, in case fork() failed.
If execlp() returns, there was an error, so deal with it.
If waitpid() returns a negative value, there was an error, so deal with it.  [OK, maybe you didn't remember the details of waitpid(), but you should be suspicious of a system library call that doesn't check for errors.]


9.  [8 points]  Indicate what is wrong with the following C program, and correct the program.  (The return type of foo() is intended, so don't change that.)    (Hint:  parameter passing, not malloc)

 1     #include <stdlib.h>  /* for malloc(), free() */

 2     /* This function acquires memory and returns the
 3      * address to the caller via the parameter target.
 4      * The memory can be released by calling free().
 5      */
 6     void foo(char *target)
 7     {
 8       void * buf = malloc(sizeof(char) * 10);
 9       (*target) = buf;
10     }

11     int main(void)
12     {
13       char *line;
14       foo(line);    /* allocate memory */
15       free(line);   /* deallocate memory */
16     }

Answers --
The first two changes are important.    [3 each]

        line 6, change  char *  to  char **
        line 14, change  line  to  &line
        This fixes a type-mismatch problem on line 9 (char = void * is corrected to char * = void *).
        The code now agrees with the comment on lines 2-4.

This may be less important, but still required.     [1]

        insert line 15.5,  return 0;

These are not required, since the default type conversion applies.      [1 each]

        line 9, change  buf  to  (char *) buf
        line 15, change  line  to  (void *) line

This is not required, in this little program, but it's a good idea in general.

        line 8.5 or 14.5, check for a NULL pointer.

How to think about this problem:

C function parameters are always call-by-value.  The only ways to return something from a function are
The assignment in line 9 looks like the right thing to do, but the types don't match in the original (char = void *).  We need to have a pointer to the allocated memory, so line 8 looks right, and the problem must be with the type of target.  The parameter to foo() (line 6) must be a pointer to a char * (although a pointer to void * would work just as well).  The argument to foo() (line 14) therefore must also be a pointer to char *.