Question

5. (20 pts) Recall that we learnt that two threads consisting of n 1 and m 1 instructions, respectively, may interleave on a general time-shared CPU in one of ("+m) ways (and all the assumptions that went into this calculation). We would like to extend this calculation to the case of signaling that we learnt in class. Say our two threads A and B comprise n- n1 n2 1 and m m1+ m2 1 instructions, respectively. Suppose the signaling we desire corresponds to the following: the n instruction of A must precede in time the mih instruction of B. Present your thoughts on calculating this number and an expression for it. Clarify if you are discounting the instructions making up the signaling code (e.g., in class we had used semaphores) from consideration either way of counting is OK as long you state your assumption clearly Hint: Consider these sanity checks to ensure you are on the right track: Clearly (+m) should be an upper bound on your solution. Why? » What is the number of interleavings for the easy extreme case of n1 and m 1? Does your expression reduce to this? 6. (25 pts) Three famous cats Pangur Ban (PB), Chairman Meow (CM), and Major Kilmowski (MK) live together. The biggest part of their daily routine is Sleep (). Occasionally, they Hunt and bring in their catch (I mouse for PB, 2 mice for CM, and 3 mice for MK) and put it into a communal pot of size N (in units of mice, of course) in which continuously brews a delicious stew. If they are hungry, they Eat (), which lasts till they are full or the pot is rendered empty (whichever occurs first). To ensure order and faimess (among the cats) and fun (for you!), we would like the following to hold only one of the cats may be eating at a given time, no one should starve indefinitely, if the pot becomes empty, the cats must wait for it to fill up fully before any of them may eat, any mice that can not be accommodated into the pot go away to mice heaven where no cats may bother them. Assuming PB, CM, and MK to be three threads, write pseudo-code for the above. You may use locks and/or semaphores. Make sure you clearly specify any shared data, initialize your synchronization vari- ables, and use comments to describe their usage. For each of the requirements listed above, describe in 1-2 sentences how it is met by your solution.

Answer 1

5)

using C and inline Assembly . For Inline Assembly Code you can just extract assembly code from //below

#include <string.h>

int _tmain(int argc, _TCHAR* argv[])
{
char source[10] = "Hello";
char dest[] = "";

int i;
for (i = 0; i < 10; ++i)
{
dest[i] = source[10-i-1];
}

__asm
{
lea esi, source
cld
lodsb

lea edi, dest
mov eax, 0xFF
stosb

lea edi, dest
cld
mov ecx, length source
mov eax, 0x44
rep stosb

lea esi, source
lea edi, dest
mov ecx, length source
cld
rep movsb
}

printf("%s",source);
printf("%s" ,"\n");
printf("%s",dest);
getchar();
return 0;
}