Experiment 15: multithreading scheduling
Corresponding to section 9.4 of p428
1. Relevant basic knowledge
2. Experimental records
2.1 experimental process
In the last experiment, the operation of a thread was realized: specifically
1. One physical page is applied as PCB
2.init_thread fills in the PCB structure located at the lowest address of the physical page where the PCB is located
3.thread_create leaves the position of interrupt stack and thread stack at the highest address of the physical page where the PCB is located, and fills in all members of the thread stack, in which eip is assigned to the function kernel_thread address.
4. In the last sentence, the inline assembly sets esp as the first address of the thread stack, ret starts the thread and executes the kernel_thread function.
Comparative learning
This experiment realizes multithreading scheduling, and the added functions are as follows
1. Add a special clock interrupt processing function to judge that if the current thread time slice runs out, execute the scheduling function schedule
2.schedule if the time slice of the current thread runs out, it will join the ready queue, then pop up the queue header and call switch_to(cur,next) function
3.switch_ The to function protects the current thread environment, restores the next thread environment, and ret starts executing the next thread.
The specific process is as follows:
1.main. Init in C_ All creates the main thread main_thread is in running state, and then thread_start creates two threads.
Note: thread at this time_ There is no ret instruction in start, which means that this thread is not started. It only completes the single thread experiment init and create, and hangs the thread on the ready queue. The start of this thread is led out by the clock interrupt.
2.main thread time slice 31, argA time slice 31, argB time slice 8. After the interrupt is opened, the clock interrupt occurs frequently. The cpu frequently executes the newly written clock interrupt processing program to constantly judge whether the time slice of the main thread is enough. If it is 0, the main thread is put into the ready queue in the schedule, the time slice is filled, and the argA at the head of the stack queue is issued, so as to execute the argA thread.
3. After that, it is executed circularly, so main argA argB will print circularly.
Functions used in series.
main. Call thread in C_ init
thread_init calls make_main_thread
make_ main_ Call running first in thread_ Thread(), due to loader S has assigned the value of esp to 0xc009f000. Take the first 20 bits to obtain the reserved PCB header address. (TMD gets the lowest address on the next page. What does it mean in the book)
Call init_thread(main_thread, "main", 31), set the member variable of the PCB located on the physical page of the real address 0x0009e000, where the state is running. Then init_all completed.
Then call two thread_. Start function. This function first applied a physical page to PCB, then called init_. Thread assigns the PCB structure to be applied well, and then calls thread_. Create leaves interrupt stack and thread stack at the highest address of the physical page, and fills in the thread stack. Finally, add the ready queue and all thread queues.
Then main C starts to print main in a loop until the clock interrupt handler consumes his time slice, and then executes the schedule(cur,next) function
When esp is located at the lowest PCB address of the main thread, cur = running can be used directly in the schedule(cur,next) function_ Thread () obtains the PCB of the current thread, joins the tail of the queue, and then queues a PCB in the ready queue as the next. Note that the PCB address that is out of the queue here is not the PCB address, but the PCB needs to be converted. Then execute switch(cur,next)
In the switch(cur,next) function, first get cur in the stack during task switching, and then get self in cur_ Save kstack to eax. Then get next in the stack during task switching, and put self in next_ Kstack is assigned to esp, then pop drops several registers, and a ret starts the function kernel_thread,kernel_thread continues to execute function and print argA until it is interrupted by the clock to consume the time slice.
2.2 main.c
#include "interrupt.h"
#include "init.h"
#include "thread.h"
#include "print.h"
void k_thread_a(void* );
void k_thread_b(void* );
int main(void) {
put_str("I am kernel\n");
init_all();
thread_start("k_thread_a", 31, k_thread_a, "argA ");
thread_start("k_thread_b", 8, k_thread_b, "argB ");
intr_enable();
while(1){
put_str("Main ");
}
return 0;
}
void k_thread_a(void* arg){
char* para = arg;
while(1){
put_str(para);
}
}
void k_thread_b(void* arg){
char* para = arg;
while(1){
put_str(para);
}
}
2.3 init.c
#include "init.h"
#include "print.h"
#include "interrupt.h"
#include "../device/timer.h"
/*Responsible for initializing all modules */
void init_all() {
put_str("init_all\n");
idt_init(); // Initialization interrupt
mem_init(); // Initialize the memory management system
thread_init(); // Initialize thread related structure
timer_init();
}
2.4 thread.c
#include "thread.h"
#include "stdint.h"
#include "string.h"
#include "global.h"
#include "debug.h"
#include "interrupt.h"
#include "print.h"
#include "memory.h"
#include "list.h"
struct task_struct* main_thread; // Main thread PCB
struct list thread_ready_list; // Ready queue
struct list thread_all_list; // All task queues
static struct list_elem* thread_tag;// Used to save thread nodes in the queue
/* Get pcb pointer of current thread */
struct task_struct* running_thread() {
uint32_t esp;
asm ("mov %%esp, %0" : "=g" (esp));
/* Take the integer part of esp, that is, the starting address of pcb */
return (struct task_struct*)(esp & 0xfffff000);
}
/* By kernel_thread to execute function(func_arg) */
static void kernel_thread(thread_func* function, void* func_arg) {
/* Disconnect the interrupt before executing the function to prevent the subsequent clock interrupt from being masked and unable to schedule other threads */
intr_enable();
function(func_arg);
}
/* Initialize thread stack thread_stack, put the function and parameters to be executed into thread_ Corresponding position in stack */
void thread_create(struct task_struct* pthread, thread_func function, void* func_arg) {
/* First reserve the space for interrupt using stack. See thread Structure defined in H */
pthread->self_kstack -= sizeof(struct intr_stack);
/* Leave space for thread stack. See thread Defined in H */
pthread->self_kstack -= sizeof(struct thread_stack);
struct thread_stack* kthread_stack = (struct thread_stack*)pthread->self_kstack;
kthread_stack->eip = kernel_thread;
kthread_stack->function = function;
kthread_stack->func_arg = func_arg;
kthread_stack->ebp = kthread_stack->ebx = kthread_stack->esi = kthread_stack->edi = 0;
}
/* Basic information of initialization thread */
void init_thread(struct task_struct* pthread, char* name, int prio) {
memset(pthread, 0, sizeof(*pthread));
strcpy(pthread->name, name);
if (pthread == main_thread) {
/* Since the main function is also encapsulated as a thread, and it is always running, it is directly set as TASK_RUNNING */
pthread->status = TASK_RUNNING;
} else {
pthread->status = TASK_READY;
}
/* self_kstack Is the top address of the stack used by the thread in the kernel state */
pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
pthread->priority = prio;
pthread->ticks = prio;
pthread->elapsed_ticks = 0;
pthread->pgdir = NULL;
pthread->stack_magic = 0x19870916; // Custom magic number
}
/* Create a thread with priority prio, the thread name is name, and the function executed by the thread is function(func_arg) */
struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg) {
/* pcb Both are located in the kernel space, including the pcb of the user process */
struct task_struct* thread = get_kernel_pages(1);
init_thread(thread, name, prio);
thread_create(thread, function, func_arg);
/* Make sure you weren't in the queue before */
ASSERT(!elem_find(&thread_ready_list, &thread->general_tag));
/* Join ready thread queue */
list_append(&thread_ready_list, &thread->general_tag);
/* Make sure you weren't in the queue before */
ASSERT(!elem_find(&thread_all_list, &thread->all_list_tag));
/* Join all threads queue */
list_append(&thread_all_list, &thread->all_list_tag);
return thread;
}
/* Perfect the main function in the kernel as the main thread */
static void make_main_thread(void) {
/* Because the main thread has already run, we are in loader Mov esp when entering the kernel in s, 0xc009f000,
The tcb is reserved for it. The address is 0xc009e000, so you don't need to get it_ kernel_ Page assign another page*/
main_thread = running_thread();
init_thread(main_thread, "main", 31);
/* main Function is the current thread. The current thread is not in thread_ ready_ In the list,
* So just add it to the thread_all_list */
ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag));
list_append(&thread_all_list, &main_thread->all_list_tag);
}
/* Implement task scheduling */
void schedule() {
ASSERT(intr_get_status() == INTR_OFF);
struct task_struct* cur = running_thread();
if (cur->status == TASK_RUNNING) { // If this thread is only cpu time slice, add it to the end of ready queue
ASSERT(!elem_find(&thread_ready_list, &cur->general_tag));
list_append(&thread_ready_list, &cur->general_tag);
cur->ticks = cur->priority; // Reset the ticks of the current thread to its priority;
cur->status = TASK_READY;
} else {
/* If this thread needs an event to occur before it can continue running on the cpu,
It does not need to be queued because the current thread is not in the ready queue.*/
}
ASSERT(!list_empty(&thread_ready_list));
thread_tag = NULL; // thread_tag empty
/* Thread_ ready_ The first ready thread in the list queue pops up and is ready to be scheduled to cpu */
thread_tag = list_pop(&thread_ready_list);
struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag);
next->status = TASK_RUNNING;
switch_to(cur, next);
}
/* Initialize thread environment */
void thread_init(void) {
put_str("thread_init start\n");
list_init(&thread_ready_list);
list_init(&thread_all_list);
/* Creates the current main function as a thread */
make_main_thread();
put_str("thread_init done\n");
}
2.5 thread.h
#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"
#include "list.h"
#include "bitmap.h"
#include "memory.h"
#define TASK_NAME_LEN 16
#define MAX_FILES_OPEN_PER_PROC 8
/* Custom general function type, which will be used as formal parameter type in many threaded functions */
typedef void thread_func(void*);
typedef int16_t pid_t;
/* The state of a process or thread */
enum task_status {
TASK_RUNNING,
TASK_READY,
TASK_BLOCKED,
TASK_WAITING,
TASK_HANGING,
TASK_DIED
};
/*********** Interrupt stack intr_stack ***********
* This structure is used to protect the context of a program (thread or process) when an interrupt occurs:
* When a process or thread is interrupted by an external interrupt or soft interrupt, the context is pushed according to this structure
* Register, intr_ The stack out operation in exit is the inverse operation of this structure
* This stack is fixed in the kernel stack of the thread itself, which is at the top of the page
********************************************/
struct intr_stack {
uint32_t vec_no; // kernel. Interrupt number pushed by push% 1 in s macro VECTOR
uint32_t edi;
uint32_t esi;
uint32_t ebp;
uint32_t esp_dummy; // Although pushad pushes esp in, ESP is constantly changing, so it will be ignored by popad
uint32_t ebx;
uint32_t edx;
uint32_t ecx;
uint32_t eax;
uint32_t gs;
uint32_t fs;
uint32_t es;
uint32_t ds;
/* The following is pushed in by the cpu when entering the high privilege level from the low privilege level */
uint32_t err_code; // err_code will be pushed after eip
void (*eip) (void);
uint32_t cs;
uint32_t eflags;
void* esp;
uint32_t ss;
};
/*********** Thread stack_ stack ***********
* The thread's own stack is used to store the functions to be executed in the thread
* This structure is not fixed in the kernel stack of the thread itself,
* Used in switch_to save the thread environment.
* The actual position depends on the actual operation.
******************************************/
struct thread_stack {
uint32_t ebp;
uint32_t ebx;
uint32_t edi;
uint32_t esi;
/* When the thread executes for the first time, eip points to the kernel function to be called_ thread
At other times, eip points to switch_ Return address of to*/
void (*eip) (thread_func* func, void* func_arg);
/***** The following is only used when the cpu is scheduled for the first time****/
/* Parameter unused_ret is only used to fill up the position and return the address */
void (*unused_retaddr);
thread_func* function; // By kernel_ The name of the function called by thread
void* func_arg; // By kernel_ Parameters required by the function called by thread
};
/* Process or thread pcb, program control block */
struct task_struct {
uint32_t* self_kstack; // Each kernel thread uses its own kernel stack
enum task_status status;
char name[16];
uint8_t priority;
uint8_t ticks; // The number of time ticks per execution on the processor
/* How many cpu ticks has this task occupied since it was run on the cpu,
* That is, how long the task has been performed*/
uint32_t elapsed_ticks;
/* general_tag The function of is used for the nodes of threads in general queues */
struct list_elem general_tag;
/* all_list_tag Is used for thread queue thread_ all_ Node in list */
struct list_elem all_list_tag;
uint32_t* pgdir; // The virtual address of the process's own page table
uint32_t stack_magic; // Use this string of numbers as the boundary mark of the stack to detect the overflow of the stack
};
extern struct list thread_ready_list;
extern struct list thread_all_list;
void thread_create(struct task_struct* pthread, thread_func function, void* func_arg);
void init_thread(struct task_struct* pthread, char* name, int prio);
struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg);
struct task_struct* running_thread(void);
void schedule(void);
void thread_init(void);
#endif
2.6 timer.c
#include "timer.h"
#include "io.h"
#include "print.h"
#include "interrupt.h"
#include "thread.h"
#include "debug.h"
#define IRQ0_FREQUENCY 100
#define INPUT_FREQUENCY 1193180
#define COUNTER0_VALUE INPUT_FREQUENCY / IRQ0_FREQUENCY
#define CONTRER0_PORT 0x40
#define COUNTER0_NO 0
#define COUNTER_MODE 2
#define READ_WRITE_LATCH 3
#define PIT_CONTROL_PORT 0x43
uint32_t ticks; // Ticks is the total number of ticks in the kernel since the interrupt was turned on
/* Put the counter of the operation_ No, read / write lock attribute rwl, counter mode counter_mode writes the mode control register and gives the initial value counter_value */
static void frequency_set(uint8_t counter_port, \
uint8_t counter_no, \
uint8_t rwl, \
uint8_t counter_mode, \
uint16_t counter_value) {
/* Write the control word to the control word register port 0x43 */
outb(PIT_CONTROL_PORT, (uint8_t)(counter_no << 6 | rwl << 4 | counter_mode << 1));
/* Write counter first_ Lower 8 bits of value */
outb(counter_port, (uint8_t)counter_value);
/* Write counter again_ The upper 8 bits of value */
outb(counter_port, (uint8_t)counter_value >> 8);
}
/* Interrupt processing function of clock */
static void intr_timer_handler(void) {
struct task_struct* cur_thread = running_thread();
ASSERT(cur_thread->stack_magic == 0x19870916); // Check whether the stack overflows
cur_thread->elapsed_ticks++; // Record the cpu time occupied by this thread
ticks++; //The number of ticks since the first processing time interruption of the kernel, and the total number of ticks in kernel state and user state
if (cur_thread->ticks == 0) { // If the process time slice runs out, start scheduling the cpu on the new process
schedule();
} else { // Time slice of the current process - 1
cur_thread->ticks--;
}
}
/* Initialize PIT8253 */
void timer_init() {
put_str("timer_init start\n");
/* Set the timing cycle of 8253, that is, the cycle of sending interrupt */
frequency_set(CONTRER0_PORT, COUNTER0_NO, READ_WRITE_LATCH, COUNTER_MODE, COUNTER0_VALUE);
register_handler(0x20, intr_timer_handler);
put_str("timer_init done\n");
}
2.7 interrupt.c add function
void register_handler(uint8_t vector_no, intr_handler function);
/* In the vector of interrupt handler array_ Register and install interrupt handler function in no elements */
void register_handler(uint8_t vector_no, intr_handler function) {
/* idt_table The functions in the array are called according to the interrupt vector number after entering the interrupt,
* See kernel / kernel S call [idt_table +% 1 * 4] */
idt_table[vector_no] = function;
}
2.8 switch.S
[bits 32] section .text global switch_to switch_to: ;Here is the return address in the stack push esi push edi push ebx push ebp mov eax, [esp + 20] ; Get the parameters in the stack cur, cur = [esp+20] mov [eax], esp ; Save stack top pointer esp. task_struct of self_kstack field, ; self_kstack stay task_struct The offset in is 0, ; So go straight to thread Just save 4 bytes at the beginning. ;------------------ The above is the environment for backing up the current thread, and the following is the environment for restoring the next thread ---------------- mov eax, [esp + 24] ; Get the parameters in the stack next, next = [esp+24] mov esp, [eax] ; pcb The first member of is self_kstack member,Used to record the top pointer of level 0 stack, ; Used on cpu Restore level 0 stack when,0 The level stack holds all the information of the process or thread,Including level 3 stack pointer pop ebp pop ebx pop edi pop esi ret ; Return to above switch_to The return address of the comment below, ; Not entered by interrupt,The first execution returns to kernel_thread
2.9 list.h
#ifndef __LIB_KERNEL_LIST_H
#define __LIB_KERNEL_LIST_H
#include "global.h"
#define offset(struct_type,member) (int)(&((struct_type*)0)->member)
#define elem2entry(struct_type, struct_member_name, elem_ptr) \
(struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))
/********** Define link list node member structure***********
*No data element is required in the node, only the pointer of the predecessor and successor nodes are required*/
struct list_elem {
struct list_elem* prev; // Forequarters node
struct list_elem* next; // Successor node
};
/* Linked list structure is used to realize queue */
struct list {
/* head It is the head of the team and is fixed. It is not the first element. The first element is head next */
struct list_elem head;
/* tail It is the tail of the team, which is also fixed */
struct list_elem tail;
};
/* Custom function type function, used in list_ Callback function in traversal */
typedef bool (function)(struct list_elem*, int arg);
void list_init (struct list*);
void list_insert_before(struct list_elem* before, struct list_elem* elem);
void list_push(struct list* plist, struct list_elem* elem);
void list_iterate(struct list* plist);
void list_append(struct list* plist, struct list_elem* elem);
void list_remove(struct list_elem* pelem);
struct list_elem* list_pop(struct list* plist);
bool list_empty(struct list* plist);
uint32_t list_len(struct list* plist);
struct list_elem* list_traversal(struct list* plist, function func, int arg);
bool elem_find(struct list* plist, struct list_elem* obj_elem);
#endif
2.9 list.c
#include "list.h"
#include "interrupt.h"
/* Initialize bidirectional linked list */
void list_init (struct list* list) {
list->head.prev = NULL;
list->head.next = &list->tail;
list->tail.prev = &list->head;
list->tail.next = NULL;
}
/* Insert the linked list element elem before the element before */
void list_insert_before(struct list_elem* before, struct list_elem* elem) {
enum intr_status old_status = intr_disable();
/* Update the successor element of the before precursor element to elem to temporarily separate the before from the linked list*/
before->prev->next = elem;
/* Update elem's own precursor node to the precursor of before,
* Update elem's own successor node to be before, so before returns to the linked list */
elem->prev = before->prev;
elem->next = before;
/* Update the precursor node of before to elem */
before->prev = elem;
intr_set_status(old_status);
}
/* Add elements to the top of the list, similar to the stack push operation */
void list_push(struct list* plist, struct list_elem* elem) {
list_insert_before(plist->head.next, elem); // Insert elem at the head of the team
}
/* Append elements to the end of the linked list queue, similar to the first in first out operation of the queue */
void list_append(struct list* plist, struct list_elem* elem) {
list_insert_before(&plist->tail, elem); // Insert in front of the tail of the team
}
/* Detach element pelem from the linked list */
void list_remove(struct list_elem* pelem) {
enum intr_status old_status = intr_disable();
pelem->prev->next = pelem->next;
pelem->next->prev = pelem->prev;
intr_set_status(old_status);
}
/* Pop up and return the first element of the linked list, similar to the pop operation of the stack */
struct list_elem* list_pop(struct list* plist) {
struct list_elem* elem = plist->head.next;
list_remove(elem);
return elem;
}
/* Find element obj from linked list_ Elem, returns true on success and false on failure */
bool elem_find(struct list* plist, struct list_elem* obj_elem) {
struct list_elem* elem = plist->head.next;
while (elem != &plist->tail) {
if (elem == obj_elem) {
return true;
}
elem = elem->next;
}
return false;
}
/* Pass each element elem and arg in the list plist to the callback function func,
* arg Give func to judge whether elem meets the conditions
* The function of this function is to traverse all elements in the list and judge whether there are qualified elements one by one.
* Find the qualified element and return the element pointer; otherwise, return NULL */
struct list_elem* list_traversal(struct list* plist, function func, int arg) {
struct list_elem* elem = plist->head.next;
/* If the queue is empty, there must be no qualified nodes, so NULL is returned directly */
if (list_empty(plist)) {
return NULL;
}
while (elem != &plist->tail) {
if (func(elem, arg)) { // When func returns true, it is considered that the element meets the conditions in the callback function and hits, so it stops traversing
return elem;
} // If the callback function func returns true, continue to traverse
elem = elem->next;
}
return NULL;
}
/* Return linked list length */
uint32_t list_len(struct list* plist) {
struct list_elem* elem = plist->head.next;
uint32_t length = 0;
while (elem != &plist->tail) {
length++;
elem = elem->next;
}
return length;
}
/* Judge whether the linked list is empty. If it is empty, return true; otherwise, return false */
bool list_empty(struct list* plist) { // Judge whether the queue is empty
return (plist->head.next == &plist->tail ? true : false);
}
3. Experimental results
Self update makefile
Run bochs
