readme.txt

MINIX操作系统的内核修改补丁

MEMBER:
Jia Tianqing 5051619053 [e-mail]
Xia Jiabin 5060379061 [e-mail]
Zhang Hongshneg 5060379098 [e-mail]

CODE STATUS:
Mission accomplished


DESCRIPTION:
Task1:
We have successfully implemented a new system service in the os so that semaphores are a part of the minix.

in src/kernel/table.c:

  #define PM_PROC_NR	  0	/* process manager */
  #define FS_PROC_NR 	  1	/* file system */
  #define RS_PROC_NR 	  2	/* reincarnation server */
! #define SS_PROC_NR 	  3	/* semaphore server */    <--------------------------we inserted the service here
! #define MEM_PROC_NR 	  4  	/* memory driver (RAM disk, null, etc.) */
! #define LOG_PROC_NR	  5	/* log device driver */
! #define TTY_PROC_NR	  6	/* terminal (TTY) driver */
! #define DS_PROC_NR	  7    	/* data store server */
! #define INIT_PROC_NR	  8    	/* init -- goes multiuser */

  #define SYS_M	(~0)
! #define USR_M (s(PM_PROC_NR) | s(FS_PROC_NR) | s(RS_PROC_NR) | s(SS_PROC_NR) | s(SYSTEM)) <--------and here
  #define DRV_M (USR_M | s(SYSTEM) | s(CLOCK) | s(DS_PROC_NR) | s(LOG_PROC_NR) | s(TTY_PROC_NR))

  #define RS_C	~0	
+ #define SS_C	~0   <-------------------------------------------------------------------------------and here
  #define DS_C	~0	

   { RS_PROC_NR,    0, SRV_F,  4,      3, 0,     SRV_T, SYS_M,  RS_C, "rs"    },
+  { SS_PROC_NR,    0, SRV_F, 32,      4, 0,     SRV_T, SYS_M,  SS_C, "ss"    },<------and here in accordance
   { DS_PROC_NR,    0, SRV_F,  4,      3, 0,     SRV_T, SYS_M,  DS_C, "ds"    },

To begin with, we carefully created the service and inserted it into the booting image. And we noticed that the number of the service must be in the 'right' position in the boot image in order to make things work. Of course changing the USR_M to SRV_M is indeed an alternative, but it is too lame. 
Also, the Makefiles all need to be taken care of, so that we can actually use the make command to compile our codes.

The implementation is rather an easier part. We get the messages we want (one message at a time, which is VERY convenient) and decide whether to block the message sender or not. We keep track of the waiting processes in an array which has 100 seats and 2 pointers to emulate a queue. Since the process table in minix couldn't handle over 104 processes, there is really no need to use linked lists for this task.

We can be sure that the semephore operations are ATOMIC operations with confidence. The message passing in the kernel are queued and buffered and is assured by the kernel to be ATOMIC. The services use a while loop to take one message from the queue each time and do not take another until it finishes dealing with the current message. That is to say, even if two processes do the down() on the same semaphore at the same time, process switching will certainly NOT affect the logic in the semaphore service.

students and professor:
The professor waits for a student to ask a question with a down() and asks a student to leave with an up(). The student have mutual exclusion on the CAN_ASK semaphore, and asks a question with an up() and leave the room until the professor says so.

Task2:
There is really a lot of places where we can tune the codes to randomize the stack. We choose the fastest way: src/servers/pm/exec.c

Once we have spotted the vsp variable, the only thing we have to do is decrease the stack space with a random number and to make sure the process does not crash. We noticed that although there is a gap between the stack and the data, it might be used when the process is running. We performed a little test and found that most system processes only have 2 or 3 gap clicks between the stack and data, and will certainly crash if we decrease the number of gap clicks. So we can only lay our hands on the user processes which normally have 31 gap clicks. By the way, minix 3 uses 4096 bytes for a memory click and minix 2 only uses 256. So, we check the gap size first and randomize the stack pointer position with respect to the gap size the process have. 

We generates the random number using the system clock. We multipled the clock ticks and added our student numbers to it and finally takes a remainder to ensure that the random number sits tight.