这个作业是用C语言完成多线程、锁相关的并发编程

CSC 112: Final (Sample)

Part 1: Possible/Impossible
Problem 1: Which of the following statements are true statements about various
page-replacement policies?
To answer: Fill in A for true statements, B for false ones.
1. The LRU policy always outperforms the FIFO policy.
2. The OPT (optimal) policy always performs at least as well as LRU.
3. A bigger cache’s hit percentage is always greater than or equal to a smaller
cache’s hit percentage, if they are using the same replacement policy.
4. A bigger cache’s hit percentage is always greater than or equal to a smaller
cache’s hit percentage, if they are using the LRU replacement policy.
5. Random replacement is always worse than LRU replacement.
Problem 2: Assume this attempted implementation of a lock:
void init(lock_t *mutex) {
mutex->flag = 0; // 0 -> lock is available, 1 -> held
}
void lock(lock_t *mutex) {
while (mutex->flag == 1) // L1
; // L2
mutex->flag = 1; // L3
}
void unlock(lock_t *mutex) {
mutex->flag = 0; // L4
}
Assume 5 threads are competing for this lock. How many threads can possibly
acquire the lock? To answer: Fill in A for possible, B for not possible.
6. 1
7. 2
8. 3
9. 4
10. 5
Problem 3: Here is a ticket lock:
typedef struct __lock_t {
int ticket, turn;
} lock_t;
Problem 4: Assume the following list insertion code, which inserts into a list
pointed to by shared global variable head:
int List_Insert(int key) {
node_t *n = malloc(sizeof(node_t));
if (n == NULL) { return -1; }
n->key = key;
n->next = head;
head = n;
return 0;
}
This code is executed by each of three threads exactly once, without adding any
synchronization primitives (such as locks). Assuming malloc() is thread-safe (i.e.,
can be called without worries of data races) and that malloc() returns successfully,
how long might the list be when these three threads are finished executing?
(assume the list was empty to begin)
To answer: Fill in A for possible, B for not possible.
Problem 5: Assume the following code, in which a “background malloc” allocates
memory in a thread and initializes it:
void *background_malloc(void *arg) {
int **int_ptr = (int **) arg; // [typo from int* -> int**
corrected here]
*int_ptr = calloc(1, sizeof(int)); // allocates space for 1 int
**int_ptr = 10; // calloc: also zeroes memory
return NULL;
}
int main(int argc, char *argv[]) {
pthread_t p1;
int *result = NULL;
pthread_create(&p1, NULL, background_malloc, &result);
printf(“%d\n”, *result);
return 0;
}
The code unfortunately is buggy. What are the possible outcomes of this code?
Assume the calls to pthread_create() and calloc() succeed, and that a NULL
pointer dereference crashes reliably. To answer: Fill in A if possible, B for not
possible.