<> reading note Chapter 2

2.3 Interrupt Mechanism

1. Two 8259A
   
2. The address: main 8259A (0x20), the slave (0xA0)
   
3. The IN and OUT instructions are used to control the 8259A initialization by CPU
4. The INT instruction is used to inform CPU by 8259A that there is an interruption occurred
5. Interrupt types：hardware interrupt and software interrupt
6. int0~int3(0x00~0x1f) used by Intel as exceptions
7. int32~int47(0x20~0x2f) used by Linux corresponding to the IRQ0~IRQ15 of 8259A
   
8. The Linux sets the system_call sent by user programs as interrupt int128(0x80)

2.4 System Timer

1. The programmable time chip is Intel82593 and It sends a signal (IRQ0) at a constant interval time.
   
2. Every time the timer_interrupt is called to accumulate the count of the intervals since the system starts. The count is stored in the variable: jiffies
3. Every time the  do_timer will be called to accumulate the time of the current running process by its DPL
4. The kernel process will not be cut over by the scheduler, but the user process will.
   

2.5 Linux  Process Control

• The system call fork is used to create processes.
• For Linux 0.11 there are at most 64 processes existing at the same time
• There kernel stack is divided from the user stack

1. Task Data Structure
   
   • The kernel uses the process table to manage the processes
   • The task_struct (PCB:Process Control Block, PD:Processor Descriptor)defines the data structure of a process and every process that currently exists has a item in the process table.
   • The process context is including all registers' value, the state of the process, the data in the stack.
   • In Linux, the process context is stored in the task_struct.
   • 
     
     The task_struct of linux kernel 0.11 in include/linux/sched.h
     struct task_struct {
     /* these are hardcoded - don't touch */
         long state;    /* -1 unrunnable, 0 runnable, >0 stopped  */
         long counter;
         long priority;
         long signal;
         struct sigaction sigaction[32];
         long blocked;    /* bitmap of masked signals  */
     /* various fields */
         int exit_code;
         unsigned long start_code,end_code,end_data,brk,start_stack;
         long pid,father,pgrp,session,leader;
         unsigned short uid,euid,suid;
         unsigned short gid,egid,sgid;
         long alarm;
         long utime,stime,cutime,cstime,start_time;
         unsigned short used_math;
     /* file system info */
         int tty;        /* -1 if no tty, so it must be signed  */
         unsigned short umask;
         struct m_inode * pwd;
         struct m_inode * root;
         struct m_inode * executable;
         unsigned long close_on_exec;
         struct file * filp[NR_OPEN];
     /* ldt for this task 0 - zero 1 - cs 2 - ds&ss */
         struct desc_struct ldt[3];
     /* tss for this task */
         struct tss_struct tss;
     };
   
   
2. Task Running State
   
   • TASK_RUNNING             : The process is running or ready to run
     
   • TASK_INTERRUPTIBLE     : The process is sleeping and waiting an interrupt, resources or a signal.
     
   • TASK_UNINTERRUPTIBLE : The process is sleeping but can be waked up only by the wake_up().
     
   • TASK_STOPPED             : The process is stopped by having received a signal(SIGSTOP,SIGTSTP,SIGTTIN,or SIGTTOU) and it is to run when the signal (SIGCONT) is received.
     
   • TASK_ZOMBIE              : The process is at this state when it is stopped but before its parent process inquired about its state.
   • To prevent kernel data error during switching between processes, all interrupts are disabled when the kernel runs the code in the critical area.
     
3. Process Initialization
   
   1. The process to initialize the kernel
   1. Booting ...
      
   2. The loader loads the kernel into memory
   3. Jump into and running in the protected mode
   4. Execute the init/main.c to initialize the system. The main.c will first decide how to allocate the system physical memory and then call the initialization functions to initialize Memory Management, Interrupt Handling, Block and Character Device, Process Management and Hard Disk and Soft Disk hardwares and so on.
      
   5. Then the program moves itself to TASK 0 and call fork() to create Process 1
   6. The Process 1 will go on to initialize the application environment can call the log application of Shell.
   7. Now the system is running.
      
   2. The Process 0 will be called at the system idle time. It only calls the pause() and the schedule function.
   3. The action to move and run into TASK 0 is completed by move_to_user_mode macro (include/asm/system.h).
      
   4. The steps to initialize the TASK 0
   1. Set the data structure's value of TASK 0 (include/linux/sched.h)
   2. Add descriptors of TASK 0's TSS and LDT and load them into tr (Task Register) and ldtr (Local Descriptor Register).
      
   5. The Kernel initialization code is the code of the TASK 0 initialization code. The difference is that to initialize the kernel has the DPL 0 but the TASK 0 initialization has DPL 3.
   6. The move_to_user_mode macro uses the method that using interrupt return instruction results the DPL changes.
      
