Process management
In the KePOS system, it involves multi-process scenarios, design process initialization, process switching, process destruction; and a reentrant spin lock is designed to achieve process synchronization and mutual exclusion.
The above figure represents the linear address space of each user process. The high address is the kernel linear address space of the process, and the low address is the user linear address space of the process. In the page table of each user process, there are complete kernel linear address mapping, and allocated user linear address mapping**. Address 0x7fffffffffff is the stack base address of the process (the stack extends to the lower address). When system calls, the user space stack is still used. The reason for this design is that I treat system calls as a kind of ordinary function calls that occur in the process, but the processed code occurs in the kernel space of the process.
The TaskManage structure has only one global variable taskManage, which is used to manage all processes. This structure manages 3 process linked lists (readys, running, waits), readys saves all processes in the ready state, running points to the currently running process, waits saves all processes that will be destroyed, and count is used to allocate new processes id.
struct TaskManage{
struct Task * readys;
struct Task * running;
struct Task * waits;
unsigned long count;
};The Task structure represents a process, cr3 represents the location of the first-level page table of the process, pages represents the page allocated by the process, and structPage represents the page number where the stack of a user process is located. This attribute is invalid for the kernel process. It is designed to directly monopolize a piece of physical memory as the stack of the kernel process, so there is no need for page switching. state represents the state of the process, path is the storage location of the process on the disk, window is the window of the process (if the process has no window, it is null), registers is the register value of the process, used for protection and recovery during process switching Context. Next and prev are used to link the process, so that the process is stored in the linked list of taskManage.
struct Task{
unsigned long id;
unsigned long cr3;
struct PageBuffer pages;
unsigned long structPage;
unsigned long state;
unsigned long path;
struct Window * window;
struct Register registers;
struct Task * next;
struct Task * prev;
} This structure represents the register to be saved when the process is switched; when the A process is switched to the B process, the current value of the cpu register will be saved in the register structure of the A process, and then the register structure of the process B The value of is restored to the cpu register, and these two steps are completed by clock interruption.
struct Register{
unsigned long r15;
unsigned long r14;
unsigned long r13;
unsigned long r12;
unsigned long r11;
unsigned long r10;
unsigned long r9;
unsigned long r8;
unsigned long rbx;
unsigned long rcx;
unsigned long rdx;
unsigned long rsi;
unsigned long rdi;
unsigned long rbp;
unsigned long ds;
unsigned long es;
unsigned long rax;
unsigned long rip;
unsigned long cs;
unsigned long rflagc;
unsigned long rsp;
unsigned long ss;
};In a multi-process environment, locks are needed to achieve synchronization and mutual exclusion between processes. The ReeTrantLock structure is a reentrant spin lock, count represents the lock status, if count>0, it means that a process has been locked, and nowTask points to the process currently holding the lock, so that the process can re-acquire the lock.
struct ReeTrantLock{
volatile unsigned long count;
volatile struct Task * nowTask;
}//传入任务的第一个代码的线性地址
void initUserTask(void * userTask){
//初始化一个task节点，用于保存进程的相关信息
struct Task * newTask = (struct Task *)getMemoryBlock(sizeof(struct Task));
initTaskNode(newTask,64);
//分配新的页基地址
unsigned long newCR3 = (struct Task *)getMemoryBlock(4096);
newTask->cr3 = KernelVirAddressToPhyAddress(newCR3);
//分配2页，并获取其物理地址
unsigned long newPageID1 = findFreeBlockInBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, 1);
modifyBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, newPageID1);
unsigned long phyAddress1 = getPageByPageID(newPageID1)->physicsAddress;
set((unsigned int *)KernalPhyAddressToVirAddress(phyAddress1),(char)0x00,PAGE_2M_SIZE);
setPageAttribute(getPageByPageID(newPageID1),1,USER);
unsigned long newPageID2 = findFreeBlockInBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, 1);
modifyBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, newPageID2);
unsigned long phyAddress2 = getPageByPageID(newPageID2)->physicsAddress;
set((unsigned int *)KernalPhyAddressToVirAddress(phyAddress2),(char)0x00,PAGE_2M_SIZE);
setPageAttribute(getPageByPageID(newPageID2),1,USER);
//将新的页插入buffer。
insertPagesBuffer(&newTask->pages,newPageID1);
newTask->structPage = newPageID2;
//设置页映射，首先分配2页，第一个页映射为线性地址0x0，第2个页映射为线性地址0x00007fffffe00000
unsigned long rspVirAdd = 0x00007fffffffffff;
unsigned long ripVirAdd = 0x00007fffffe00000;
virPageTOPhyPage(ripVirAdd,phyAddress2,newTask->cr3,7);
virPageTOPhyPage(0x0000000000000000,phyAddress1,newTask->cr3,7);
//copy进程代码到进程的0x0线性地址，因为用户程序代码被loader保存在物理内存中
copy((unsigned long)userTask,KernalPhyAddressToVirAddress(phyAddress1),200000);
//设置该进程的初始化寄存器
newTask->registers.cs = 0x23;
newTask->registers.rip = 0x0000000000000000; //rip初始为线性地址空间0地址
newTask->registers.ss = 0x1b;
newTask->registers.ds = 0x1b;
newTask->registers.es = 0x1b;
newTask->registers.rsp = rspVirAdd; //rsp初始为0x00007fffffffffff
newTask->path = NULL;
newTask->registers.rbp = newTask->registers.rsp;
newTask->registers.rflagc |= (1UL << 9);
newTask->id = taskManage.count;
taskManage.count += 1;
//初始化后，将该进程插入到taskManage的readys链表中
insertTaskBehand(taskManage.readys->prev,newTask);
newTask->state = READY;
newTask->window = NULL;
//初始化该进程的内核态页表-设置该进程的内核地址空间映射
initKernelPage(newTask->cr3);
}Through the interrupt/exception management, it is known that the system will automatically save the rsp, rip, cs, ss registers when interrupted, and the general-purpose register value will also be saved at the entry of the interrupt processing function, and will be restored first when the interrupt returns to the exit General register value, finally iretq will pop up rsp, rip, cs, ss, and then jump to the target program for execution. Using this feature, the process switching is completed by clock interruption, and each time slice is 10ms. The saveTaskRegisterTogStick(struct Task * task, unsigned long rsp) function is used to save the general register value of the interrupt entry overwhelming the stack to the registers of the task structure of the current process. The backTaskRegisterTogStick(nowTask, rsp) function is used to put the value saved in the current process task structure registers into the interrupt stack. When returning through the clock interruption, you can jump to the new process execution after the scene is restored, and the page table switching must be completed at the same time after switching.
//时钟中断处理函数
void timeHandle(unsigned long rsp){
//.......
//一个时间片10ms，进行一次任务切换
changeTask(rsp);
//.......
}
//任务切换，输入当前栈指针
void changeTask(unsigned long rsp){
//如果没有就绪的任务，直接返回
if((taskManage.readys->prev) == &NullTaskReady){
return;
}
//如果有就绪，但是没有运行中的任务，则直接切换。
if((taskManage.running->prev) == &NullTaskRunning){
struct Task * nowTask = taskManage.readys->next;
deleteTargetTask(nowTask);
insertTaskBehand(taskManage.running->prev,nowTask);
nowTask->state = RUNNING;
backTaskRegisterTogStick(nowTask,rsp);
//设置CR3为新进程的CR3，完成页表切换
modifyCR3(nowTask->cr3);
}else{
//两个队列都不为空,把就绪队列的第一个加入running队列，把running的第一个移到就绪队列。
struct Task * nowReadTask = taskManage.readys->next;
struct Task * nowRunningTask = taskManage.running->next;
deleteTargetTask(nowReadTask);
deleteTargetTask(nowRunningTask);
insertTaskBehand(taskManage.readys->prev,nowRunningTask);
insertTaskBehand(taskManage.running->prev,nowReadTask);
nowRunningTask->state = READY;
nowReadTask->state = RUNNING;
saveTaskRegisterTogStick(nowRunningTask,rsp);
backTaskRegisterTogStick(nowReadTask,rsp);
modifyCR3(nowReadTask->cr3);
}
}First, after the kernel process is initialized, it will not exit, so only the exit of the user process is considered.
- The execution flow of the user process:
The following _start will be linked to the 0x0 linear address in the link phase. According to the above description, the 0x0 linear address is the address of the first instruction of the user process. When the program is functioning, it jumps to the starttask function for execution.
_start:
leaq starttask(%rip) ,%rax
callq *%rax
nop
Disassembly code
0000000000000000 <_start>:
;线性地址 机器码 汇编代码
0: 48 8d 05 e6 01 00 00 lea 0x1e6(%rip),%rax # 1ed <starttask>
7: ff d0 callq *%rax
9: 90 nopThe function of the starttask function is to jump to the execution of the main function, and after the main execution is completed, an exit system call will be executed to exit.
void starttask(){
__asm__ __volatile__ (
"leaq main(%%rip) , %%rax \n\t"
"callq *%%rax \n\t"
:
:
:"memory"
);
//执行结束退出
exit();
}
The final processing function called by the exit system is as follows:
This function inserts the current process into the waits linked list of taskManage, and then executes an endless loop to wait for the process to switch. Therefore, the process switch is only between the readys linked list and running, so the process will not be executed after being switched. There is a cleanup process in the kernel that monitors the waits linked list, and then cleans up the processes in the waits linked list one by one.
//任务运行结束，任务退出
unsigned long sys_taskExit(){
//将当前进程插入到等待队列，等待删除
reetrantlock();
struct Task * nowRunningTask = taskManage.running->next;
//关中断，原子操作
deleteTargetTask(nowRunningTask);
insertTaskBehand(taskManage.waits->prev,nowRunningTask);
//开中断，原子操作完成
reetrantUnLock();
//等待时钟中断切换到下一个任务
while(True);
}2.Clean up
//该进程负责清除wait队列中任务
void cleanTask(){
while (True){
while(taskManage.waits->prev != &NullTaskWait){
exitNowtask(taskManage.waits->prev);
}
}
}
//清理进程
void exitNowtask(struct Task * nowRunningTask){
reetrantlock();
deleteTargetTask(nowRunningTask);
//归还当前task获得的所有页面
unsigned long pageId = nowRunningTask->structPage;
modifyBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, pageId);
setPageAttribute(getPageByPageID(pageId),1,0);
while(!isPagesEmpty(&nowRunningTask->pages)){
pageId = deleteAndreturnPage(&nowRunningTask->pages);
modifyBitmap(memory.zone[RAM].bitmap, memory.zone[RAM].length, pageId);
setPageAttribute(getPageByPageID(pageId),1,0);
}
//归还CR3占用的空间
backCR3page(nowRunningTask->cr3);
//归还pagsbuffer
backPagesBuffer(&nowRunningTask->pages);
//归还该task结构体占用空间
backMemoryBlock(nowRunningTask);
//归还窗口占用的空间
if(nowRunningTask->window->windata != NULL) deleteTaskWindow(nowRunningTask->window);
reetrantUnLock();
}Because the process will only switch when it is interrupted; therefore, you can use off interrupt to complete atomic operations.
1.Lock
//加锁
void reetrantlock(){
//原子操作，关中断
cli();
//如果获得锁的进程不是当前进程，则判断锁是否可以被当前进程获取
struct Task * noTask = taskManage.running->prev;
int i;
if(reeTrantLock.nowTask != noTask){
//当前程序获取到锁
if(reeTrantLock.count == 0){
reeTrantLock.count ++;
reeTrantLock.nowTask = noTask;
}else{
//当前线程获取锁失败，自旋。
while(reeTrantLock.count != 0){
sti();
//等待一段时间在获取锁
for(i = 0;i<1000;i++);
cli();
}
//获得到锁
reeTrantLock.count ++;
reeTrantLock.nowTask = noTask;
}
}else{
reeTrantLock.count ++;
}
//开中断
sti();
}2.Unlock
//解锁
void reetrantUnLock(){
//原子操作
cli();
//给当前锁的引用计数减去1
reeTrantLock.count --;
//如果当前锁的计数为0，该进程释放持有锁
if(reeTrantLock.count == 0){
reeTrantLock.nowTask = NULL;
}
sti();
}KeeProMise/KePOS: Design and implement your own operating system (github.com)