Linux Operating System Scenario Design based on 5 programs
Introduction
In this story, I will first introduce essential Operating System Scenarios based on Linux. Then we will go into five specific programs to show how to design and implement the above OS scenarios in Kernel Level. Finally, I will integer the five programs together and analyze how the OS manages them at the same time. The Five Programs and Related Scenarios are as follows —
# Five programs
P1: create process
P2: create thread
P3: IPC pipe
P4: Priority Queue
P5: Device Driver# Related scenarios
S1: bootstrap
S2: loading
S3: system call
S4: PCB
S5: process management
S6: page table
S7: IPC
S8: cache
S9: file system
S10: device driver
...
How does programs being executed
Let’s say, we want to lit the LED device or input characters from keyboard. First at the User mode, the c programs of LED_lit and Keyboard_input are created. The c library is called to trigger the Interrupt or the System call. Then we come into Kernel mode. In the system call interface, the interrupt handlers are invoked to give the solution of program. VFS will first find specific driver based on the specific files and then find the related drivers to drive the LED or Keyboard.
First Program — create process
1. flow chart
2. source code
#include <sys/types.h> /* define pid_t */
#include <sys/wait.h>
#include <stdio.h>
#include <unistd.h>
int main()
{
pid_t pid;/* fork a child process */
pid = fork();if (pid < 0) { /* error occurred */
fprintf(stderr, "Fork Failed\n");
return 1;
}
else if (pid == 0) { /* child process */
execlp("/bin/ls", "ls", NULL);
}
else { /* parent process */
/* parent will wait for the child to complete */
wait(NULL);
printf("Child Complete\n");
}return 0;
}
3. scenarios design
Loading design: loaders(static loader, dynamic loader) load process resources from disk to memory, and allocate a segment on memory to store it. The length of segment depends on the length of program.
Fork System Call design: sys_clone() clarifies the resources processes need, and call do_fork(). do_fork() assigns pid, task structure and stack space. Set time slices and process state.
PCB design: task_struct can be generally divided into proc struct and user struct. proc struct contains essential process information, including static and dynamic period, such as{p_textp, p_addr, p_size, …}. user struct constains only run time data and state, such as{uid, utime, cutime, …}.
Second Program — create thread
1. flow chart
2. source code
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> //Header file for sleep(). man 3 sleep for details.
#include <pthread.h>// A normal C function that is executed as a thread
// when its name is specified in pthread_create()void *myThreadFun(void *vargp)
{
sleep(1);
printf("Printing GeeksQuiz from Thread \n");
return NULL;
}int main()
{
pthread_t thread_id;
printf("Before Thread\n");
pthread_create(&thread_id, NULL, myThreadFun, NULL);
pthread_join(thread_id, NULL);
printf("After Thread\n");
exit(0);
}
3. scenario design
PCB design: Threads of same process share the resources. In Linux threads are regarded as process, so threads are processes which can get the shared resource from on another process.
Thread management design: kthread_create() function (threadfn is thread address, data is thread reference, namefmt is thread name)
Interrupt design: interrupt_init(void): start kernel and do some initialzation like init trap, init timer. interrupt_drive(): start fork handler, update the program counter…
Third Program — IPC pipe
1. flow chart
2. source code
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#define MSGSIZE 16char* msg1 = "msg1";
char* msg2 = "msg2";
char* msg3 = "msg3";int main()
{
char inbuf[MSGSIZE];
int p[2], i;
if(pipe(p) < 0)
exit(1);/* continue write pipe */
write(p[1], msg1, MSGSIZE);
write(p[1], msg2, MSGSIZE);
write(p[1], msg3, MSGSIZE);
for(i = 0; i < 3; i++) {
/* read pipe */
read(p[0], inbuf, MSGSIZE);
printf("%s\n", inbuf);
}
return 0;
}
3. scenario design
Pipe System Call design: init_pipe_fs: register_filesystem, kern_mount, unregister_filesystem. do_pipe: memory apply, create flag for write/read. create write pipe(), get_flags(). create read pipe()…
Fourth Program — Priority Queue
1. flow chart
p.s. The priority queue orders the elements by priority instead of value.
2. source code
// C code to implement Priority Queueusing Linked List
#include <stdio.h>
#include <stdlib.h>// Node
typedef struct node {
int data;
// Lower values indicate higher priority
int priority;
struct node* next;
} Node;// Function to Create A New Node
Node* newNode(int d, int p)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}// Return the value at head
int peek(Node** head)
{
return (*head)->data;
}// Removes the element with the highest priority form the list
void pop(Node** head)
{
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}// Function to push according to priority
void push(Node** head, int d, int p)
{
Node* start = (*head);
// Create new Node
Node* temp = newNode(d, p);
// Special Case: The head of list has lesser
// priority than new node. So insert new
// node before head node and change head node.
if ((*head)->priority > p) {
// Insert New Node before head
temp->next = *head;
(*head) = temp;
}
else {
// Traverse the list and find a position to insert new node
while (start->next != NULL && start->next->priority < p) {
start = start->next;
}// Either at the ends of the list or at required position
temp->next = start->next;
start->next = temp;
}
}// Function to check is list is empty
int isEmpty(Node** head)
{
return (*head) == NULL;
}// Driver code
int main()
{
// Create a Priority Queue
// 7->4->5->6
Node* pq = newNode(4, 1);
push(&pq, 5, 2);
push(&pq, 6, 3);
push(&pq, 7, 0);
while (!isEmpty(&pq)) {
printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}
3. scenario design
Queue System Call design: Kernel manages heap memory by maintaining the *break pointer.
related kernel methods: make_heap(void *break). push_heap(void *break). pop_heap(void *break). sort_heap(void *break). isEmpty(void *break)
Fifth Program — char device driver
1. flow chart
2. source code
The source code of this program is a little bit complex. You can access it by this link (tbc). Check “read me” to know how to run it on your Linux Operation.
The source code includes hello.c, memory.c and hellotest.c which contains the kernel APIs to create a device driver and do file operations on a Linux OS. The file operations are as follows:
Five Programs Recap
p1~p5 will first be compiled by compiler. The related resources are loaded into memory. Then the programs go into Kernel mode by triggering the Interrupt or System Call. PCB manages the process resources and do the context switching among 5 processes. MMU does the address translation to help find the physical address of each system call in heap.
Closing
This story talked about the essential scenarios of Linux Operating System and how to design them in detail. You can check all the source code here (tbc) If you have any question, feel free to contact me by Github or by Linkedin: linkedin.com/in/linxiu-frances-jiang-961986117 See you in next story!