4.  Creating New Process
1. In Linux, use fork() to create new process.
2. All processes are copies of Process 0 and all are child of Process 0
   
3. Steps to create new process:
1. The system first finds an empty item in the TASK array. If there is no empty item ( the max item count is 64), the fork() will return with error.
2. Then system requires a memory page to store the data structure of the new TASK and copies all the task data structure and its data contents of the current process as the task data structure template for the new process. To prevent the new process which is not completely created from being executed by the schedule function, the state of the new process is set as TASK_UNINTERRUPIBLE.
3. Then update the contents of the copied data structure.
1. Set the current process as the parent of the new process
2. Clear the signal bmp, reset each system statistic value and set 15 system interval as time clip
3. tss.eax = 0; tss.esp0; tss.ss0; tss.ldt; tss.i387
4. Process Scheduling (30／652)
   
   • The Linux processes are robbing mode.
   • The processes robbed are still at TASK_RUNNING state, which are only run by CPU.
   • The process robbing is occurred at the use mode and running in the kernel mode can not be robbed
   • The process schedule in Linux 0.11 is based on the priority queue algorithm.a
1. Schedule processes
1. Scanning the TASK array, schudle() decides which process' running time is the  fewest by the counter value.  The bigger the counter value is the fewer time the process is running. The process with the biggest counter will be selected by the scheduler to be switched to.
2. If the time chips of all processes at TASK_RUNNING are run out, system will recompute the time chip of every process including processes at TASK_SLEEP by its priority. counter=(counter/2) + priority.
3. Then the schedule() function scans all the processes at TASK_RUNNING and repeat the steps above until a process is selected.
4. At last switch_to() executes the actual process switching operation.
5. If there is no process to select, the system will run the Process 0.Save & close
2. Switch processes
1. The switch_to() executes the actual operation of process switching.
2. 
   
5. Stop processes
1. Pending...

   
2.6 The Memory Using in Linux Kernel

1. Blocks of memory Divided by Linux
   
1. Kernel mode block is at the start of memory
2. Cache Memory:
   
3. Virtual Disk
4. Main Memory block
   
2. Memory Management System In Intel CPU
1. Segmentation System
2. Paging System (can be selected by system programmer)
   
3. Different Addresses
1. Logical Address of Programs : the offset address
   
2. Linear Address of CPU : it is between the Logical address and the physical address in the address conversion. The capacity of the Intel 80386 linear address is 4G.
   
3. Physical Address :
   
4. Virtual Memory means the computer can use much more memory that it actually has. In Linux 0.11, every program is assigned 64M memory in size.
5. Virtual Memory Management
1. When a program accesses a memory address that not exists in the memory pages will cause page error interrupt and the linear address which caused the interrupt will be placed in CR2 (Control register)
2. The interrupt handler gets the specific address that caused the page exception and loads the requested page from secondary memory space to memory.
3. If all physical memory has been occupied, use part of the secondary memory space as swapper, switch the memory pages that are not used currently to this swapper and then load the requested page into memory. This is the missing page loading mechanism and it is implemented in the mm/memory.c.
4. Addressing Using Segment Concept
1. Intel CPU uses the Segment concept to implement addressing
2. Every segment defines some specific memory block and access priority and so on. Every program can have several segments.
3. In Linux 0.11, the address mapping from program logical address to linear address uses the global descriptor table (GDT) and local descriptor table (LDT) of CPU. The global address memory is mapped by GDT and the LDT maps the local address memory. The two constitutes virtual address memory.
   
4. In Linux 0.11, there is no system segment descriptor table.
   
5. Memory Paging Management
1. This theory divides the main memory into pages one of which is 4096kb in size. The page is used as the unit when programs request memory.
2. Using this method, every running process can use much larger continuous address memory that it really has.
1. In Intel 80386, CPU can supply 4G linear address memory in size.
2. In Linux 0.11, the GDT has at most 256 items among which two are idlesse, two are used by system and every process uses two items. Therefor, system can have at most 127 tasks. Every task can be assigned to 64MB virtual address memory. Totally, it is 8GB. In Linux 0.11, the maximum number of tasks defined manually is 64. So it requires 4GB virtual address memory totally same as the size CPU can supply.
3. 
   
3. The virtual address of processes is first mapped as the linear address by GDT and LDT, then the linear address is mapped as physical address by Page Directory Table (PDT) and Page Table (PT).
4. In order to use physical memory, the linear address of processes is dynamically mapped to main memory pages by PT. The logical address plus (TASK Number * 64MB) is the linear address.
5. After Linux 0.99, every process can use all 4GB address memory independently.

