Homework 5 Solutions

22C:116, Spring 1997

Ioana M. Lungeanu
Problem 1

    Other solutions than the one presented here could use the
    "union" structure, or even the "switch" command.  This solution
    generates machine code that is very close to that generated by
    efficient compilers for object oriented languages:


    /*** the parent class stack ***/

    typedef struct stack {
        void (*push)(stack *p, int);
        int (*pop)(stack *p);
    } stack;

    /* this can never be instantiated */

    /*** the child class array_stack ***/

    typedef struct array_stack {
        void (*push)(stack *p, int);
        int (*pop)(stack *p);
        int arr[100];
        int top;
    } array_stack;

    void push_array(stack *p, int item)
	array_stack * ap = (array_stack *)p;
        ap->arr[ap->sp] = item;
        ap->sp += 1;

    int pop_array(stack *p, int item)
	array_stack * ap = (array_stack *)p;
        ap->sp -= 1;
        return ap->arr[ap->sp] = item;

    stack * arraystack()
        array_stack *ap = (array_stack *) malloc( sizeof(array_stack) );
        ap->push = push_array;
        ap->pop = pop_array;
        ap->sp = 0;
        return (stack *) ap;

    /*** the child class list_stack ***/

    typedef struct list_item {
        struct list_item * next;
        int item;
    } list_item;

    typedef struct list_stack {
        void (*push)(stack *p, int);
        int (*pop)(stack *p);
        list_item * top;
    } list_stack;

    void push_list(stack *p, int item)
        list_stack * lp = (list_stack *)p;
        list_item * ip = (list_item *) malloc( sizeof(list_item) );
        ip->item = item;
        ip->next = lp->top;
        lp->next = ip;

    void pop_list(stack *p)
        list_stack * lp = (list_stack *)p;
        list_item * ip = lp->top;
        int item = ip->item;
	lp->top = ip->next;
        free( ip );
        return item;

    stack * liststack()
        list_stack *lp = (list_stack *) malloc( sizeof(list_stack) );
        lp->push = push_list;
        lp->pop = pop_list;
        lp->top = NULL;
        return (stack *) lp;

Problem 2

    Given that:
    - L = Average Latency time in seconds(seek + rotation)
    - T = Disk date transfer rate in bytes per second
    - N = CPU processing rate in bytes per second

    Let S be the Sector size in bytes.

    The optimal sector size in bytes can be obtained by
    solving the following equation for S:

    CPUtime / sector  =  IOtime / sector

           S/N        =      L + S/T

    S(1/N - 1/T) = L
    S = L / (1/N - 1/T) = LNT/(T-N)

    Note that this only has a solutions when T > N; this is true on
    any system where the disk is relatively fast and well balanced
    with the memory bandwidth.  Where this is not true, there is no
    optimum because the CPU can always stay ahead of the I/O hardware
    and no matter what sector size is used, the system will be I/O

    Also, of course, the expression for S must be rounded to an integer!

Problem 3 Part A

    From the user perspective, the access time for each block of a
    smaller or a larger file is same in XDFS. This is because the
    addresses of blocks are all at the leaves of a B-tree structure
    which is balanced. In UNIX one needs to go through zero, one or
    two indirectations in order to find the address of one block of
    a file, depending on the dimension of the file.

    The maximum size of a UNIX file is bounded by the low level
    file system structure while in XDFS it's bounded by the phisical

    The access time in XDFS depends on the size of the B-tree, which
    in turn depends upon how many and how large are the files of all
    users in the system.  In UNIX the access time at the low level
    file system per file per user doesn't depend upon the "file load"
    of the system.

Problem 3 Part B

    Changing from UNIX to XDFS the performance on small files
    decreases and the performance on large files may increase.
    Depending on the procentage of accesses to small/large file in
    one system one low level file system may be more suitable than the
    other.  Even if searching through the B-tree requires comparissons
    this woun't slow down the performance significantly since CPU is
    much faster than the I/O anyway.

    B-tree nodes contain not only pointers but also keys, so the number
    of disk addresses per index block will be smaller with the XDFS
    system than with UNIX.  Thus, for a given size of file system,
    the B-tree approach may take more space for indexing the data
    sectors.  But, in systems with many small files, UNIX stores at
    least 10 disk addresses per file in the I-node, and these would
    not be stored under the XDFS B-tree approach.  So, in systems with
    many small files, B-trees may still be more efficient in terms of

Problem 4

    Under XDFS, the sector zero of each file should contain the file
    number of the directory holding that file, as well as the name of
    the file.  Since we assumed a simple hierarchical tree-structured
    directory with no access rights or other extraneous material this
    info should be enough to reconstruct the directory structure in
    case of corruption.

    If the worst case damage to the disk destroys at most one sector,
    we can reconstruct sector zero of a file from the directory that
    references that file, and we can reconstruct a directory from a
    search of sector zero of every file.

    In the event that multiple sectors are destroyed by any event short
    of a disk head crash, it is highly unlikely that both the directory
    entry for a file and sector zero of the same file will be destroyed.
    So, the most we will lose as a result of common disk failures will
    be one sector of data from some file.

Problem 5

    A group needs to be created by the superuser(system administrator)
    which consists of the instructor and the TA,  call it GRADERS.
    The assignment file is owned by each and every student (his/her own).
    They should have R/W access for this file and they should give the
    GRADERS group R access for the assignment.  In creating the assignment
    file, the effect should be as if the following two commands were given:

        chgrp GRADERS assignment
        chmod 640 assignment

    For the gradebook file either the instructor or the TA could be the
    owner.  The group for this file should be set to GRADERS. The access
    rights should be set to W/R both for the owner and for the group.

        chgrp GRADERS gradebook
        chmod 660 gradebook

    For the examfile, the instructor is the owner and he has R/W rights
    to it and nobody else has any rights to it.

        chmod 600 examfile

    The persons involved could belong to other groups  but the filea under
    disscusion have the groups and access rights set as above.

    We do exactly this when we administer courses on our departmental UNIX