Search code examples
processoperating-systemscheduling

How OS manages the process control block associated with a process?


I am currently studying about processes in my operating system course. I am little confused about how processes actually work. According to my understanding

  1. when we double click a executable file(assuming single threaded), a process control block for this new process is created and some space is allocated to the process in the main memory.
  2. Then the short term scheduler, dispatches the process to the CPU (assuming uniprocessor system).
  3. The CPU executes the process and before blocking it (incase an interrupt occurs or the process requests for some I/O), saves the content of CPU in the process control block. And then the process is sent into ready queue.

My first question is, where are these PCB stored? Form what I have read from the other websites, since the information in PCB is quite important, OS save it in the kernel space, but some other websites say that the PCB is stored on Kernel Stack (which is inaccessible in user mode) which is located in the same address space as the process (maybe a process have two stack, a user stack and a kernel stack). So where actually the PCBs are stored?

Also how does OS knows the mapping between the process and it's PCB? How the OS knows the physical location of the process associated with a PCB. I assume because PCB contains memory management information(like value of base register and stack register), so is my assumption correct?

And my last question is what are process table? what information process table stores. (I guess they store pid and a pointer to the PCB of the process)

Sorry for asking such a basic question, but I am unable to find any satisfactory resource regarding this. :(

EDIT 1: researched a bit more and found that OS uses both the kernel stack (which is indeed located under same address space as the process) and PCB. But it turn's out that kernel stack does not stores PCB, it just stores the content of register within the CPU (as answered here: During a context switch, does the OS use PCB or kernel stack to restore registers? . So the question still remains, where are the PCB actually stored?

EDIT 2: after researching a bit more and studying few books, it seems that all the PCBs are actually stored on something called scheduling queue. These queue are indeed kept in system space (not on the kernel stack) and contains PCB. There are quite a few scheduling queue like ready queue, waiting queue, intermediate queue(to store the info about swapped out process), I/O queues and lastly job queue. If a process is not being executed, it's PCBs are stored on one of these queue. Also it turns out that PCB indeed store information like base address of the process and reference to the page table of the process. Though I am still not sure about what is the role of the process table.


Solution

  • Your operating-system course seems to be the classic kind of course where the author gives you information that is not always true with terminology that is not used everywhere and confusing. Overall, os design will be different based on where the os will run and what are its uses. Every os development team will have different terminology for different things. Some data structures you learn about might not be used at all.

    With that said, whether there is a kernel stack and a user stack, where the registers are stored, where the PCB is stored, etc, is so unimportant and varied that it isn't information that an os course should even mention. The course should only mention that the information should be saved somewhere.

    In general, the Linux kernel has one stack for user mode and one stack for kernel mode. It will also have one stack for interrupts for each core (not tied to one process). On Linux, the process has one PCB but, the kernel works on threads. Each thread belonging to the same process share the same virtual address space. The Linux kernel will tie each process to one core. This is due to the cores proximity to some portion of physical memory (called NUMA on x86-64). The ACPI tables give information on which range of physical memory is closer to a certain core. If the kernel wanted to change a thread's core, it would make its execution slower because its memory would have been allocated in the NUMA node of another core.

    The virtual address space (VAS) of modern 64 bits CPUs is enormous (more than 200k GB). All threads have access to its bottom half because the kernel reserves the top half. The instructions of threads and the kernel contain virtual addresses that will be translated by the page tables. The kernel's job is to make sure that the page tables translate virtual addresses to available physical memory. For example, on a computer with 8GB of RAM, the translations must land below 8GB. There is also the NUMA node which needs to be considered.

    On Linux, the PCB is thus stored in the top half of the VAS. On x86-64, the top half of the VAS is made global by switching flags in the page tables. This means that, when the kernel changes the CR3 register (the register pointing to the first page table level for x86), this portion of the TLB (translation cache) is not flushed. There is also PCID (process IDs) support in modern TLBs.

    If you have a bunch of ready threads but not enough cores to run them, you can use timers that raise interrupts when a time slice has elapsed.

    The kernel stack is also stored in the top half of the VAS. Where the registers are saved is really unimportant and is a basic design decision. The PCB stores information on the portion of the VAS that is allocated for a certain process and its corresponding physical counterpart. The remainder of the VAS is made non-present in the page tables by switching a flag. If a thread attempts to read, write or execute there, the kernel kills it (a segfault on Linux).