2.7 Stack Using In Linux (Pending 35 of 652)

2.8 Directory Tree of Linux Kernel Source Code

// The Directory Tree of Linux Kernel 0.11
\---linux- 0.11  
+---boot       // Assembly programs to boot system
+---fs         // File System
+---include    // Head Files (*.h)
| +---asm       // Related to CPU architecture
| +---linux     // Exclusive used by Kernel
| \---sys       // Data structures of System
+---init       // Programs to initialize Kernel
+---kernel     // Process Scheduler, Signal Handler, System Call of Kernel
| +---blk_drv   // Block Device Driver
| +---chr_drv   // Character Device Driver
| \---math      // Math Co-processor Simulator
+---lib        // Kernel Function Library
+---mm         // Memory Management Programs
\---tools      //  Tools to generate Kernel Image file

//Kernel File Tree:
//
\---linux- 0.11
| Makefile
|
+---boot         // It's function is to guide the kernel to boot,
                    // load the kernel code into memory
                    // and do some preparations for running into the 32-bit protection mode.
| bootsect.s   // disk bootstrap program
| head.s        // will be compiled to the head of the system module
                   // and used to set hardware probing and
                   // initialize the memory page management

| setup.s      // used to read hardware configuration parameters and move kernel system module to proper location
|
+---fs         // to manage the using of cache blocks in Cache Storage and file systems of block devices
| bitmap.c        // to handle the bitmaps of the i-th node and logical data blocks in file system
| block_dev.c   // functions to read and write to data blocks
| buffer.c    // to manage the using of cache blocks
| char_dev.c      // has the function to read and write to character devices
| exec.c     // to supply a function : do_execve() to run programs
| fcntl.c     // to supply functions of IO Control of file system
| file_dev.c   // functions to read and write to files based on i-th note and file descriptor
| file_table.c // only defined a data structure of file descriptor
| inode.c      // functions to control the i-th node in file system
| ioctl.c       // to supply functions to control IO of character block devices by referring to functions in kernel/chr_drv/tty.c.
| Makefile
| namei.c    // to manage the name of file and directory.
| open.c      // contains functions to modify file properties, create and close files
| pipe.c       // functions to read and write to pipelines, and create pipelines.
| read_write.c    // to define three file functions: read, write and locate
| stat.c            // two functions to gain file status
| super.c         // contains functions to handle the supper blocks of file system
| truncate.c      // to release device and data resources  used by files  which will be deleted during deleting these files
|
+---include
| | a. out.h      // defines the executable file format of a.out
| |  const.h
| | ctype.h     // defines same macro of type determination and conversion of characters
| | errno.h     // system error numbers
| | fcntl.h      // file control
| | signal.h    //
| | stdarg.h
| | stddef.h
| |  string.h
| | termios.h
| | time.h
| | unistd.h
| | utime.h
| |
| +---asm
| | io.h
| | memory.h
| | segment.h
| | system.h
| |
| +---linux
| | config.h
| | fdreg.h
| | fs.h
| | hdreg.h
| | head.h
| | kernel.h
| | mm.h
| | sched.h
| | sys.h
| | tty.h
| |
| \---sys
| stat.h
| times.h
| types.h
| utsname.h
| wait.h
|
+---init
| main.c
|
+---kernel
| | asm.s
| | exit.c
| | fork.c
| | Makefile
| | mktime.c
| | panic.c
| | printk.c
| | sched.c
| | signal.c
| | sys.c
| | system_call.s
| | traps.c
| | vsprintf.c
| |
| +---blk_drv
| | blk.h
| | floppy.c
| | hd.c
| | ll_rw_blk.c
| | Makefile
| | ramdisk.c
| |
| +---chr_drv
| | console.c
| | keyboard.S
| | Makefile
| | rs_io.s
| | serial.c
| | tty_io.c
| | tty_ioctl.c
| |
| \---math
| Makefile
| math_emulate.c
|
+---lib
| close.c
| ctype.c
| dup.c
| errno.c
| execve.c
| Makefile
| malloc.c
| open.c
| setsid.c
| string.c
| wait.c
| write.c
| _exit.c
|
+---mm
| Makefile
| memory.c
| page.s
|
\---tools
build.c

1. boot (39 of 652)
2. fs
1. Regarding to the reading and writing action of block device data, the file system will use Cache Storage Block and block device drivers and the file system function set itself will not deal with block device drivers directly.
   
3. include
4. init
5. kernel
6. lib
7. mm
8. tools
   

2.9 Relationship Between Kernel System and User Programs

1. Two parts of system interface to user
1. Interrupt call : int 0x80
2. Kernel Lib
   
2. 
   

2.10 linux/makefile

Pending


--
Happy day, happy life!