Disadvantage:
1. Slower communication vs. using shared
memory in multiprocessor machines.
2. Multithreaded programs will not take
advantage of a cluster.
3. Need to rewrite program to use cluster.
2. (3 pts.) Mention in what circumstances the user time of a process
may exceed the real time.
A multithreaded program running in a multiprocessor
machine where different threads run concurrently in multiple processors
may make the user time exceed the real time.
3. (3 pts.) Write the factors used to determine the length of a quantum.
1. Average response time.
2. Context switch overhead.
3. Average burst time.
4. (3 pts.) Give the reasons why system calls are implemented using
software interrutps.
Because system calls need to cross the
user-kernel boundary to be able to access the kernel data structures, device
registers, and operations that are only available in kernel mode.
5. (3 pts.) What are the advantages and disadvantages of preemptive
vs. non-preemptive scheduling.
Advantage of preemptive scheduling:
1. More robust. One non-cooperative thread
will not hang the system.
2. More fair.
3. Can use multiple processors.
Disadvantage:
1. Difficult to implement.
2. Problems doing synchronization of resources.
| 6. (10 pts.) Implement the code for the following function
char *strstr(const char *haystack, const char *needle) The strstr() function finds the first occurrence of the substring needle in the string haystack. The terminating `\0' characters are not compared. The strstr() function returns a pointer to the beginning of the substring, or NULL if the substring is not found. |
char *strstr(const char *haystack, const char *needle)
{
char * start = haystack;
while( * start) {
//compare needle at this position.
char * p = needle;
char * q = start;
while (*p && *q && *p == * q) {
p++;
q++;
}
if( *p == 0) {
return start;
}
start++;
}
return NULL;
}
|
| 7. (10 pts.) Write the implementation of the procedure getenv() that returns the value of an environment variable or NULL if that variable does not exist. |
extern char ** environ;
char * getenv( char * var_val ) {
char ** p = environ;
while(*p != NULL) {
char * q = strstr(*p, var_val);
if(q == p && (*p)[strlen(var_val)] == '=') {
break;
}
p++;
}
if(*p != NULL) {
return &(*p)[strlen(var_val) + 1];
}
else
return NULL;
}
|
| 8. (10 pts.) The add() method adds a number to a linked list of integers. This add method does not have mutexes. Thread T1 calls add(5) and thread T2 calls add(7) at the same time. Give a sequence of instructions (use the labels a, b, c, d) that can cause the node with the "7" value to be lost. |
struct Node {
int _val;
Node * _next;
};
class IntList {
Node * _head;
IntList() {
_head = NULL;
}
void add( int val ) {
a) Node * n = new Node()
b) n->_val = val;
c) n->next = _head;
d) _head = n;
}
}
t -------------------------------->
T1 -> a b c d
T2 -> a b c d
|
| 9. (5 pts) Write a synchronized bounded buffer class with a circular buffer where the writer thread that calls add(int val) will block if the buffer is full. The reader thread calling remove() will block if the bounded buffer is empty. The constructor BoundedBuffer(int max) allocates space for _buffer with max size elements and it also initializes semaphores. Add also the semaphores and mutexes that are necessary. |
class BoundedBuffer {
int * _buffer; int _max; int _head; int _tail; // More variables or semaphores if necessary sema_t _full; sema_t _empty; mutex_t _mutex;BoundedBuffer( int max ) { _buffer = (int *) malloc (max * sizeof(int)); assert(_buffer != NULL); _max = max; _head = 0; _full = 0; seam_init(&_full, max); seam_init(&_empty, 0); mutex_init(&_mutex); } void add( int val ) { // Block if buffer is full sema_wait(&_full); mutex_lock(&_mutex); _buffer[tail] = val; _tail = (_tail + 1 ) % _max; mutex_unlock(&_mutex); sema_post(&_empty); } int remove() { // Block if buffer is empty sema_wait(&_empty); mutex_lock(&_mutex); int tmp = _buffer[_head]; _head = (_head + 1) % _max; mutex_unlock(&_mutex); sema_post(&_full); return temp;
|
| 10. (10 pts.) Write a function redirectOutput(args, outfile) that will execute the program in args[0] in a separate process and it will redirect the output to the file named outfile. args is an array of arguments where args[0] is the program to run and the last aregument is a NULL pointer. You will have to implement the procedure in two ways: 1. Do the reedirection in the parent. and 2. Do the redirection in the child.The procedure will return 0 if success or different than 0 otherwise. |
int redirectOutput(char ** args, char * outfile)
{
// Do the redirection in the parent
int tmpout = dup(1);
int fd = open(outfile, O_WRITE|O_CREATE|O_TRUNC, 0666);
if(fd < 0) {
return -1;
}
dup2(fd, 1);
int res = fork();
if(res == 0) {
execvp(args[0], args);
exit(1);
}
if(res < 0) {
close(fd);
return -1;
}
//restore output
dup2(tmpout, 1);
close(tmpout);
waitpid(res);
return 0;
}
int redirectOutput(char ** args, char * outfile)
{
// Do the redirection in the child
int res = fork();
if(res == 0) {
//child
int fd = open(outfile, O_WRITE|O_CREATE|O_TRUNC, 0666);
if(fd < 0) {
exit(1);
}
dup2(fd, 1);
execvp(args[0], args);
exit(1);
}
else if (res < 0)
return -1;
}
waitpid(res);
}
|
| 11. (10 pts.) Implement the procedure int runpipe( char ** args1, char ** args2) that runs the programs in args1 and args2 in different children processes where the output of args1 goes to the input of args2 using a pipe. args1 and args2 are arrays of arguments where the last argument is NULL. The element args1[0] and args2[0] are the names of the programs to execute. runpipe() will return 0 if success or different than 0 otherwise. |
int runpipe( char ** args1, char ** args2)
{
int fdpipe[2];
pipe(fdpipe);
//process1
int ret1 = fork();
if(ret1 < 0)
return -1;
if(ret1 == 0) {
//direct output
dup2(fdpipe[1], 1);
execvp(args1[0], args1);
exit(1);
}
//process 2
int ret2 = fork();
if(ret2 < 0)
return -1;
if(ret2 == 0) {
dup2(fdpipe[0], 0);
execvp(args2[0], args2);
exit(1);
}
close(fdpipe[0]);
close(fdpipe[1]);
waitpid(ret1);
waitpid(ret2);
}
|
| 12. (10 pts.) Implement a name table class using an array of TableEntry
struct's. The constructor NameTable(max) will allocate space for a table
with n entries. The function add(var,val) will block until there is space
in the table, then it will search for an entry in the table that is unused
( _var and _val are NULL) and it will add the var and val strings
in that entry. Duplicated values are allowed.
The function lookup(var) will lookup the string var in the table and it will return the corresponding value. If the variable does not exist, lookup() will wait until that variable is added with the add() function. Add the semaphores and mutexes that are necessary and the code that implements the behavior described. |
|
struct TableEntry { char * _var; char * _val; // Other variables here sema_t _pendingSem;
class NameTable {
// Array of TableEntry entries
// Other variables here
public:
void add(char *var, char *val) {
mutex_lock( &_mutex
)
// Search for an unused
entry in the table
// We should never reach
this point
char * lookup(char * var) {
// There is no entry. Add
one entry, label it as pending and wait
// Wait until this entry is added
// The variable was added
// We should never reach
this point
};
|