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:
#include
/******************************/
/*** 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
bound.
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
resources.
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
storage.
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
system.