Study in sophomore 《 operating system 》 In this course , The main purpose of the course is to linux The system is a case study , At that time, the teacher recommended us to read minix3.1.8 Source code for ,minix3 yes
Classes based on microkernel architecture UNIX Computer operating system , Smart and fully open source , It is easier for the operating system entry-level to understand . The following is my reading notes of source code in the course , If you want to read it minix3.1.8 Friends of source code , Recommend a code reading software
source insight, The tree structure can be used to trace function and variable definition clearly .

One ,Minix3 Start of :

l  Hardware read in bootloader , Bootloader loading boot,Boot Load boot image in memory ( Include kernel ,pm,fs etc. )

l  Kernel initialization (/Kernel/main.c):

1, Initialization process table and privileged process table :

The state is set to idle , Distinguish between task and other process settings p_nr value , take priv[i] Map to ppriv_addr[i] etc.

2, Initializing a program in the boot image , Process name , Process pointers, etc. are copied to proc In the table , And set their privileges ( Are traps allowed , Can it run kernel
call wait ); If it is a kernel task or root system process, it can be immediately scheduled , Other processes cannot be scheduled ;

3, Initialization stack , Establish memory mapping , Initialization register value

4, Initialize the stack pointer of the server , take proc_ptr Points to the current process , Join the team , Set to schedulable state

5, System tasks system get CPU,system After initialization, it enters the blocking state

6, Clock task acquisition CPU, After initialization, it attempts to accept messages from the clock interrupt program and block

7, Other drivers and server processes get CPU And initialize

8,CPU Finally, it is handed over to the first ordinary user process INIT

l  Init implement /etc/rc script , Start other drives and servers that are not in the boot image ( Service, etc ),Rc The script checks to see if it was shut down properly last time

l  Init according to /etc/ttytab File creates a child process for the terminal , implement /usr/bin/getty Waiting for user login , Execute after successful login shell, Waiting for user command


Two , Realization of message mechanism :(/Kernel/proc.c)

l  structure notify( Macro definition BuildNotifyMessage):

1, Change the type of the message to notify

2, call get_uptime Function to read the clock beat to include a timestamp in the notification

3, Determine the originator of the message , If it is HARDWARE, Set the interrupt bitmap of the target process , If it is SYSTEM, Set the signal bitmap of the target process

l  message passing (do_ipc)

1, Tracking progress

2, Synchronous messaging calls do_sync_ipc

Asynchronous messaging call mini_senda

l  Synchronous messaging (do_sync_ipc)

1, Check for errors : Only the system call number is less than 32 Is allowed to be called ; Only by receiving information can the destination process be set to arbitrary ; Are the specified source and destination processes valid ; Whether the initiating process is allowed to send messages to the destination process ; Is the process privileged to issue calls

2, Call the function according to the type of message

SENDREC: Set flag off interrupt , Continue calling SEND and RECEIVE

SEND: call mini_send, Judge whether the transmission is completed

RECEIVE: empty IPC Status bits of , call mini_receive

NOTIFY: call mini_notify

SENDNB: call mini_send, Not clogged when not ready

other : error

l  Specific implementation function :


Check whether the destination process is blocked due to waiting for this message ( The waiting object is the sending process or ANY), Copy message , Receive process through reset RECEIVING Bit unblock , Queue the receiving process so that it can run ; If the receiving process is not waiting for this message , Check deadlock , Blocks and queues the sending process to the end of the waiting send queue of the receiving process


Check whether there are processes in the waiting queue waiting to send messages , If so, find the destination process and receive the message , Dequeue the destination process that has finished receiving messages ; Otherwise, if the queue is empty, check the bitmap to see if there are pending notifications , If it is found that the suspended notification is waiting for the process , Is marked as no longer suspended , And copy the receiving notification , return OK; If not found , Then check MF_ASYNMSG To see if there are any pending ones senda, If so, try to receive asynchronously ; No suitable message was found , Check the deadlock again , This process will be blocked


