Operating system of Jilin University (Experiment 2: processor scheduling -- real-time scheduling algorithms EDF and RMS)
Vegetable chicken blog, just as a learning record... Learn the operating system!
1. Getting ready
Our teacher suggested to experience gcc programming under Linux, so if we don't use the computer provided by the school and experience it on our own computer, we should build a linux environment.
There are many ways to do this (such as installing the corresponding Linux version iso file for VMware virtual machine, installing the virtual machine with hardware isolation, and doing some security tests are more practical). I use WSL (Microsoft's solution for both fish and bear's paw: Windows Subsystem for Linux, that is, the Linux subsystem in the windows system)
For the corresponding configuration environment, please refer to the blog:
Windows 10 turns on the Linux subsystem
tips:
- Where is the location of WSL file in Windows 10 system?
Enter in Explorer: \ \ wsl$
The corresponding path is:
C:\Users \ username \ appdata \ local \ packages \ canonicalgrouplimited UbuntuonWindows_ 79rhkp1fndgsc\LocalState\rootfs
(replace the highlighted part of the path according to your user name and WSL system)
In this way, the corresponding file data can be modified directly by using the graphical interactive interface of windows.
- There is no gcc compiler in the initial state of installed linux, so you need to download it yourself. Because the download source address of ubuntu is in Europe, it's best to change to the domestic image source. There are many online tutorials. You can learn and follow.
2. Some important operations under Linux
- Display all files in the current directory: ls
- Enter subdirectory: cd directory name
- Back to parent directory: cd
- Create a new directory: mkdir directory name
- How to mount a USB drive: Mount – t vfat /dev/sdb /mnt/usb (the USB drive is mounted under / mnt/usb.)
- How to enter the editing interface: gedit file name (you can write the original code of C in this program)
- Switch permissions of root user: su
- Switch back to a user: su user name
- View process status: ps aux
Table name | Respective meanings |
---|---|
USER | user |
PID | Process number |
%CPU | Percentage of CPU consumed by the process |
%MEM | Percentage of memory used |
STAT | Process state, e.g. S is in sleep state; R is running; Z zombie process does not exist but cannot be eliminated for the time being |
COMMAND | command |
3. GCC programming
gcc is a super compiler that can compile executable programs on a variety of hardware platforms. Its execution efficiency is 20% ~ 30% higher than that of general compilers.
As we know, a C/C + + program must go through at least four steps from coding to generating binary executable files:
- Preprocessing: expand the macro of the source file
- Compile: compile the source program into an assembly file
- Assembly: compile assembly files into machine code
- Link: link the target file with an external symbol to generate an executable file
Therefore, - c in gcc will generate the corresponding target file, and - o command will generate binary executable file. The basic process is:
- vi [target document] c
- gcc [target file] c -o [executable document]`
- . / [executable]
The most basic usage of gcc is:
- gcc [options] [filenames]
(1) Where options is the parameter required by the compiler;
(2) filenames gives the relevant file name. - -o output_filename
Make sure the name of the output file is output_filename, and this name cannot have the same name as the source file. If this option is not given, gcc gives the default executable a.out. - -lname
When connecting, load the function library named "libname.a", which is located in the directory preset by the system or the directory determined by the - L option. For example, - lm indicates a connection to a mathematical function library named "libm.a". - -Ldir
When compiling, search the path of the library. This option tells the connector to first look in the directory specified by - L, and then look in the system preset path
For example: gcc – lm -L/home/mylib ts.c – o ts.out
At this time, precompile, compile and connect ts.c to generate an executable file with the specified name ts.out. m library needs to be introduced in the compilation process For some standard libraries, there is no need to point out the path As long as they are under the path of the default library, the path of the system's default library / usr/lib /usr/local/lib /lib is under these three paths. We can not specify the path.
Exercise: the starting point of everything - print helloworld
① Create a C file VI hello c
② Press i under the English input method to enter the write state and start writing the code content. The following will change to "INSERT"“
③ After input, press Esc to exit the write status, and then enter: wq save to exit
④ Directive: GCC hello c -o helloworld
gcc compiler. After compiling, a helloworld running file appears in your file. (enter ls to view)
3. Instruction:/ helloworld
You can see the successful output. After the preliminary work, we begin our operating system experiment class practice.
4. Experiment 1 process and thread -- Linux Process and thread communication
Experimental purpose
Deeply understand the concept of thread and process, master the differences between thread and process in components, as well as their corresponding communication methods and application objectives.
Experimental content
- Based on the Linux system process and thread mechanism, master the forms and functions of fork() and clone() system calls, as well as the corresponding advanced communication methods. The sub processes derived from fork communicate through pipe, and the threads created by clone communicate through shared memory. The latter needs to consider the problem of mutual exclusion.
- Take the producer / consumer problem as an example to understand the difference between fork() and clone() system calls through experiments. The program requires that four processes or threads can be created, and data can be transferred between producers and consumers.
Experimental preparation
fork system call
pid=fork()
Create a child process. The child process is a complete copy of the parent process. The new process created by fork() is a copy of the current process (except the return value). All resources of the child process inherit from the parent process to obtain a copy of the parent process resources. Since they are copies, that is, they do not share the address space (using write time replication technology).
A wonderful thing about fork call is that it is only called once, but it can return twice. It may have three different return values:
1) In the parent process, fork returns the process ID (pid) of the newly created child process;
2) In the child process, fork returns 0;
3) If an error occurs, fork returns a negative value;
clone system call
#define _GNU_SOURCE #include <sched.h> int clone(int (*func)(void*),void *child_stack,int flags,void *func_arg,.... /*pid_t *ptid,struct user_desc *tls,pid_t *ctid*/); Return process ID of child on success,or -1 on error
-
Like fork(), the new process created by clone() is almost a replica of the parent process. However, unlike fork(), when the cloned sub process continues to run, it does not take the calling place as the starting point, but instead calls the function specified by the parameter func, which is also called a sub function. The parameters when calling a sub function are defined by func_arg specified. After conversion, the sub function can freely interpret the meaning of the modified parameter, for example, it can be used as an integer value (int) or as a pointer to the structure.
-
When func returns or calls exit() (or _exit()), the cloned child process will terminate. As usual, the parent process can wait for the cloned child process through functions such as wait().
-
Because the cloned child process may share the memory of the parent process, it cannot use the stack of the parent process. The caller must allocate a moderate memory space for the stack of the child process, and place the pointer of this memory in the parameter child_stack.
-
The parameter flags serves a dual purpose. First, its low byte stores the termination signal of the child process. When the child process exits, its parent process will receive this signal. (if the child process generated by the clone terminates due to the signal, the parent process will still receive the SIGCHLD signal) this byte may also be 0, and no signal will be generated at this time.
-
The flags parameter in the clone() function is a combination of masks:
Mask | significance |
---|---|
Shared file descriptor: CLONE_FILES | If this flag is specified, the parent and child processes share the same open file descriptor table. In other words, the allocation and release of file descriptors by any process will affect a process. |
Sharing file system related information: CLONE_FS | If this flag is specified, the parent and child processes will share information related to the file system: permission mask, root directory and current working directory. That is to say, in any process, calling umask(), chdir() or chroot() will affect another process. |
Shared signal handling settings: CLONE_SIGHAND | If this flag is set, the parent and child processes will share the same signal processing table. In any process, calling sigaction() or signal() to change the setting of signal processing will affect the disposal of signals by other processes. |
Shared virtual memory of parent process: CLONE_VM | If this flag is set, the parent and child processes will share the same virtual memory page. No matter which process updates memory or calls mmap(), munmap(), the other process will also observe the change. |
Thread group: CLONE_THREAD | If this flag is set, the child process will be placed in the thread group of the parent process. If this flag is not set, the child process is placed in a new thread group. |
Thread library support: CLONE_PARENT_SETTID,CLONE_CHILD_SETTID and CLONE_CHILD_CLEARTID | To implement POSIX threads, Linux 2 6 provides for CLONE_PARENT_SETTID,CLONE_CHILD_SETTID and clone_ CHILD_ Clearid support. These flags will affect the processing of the parameters ptid and ctid by clone(). If clone is set_ PARENT_ Settid, the kernel will write the thread ID of the child process to the location pointed by ptid. If clone is set_ CHILD_ Settid, then clone() will write the thread ID of the child thread to the position pointed by the pointer ctid. If clone is set_ CHILD_ Clearid, the memory pointed to by ctid will be cleared when the child process terminates. |
Thread local storage: CLONE_SETTLS | If this flag is set, the user pointed to by the parameter tls_ The desc structure describes the thread local storage buffer used by the thread. |
Undo value of shared systemV semaphore: CLONE_SYSVSEM | If this flag is set, the parent and child processes will share the same SystemV semaphore revocation value list. |
Per process mount namespace: CLONE_NEWNS | Set the parent process of the child process as the parent process of the caller: CLONE_PARENT |
Process tracking: CLONE_PTRACE and CLONE_UNTRACED | If clone is set_ If ptrace is and the child process is being tracked, the child process will also be tracked. From Linux 2 From 6, clone can be set_ Untrained flag, which also means that the tracking process cannot force its child process to be set to CLONE_PTRACE |
Suspend the parent process until the child process exits or call exec():CLONE_VFORK | If this flag is set, the parent process will hang until the child process calls exec() or_ exit() to free virtual memory resources. |
pipe system call
// fd[0] is the FD (file descriptor) of the pipeline reading end // fd[1] is the fd of the pipeline write end // Return on success: 0 // - 1 in case of error int pipe(int fds[2]);
Conceptually, a pipe is a connection between two processes, which makes the standard output of one process become the standard input (Communication) of another process.
The pipeline is only one-way communication. One process writes to the pipeline and another process reads from the pipeline. This is a main memory area that is considered a "virtual file". The created process and all its child processes can use pipes for reading and writing. One process can write to the pipeline, and another related process can read from it. If the pipeline is empty and at least one process is open at the input port of the pipeline, a process will be suspended when trying to read the of the pipeline.
wait()
wait() will temporarily stop the execution of the current process until a signal comes or the child process ends:
- If the child process has ended when calling wait(), wait() will immediately return the child process end status value. The end status value of the child process will be returned by the parameter status, and the process ID of the child process will be returned together.
- If you don't care about the end status value, the parameter status can be set to NULL.
If the execution is successful, the sub process identification code (PID) is returned. If an error occurs, the return value - 1 is returned:
pid_t pid; int status=0; i=wait(&status);
i returns the identification code PID of the sub process; Status stores the end status of the child process; The state of exit(3) of the child process can be obtained by using the macro wired (status), which is also 3;
#include<stdio.h> #include<stdlib.h> #include<unistd.h> #include<sys/types.h> #include<sys/wait.h> int main(int argc,char *agrv[]){ pid_t pid;//pid represents the value returned by the fork function pid=fork();//Create a child process if(pid<0)//abnormal perror("error in fork!\n"); if(pid==0){//The parent process recognizes that this is a child process running int i=0; for(i=0;i<4;i++){ printf("this is son process,the process's pid is %d.\n",getpid()); sleep(2);//Let the child process sleep for 2 seconds to see the behavior of the parent process } exit(1); } else{//The child process ends and the parent process runs int status=0; wait(&status); if(WIFEXITED(status)!=0){ printf("son process is over and return %d \n",WIFEXITED(status)); } printf("this is father process\n"); } return 0; }
Output results:
sem_ Post (& status) and SEM_ wait(&status)
sem_post function
int sem_post(sem_t *sem);
The function is to add a "1" to the value of the semaphore. When a thread is blocked on this semaphore, calling this function will make one of the threads no longer block. The selection mechanism is determined by the thread scheduling policy.
sem_wait function
int sem_wait(sem_t * sem);
Its function is to subtract a "1" from the value of the semaphore, but it will always wait for the semaphore to be a non-zero value before starting the subtraction.
pthread_ mutex_ Lock (& mutex) and pthread_ mutex_ unlock(&mutex)
Condition variable is a mechanism for synchronization by using global variables shared between threads, which mainly includes two actions:
① A thread hangs while waiting for "the condition of the condition variable is established";
② Another thread makes the "condition true" (gives the condition true signal).
To prevent contention, the use of conditional variables is always combined with a mutex.
pthread_mutex_init(&mutex,NULL);//initialization pthread_mutex_lock(&mutex); //Mutex lock pthread_mutex_unlock(&mutex);//Mutex unlock
Note: 1) functions are atomic operations, which can be understood as an instruction and will not be interrupted by other programs
2)pthread_cond_wait, first release the mutex of the current thread, then hang up the thread and wait for the condition variable to meet the condition. Once the condition variable meets the condition, the thread will be locked and continue to execute pthread_cond_wait.
Compiling: gcc thread_test.c -o thread_test -lpthread
experimental design
- Create a pipe file with pipe(), and then create two production processes and two consumption processes with fork(), and transfer information between them through pipe().
- Create four light processes (threads) with clone(), specify resources such as shared memory with parameters, simulate production and consumption problems through shared memory, and use pthread_ mutex_ lock(), pthread_ mutex_ Functions such as unlock () realize mutual exclusion of shared memory access.
fork system call experiment code
#include "sys/types.h" #include "sys/file.h" #include "unistd.h" char r_buf[4]; //Read buffer char w_buf[4]; //Write buffer int pipe_fd[2]; pid_t pid1, pid2, pid3, pid4; int producer(int id); int consumer(int id); int main(int argc,char **argv){ if(pipe(pipe_fd)<0){//Transmission error printf("pipe create error \n"); exit(-1); } else{ printf("pipe is created successfully!\n"); //Who occupies the pipeline and who transmits data if((pid1=fork())==0) producer(1); if((pid2=fork())==0) producer(2); if((pid3=fork())==0) consumer(1); if((pid4=fork())==0) consumer(2); } close(pipe_fd[0]); //These two sentences need to be added close(pipe_fd[1]); //No, there will be readers or writers waiting forever int i,pid,status; for(i=0;i<4;i++) pid=wait(&status); //Return child process status exit(0); } //producer int producer(int id){ printf("producer %d is running!\n",id); close(pipe_fd[0]); int i=0; for(i=1;i<10;i++){ sleep(3); if(id==1) //Producer 1 strcpy(w_buf,"aaa\0"); else //Producer 2 strcpy(w_buf,"bbb\0"); if(write(pipe_fd[1],w_buf,4)==-1) printf("write to pipe error\n"); } close(pipe_fd[1]); printf("producer %d is over!\n",id); exit(id); } //consumer int consumer(int id){ close(pipe_fd[1]); printf(" producer %d is running!\n",id); if (id==1) //Consumer 1 strcpy(w_buf,"ccc\0"); else //Consumer 2 strcpy(w_buf,"ddd\0"); while(1){ sleep(1); strcpy(r_buf,"eee\0"); if(read(pipe_fd[0],r_buf,4)==0) break; printf("consumer %d get %s, while the w_buf is %s\n",id,r_buf,w_buf); } close(pipe_fd[0]); printf("consumer %d is over!\n", id); exit(id); }
Output results:
Analyze the experimental results of fork():
It can be seen from the results of program (1) that when a process changes its spatial data, the corresponding data content of other process spaces does not change, indicating that the child process created by fork() statement has a relatively independent address space with its parent process, and pipe() can be used for communication when solving the problem of production and consumption. Because the child process copies the open file table of the parent process, the communication pipeline established by pipe() can be inherited by the child process, and the production and consumption processes can communicate through reading and writing the same pipeline file.
In program (1), the consumer receives the data sent by the producer from the pipeline and compares it with the data in its own storage area. The data of the two processes are different, indicating that the two processes have different storage space.
As like as two peas, the most difficult thing to understand is the relative independence of address space between father and son process. Or does the subprocess open up a new? Moreover, we know that the child process is almost a complete copy (Replica) of the parent process. The child process only has its own process number resources and timers. When we change the content of the child process without affecting the parent process and saving system overhead to a certain extent, what we actually do is:
- When fork() is called, the child process has the same page table as the parent process
- The part of the page table that points to the RAM code segment will not change (because if the code segments of the parent and child processes are definitely the same, there is no need to copy the code segment, so the kernel marks the code segment as read-only, so that the parent and child processes can safely share this code segment).
- For the contents of data segments, heap segments and stack segments, we should not only ensure that the parent-child processes are independent of each other, but also ensure the utilization of the kernel (we must not directly open a new space in the memory and copy one exactly, which is too wasteful!), So we let the father and son point to the same physical memory page first, then capture the memory request, and when processing the request, create and copy the page to be modified in the corresponding request to the new page (copy on write technology), which is much more intelligent, This achieves the effect that the parent-child storage space is relatively independent.
Reference blog
clone system call experiment code
#define _GNU_SOURCE #include "sched.h" #include<sys/types.h> #include<sys/syscall.h> #include<unistd.h> #include <pthread.h> #include "stdio.h" #include "stdlib.h" #include "semaphore.h" #include "sys/wait.h" #include "string.h" int producer(void * args); int consumer(void * args); pthread_mutex_t mutex; sem_t product; sem_t warehouse; char buffer[8][4]; int bp=0; int main(int argc,char** argv){ pthread_mutex_init(&mutex,NULL);//initialization sem_init(&product,0,0); sem_init(&warehouse,0,8); int clone_flag,arg,retval; char *stack; //clone_flag=CLONE_SIGHAND|CLONE_VFORK //clone_flag=CLONE_VM|CLONE_FILES|CLONE_FS|CLONE_SIGHAND; clone_flag=CLONE_VM|CLONE_SIGHAND|CLONE_FS| CLONE_FILES; //printf("clone_flag=%d\n",clone_flag); int i; for(i=0;i<2;i++){ //Create four threads arg = i; //printf("arg=%d\n",*(arg)); stack =(char*)malloc(4096); retval=clone(producer,&(stack[4095]),clone_flag,(void*)&arg); //printf("retval=%d\n",retval); stack=(char*)malloc(4096); retval=clone(consumer,&(stack[4095]),clone_flag,(void*)&arg); //printf("retval=%d\n\n",retval); usleep(1); } exit(1); } int producer(void *args){ int id = *((int*)args); int i; for(i=0;i<10;i++){ sleep(i+1); //Performance thread speed difference sem_wait(&warehouse); pthread_mutex_lock(&mutex); if(id==0) strcpy(buffer[bp],"aaa/0"); else strcpy(buffer[bp],"bbb/0"); bp++; printf("producer %d produce %s in %d\n",id,buffer[bp-1],bp-1); pthread_mutex_unlock(&mutex); sem_post(&product); } printf("producer %d is over!\n",id); exit(id); } int consumer(void *args){ int id = *((int*)args); int i; for(i=0;i<10;i++) { sleep(10-i); //Performance thread speed difference sem_wait(&product); pthread_mutex_lock(&mutex); bp--; printf("consumer %d get %s in %d\n",id,buffer[bp],bp+1); strcpy(buffer[bp],"zzz\0"); pthread_mutex_unlock(&mutex); sem_post(&warehouse); } printf("consumer %d is over!\n",id); exit(id); }
Compilation: GCC - pthread clone c -o clone. out
Operation:/ clone.out
Output result (output clip excerpt):
producer0 produce aaa in 0 producer1 produce bbb in 1 producer0 produce aaa in 2 producer1 produce bbb in 3 producer0 produce aaa in 4 producer1 produce bbb in 5 consumer0 get bbb in 5 consumer1 get aaa in 4 producer0 produce aaa in 4 producer1 produce bbb in 5 producer0 produce aaa in 6 producer1 produce bbb in 7 consumer0 get bbb in 7 consumer1 get aaa in 6 producer0 produce aaa in 6 producer1 produce bbb in 7 consumer0 get bbb in 7 consumer1 get aaa in 6 producer0 produce aaa in 6 producer1 produce bbb in 7 consumer0 get bbb in 7 consumer1 get aaa in 6 producer0 produce aaa in 6 producer1 produce bbb in 7 consumer0 get bbb in 7 consumer1 get aaa in 6 consumer0 get bbb in 5 consumer1 get aaa in 4 producer0 produce aaa in 4 producer1 produce bbb in 5 consumer0 get bbb in 5 consumer1 get aaa in 4 consumer0 get bbb in 3 consumer1 get aaa in 2 consumer0 get bbb in 1 consumer1 get aaa in 0 producer0 produce aaa in 0 producer0 is over! producer1 produce bbb in 1 producer1 is over! consumer0 get bbb in 1 consumer0 is over! consumer1 get aaa in 0 consumer1 is over!
Analysis of clone() experimental results:
As can be seen from the result of program (2), when creating a process, clone() statement can set whether the child process and the parent process share storage space through parameters, so as to create a real thread. Producer and consumer processes share memory so that data can be exchanged directly through shared memory. However, multiple processes need a mutual exclusion mechanism to share memory. The program defines the critical area variable mutex and two semaphores product, warehouse. The critical area variable is used for mutual exclusion of shared memory operations. Semaphores realize the waiting of producers and consumers respectively.
In program (2), the consumer outputs the data in the storage area, and the data in the storage area changes with the data stored by the producer, indicating that the clone() statement passes through the clone_ The parameter setting of flag realizes the shared memory. If clone is removed in the experiment_ VM option, unexpected results will occur.
Leave a hole here. The output of the above clone system is idealized output. I didn't run out myself. I got the file without output:
The teacher explained to me that because the experiment of clone thread is relatively old and linux has been updated for many generations, there may be incompatibility between linux and the old version. The updated header file cannot recognize some of the parameters, so the compilation can pass, but the corresponding function cannot be realized if there is a problem with parameter recognition. The problem with this code is clone_ Clone in flag_ Sighand, verified clone_ After sighand is added, the clone () function call always returns - 1, that is, the new creation is unsuccessful. Then I tried to clone_ Remove sighand and replace with clone_ VFORK, you can clone() successfully and return a process number, And you can see some in the output, as shown in the figure below (however, this is not the thread communication we pursue, because this code only involves threads, but the following code shows that there should be 10 cycles in the process producer, but only 8 cycles are displayed, and then they are stuck all the time. I haven't figured out, or in other words, how CLONE_VFORK affects threads? I'll leave a pit here, and I just give an example to illustrate this parameter Problems. The solution is to try the old version of virtual machine in the school computer room or your own next old version of linux):
My own ubuntu and gcc versions are:
I think the configuration is very troublesome. The blogger is still a sophomore vegetable dog preparing for the end of the term. I have time to configure an old version in the summer vacation. hu~
Thinking questions
• in Linux environment, in addition to pipe and clone public memory communication, shm and msg communication methods can also be used. Try to consult relevant materials to understand these communication methods, and use any of the above methods to simulate and realize the "producer / consumer" problem.
• compare the advantages and disadvantages of pipe, clone, shm and msg advanced communication methods in Linux system and their respective environments.
Reference blog: shm shared memory
Reference blog: msg message queue
code:
#include <stdio.h> #include <unistd.h> #include <string.h> #include <sys/ipc.h> #include <sys/shm.h> #include <error.h> #define SIZE 1024 int main() { int shmid; char *shmaddr; struct shmid_ds buf; int flag = 0; int pid; //Create shared memory shmid = shmget(IPC_PRIVATE, SIZE, IPC_CREAT|0600); if ( shmid < 0 ) { perror("get shm ipc_id error"); return -1; } //When a child process is created, calling fork will return twice. The parent process returns the created process, and the child process returns 0 pid = fork(); if( pid == 0 ) {//Subprocess //Map shared memory to local processes shmaddr = (char *)shmat(shmid, NULL, 0); if( (int)shmaddr == -1 ) { perror("shmat addr error"); return -1; } strcpy( shmaddr, "Hi,I am child process!\n"); //Break mapping shmdt( shmaddr); return 0; } else if( pid > 0 ) {//Parent process //It may occur that the parent process ends execution earlier than the child process, so delay waiting for the child process to finish execution first sleep(3); //Get the state of shared memory and put the shmid of shared memory_ Copy DS structure to buf flag = shmctl ( shmid, IPC_STAT, &buf); if( flag == -1 ) { perror("shmctl shm error"); return -1; } printf("shm_segsz=%d bytes\n", buf.shm_segsz); printf("parent pid=%d,shm_cpid=%d\n",getpid(),buf.shm_cpid); printf("chlid pid=%d,shm_lpid=%d\n",pid,buf.shm_lpid); //Map shared memory to local shmaddr = (char *)shmat(shmid, NULL, 0); if( (int)shmaddr == -1 ) { perror("shmat addr error"); return -1; } printf("%s",shmaddr); //Disconnect shared memory shmdt(shmaddr); //Delete shared memory shmctl(shmid,IPC_RMID,NULL); } else { perror("fork error"); shmctl(shmid,IPC_RMID,NULL); } return 0; }