Operating Systems and Systems Integration Tutorial: Process Control Blocks — Solutions 1. What is a process control block (pcb)? i A process control block is a data structure used by an operating system to manage processes. 2. Is a pcb only found in a Linux or posix os or is it found in all operating systems? i As I mentioned in the notes, process control blocks are found in all modern operating systems. The structure of pcbs will be different on each operating system though. 3. Give ONE other name for a pcb. i It is sometimes called a process descriptor, or a task descriptor. In the 2.6 source code of Linux, the data type is a structure called task struct 4. Give ONE name for the data structure that holds the pcbs. i The process table. The pcbs may be put into a number of lists at the same time. The process table describes the system by which the operating system finds a pcb by its process id. 5. Briefly define the term program counter. i The program counter is a cpu register that holds the address of the next instruction that will be fetched. As the cpu fetches each instruction, the pc is automatically incremented to point to the next instruction. You might like to play with the simple Macromedia Flash model of a simple computer consisting of a cpu and ram connected by a 4-bit data bus, 3-bit address bus, and 2-line control bus. You can find it at http://ictlab.tyict.vtc.edu. hk/ossi/lectures/processes/fetching.swf. The ram contains three instructions, each occupies two 4-bit memory locations. 6. What data is held in the program counter ? i The address of the next machine instruction that will be fetched and executed. Process Control Blocks: In figure 1 on the following page we see three processes, P1, P2 and P3. There are seven moments in time where the main values of the pcbs of the three processes are shown. The time intervals are not equal; they are just where the scheduler changed the process. The size of all i/o instructions is three bytes. In each pcb I have shown the program counter value, and the process state. The process state can be running (i.e., executing on the cpu), ready (i.e., ready to run), and sleeping (i.e., blocked). There are two queues shown: a wait queue for processes that are blocked waiting for i/o, and a ready queue, for processes that are in the ready to run state. Nick Urbanik nicku(at)vtc.edu.hk ver. 1.0 Solutions Tutorial: Process Control Blocks Operating Systems and Systems Integration CPU idle t0 2 t4 t5 t6 time t1 t2 t3 Ready Queue: Wait Queue: P3 P2 P3 P1 P1 P2 P2 P3 P3 PCB for P1 0xCAFE Running 0xC0DE Sleeping 0xC0DE Ready 0xC0DE Running Process 1 has terminated; It’s PCB has been freed PCB for P2 0xFACE Ready 0xFACE Running 0xFEED Sleeping 0xFEED Ready 0xFEED Running Process 2 has terminated PCB is freed PCB for P3 0xDEAF Ready 0xDEAF Ready 0xDEAF Running 0xD1CE Sleeping 0xD1CE Ready 0xD1CE Running P3 has exited; PCB freed Figure 1: An example of three processes executing, showing their process control blocks. 1. State the technical term for what the scheduler does at each of the times t0 , t1 , t2 , t3 , t4 , t5 and t6 . i Context switch. 2. Does process P1 perform i/o? If so, at what address is the i/o instruction? i Yes, you can see that it does, because the state of that process is sleeping after t1 , and you can see that it appears in the wait queue, where it waits for the input or output to finish. We are told that the i/o instructions are three bytes long in this particular example, as specified in the question. At t1 , the cpu has already executed the i/o instruction. This is what caused the os to put the process onto the wait queue, since i/o devices are typically much slower than the rate at which the cpu can execute instructions. The os put the process into the sleeping state when the program counter was pointing to the next instruction to be fetched that comes immediately after the i/o instruction. So we know that the address of the instruction after the i/o instruction is at address C0DE16 . The size of the i/o instruction is three bytes, i.e., it is three address locations before C0DE16 , so its address is C0DE16 − 3 = C0DB16 . 3. Does process P2 perform i/o? If so, at what address is the i/o instruction? i Yes, we can see that P2 moves to the sleeping state at time t2 , where we see that it is also on the wait queue. Using the same reasoning as before, we can see that the address of the i/o instruction is FEED16 − 3 = FEEA16 . Nick Urbanik nicku(at)vtc.edu.hk ver. 1.0 Solutions Tutorial: Process Control Blocks Operating Systems and Systems Integration 3 4. Does process P3 perform i/o? If so, at what address is the i/o instruction? i Yes, P3 is blocked for i/o at time t3 . The address of the i/o instruction is D1CE16 − 3 = D1CB16 . 5. List at least FIVE other kinds of data that will be stored in a pcb that is not shown in figure 1 on the previous page. i If you look at the definition of the data type task struct in the header file /usr/ src/linux-2.4.22-1.2188.nptl/include/linux/sched.h and also see the definition of thread struct in /usr/src/linux-2.4.22-1.2188.nptl/include/ asm/processor.h, you will see that the pcb contains a great deal of information about the process, including: • The process id • the process state (for example, whether it is executing, ready to run, or sleeping) • program counter (stored in thread struct) • the scheduling priority • information about the user and groups associated with this process • pointer to the parent process pcb • pointer to a list of child process pcbs • pointers to the process’s data and machine code in memory • pointers to open files and other resources held by the process Nick Urbanik nicku(at)vtc.edu.hk ver. 1.0