And mini_send similar , If the recipient of the notification is blocked and waiting to receive the message , Then construct message sending , And make the receiver leave the waiting queue ; If the receiver is not waiting for the message , Set the bitmap of the pending signal and return


Clear the table , Resets the header address and the number of parameters in the table ; Check the quantity to send , Read in bits that are not empty and have not been processed by the kernel ; Check for various possible errors ; Check whether the receiver is waiting for this message , If so, copy and send ; If not , Then inform the receiver . If the receiver does not receive the message immediately , Record the header address and the number of parameters


Three , Process scheduling

l  The header file is defined in (/servers/sched/schedproc.h)

Structs include the endpoints of the process , Marker bit , Maximum allowed privilege level , Current privilege level and time slice length

l  Initializing and receiving messages (/servers/sched/main.c)

1, Start locally and initialize

2, Wait for the next message , If it is a notification, judge whether the message sender is a clock , If yes, check if the timestamp has expired , No reply ; If it's not a clock , Then reply to the sender “ The function is not implemented ”

3, towards sched Server send message request operation

l  Specific scheduling (/servers/sched/schedule.c)


After the time slice is used up , If the priority of this process is higher than the lowest priority of an ordinary process , Demote the process , From inside

The kernel hangs the process to the end of the team


Receive from PM and RS All messages for , Set flag bit representation schedule Is out of service


Receive from PM and RS All messages for , When the port is valid, set the process's schedproc The endpoint of , inspect schedproc Type of , If it's just generated , Set the priority to the highest allowed priority , Assign full timeslot , If it's inherited from your parents , The priority and time slice length are consistent with the parent process . Set flag to indicate schedproc Is in use . Process of takeover scheduling , The kernel call reply message is used to fill the current priority and time slice of the process . Using system call to allocate time slice . Mark yourself as a new schedule .


Keep old information about the request process ( Include old priorities , Old top priority ), Set the new priority to the highest priority , It is hung back to the team by the kernel , If an error occurs during the hang back process , The old value is restored

l  Regular upgrade (balance_queues)

Setting timing , each 100ticks Increase the priority of processes that run out of timeslices by one level


Four , Clock service

l  Start timer interrupt processing (bsp_timer_int_handler):

1, Get the current tick number (lost_ticks by clock_task It was recorded externally when it was not executed tick number , To add it to the current time ), Update time

2, Call interrupt handling function

3, If next time timeout Time is up. , Prove timers out of date , To inform clock task

l  Get beat count (get_uptime):

Return to the ticks number

l  New design timers (set_timer):

1, Will the new timer Structure insertion clock_timers queue , Note that the queue is arranged from small to large according to the overflow time

2, use clock_timers->tmr_exp_time Set a new next time timeout Time of

l  Delete timer (reset_timer):

1, Will no longer be needed from valid and expired timers timer Delete in queue , Update next time timeout Time of

2, if timer The queue is empty , Set the next time timeout At NEVER

l  Update load (load_update):

1, Put the process in line , Calculate the average load

2, Time to update structure

l  Interrupt handling function (ap_timer_int_handler):

1, If a process can be charged, its system time and the number of beats left are updated

2, Decrement virtual timer , If applicable , Decrements the virtual and real timers for the current process

3, If the timer expires , Then send a signal

4, Update average load


©2019-2020 Toolsou All rights reserved,
Final review of database : Summary of comprehensive application questions Laplance operator ( Second derivative ) Simple learning of computer composition principle pyqt Button call python program _PyQt: Link button to function in program How much can you go up once you change jobs ? Today, I saw the ceiling of job hopping python in str Function usage _python in str Usage Summary of built-in functions MySQL trigger web The server nginx---linux Installation and deployment C++ Chapter V polymorphism exercises :( It's coming to an end )python Check built-in functions , How to check python Built in function