리눅스 커널의 이해

참 좋은 자료다. 시대가 변해도 한번 읽을만한.
Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
부족하나마 정보의 공유를 목적으로 공개하오니 내용이 잘못되었거나 하시고 싶은 말은 rtlinux@rtlinux.to로 연락 바랍니다.
차례
Chapter 1. Introduction
Chapter 2. Memory Addressing
Chapter 3. Process
Chapter 4. Interrupts and Exceptions
Chapter 5. Timing Measurements
Chapter 6. Memory Management
Chapter 7. Process Address Space
Chapter 8. System Calls
Chapter 9. Signals
Chapter 10. Process Scheduling
Chapter 11. Kernel Synchronization
Chapter 12. The Virtual Filesystem
Chapter 13. Managing I/O Devices
Chapter 14. Disk Caches
Chapter 15. Accessing Regular Files
Chapter 16. Swapping ; Methods for free memory
Chapter 17. The Ext2 Filesystem
Chapter 18 . Process Communication
Chapter 19 . Program Execution(생략)

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 1. Introduction
차례
리눅스 vs 유닉스 커널
운영체계 기본 개념
유닉스 커널 개요
참고 사항
리눅스 vs 유닉스 커널
상용 유닉스 커널에 대한 리눅스 평가 항목
The Linux kernel is monolithic.
Tranditinal Unix Kernel are compiled and linked statically.
Kernel Threading.
Multithreaded application support.
Linux is a nonpreemptive kernel.
Multiprocessor support.
Filesystem.
STREAMS.
운영체계 기본 개념
하드웨어 플랫폼에 포함되어있는 모든 하드웨어 구성요소에 작용
컴퓨터 시스템에서 실행되는 응용 프로그램의 구동 환경 제공
Multiuser Systems
사용자 확인 인증 메커니즘
시스템에 실행중인 응용 프로그램으로부터 사용자 프로그램 보호 메커니즘
다른 사용자들의 작업 감시 프로그램으로부터 보호 메커니즘
각 사용자에 제한된 리소스를 할당하는 관리 메커니즘
Users and Groups
UID, GID
root, superuser, supervisor
Processes
address space
multiprogramming, multiprocessing
scheduler
nonpreemptive, preemptive
system call
Kernel Architecture
microkernel
module
모듈 사용시 장점
Modularized approach
Platform independence
Frugal main memory usage
No performance penalty
Integrated(Monolithic) Kernel vs Micro Kernel Architecture
유닉스 커널 개요
The Process/Kernel Model
System calls
커널 서비스를 필요로 하는 프로세스가 사용하는 프로그래밍 구조
프로세스가 요구하는 사항들을 식별하여 설정하고 하드웨어 의존적인 CPU 명령을 User Mode와 Kernel Mode를 오가며 실행
Kernel Threads
커널 주소 공간에서 Kernel Mode로 실행
사용자에 직접적인 영향을 주지 않으므로 터미널 디바이스 필요 없음
대부분 시스템이 구동될 때 생성되고 시스템이 종료되기 전까지 남아있음
USER MODE
KERNEL MODE
Process 1
Process 1
Process 2
Process 2
System call
handler
System call
Schedular
Timer interrupt
Interrupt
handler
Device interrupt
Process Implementation
process descriptor
Reentrant Kernels
reentrant
reentrant functions
kernel control path
Process Address Space
mmap()
Synchronization and Critical Regions
Nonpreemtive kernel
Interrupt disabling
Semaphores
Spin locks
Avoiding deadlocks
Signals and Interprocess Communication
Asynchronous notifications
Synchronous errors or exceptions
Semaphores, message queues, shared memory
Process Management
Zombie process
Process groups and login sessions
Memory Management
Virtual Memory
Random access memory usage
Kernel Memory Allocator
Process virtual address space handling
Swapping and caching
Device Drivers
참고 사항
Kernel Thread
필요시 kernel에 의해서 생성 및 삭제
Kernel의 text와 global data를 공유
자신만의 kernel stack을 가짐
독립적으로 scheduling되며 표준화된 synchronization
Asynchronous한 연산 수행시 유용
Kernel stack과 register등 context 정보를 보관할 정도의 공간
Kernel thread의context switch는 일반 프로세스 보다 빠름
-> memory mapping을 다시할 필요가 없음
Linux에서는 boot 초기에 init를 kernel thread로 생성
init thread는 kernel의 특정 function을 수행하는 thread가 됨
Lightweight Process
User Threads
Nonpreemptive kernel
다른 말로 Cooperative multitasking
Real-Time system에서는 사용될 수 없는 구조
Windows 3.1 이 nonpreemptive kernel의 예
preemptive kernel
CPU를 사용할 준비가 된 가장 높은 priority의 task가 점유
RTOS에서 사용
Windows 95/98/NT, Unix
reentrancy
코드가 재진입이 가능하다는 것
semaphore
공유자원을 액세스 하기 위한 하나의 키(key)
Deadlock
#define N5
philosohper(int i)
{
while (TRUE)
{
think();
take_fork(i);
task_fork((i+1) % N);
eat();
put_fork(i);
put_fork((i+1) % N);
}
}
시스템이 더 이상 진행될 수 없는 상태에 도달

Semaphore 적용시
get_semaphore(mutex);
state [i] = HUNGRY;
test(i);
release_semaphore(mutex);
get_semaphore(s[i]);
}
put_forks(int i)
{
get_semaphore(mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
release_semaphore(mutex);
}
test(i)
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
{
state[i] = EATING;
release_semaphore(s[i]);
}
}
#define N5
#define LEFT(i-1) % N
#define RIGHT(i+1) % N
semaphore mutex = 1;
semaphore s[N];
philosopher (int i)
{
while (TRUE)
{
think();
take_forks(i);
eat();
put_forks(i);
}
}
take_forks(int i)
{
Linux 커널 구조

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 3. Process
차례
Process Descriptor
Process Switching
Creating Processes
Destroying Processes Introduction
Process Descriptor
process를 관리하기 위해서 kernel은 각각의 process가 무엇을 하는지 명확히 알고 있어야 한다.
task_struct type structure
Single process에 관련된 모든 정보를 포함하고 있는 field
Complex : 다른 data structure를 point로 가지고 있기 때문
Figure 3-1. The Linux process descriptor
Process State
Process state를 기술할 수 있는 flag의 집합으로 구성되어 있다.
현재의 Linux version에서는 status가 mutually exclusive하다
따라서 flag 하나가 set되면 나머지 flag들은 clear된다
Possible Process State
TASK_RUNNING
프로세스가 실행중이거나(or 현재 프로세스), 언제든지 실행 할 준비가 되었다(시스템의 CPU 중 하나에 할당되는 것을 기다리고 있는 것)
TASK_INTERRUPTIBLE
시그널에 의해 인터럽트 될 수 있다
TASK_UNINTERRUPTIBLE
하드웨어를 직접 기다리면서 어떤 환경에서도 인터럽트 되지 않는다.
TASK_STOPPED
프로세스가중단된경우로, 대개시그널을 받았을경우이다. 프로세스를 디버그 할때 이런 상태에 있다.
TASK_ZOMBIE
정지된 프로세스이나, 여전히 task_struct자료구조는task벡터에 있다.
Identifying a Process
Process ID(PID)는 32 bit unsigned integer로 되어있다.
예전에는 16bit였는데 이때는 recycling으로 부족한 PID를 해결했다.
The task array
Lifetime : 몇 밀리초에서 몇 달
NR_TASKS : task의 개수
Storing a process descriptor
Process : dynamic entity
process descriptor : dynamic memory에 저장
8KB memory area : process descriptor, Kernel Mode process stack
Figure 3-2. Storing the process descritor and the process kernel stack
esp register : CPU stack pointer
The current macro
Kernel은 현재 CPU에서 실행중인 esp 레지스터 값의 process descriptor pointer를 쉽게 얻을 수 있다. p70
Linux 2.0에서는 current라는 descriptor를 쓴다.
currentàpid

Task_struct_stack :
cache내의 process descriptor의 pointer를 가지고 있다.

push, pop으로 동작

free_task_struct()

alloc_task_struct()

The process list
효율적인 검색을 위해서 kernel은 몇 가지 process list를 생성한다.
Figure 3-3. The process list(복잡한환형 큐방식)
SET_LINKS(insert), REMOVE_LINKS(remove)
for_each_task(scans the whole process list)
The list of TASK_RUNNING processes
CPU에서돌고 있는new process를 찾을 때 TASK_RUNNING(called runqueue list)를 쓴다.
next_run, prev_run, nr_running(runnable processes의총합)
add_to_runqueue(), del_from_runqueue()
for scheduling purpose
move_first_runqueue(), move_last_queue()

wake_up_process() :
set TASK_RUNNING à add_to_runqueue() à nr_running 증가

The pidhash table and chained lists
Scanning은 순차적으로 process list 를 찾거나 process descriptor 의 pid field를체킹하는게 가능하지만 비효율적이다.
따라서 검색향상을위해 PIDHASH_SZ의 element인 pidhash hash table을이용한다
하지만 언제나 PID와 table index가 1:1로 일치 하는 것은 아니다(colliding)
Linux에서는 PID의colliding을 핸들하기 위해서 chaining 를 사용한다.
pidhash_next, pidhash_pprev에 의해 구현됨

Figure 3-4. The pidhash table and chained lists
hash_pid(), unhash_pid(), find_task_by_pid()
The list of task free entries
task array는 process가 계속 create와 destroy된다
kernel은 add작업이 더 효율적이기 때문에 array linearly와 first free entry를 찾는 대신 분리된 더블 linked와 free entry를 tarray_freelist로 관리한다.
Figure 3-5. An example of task array with free entries
Parenthood Relationships Among Processes
process는 parent/child relationship으로 생성이된다.
또한 몇 개의sibling relationship으로생성도 가능하다.
process 1(init) : the ancestor of all other processes
process P : following fields
Figure 3-6. Parenthood relationships among five processes
p_opptr(original parent), p_pprt(parent)
p_cptr(child), p_ysptr(younger sibling), p_osptr(older sibling)
Wait Queues
Wait queue는 커널, 부분적인 인터럽트 핸들링, process synchronization, timing등에서 사용된다 .
process는 disk operation이 끝나거나, system자원이 release되거나 지정된 시간 간격이 지날 때 이벤트가 발생하기를 기다린다.
Wait queue는 이벤트의 wait상태를 구현한다.
Wait queue는 어떤 condition이 true가 될 때 커널에 의해 sleeping 상태로 설정 된다 .
wait queue는 process descriptor에pointer가 포함 되는 element가있는 순환 list 로 구현된다 .
wait queue pointer(for intel 4byte) : list의 첫 element이거나 list 가 비어있다면null pointer
Figure 3-7. The wait queue data structure
init_waitqueue()
add_wait_queue(q,entry)
remove_wait_queue()
sleep_on()
wake_up
Process Usage Limits
system resources의 제한
current->rlim[RLIMIT_CPU].rlim_cur
getrlimit(), setrlimit() : superuser만수정 가능
RLIMIT_CPU, RLIMIT_FSIZE
RLIMIT_DATA, RLIMIT_STACK
RLIMIT_CORE, RLIMIT_RSS
RLIMIT_NPROC, RLIMIT_NOFILE
RLIMIT_MEMLOCK, RLIMIT_AS
Process Switching
process switching, task switching, context switching
CPU에서돌고있는 process를suspend시키고다른 process를실행시키는 작업
Linux에서 process switching의요소
Hardware context, Hardware support, Linux code, Saving the floating point registers
Hardware Context
각 process가 자신의 address space 를 가지는 동안 모든 process는 CPU register를 공유한다.
hardware context시에 saving과loading에 소요 되는 시간을최소화 하는 것이 중요하다.
초기버전에서는 hardware context switch 가 쓰였다 .
Intel architecture에서 지원, CPU가 자동으로 수행가능
Linux 2.2에서는 hardware context switch 대신 process switching을 쓴다.
segmentation register의 값 체크가 가능하다.
hardware context switch에서는 optimize가 불가능 하지만 current switching에서는 미래에는 가능하게 될것이다.
Task State Segment
Intel 80x86 architecture는 Task State Segment(TSS) 라는 hardware context 를 저장하기위한 segment타입이있다
The Switch_to Macro
prev와next를이용하여 process switch 를 수행한다 .
switch_to는kernel에서가장 hardware_dependent 한 routine이다.
Saving the Floating Point Registers
Intel 80486부터 arithmetic floating point unit(FPU)가 CPU에통합되어 사용되었다.
옛날 모델과 호환성을유지하기 위해 mathematical coprocessor는 ESCAPE instructions 를 사용하여floating point arithmetic function을 수행했다.
최근 보다 빠른 multimedia application 실행속도를 위해 microprocessor 에 assembly명령을 넣은 MMX가나왔다.
단점 : floating point instruction 와 MMX instruction는 mix 안됨.
장점 : floating point unit 의 상태를저장하는 task-switching code 와 MMX 상태를저장하는것이 같기때문에운영체제 디자이너는 새로운 instruction set 을 고려하지않아도된다
hardware context switch가 일어날 때 cr0 register의 TS(Task Switching) flag 가 set된다 .
TS flag가 set되면 매 시간 ESCAPE혹은 MMX instruction 이 실행되며, 제어장치는 “Device not available”라는 exception을 내 보낸다.
TS flag는 필요로 할때 kernel이 floating point register를저장하고 되돌려 주게 한다.
Creating Processes
전통적인 UNIX 시스템에서는 모든 프로세스가 같은 방법으로 다루어진다.
resource의 소유권은 parent와 동등하게 되고 copy하면 child 도 같이 부여된다.
이러한 process 생성 방법은parent의 주소공간 전체가복사되므로 느리고 비효율적이다.
child process는 부모의 자원을읽거나 수정하는 일이드물다
Modern Unix kernel은 같은 physical page에 parent와 child가write하면서 복사하는 것을 허용한다.
둘 중 하나가 physical page에 쓰려고 하면 kernel은 새로운 physical page를 복사해서 writing process를할당한다.
vfork()는 parent 의 memory address space를 공유할 수있게생성한다.
Child에의해서 parent 의 data가 overwriting 되는 것을막기위해서 child가 존재 하거나 새 프로그램이 실행 될 때까지 parent에 block을 걸어둔다.
The clone(), fork(), and vfork() System Calls
__clone()
Lightweight processes를생성된다.
__clone()에는 4개의 parameter 가 있다.p-94
fn : 새 process 에 의해실행되는 function
arg : fn() function에 들어갈 data 포인터
flags : 기타 정보(child가 종료됐을 때parent에게 보내지는 signal number)
child_stack : child process의 esp 레지스트에 할당되는 User Mode stack pointer
Kerlnel Threads
전통적인 Unix system 은 몇 가지critical task(flushing disk cache를포함하거나, 사용하지않는 page frames 을 swapping하거나network connections을 service 하는 것)를running process에게 일시적으로 위임 한다.
linear fashion은 수행이 비효율적이다 .
function과 end user process 가 background에서scheduled된다면 더 좋은 결과를 얻을 수 있다.
system process 중의 일부는 Kernel Mode 에서만 동작하기때문에최근에는 운영체제가kernel thread에 그 기능을위임
Creating a kernel thread
Kernel_thread()는새로운 kernel thread를생성하고다른 kernel thread를실행시킬 수있다.
Process 0
process 0는 모든 프로세스의 조상이다.
start_kernel() function에 의해 Linux는 초기화되는 동안 kernel thread 가 생성된다 .
start_kernel() 커널에의해 모든 data structure(enable interrupts, create another kernel thread, named process 1, init process 로 참조되는 일반적인 것들)를 초기화 시킨다.
새로 생긴 kernel thread 는 PID 1 을 가지며process 0를공유한다.
scheduler로부터 선택이 되면init process는 init() function 을 수행한다 .
init process가 생성되고 나면 process 0 는 cpu_idle()를 수행한다.
Process 1
kernel thread는 process 0 가 수행하는 init()에 의해 생성된다 .
kernel_thread()에는 kernel task routine 을 위해 4개의 kernel thread가 초기화 된다. p-96
결과적으로 4개의 kernel thread 의 추가는 memory cache 핸들을 생성하고 swapping 한다.
init()은 init program을 실행하기 위해 execve() system call을 호출한다.
init process는 결코 terminate되지 않는다.
Destroying Processes
대부분의 process 는 코드가실행되다가 죽는다
이때소유된 resource(memory, open file 등)를release해 줘야 한다.
exit() system call을 만나 종료하는 경우
코드의 마지막은 자동으로 exit()가호출된다.
kernel이 강제로 죽이는 경우
process가 받는 signal을 handle 혹은 ignore할 수 없거나 CPU exception을 복구할 수 없을때
Process Termination
모든 process 는 do_exit()에의해서 종료된다 .
Process Removal
Unix kernel은 process terminate 직후에 process descriptor field에 포함되어 있는 data를버리지 않는다.
따라서 Unix Operating system은 parent process 의 PID나 children 의 execution state를 알아 낼 수 있다.
TASK_ZOMBIE : process가 죽었다 할지라도process descriptor는 parent process 가 notified 할 때까지는 저장하고 있어야한다.
이러한 문제를 해결하기 위해서 orphan process는 init process의 children 이 되고 init은 wait()와 같은 system call 을 이용하여 children을 죽일 수 있게 한다 .

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 4. Interrupts and Exceptions
차례
Interrupts and Exceptions
Nested Excecution of Exception and Interrupt Handlers
Initializing the Interrrupt Desciptor Table
Exception Handling
Interrupt Handling
Returning from Interrupts and Exceptions
Introduction
인터럽트란 프로세서에 의해 명령 수행이 변경되는 이벤트
CPU 내/외부 하드웨어에 의해 생성되는 전기적 시그널
동기적 인터럽트(synchronous interrupts)
비동기적 인터럽트(asynchronous interrupts)
Intel 80x86 프로세서에서는 동기, 비동기를 각각 exceptions, interrupts로 설명
Interrupts and Exceptions
Interrupts
Maskable interrupts
Nonmaskable interrupts
Exceptions
Processor-detected exceptions
Faults
Traps
Aborts
Programmed exceptions
Interrupt and Exception Vectors
0~255 사이의 숫자로 확인
Intel 아키텍쳐에서는 벡터라는 8비트로 불림
Unmaskable interrupt 및 exception은 고정
Maskable interrupt는 프로그램해서 변경 가능
0~31 벡터 : exception, nonmaskable 인터럽트
32~47 벡터 : maskable 인터럽트
48~255 벡터 : software interrupt
128 or 0x80 벡터 : 시스템 콜
IRQs and Interrupts
IRQ(Interrupts ReQuest)
Programmable Interrupt Controllers(PIC)
Exceptions
Intel 80x86에서 20가지 다른 exception 존재
펜티엄 모델에서의 exception (p105~p107)
Interrupt Descriptor Table
8바이트 디스크립터로 구성, 최대 256*8=2048바이트
Task gate, Interrupt gate, Trap gate
Hardware Handling of Interrupt and Exceptions
Nested Excecution of Exception and Interrupt Handlers
리눅스에서는 CPU가 인터럽트와 연관된 kernel control path를 실행하는 동안 프로세스 변경을 허용하지 않음
kernel control path는 자유스럽게 존재
프로그램 가능한 인터럽트 컨트롤러와 디바이스 컨트롤러의 처리량 향상
우선순위 레벨없는 인터럽트 모델 수행
Initializing the Interrrupt Desciptor Table
커널에서 인터럽트를 다루려면 IDT 테이블의 초기 주소를 로딩하고 테이블 엔트리를 초기화 해야함.
Interrupt, Trap, System Gates
set_intr_gate(n,addr)
set_system_gate(n,addr)
set_trap_gate(n,addr)
Preliminary Initialization IDT
리눅스에서는 BIOS 루틴 사용 안함
setup_idt() 함수에서 idt_table에 저장
Exception Handling
리눅스에서의 exception
변동적인 상황을 알리기 위해 시그널을 프로세스에 보냄
요구 페이징을 다루기 위해
Exception handler 구성
커널모드 스택에 대부분의 레지스터의 내용을 저장
고수준 C 함수로 exception을 다룸
ret_from_exception() 함수로 핸들러 탈출
Saving the Register for the exception handler
C 함수 중지후 명령 리턴 주소
유저 모드 레지스터에 대한 스택 주소
하드웨어 에러 코드
Interrupt Handling
인터럽트에서는 exception과 같은 방식으로는 어려움
하드웨어적인 제한이 있을 경우
리눅스의 인터럽트
Critical
Noncritical
Noncritical deferable
Interrputs Vectors
내부타이머 장치 IRQ0
salve 8259A PIC IRQ2
외부 연산 프로세서 IRQ13
IRQ Data Structures
Irq_desc_t descriptor
hw_interrupt_type descriptor
Irqaction descriptor
Saving the Register for the Interrupt Handler
IRQn interrupt
BUILD_IRQ
SAVE_ALL
do_IRQ() Function
인터럽트와 관련된 모든 인터럽트 서비스 루틴에서 실행
Interrupt Service Routines
irq
dev_irq
regs
Bottom Half
낮은 우선순위의 함수이며 커널 인터럽트 관련해서 수행되도록 기다리는 인터럽트 핸들링을 다루는 경우
Activating and tracking the state of bottom halves
init_bh(n, routine)에 의해 초기화
mark_bh(n), bh_active, do_bottom_half()
Extending a bottom half
커널함수가 인터럽트 서비스를 하는 단순 함수가 아닌 bottom half로서 실행이 필요한 경우
Dynamic Handling of IRQ Lines
IRQ0, IRQ2, IRQ13을 제외한 나머지 13개의 IRQ
프로그램에서 /dev/fd0 디바이스 파일 어드레싱 가정
Returning from Interrupts and Exceptions
여러 개의 kernel controal path가 동시에 수행되는 경우
Bottom half를 활성화 시켜야 하는 경우
프로세스 변경 요청을 미루는 경우
시그널을 미루는 경우
ret_from_intr()
ret_from_sys_call()
ret_from_exception()

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 5. Timing Measurements
차례
Introduction
Hardware Clocks
The Timer Interrupt Handler
PIT's Interupt Service Routine
The TIMER_BH Botton Half Functions
System calls related to timing measurements
Introduction
다음은 linux kernel에 의해 수행되는 timing measurement에 필요한 hardware, kernel data structure and function, systemcall에 대해 살펴본다
Linux kernel에 의해 수행되는 timing measurement의 2종류
Keeping the current time and date
Maintaining timers : kernel or user program에게 주어진 시간이 다 경과 됐음을 알리기 위한 것.
Hardware Clocks
kernel은 다음 3가지 clock과의 상호작용을 통해 timer기능을 수행한다
Real Time Clocks
Time Stamp Counter
Programmable Interval Timer
Real Time Clocks
CPU와 다른 chip에 독립적으로 존재
2Hz~8192Hz의 주기적인 interrupts 발생 (IRQ8 system clock)
linux에서는 오직 time과 date를 유지하기 위해 사용
I/O port 0x70, 0x71연결
/sbin/clock으로 RTC 설정할수 있음
Time Stamp Counter
64bit Time Stamp Counter(TSC) register
CPU CLK input pin으로 들어오는 각 입력 clock에 증가하는 counter
linux에서는 좀더 정확한 시간 측정을 위해 Programmable Interval Timer와 같이 사용
Programmable Interval Timer
timer interrupt를 발생시킴
IRQ0에 10ms 간격으로 timer interrupt을 발생(이러한 시간 간격을 tick이라 함)
짧은 tick은 빠른 system 응답을 가져오지만 user program이 느려짐(trade-off)
PIT는 init_IRQ()에서 초기화
PIT를 프로그램하기위해 HZ(IBM PC인 경우 100Hz), CLOCK_TRIC_RATE, LATCH 매크로 사용
The Timer Interrupt Handler
Timer interrupt 발생하면 다음의 주요 활동을 야기한다
updates the time elapsed since system startup
updates the time and date
현재 process의 cpu 점유시간의 결정과 할당된 cpu점유시간 초과시 회수
updates resource usage statices
software timer와 관계된 시간간격이 경과됐는지를 check
time_init()
system startup시 실행. Time Stamp Counter(TSC)의 존재 여부를 조사 각함수에 맞는 변수를 설정하고 interrupt gate를 IRQ0에 setting
PIT's Interupt Service Routine
IRQ0 초기화 - timer_interrupt()(interrupt disable, TSC register와 PIT chip 상태 저장) - do_timer_interrupt() ( do_timer()호출과 adjtimex()systemcall이 발생하면 RTC 보정)
do_timer()는 시스템의 시작직후의 기본적인 시간경과값을 가지고 가지고 있다.
do_timer()의 주요변수
jiffies : 시스템이 시작된후 부터의 경과된 tick수(32bit, 0~497days)
lost_ticks : xtime 변수의 마지막 update후 경과된 tick수
The TIMER_BH Botton Half Functions
Botton half는 interrupt handling에 관계된 low-priority function으로 다음과 같은 기능을 수행한다.
Updating the time and date : 시스템 시작시 RTC로 부터 시간을 읽어와 xtime변수에 저장하고 그 후로는 RTC를 사용하지 않고 TIMER_BH 매크로를 이용 xtime값을 사용
Updating resource usage statistics : lost_ticks 와 lost_ticks_system을 이용
CPU's time sharing : quantum(about 10ms)
linux에서는 timer의 기능이 botton half에서 수행되므로 수백ms의 지연이 발생한다고 가정되기 때문에 정확한 시간응답을 요하는 real-time application에는 적합하지 않다
linux에서는 kernel에 의해서 사용되는 static timers와 dynamic timers 그리고 user mode의 process에 의해서 생성되는 internel timers를 고려한다.
Static Timers
초기 linux version에서 사용된 32개의 timers
Table 5-1참조
Dynamic Timers
동적으로 생성 소멸, 현재 활성화된 timer의 갯수에 제한이 없다
expires values를 수 블럭의 tick으로 구분하고 expires값에 따라 정렬하여 사용
main data structure tvecs와 tv1,tv2,tv3,tv4,tv5사용 (Figure 5-1참조)
tv1는 index field 와 256개의 vec array로 구성
tv1의 모든 timer가 발생 되면 tv1의 index field값이 0이되고 tv2의 하나의 entry가 다시 tv1에 채워진다.
System calls related to timing measurements
time(), ftime(), gettimeofday() system calls
user mode에 있는 process가 현재의 시간과 날짜를 얻기 위해 사용
adjtimex() system call
Network Time Protocol(NTP)와 같은 time synchronization protocol을 실행하는 프로그램에 의해 사용. 즉 각 tick마다 약간의 시간을 변경할때 사용
setitimer(), alarm() system calls
linux에서는 user mode processe가 interval timers라는 특별한 timer를 활성화 할 수 있다. 이 timer는 process에게 주기적으로 Unix signal을 보내는데 사용되고 이 timer를 활성화 시키기 위해 사용된다.

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 6. Memory Management
차례
Introduction
Page Frame Management
Memory Area Management
Noncontiguous Memory Area Management
Introduction
Intel Pentium processor
Page frame size : 4KB and 4MB
Page frame
Paging 회로도는 자동으로 다른 page frame에 포함된 주소인지를 체크해 준다.
4KB의 크기는 많은 disk block size로 되어 있어 메인 메모리와 disk사이에 전송이 가능하다.
단점 : 4MB보다 더 많은 manage가 필요하다.
Kernel은 dynamic memory가 free인지 아닌지를 결정해야 한다.
Page Frame Management
Page frame
Struct type p-159
Table 6-1. Flags Describing the Status of a Page Frame
Figure 6-1. Memory layout
Start_mem : 동적 메모리 바로 뒤의 첫 선형 주소
End_mem : 동적 메모리의 마지막 주소+1
I386_endbase : 예약된 page frame의 초기 주소가 저장
Requesting and Releasing Page Frames
P-163 : page frame requesting
Table 6-2. Groups of Flag Values Used to Request Page Frames
The Buddy System Algorithm
외부 단편화의 메모리 관리 문제
다른 크기의 연속된 page frame이 자주 요청되고 release된다.
결과적으로 요구에 만족하는 충분한 free page가 있더라도 연속된 page frame에 큰 블록을 할당하는 것은 불가능 하다.
외부 단편화를 피하는 두 가지 방법
Paging 회로도를 사용한다.
커널에서 처리한다.
Buddy algorithm
Page Allocation
페이지 할당 코드는 하나 이상의 물리적 페이지로 구성된 하나의 블록을 할당한다.
페이지들은 2의 제곱 크기인 블록으로 할당 된다.
할당 알고리즘은 먼저 요청된 크기의 페이지 블록을 검색한다.
Free_area 자료구조의 list원소에 큐 되어 있는 프리페이지의 고리를 따라간다.
만일 요청된 크기의 프리 페이지 블럭이 없다면, 그 다음 크기(요청된 크기의 두 배)의 블럭을 찾아본다.
찾아낸 페이지 블럭이 요청한 크기보다 크다면, 그 페이지 블럭은 요청한 크기가 될 때까지 분할한다.
블럭에 들어있는 페이지의 수는 두 배씩 늘어나는 크기로 되어 있기 때문에, 분할과정은 블럭을 반으로 잘라가기만 하면 된다.
Free_area의 자료구조

Page Deallocation
페이지 블럭이 해제될 때마다, 같은 크기의 인접한 버디(buddy) 블럭이 프리인지 검사한다.
그렇다면 그 블럭과 새로 프리 블럭이 된 페이지들이 합쳐져서, 새로운 빈 블럭이 되어 다음 크기의 프리 블럭을 이룬다.
두개의 페이지 블럭이 합쳐져서 더 큰 프리 페이지 블럭이 될 때마다, 페이지 해제 코드는 이 블럭을 다시 인접한 것과 합쳐서 더 큰 것으로 만들려고 한다.
이렇게 해서 프리 페이지 블럭은 메모리가 허락하는 만큼 커질 수 있게 된다.
Memory Area Management
The Slab Allocator
Slab allocator schema
Constructor와 destructor로 인한 반복적인 초기화를 피하기 위해 slab allocator를 할당한다.
Release된 객체를 버리지 않고 메모리에 저장하여, 새로운 객체가 요청 되었을 때 다시 초기화 할 필요 없이 메모리로부터 얻을 수 있다.
빈번히 발생하는 각각의 사이즈에 대한 요구는 알맞은 사이즈의 특별한 목적 객체들의 set을 만들어 효율적으로 처리할 수 있다.
Slab allocator는 cache에서 객체화 시킨다(/proc/slabinfo)
Figure 6-3. The slab allocator components
size-13107200
size-6553600
size-3276801
size-1638401
size-819201
size-409678
size-20485164
size-10241216
size-5121524
size-2561928
size-128415504
size-6457886150
size-321931420832
slab_cache2884
slabinfo - version: 1.0
kmem_cache3042
pio_request00
tcp_tw_bucket042
tcp_bind_bucket11127
tcp_open_request063
skbuff_head_cache223
sock3444
dquot00
filp843882
signal_queue029
kiobuf00
buffer_head7002450
mm_struct4562
vm_area_struct15371638
dentry_cache128361 144336
files_cache4454
uid_cache5127
Cache descriptor
각 cache는 kmem_cache_s에 의해 기술된다.
Slab descriptor
cache의 각 slab는 kmem_slab_s에 의해 기술된다.
Slab은 객체의 크기에 의존해서 저장된다.
객체 < 512byte : slab의 끝에 저장
객체 >= 512byte : slab의 외부에 저장(큰 객체)
Figure 6-4. Relationships between cache and slab descriptors
General and Specific Caches
Cache
General : slab allocator로 사용
First cache : kernel에 의해 사용되고 남은 cache의 cache descriptor를 가지고 있다.

Second cache : slab내부에 저장되지 않은 slab descriptor를 가지고 있다.

Thirteen additional cache : 분산된 memory area를 가지고 있다. Cache_size는 주어진 크기에 일치하는 cache address를 얻어 효율적으로 이용한다.

Specific : kernel의 나머지 부분에 사용
Kmem_cache_create()에 의해 생성된다.

Allocating a Slab to a Cache
새로운 slab할당
연속된 free page frame의 group을 얻어 buddy system 알고리즘으로 행한다.
새로운 객체 할당하고 cache가 어떠한 free object를 포함하지 않을 때, kmem_cache_grow()에 의해 new slab이 할당된다.
Releasing a Slab from a Cache
slab allocator는 비어있는 slab의 page frame을 결코 release하지 않는다.
slab는 아래 두 가지 상태에서 release된다.
Buddy system이 page frame의 group을 새로 요청 하는 게 불가능 하다
Slab이 비어있다. 이것은 모든 객체가 비어있는 상태를 가진다.
Linux의 몇몇 모듈은 cache를 생성하는데, 메모리 공간의 낭비를 막기위해서 kernel은 모듈에 의해 생성된 cache내의 모든 slab을 소멸시켜야 한다.
Object Descriptor
Figure 6-5. Relationships between slab and object descriptors
Object descriptor는 두 가지 방법으로 저장된다.
External object descriptors : Slab 외부에 저장된다.
internal object descriptors : 객체 바로 뒤, slab의 안쪽에 저장된다.
Slab allocator는 객체의 크기가 512, 1024, 2048, 4096등 배수일때, External object descriptors를 선택한다.
이 경우, slab 내부에 제어구조를 저장하는 것은 내부 단편화의 high level의 결과이다.
객체의 크기가 512byte보다 작거나 512, 1024, 2048, 4096의 배수가 아니면 slab allocator는 slab내부에 객체 기술자를 저장할 것이다.
Aligning Objects in Memory
slab allocator에 의해 관리되는 객체는 메모리에 할당되는데, 초기 물리적 주소가 주어진 constant의 배수인 메모리 셀에 저장된다.
이 constant는 alignment factor라고 불리고 그 값은 cache descriptor의 c_align field에 저장된다.
C_align의 값이 0이면 alignment는 객체를 필요로 하지 않는다.
Slab allocator에 허용되는 가장 큰 alignment 인수는 4096이다.
어쨌든, 메모리의 낭비가 있으면 함수는 객체를 정렬하지 않는다.
Slab allocator가 무엇을 하든 access time과 메모리 공간은 trade off한다.
객체의 크기가 증가하면 cache의 성능은 더 좋아 진다.
하지만 추가적인 내부 단편화가 일어난다.
Slab Coloring
같은 크기의 객체는 cache의 같은 offset에 저장하려고 한다.
다른 slab의 같은 offset을 가진 객체는 같은 cache line에 매핑될 것이다.
cache line을 충분히 활용하지 못할 때, Cache 하드웨어는 같은 cache line으로부터 다른 RAM위치로 두 객체를 옮기는 메모리 cycle을 낭비한다.
Slab allocator는 slab coloring으로 cache의 낭비를 줄인다
Color라고 부르는 다른 임의의 값이 slab에 할당된다.
Color는 slab을 다시 분할하여 간단하게 사용하고 다른 선형 주소들 사이에 넓게 퍼져서 메모리를 할당하는 것을 허용한다.
이 방법은 kernel이 microprocessor의 하드웨어 캐쉬로부터 가능한 최고의 성능을 얻을 수 있다.
slab coloring
Figure 6-6은 slab내부에 있는 객체가 slab color에 어떻게 의존하는지 보여준다.
Coloring은 slab의 free area를 끝에서부터 처음으로 옮기는 작업을 한다.
Coloring은 free가 충분히 클 때 작업한다
만약 정렬이 객체를 위해 필요하거나 slab내부에서 사용하지 않은 byte의 수가 요구된 정렬보다 작다면 정렬하지 않는다(free
다양한 color는 c_colour_next라고 불리는 cache descriptor의 필드에 있는 current color를 저장한 주어진 객체 타입의 slab사이에 동등하게 분산된다.
Allocating an Object to a Cache
새로운 객체는 kmem_cache_alloc()에 의해 얻어진다.
new free 객체로부터 cache descriptor를 가리키는 parameter cachep가 얻어진다.
Kmem_cache_alloc()는 먼저 cache descriptor가 존재하는지 아닌지를 체크한다.
Releasing an Object from a Cache
kmem_cache_free()는 slab allocator에 의해 이전에 얻어진 객체를 release한다.
slab이 객체를 포함하는 객체 기술자의 주소가 결정된 후에, parameter checking에 의해 함수가 시작된다
객체기술자가 slab의 내부에 있는지 외부에 있는지를 결정하기 위해서 cache descriptor를 포함하는 cachep->c_flags flag를 사용한다.
전자는 초기 주소에 객체의 크기를 추가 시킴으로써 객체기술자의 주소를 결정한다.
후자의 경우, 객체를 포함하는 page frame descriptor의 prev필드로부터 slab descriptor의 주소를 결정한다.
General Purpose Objects
memory area로부터 자주 발생되지 않는 요구는 최소 32부터 최대 131072byte의 크기로 분산된 객체의 general cache의 그룹을 통하여 처리된다.
알맞은 size의 객체를 포함하는 cache의 cache descriptor가 위치한 cache_sizes table을 사용한다.
Cache descriptor는 memory area를 포함하는 첫번째 page frame descriptor의 next 필드를 읽는 것에 의해 식별된다.
Noncontiguous Memory Area Management
memory area의 요구가 빈번하지 않을 때
연속된 선형 주소를 통하여 접근되는 연속되지 않은 페이지 프레임을 기반으로 한 allocation schema를 고려해 볼 수 있다.
장점
외부 단편화를 피할 수 있다.
단점
kernel page table의 조작이 필요하다
인접하지 않은 memory area의 크기는 4096의 배수이어야 한다.
Linear Addresses of Noncontiguous Memory Areas
선형 address의 free range를 찾기 위해서 PAGE_OFFSET의 시작 area를 찾아야 한다.
Kernel이 사용하는 RAM map에 memory의 상위 전체 area를 kernel이 reserve한다.
예약된 area의 모든 선형 주소는 인접하지않은 memory area mapping에 쓸 수 있다.
Figure 6-7. The linear address interval starting from PAGE_OFFSET
8MB의 간격은 물리적 메모리의 끝과 첫번째 메모리 영역사이에 삽입하여 메모리 접근 범위 밖을 "capture“한다.
같은 이유로 4KB의 추가적인 간격은 연속되지 않은 메모리 영역에 분리되어 삽입된다.
Descriptors of noncontiguous Memory Areas
연속되지 않은 각 메모리 영역은 vm_struct type의 기술자와 연결된다.
처음에 Kmalloc()을 호출하여 새로운 descriptor를 위한 메모리 공간을 얻는다.
적어도 size+4096 address에 포함되는 선형주소의 유효한 범위를 찾는 vm_struct struct type의 기술자 list를 찾는다.
만약 그러한 interval이 존재한다면 함수는 descriptor field를 초기화하고 연속되지 않은 메모리영역의 초기 주소를 return해서 종료할 것이다.
그렇지 않으면 addr+size가 4GB의 한계를 초과할 때 get_vm_area()는 descriptor를 release하고 NULL을 리턴 할 것이다.
Allocating a Noncontiguous Memory Area
vmalloc()는 연속되지 않는 메모리 영역을 커널에 할당한다.
만약 함수가 요구에 만족한다면 새로운 영역의 초기 선형 주소를 리턴해 줄 것이다. 그렇지 않으면 NULL pointer를 리턴한다.
만약 메모리의 크기가 적당하다면 새로운 객체를 생성하고 메모리 영역에 할당된 선형 어드레스를 리턴한다.
vmalloc()는 get_vm_area()를 수행한다.
그러면 vmalloc()는 연속되지 않는 페이지 프레임을 요구하기 위해서 vmalloc_area_pages()를 호출하고 연속되지 않는 메모리영역의 초기 선형 주소를 리턴하고 종료한다.
Releasing a Noncontiguous Memory Area
vfree()는 연속되지 않는 메모리 영역을 release한다.
Descriptor의 size field는 released된 영역의 size를 나타낸다.
Descriptor는 kfree()에 의해 released되고 영역 그 자체는 vmfree_area_pages()의 호출에 의해 released된다.
Vmfree_area_pages()는 두개의 파라미터(초기 선형 주소와 영역의 크기)를 가진다.
연속되지 않는 메모리 영역의 각 페이지 프레임은 buddy system free_page()에 의해서 released된다.
Page table에 있는 알맞은 entry는 pte_clear 매크로에 의해 0으로 셋팅된다.

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 7. Process Address Space
차례
Introduction
The Process’s Address Space
The Memory Regions
Page Fault Exception Handler
Creating and Deleting a Process Address Space
Managing the Heap
Introduction
커널에서 메모리 할당
커널함수가 동적 메모리에 대한 요청을 수행한다면 요청에 대한 적절한 근거를 가지고 있어야한다.
커널 스스로 신뢰적인 기능을 가지고 있다.
모든 커널 함수는 에러에 대하여 자유스러우며 프로그램에러에 대한 보호를 해줄 필요가 없다.
유저모드 프로세스에서 메모리 할당은 이와는 다르다.
유저 모드에서 프로세스 실행 파일이 로딩될 때 프로세스는 모든 코드 페이지를 바로 어드레싱하지 않을 것이다. 커널은 유저 모드 프로세스가 동적 메모리에 할당하도록 처리할 것이다.
유저 프로그램은 신뢰할 수 없으므로 커널은 유저모드 프로세스의 에러를 모두 잡아내야만 한다.
커널이 새로운 리소스를 이용하여 프로세스에 동적 메모리 할당을 하도록 요인 파악
유저 모드 프로세서가 동적 메모리를 요청할 때 페이지 프레임을 추가하는게 아니라 새로운 주소 범위 사용 권한을 얻음. 메모리 영역이라 불림
**프로세소 주소 공간 섹션에서는 프로세스가 어떻게 동적 메모리를 참조하는지에 대해 알아보고, 메모리 영역 섹션에서는 프로세스 주소의 기존 구성요소에 대해 알아본다.
다음에는 프로세스에서 페이지 프레임의 할당할 때 페이지 오류 exception handler에 의해 진행되는 내용을 검토해 보고 커널이 어떻게 프로세스 주소 공간을 생성하고 지우는지에 대해 알아본다. 마지막으로 메모리 공간을 관리하는 API 및 시스템 콜에 대해서 알아보도록 한다.
The Process’s Address Space
프로세스의 메모리 공간에서는 프로세스가 사용하는 모든 주소가 선형으로 구성되어있다. 각 프로세스는 선형 주소의 셋을 참조하고 한 프로세스에서 사용되는 주소는 다른쪽 주소와 관련이 없게 되어있다.
뒤에 나오겠지만 커널은 선형 주소의 간격을 조절함으로써 프로세스 주소 공간을 동적으로 수정한다.
커널은 초기 선형 주소, 길이 및 액세스 권한으로 구성된 메모리 영역이라는 리소스에 의해 선형 주소의 간격을 나타낸다. 효율성을 위해 초기 주소와 메모리 영역의 길이는 지정되고 데이터는 각 메모리 영역을 페이지 영역으로 채워감으로써 인식하게 된다.
프로세스가 새로운 영역을 확보하는 상황들에 대해 알아본다.
사용자가 콘솔에서 명령어를 수행한다면 쉘 프로세스는 명령 수행을 위해 프로세스를 생성한다. 결과적으로 메모리 영역 확보를 위해 새로운 주소 공간이 새로운 프로세스에 할당된다.
실행 중인 프로세스는 다른 프로세스 로딩 결정한다. 이 경우에는 프로세스 ID는 빈 상태로 남게되나 메모리 영역은 프로그램이 로딩된 후에 사용하며 새로운 메모리 영역이 프로세스에 할당된다.
실행중인 프로세스는 파일에 메모리 매핑으로 수행된다. 이 경우에는 커널은 파일 매핑을 위해 새로운 메모리 영역을 프로세스에 할당한다.
프로세스는 스택을 매핑하는 메모리 영역에서 모든 메모리 주소가 사용될 때 까지 유저 모드 스택에 데이터를 저장한다.
프로세스는 관련된 다른 프로세스의 데이터를 공유하기 위해 IPC 공유 메모리 영역을 생성한다. 이 경우에는 커널은 이러한 구조를 이행하기 위해 프로세스에 새로운 메모리 영역을 할당한다.
프로세스는 malloc() 함수를 통해 동적 영역(heap)을 확장한다. 그 결과 커널은 heap에 할당된 메모리 영역 사이즈를 확장한다.
Page Fault Exception Handler는 커널이 프로세스에 의해 현재의 메모리 영역을 식별하는데 필수적인 요소이다. 두가지 형태 비교를 효과적으로 하기위해 쓰임.
프로그래램 에러의 의한 발생

페이지 누락에 의한 발생; 프로세스의 주소 공간에 속해있는 선형 주소일 지라도 페이지 프레임은 할당된 주소와 일치되는 경우

The Memory Descriptor
프로세스 주소 공간에 관계되있는 모든 정보는 프로세스 디스크립터의 mm 필드를 참조하여 테이블에 포함되어 있다.
Memory Regions
리눅스에서는 type vm_area_struct의 디스크립터로서 메모리 영역을 구성한다.
프로세스에 의한 메모리 영역은 절대 오버랩 되지 않으며 새로운 프로세스가 바로 할당되려고 할 때 커널은 영역을 합치려고 한다.
두개의 근접 영역은 접근 권한이 일치한다면 합쳐질수 있다.
(p.199-200)
그림7-1에서는 새로운 선형 주소의 영역이 프로세스 주소 공간에 추가될 때 커널은 이미 존재하는 메모리 영역이 확장될수 있는지 점검한다.(case a)
공간이 없으면 새로운 메모리 영역이 생성된다.(case b)
이와 유사하게 선형 주소의 영역이 프로세스 주소 공간에 의해 제거되면 커널은 관련된 메모리 영역을 재조정 한다.(case c)
어떤 경우에는 재조정이 메모리 영역이 두가지의 작은 형태로 분리될 때도 있다.(case d)
Memory Region Data Structure
프로세스가 소유한 모든 영역은 간단한 리스트에 서로 링크되어 있다. 영역은 메모리 주소 순으로 순차적으로 리스트되어 있으나 각 두 영역은 사용되지 않는 메모리 주소에 의해 분리될 수도 있다.
그림 7-2 프로세스, 메모리 디스크립터 및 메모리 영역 리스트의 주소 공간 사이의 관계를 나타낸 것이다.
커널에 의해 수행되는 빈번한 동작은 특정 주소를 포함하는 메모리 영역을 검색한다. 리스트가 정렬되어 있기 때문에 검색은 특정 주소가 발견되고 난후 메모리 영역에서 가능한 빨리 끝날 수 있게 된다.
그러나 프로세스가 작은 메모리 영역을 차지할 때만 이런 리스트 방식이 편리하고 커지면 비효율적으로 된다.
** 대부분 리눅스 프로세스는 매우 작은 메모리 영역을 사용하지만 수백 또는 수천 영역을 사용하는 데이터 베이스와 같은 몇몇 큰 애플리케이션이 있을 수 있다.
이런 경우에는 메모리 영역 리스트 관리는 비효율적으로 되고 메모리 관련 시스템 콜 수행이 intolerable point로 떨어지게 된다.
프로세스가 많은 수의 메모리 영역을 가지는 경우에 리눅스는 AVL 트리라는 데이터 구조에 각 디스크립터를 저장하는 방식을 취하고 있다.
AVL 트리에서 각 노드는 두개의 자식을 가지고 있다. (왼쪽 자식과 오른쪽 자식)
AVL 트리의 노드들은 정렬되어 있으며 노드 N에서는 서브트리의 모든 노드가 N 앞선 N 왼쪽 자식에서 이어지나 서브트리의 모든 노드가 N 따라 N 오른쪽 자식에서 이어진다.
그림7-3(a)
AVL 트리의 모든 노드 N은 노드의 가지들이 얼만큼 잘 구성되어 있는가를 나타낸 밸런스 요인(balancing factor)를 가지고 있다. 밸런스 요인은 N의 왼쪽 자식의 depth와 오른쪽 자식의 depth의 차이다. 밸런스된 AVL 트리의 각 노드는 –1, 0, +1의 밸런스 요인을 가지고 있어야 한다.
AVL 트리에서 노드 검색은 매우 효율적이며 메모리 영역의 수의 배는 단지 작업을 한번더 반복한다는 것…..
노드 삽입, 제거에도 효율적..
이러한 과정에서 AVL 트리에 언밸런스를 가져올 수 있다.
예) 그림 7-3(a)에서 처럼 값11이 삽입되어야 한다면 적절한 위치는 값 12인 왼쪽 자식 위치로 되나 삽입이 일어나면 값 13 키는 –2의 밸런싱 요소를 가지게 된다. AVL 트리를 재조정하기 위해 값13의 키를 가진 노드에서 생성된 서브트리에서 rotation이라는 알고리즘을 수행한다. 결과 새로운 AVL 트리가 생성(그림 7-3(b)).
프로세스의 메모리 영역을 저장하기 위해 일반적으로 리눅스는 메모리 디스크립터의 mmap 필드를 참조하여 링크된 리스트를 사용한다.
Memory Region Access Rights
Read/Wtire, Present, User/Supervisor 와 같은 각 페이지 테이블 엔트리에 저장된 플래그
각 페이지 디스크립터의 플래그 필드에 저장된 플래그 셋
첫번째는 인텔 80x86 하드웨어에 의해 사용됨, 두번째는 리눅스에 의해 사용
인텔 80x86 프로세서의 페이지 테이블은 Read/.Write와 User/Supervisor 플래그 두개의 보호 비트를 가지고 있다. 페이지가 항상 유저모드 프로세스에 의해 액세스될 수 있도록 하여야 하기 때문에 메모리 영역이 포함된 페이지의 User/Supervisor 플래그는 항상 set이 되어야 한다.
이러한 인텔 마이크로 프로세서의 하드웨어 한계를 극복하기 위해 리눅스는 다음의 규칙을 사용한다.
읽기 권한은 항상 실행 액세스 권한을 내포한다.
쓰기 권한은 항상 읽기 권한을 내포한다.
Memory Region Handling
Finding the closest region to a given address
메모리 디스크립터는 mmap_cache 필드 포함, 주어진 주소 영역을 찾는 시간을 줄임
Finding a region that overlaps a given address interval
주어진 주소 간격을 오버랩한 첫번째 메모리 영역을 찾는다.
Finding a free address interval
Inserting a region in the memory descriptor list
AVL 트리를 사용하는가, 아닌가에 따라 구분
Merging contigous regions
같은 액세스 권한을 가진 연속적인 영역인 경우
Allocating a Linear Address Interval
새 주소 간격이 어떻게 할당되는가에 대해 알아본다.
이를 위해 do_mmap() 함수는 현재 프로세스의 새로운 메모리 영역을 생성하고 초기화한다.
do_mmap() 함수는 파라미터 값이 올바른지 여부와 요청 내용이 만족될 수 있는지에 대한 점검을 시작
다음은 주소 간격이 가지고 있는 구성을 점검
새로운 영역을 할당하고 메모리 영역 디스크립터를 초기화 시킴
에러 상황을 점검하여 모든 정보를 메모리 디스크립터에 저장
마지막으로 메모리 영역의 모든 페이지 할당이 되었으면 RAM에 lock시킨다.
Releasing a Linear Address Interval
do_munmap() 함수는 현재 프로세스의 주소 공간에서의 주소 간격을 삭제한다.
삭제된 간격은 메모리 영역과는 일치되지 않고 한 메모리 영역에 포함되거나 두개 이상의 영역에 걸쳐있을 수 있다.
두가지 단계
첫번째는 주소 간격을 프로세스가 가진 메모리 영역 리스트를 복사하고 오버랩한 모든 영역 제거한다.
두번째는 함수는 프로세스 페이지 테이블을 업데이트하고 첫번째 부분에서 제거된 메모리 영역의 축약된 내용을 다시 삽입하게 된다.
First phase : Scanning the memory regions
Second phase : updating the page tables
Page Fault Exception Handler
리눅스의 페이지 오류 exception 핸들러는 프로그램 에러에 의해 발생된 exception과 할당되지 못한 프로세스 주소 공간에 속한 참조 페이지를 반드시 구별해야 한다.
메모리 영역 디스크립터는 exception 핸들러가 효과적으로 일을 수행하도록 한다.
페이지 오류 인터럽트 서비스 루틴은 현재 프로세스의 메모리 영역에 대한 페이지 오류 발생한 주소를 비교하며 exception을 적절히 다룰 수 있도록 한다.(그림7-4)
실제로 페이지 오류 핸들러가 몇가지 특별한 서브 케이스를 인식해야 하므로 복잡해질 경우가 있다. (그림7-5 )
do_page_fault() 함수
페이지 오류로 인한 주소를 읽어들이고 exception이 일어나면 CPU 제어 유닛은 제어 레지스터에 값을 저장한다.
Exception이 발생했는지 커널 쓰레드가 발생했는지를 점검한다.(그림7-5 위)
두 가지 경우를 서로 비교할 필요는 없다. Interrupt 핸들러와 커널 쓰레드는 PAGE_OFFSET 하부의 주소를 사용하지 않으므로….
어떠한 메모리 영역을 포함하지않는 주소를 결정한다. 그러나 유저 모드 스택에 쌓이는 push에 의해 잘못된 주소가 생길 수 있으므로 추가적인 점검이 수행된다.
Handling a Faulty Address Outside the Address Space
주소가 프로세스 주소 공간에 존재하지 않는다면 do_page_fault() 함수는 bad_area 코드를 실행하게 된다.
커널 모드에서 exception이 발생되면 다음의 두가지 경우가 있다.
커널에게 시스템 콜의 파라미터로 넘겨주는 주소가 사용되는 동안 발생되는 exception
실제 커널 버그로 인해 발생되는 exception
Handling a Faulty Address Inside the Address Space
주소가 프로세스 주소 공간에 존재한다면 do_page_fault() 함수는 good_area 코드를 실행한다.
Exception이 쓰기 액세스에 의해 발생되면 함수는 메모리 영역이 쓰기 가능한가를 점검한다. 그렇지 않다면 bad_area 코드로 점프한다.
읽기, 실행 액세스에 의해 발생되면 함수는 페이지가 RAM에 존재하는지를 점검한다.
이 경우에 발생되는 exception은 유저 모드에서 프로세스가 특수한 페이지 프레임에 접근하려고 할 때 생긴다.
Demand Paging
Demend paging이란 페이지 프레임 할당 구성이 가능한 마지막 순간까지 혹은 프로세스가 RAM에 존재하지 않는 페이지 주소를 접근할 때 까지의 페이지 오류 exception를 포함하여 구성된 동적 메모리 할당하는 것을 나타낸다.
프로세스가 주소 공간 권한이 있는 모든 주소를 어드레싱 안하는 경우
요구 페이징은 전체 할당으로 처리하는게 낫다. 시스템에서 프리 페이지 프레임의 평균 수를 증가 시키거나 사용 가능한 프리 메모리 사용을 원할히 하기 위해…..
Copy On Write
초기 유닉스에서는 프로세스 메모리 사용에 있어 메모리 복사를 계속하여 CPU의 부하를 늘렸다.
Copy On Write는 페이지 프레임을 복사하는 것 대신에 부모, 자식 프로세스 사이에서 공유시키는 것.
공유되는 한 수정될 수 없고 부모, 자식 프로세스가 공유 페이지 프레임에 쓰기를 시도할 때마다 exception이 발생하여 커널에서 쓰기 가능한 새로운 페이지 프레임을 복사한다. 원본 페이지 프레임은 쓰기방지가 되어있게 된다.
Creating and Deleting a Process Address Space
Creating a Process Address Space
새로운 프로세스를 생성할 때 커널에서는 copy_mm() 함수를 발생시킨다.
이 함수는 모든 페이지 테이블과 새 프로세스의 메모리 디스크립터를 구성함으로써 프로세스 주소 공간 생성을 다룬다.
각 프로세스는 자신의 주소 공간을 다루나 lightweight 프로세스는 __clone() 함수에 의해 생성될 수 있으며 같은 주소 공간을 공유한다.
전통적인 프로세스는 부모의 주소 공간에서 존재하며 읽기만 할 때 공유되어 남게된다.
프로세스가 쓰기를 시도한다면 페이지가 복사되며 fork된 프로세스는 부모 프로세스와 다른 주소 공간을 가지게 된다.
Lightweight 프로세스는 부모 프로세스의 주고 공간을 사용한다. 리눅스에서는 주소 공간 복사를 하지 않으며 lightweight 프로세스는 일반 프로세스보다 빨리 생성될 수 있으며 페이지 공유는 부모와 자식들이 액세스하는데 잇점이 있다. à COW
Deleting a Process Address Space
프로세스가 소멸되면 커널은 프로세스가 소유한 주소 공간을 해제시키기 위해 exit_mm() 함수를 발생시킨다.
Managing the Heap
각 프로세스는 heap이라고 불리는 특수한 메모리 영역을 가지고 있으며 이는 프로세스의 동적 메모리 요청을 만족하기 위해 사용된다.
동적 메모리 요청 및 해제에 사용되는 함수들이 존재..
malloc(size) : 동적 메모리 요청
calloc(n,size) : 배열 형태로 요청
free(addr) : 메모리 영역 해제
brk(addr) : heap 크기를 직접 수정
Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 8. System Calls
차례
Introduction
POSIX APIs and System Calls
System Call Handler and Service Routines
Wrapper Routines
Introduction
System Call : user mode process에게 제공되는 Hardware와 관련된 일련의 interface.
Application과 Hardware사이에 extra layer를 사용하는 장점
Make programming easier
Increase system security
Make programs more portable
Figure 1. A set of interfaces to interact with hardware
POSIX APIs and System Calls
APIs와 System call의 차이
API(application programmer interface)
주어진 서비스를 획득하는 방법을 규정한 함수의 정의(library)
System call
Software interrupt를 통한 kernel에 대한 서비스 요청(kernel)
Wrapper routine : system call을 일으키는 routine
일부 API만 wrapper routine을 통해 system call을 호출
POSIX standard는 system call이 아니라 API를 정의
System Call Handler and Service Routines
int 0x80 - user mode -> kernel mode - system call function 수행
System call number : user mode process에서 넘겨준 parameter(service routine을 구분하기 위해)
일반적인 system call return code
Positive or null values : success
Negative values : fail. error condition code(include/asm-i386/errno.h 정의)
System call handler 동작
Kernel mode stack에 대부분의 registers를 저장
System call service routine 실행
ret_from_sys_call()에 의해 복귀
System call dispatch table : system call number n의 service routine의 주소를 가지는 table entry(일반적으로 256개)
Initializing System Calls
Kernel 초기화시 IDT entry의 ector 128에 setup( trap_init() )
set_system_gate(0x80, &system_call);
The system_call() Function
System call handler 수행
System call number 유효 여부 확인(NR_syscalls)
PF_TRACESYS flag 확인(debugger에 의한 trace여부
Service routine 실행( sys_call_table() )
ret_from_sys_call()에 의해 복귀
Parameter Passing
최소 하나의 parameter는 필요(system call number)
Register에 의한 parameters passing의 제한 (32bit , 6개까지(system call number 포함)
eax, ebx, ecx, edx, esi, edi register 사용
위의 제한은 하나의 register에 parameter value값을 가지고 있는 memory address 지정함으로써 해결
Verifying the Parameters
System call과 특정 parameter에 따라 다름
Parameter에 정의된 address가 process address space 안에 존재하는 지를 검사(모든 system call에 공통
Linux 2.2에서는 단지 linear address가 PAGE_OFFSET보다 작은지만을 검사(very coarse check)
Linux 2.2 에서는 Paging Unit에서 linear를 physical address로 변환할때 까지 검사하지 않고 지연.
verify_area(), access_ok macro제공
Accessing the Process Address Space
System service routine에서 process address space data의 read/write
get_user(),put_user()
Dynamic Address Checking: The Fixup Code
verify_area()함수와 access_ok macro는 매우 허접하기 때문에 잘못된 address를 전달 받으므로써 Page Fault exception을 일으킬수 있다. 이렇한 error를 검사하는 방법에 대해 알아본다.
우선 Kernel Mode에서 Page Fault exception이 일어날수 있는 3가지 상황에 대해 알아보면
Page frame이 없을때 또는 read-only page를 write하려 할 때
Handler는 새로운 page frame을 할당 초기화
Programming bug 또는 hardware error
Handler는 kernel oops수행
System call parameter에 의해 전달된 address가 process address space에 속해 있지 않을 때(여기서 알아볼 내용)
Error code를 return하고 system call을 끝낸다
위 세가지 경우는 모두 다른 수행이 돼어야 하기 때문에 page fault handler에 의해 반드시 구분되어야 한다.
The exception table
Process address space에 접근 할수 있는 모든 kernel instruction의 address를 exception table에 저장
Exception이 발생하면 do_page_fault()는 exception table을 검색
Linux에는 여러개의 exception table이 존재
C compiler에 의해 자동으로 생성
Kernel의 dynamic loaded module에도 exception table이 존재
exception_table_entry는 insn(instruction의 linear address)과 fixup(assembly code의 address)으로 구성
fixup code는 service routine이 User Mode process에게 error code를 return할수 있게 함
Generating the exception tables and the fixup code
다음과 같은 Gnu assembler로 생성할수 있다.
.section __ex_table, "a"

.long faulty_instruction_address, fixup_code_address

.previous

Wrapper Routines
System call은 주로 User Mode process에 의해 사용
Kernel thread에서도 사용할수 있는 wrapper routine에 상응하는 macro 제공
_syscall0 ~ _syscall5(0 ~ 5 까지 system call에서 사용되는 parameter 수)
이 macro는 2+2n개의 parameters 필요(n:system call의 parameter 수)
Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 9. Signals
차례
The Role of Signals
Sending a Signal
Receiving a Signal
Real-Time Signals
System Calls Related to Signal Handling
The Role of Signals
Signal
Signal은 초기에 UNIX 시스템에서 간단하게 프로세스간 통신을 위해 사용되었다.
커널 또한 시스템 이벤트를 프로세스에게 알리기 위해서 signal을 사용한다.
간단하고 효율적이어서 꾸준히 넓게 사용되어, 지난 30년동안 signal의 내용은 거의 바뀌지 않았다.
signal은 프로세스나 프로세스그룹에 보내는 짧은 메시지이며, 프로세스에 주어진 정보는 대개 signal의 식별 번호이다.
SIG로 시작하는 이름의 macro의 집합은 signal을 식별하는데 사용한다.
Signal의 두 가지 목적
특정 이벤트가 발생한 것을 프로세스가 알게 한다.
코드에 포함된 signal handler function을 프로세스가 실행하게 한다.
Table 9-1. The First 31 Signals in Linux/i386
시스템 콜의 number 는프로그래머가 signal 을 보낼 수 있게 하고 프로세스가 signal 을 어떻게 받아서 이용하는지를 결정한다.
Table 9-2. System Calls Related to Signals
pending signal
각 signal은 보낸 뒤 한번 혹은 받지 않을 수 있다.
한번 받으면, 이전에 참조한 모든 프로세스 기술자 정보는 취소된다.
Signal을 보냈지만 받지 못했을 때 pending signal이라고 부른다.
주어진 타입의 pending signal은 단 하나만이 프로세스에 존재한다.
하나의 프로세스에 같은 타입의 추가적인 pending signal은 대기하는 게 아니라 버려진다.
일반적으로 signal은 예측할 수 없는 많은 시간동안 pending된다.
고려사항
Signal 은 일반적으로 현재의 running 프로세스에 의해 received 된다.
Signal 은 프로세스에의해 blocked 된다.
이 경우 프로세스는 block 이 제거될 때 까지 다른 signal 을 receive 하지않을 것이다.
프로세스가 signal-handler 기능을 수행할때
handler 가종료될 때까지 자동으로 signal 이 block 된다.
Signal handler 는 다른 signal 핸들의 발생으로 인해 인터럽트 될 수 없다.
커널 구현
Signal의 개념이 직관적이라 하더라도 커널 구현은 보다 복잡하다
커널은 Signal이 각 프로세스에 의해 blocked된 것을 기억해야 한다
커널 모드에서 사용자 모드로 바뀌었을 때, 어떤 프로세스의 signal이 도착했는지 안했는지 체크한다.
이것은 모든 timer interrupt에서 대략 10ms간격으로 일어난다.
Signal이 무시될 수 있는지 없는지 결정한다.
함수가 return 된 이후에 커널이 수행되고 원래의 execution context를 저장하는 시점에서 프로세스의 switching을 요구하는 Signal을 처리한다.
Actions Performed upon Receiving a Signal
프로세스가 signal 에응답하는 3 가지방법
명시적으로 signal 을무시한다.
Signal 과관련된 default action 을수행한다.
Abort, Dump, Ignore, Stop, Continue

일치하는 signal-handler 가발생했을때 signal 을 catch 한다.
Signal 을 blocking 하는것과그것을 ignoring 하는것과는다르다.
Signal 이 blocked 됐을때는결코 received 하지않는다.
Ignored signal 은언제나 received하지만더이상의 action 은하지않는다.
Sending a Signal
The send_sig_info() and send_sig() Functions
만약 sig 파라미터가 0이 되면 어떠한 signal도 보내지 않고 즉시 리턴 된다.
0은 유효한 signal 번호가 아니다.
만약 목적 프로세스가 TASK_ZOMBIE상태이면 리턴한다.
The force_sig_info() and force_sig() Functions
force_sig_info() 은목적지프로세스에의해명시적으로 ignored 나 blocked될수없을때 signal 을보내기위해서커널에서사용한다.
force_sig() 는 force_sig_info() 와비슷한데커널에의해 signal 을보내는것을제한할때사용한다. force_sig_info() 의특별케이스로구현된다.
Receiving a Signal
커널에 signal이 도착하면
User Mode 에서프로세스를다시실행시키기위해커널은 nonblocked pending signal 인지아닌지를체크한다.
Nonblocked pending signal 을처리하기위해,커널은 do_signal() 을실행시킨다.
내용에따라
ignoring the signal, executing a default action, executing a signal handler 수행
Receiving a Signal
Ignoring the Signal
signal 이도착했을때명시적으로 ignored 된다.
Do_signal() 은보통은 loop 의새로운수행으로계속된다.
따라서다른 pending signal 을고려한다.
Executing the Default Action for the Signal
만약 ka->sa.sa_handler 가 SIG_DFL 이면 do_signal() 은 signal 의 default action 을수행한다.
Receiving process 가 init 이될때 exception 이발생한다.
Default action 이 "ignore“
signal 은쉽게핸들링된다.
Default action 이 "stop“
signal 은현재의프로세스를멈출것이다.
do_signal() 은현재의상태를 TASK_STOPPED 로바꿀것이고 schedule() 을발생시킬것이다.
Default action이 "dump“
프로세스가 현재 작업 중인 디렉토리에서 core파일을 생성할 것이다.
이 파일은 프로세스의 주소공간과 CPU레지스터의 완전한 내용을 list한다.
Do_signal()은 core file을 생성한 후에 프로세스를 죽인다.
Do_exit()에서 core dump가 수행되었을 때
입력 파라미터로써 플래그의 OR된 signal 번호를 받는다.
그 값은 프로세스의 exit 코드를 결정하는데 사용된다.
이 함수는 현재 프로세스를 종료 시키고, 따라서 리턴되지 않는다.
Catching the Signal
signal이 특정 핸들러를 받으면 do_signal()은 그것의 수행을 요구한다. 이것은 handle_signal()에 의해 일어난다.
Do_signal()은 single signal을 처리한 후 리턴한다.
이때 다른 pending signal은 do_signal()의 다음 발생까지 고려되지 않는다.
리눅스는 현재 프로세스의 User Mode stack 위의 Kernel Mode stack에 저장된 hardware context를 복사하는 것으로 변경된다.
Signal handler가 종료될 때, sigreturn() system call은 Kernel Mode stack에 자동으로 hardware context를 복사하고, User Mode stack의 원래의 content를 저장한다.
Figure 9-1. Catching a signal
Nonblocked signal은 프로세스에게 보내어진다.
커널은 do_signal()을 수행하며, handle_signal()로 signal의 핸들을 바꾸고 setup_frame()의 호출로 User Mode stack을 설정한다.
handler의 시작 주소가 프로그램 카운터이기 때문에, 프로세스가 다시 User Mode로 바뀔 때, signal handler를 수행하기 시작한다.
함수가 종료될 때, setup_frame()의 User Mode stack에 놓여진 리턴 코드가 수행된다.
이 코드는 Kernel Modes stack에 normal 프로그램의 hardware context를 복사하는 서비스 루틴인 sigreturn() system call을 호출한다.
System call이 종료되었을 때, normal program은 그 수행을 다시 시작한다.
Setting up the frame
User Mode stack 의 data strucure 를 frame 라고부른다.
Frame 은 signal handle 에필요한정보를가진다.
프로세서의 User Mode stack 을적절히맞추기위해서 handle_signal() 은 setup_frame()혹은 setup_rt_frame() 을실행한다.
Frame 은다음을포함하는 sigframe table 이다.
Pretcode : signal핸들러의리턴주소, retcode 를가리킨다.
Sig : signal number, signal핸들러에의해파라미터가요구된다.
Sc :커널모드( 현재의 Kernel Mode stack 로부터복사된정보) 로바뀌기직전, User Mode process 의 hardware context 를포함하는 sigcontext 타입의구조체
Fpstate : User Mode process 의 floating point register 에저장될때사용하는 _fpstate struct타입
Exrtamasg : blocked real-time signal 을명세하는 bit array
Retcode : sigreturn() 시스템콜에의해생기는 8byte 코드,이코드는 signal handler 로부터리턴될때수행된다.
Evaluating the signal flags
User Mode stack 를설정한후에 handle_signal() 은 signal 에관련된플래그값을체크한다.
Starting the signal handler
do_signal() 이리턴될때,현재의프로세스는 User Mode 에서실행이다시시작된다.
Terminating the signal handler
signal handler 가 종료될때리턴은프래임의 retcode 필드의코드에스택포인터상위의주소로한다.
Reexecution of System Calls
몇가지 경우에 system call은 커널이 즉시 처리할 수 없다.
이때, system call 서비스 루틴은 job을 완료하지 않고 EINTR, ERESTARTNOHAND, ERESTARTSYS, 혹은 ERESTARTNOINTR 에러코드를 리턴한다.
프로세스는 User Mode로 다시 바뀔 때 signal을 받는다.
이 상황에서 User Mode process가 얻을 수 있는 유일한 error code는 System call이 완료되지 않은 것을 의미하는 EINTR이다.
에러코드가 남는 것은 system call이 signal handler가 종료된 후에 자동으로 재실행 될지 아닌지에 대해 명시하기 위해 커널이 내부적으로 사용한다.
Table 9-4는 unfinish된 system call에 관련된 error code의 list이고, 3개의 signal action에 영향을 준다.
Terminate : system call은 자동으로 재실행하지 않을 것이다. 프로세스는 0x80을 따르는 명령에서 User Mode의 실행을 재개할 것이고, eax register는 -EINTR값을 가질것이다.
Reexecute : 커널은 User Mode process가 0x80명령을 다시 실행하기 위해서 system call number를 가지고 eax register를 reload하게 한다. 프로세스는 재실행을 알아채지 못하고 error code는 통과되지 않는다.
Depends : system call은 받은 signal의 SA_RESTART flag가 set될 때에만 재실행된다. 그렇지 않으면 system call은 -EINTR error code로 종료된다.
Real-Time Signals
POSIX는 signal number range가 32에서 63까지인 real-time signals을 나타내는 signal의 새로운 부분이다.
표준 signal과의 주된 차이점은 같은 종류의 real-time signal이 queue되는 것이다.
이것은 보내는 여러 개의 signal을 받을 수 있다는 것을 말한다.
Linux kernel이 real-time signal을 사용하지 않는다 하더라도, 몇가지 특정 system call의 POSIX 표준은 모두 제공한다.
signal을 보낼 때
send_sig_info()는 number가 31보다 큰지 아닌지를 체크한다.
만약 그렇다면 목적프로세스의 real-time signal의 queue로부터 signal을 삽입한다.
signal을 받을 때
dequeue_signal()은 pending signal이 31보다 큰 signal 넘버인지를 체크한다.
만약 그렇다면 받은 signal의 적당한 요소를 queue에서 추출한다.
만약 queue가 같은 타입의 다른 signal을 가지고 있지 않다면 current->signal에 bit를 clear한다.
System Calls Related to Signal Handling
The Kill() System Call
Kill(kid,sig) system call은 일반적으로 signal을 보낼 때 사용한다.
유사한 서비스 루틴은 sys_kill()이다.
Pid 파라미터는 몇가지 의미가 있고 그 값에 의존한다.
Pid>0 : sig signal은 PID가 pid인 프로세스에게 보낸다.
Pid=0 : sig signal은 호출한 프로세스의 같은 그룹에 있는 모든 프로세스에게 보낸다.
Pid=-1 : signal은 모든 프로세스에게 보낸다. Swapper(PID 0), init(PID 1),와 current만 제외하고
Pid<-1 : signal은 프로세스 그룹이 -pid인 모든 프로세스에게 보낸다.
Changing a Signal Action
sigaction(sig, act, oact) system call 은사용자에게특정 signal 의 action 을허용한다.
signal action 이정의되지않았다면,커널은받은 signal 에관련된 default action 을수행할것이다.
유사한 sys_sigaction()서비스루틴은두개의파라미터로활동한다.
Signal number 와새로운 action 을명시한 sigaction type 의 act table
세번째 oact 는 signal 에관련된이전의 action 을얻기위해사용하는옵션파라미터이다
Examining the Pending Blocked Signals
sigpending() system call
프로세스가 pending blocked signal 을조사하는것을허용한다.
이것은 blocked됐을때일어난다.
System call 은단지표준 signal 을가지고온다.
유사한 sys_sigpending()
sys_sigpending()서비스루틴은 single parameter, set, namely, bit 열에복사된사용자변수의주소에작동한다.
Modifying the set of Blocked Signals
sigprocmask() system call은 프로세스가 blocked signal의 집합을 변경하는 것을 허락한다.
Sigpending() 처럼, 이 시스템 콜은 표준 signal에게 적용한다.
유사한 sys_sigprocmask() 서비스 루틴은 3개의 파라미터로 동작한다.
Oset : 이전의 bit mask가 저장된 bit 열에 프로세스 주소 공간을 가리킨다.
Set : 새로운 bit mask를 포함하는 bit열에 프로세스 주소 공간을 가리킨다.
How : flag는 SIG_BLOCK, SIG_UNBLOCK, SIG_SETMASK 값들 중 하나가 된다
Suspending the Process
mask파라미터가가리키는 bit mask 열에의해명시된표준 signal 을 blocked한후에 sigsuspend() system call 은 TASK_INTERRUPTIBLE 상태의 process 가된다.
Schedule() 는실행되는다른프로세스를선택한다.
Sigsuspend() system call프로세스가다시수행될때,
sys_sigsuspend() 는프로세스를깨웠던 signal 을받기위해서 do_signal() system call 을발생시킨다.
만약함수가 1 의값을리턴하면, signal 은 ignored 되지않는다.
따라서 system call 은 -EINTR에러코드를리턴하며종료된다.
System Call for Real-Time Signals
real-time signal(rt_sigaction(), rt_sigpending(), rt_sigprocmask(), rt_sigsuspend())을 위한 몇몇 system call은 먼저 기술된 것과 유사하다.
두개의 다른 system call은 real-time signal의 queue에서 다루어 진다.
Rt_sigqueueinfo()
목적 프로세스의 real-time signal queue에 추가하기 위해서 real-time signal을 보낸다.
Rt_sigtimedwait()
rt_sigsuspend()와 비슷하지만 프로세스는 fixed time interval동안 단지 suspend로 남는다.
Interrupt & Exception
Interrupt
Interrupt가 발생하면 시스템은 커널 모드로 전환한 후 커널에 있는 인터럽트 핸들러를 실행한다.
그리고 핸들러 실행을 마치면 다시 이전의 작업으로 복귀한다.
이전 작업은 커널 모드에 있을 수도 사용자 모드에 있을 수도 있다.
Exception
Exception 역시 interrupt와 마찬가지로 동작한다.
Interrupt와 exception의 차이는 발생하는 원인이 다르다.
Interrupt는 주변장치에서 exception은 CPU 내부에서 발생한다.
System call & Signal
System call
System call은 리눅스에서 exception의 일종으로 처리한다.
System call은 항상 사용자 모드에서 부른다.
시스템 콜을 부르면 0x80 exception이 발생하고 커널 모드로 전환한 후 exception handler가 불리고 이것이 개별 system call 처리함수를 부른다.
Signal
Signal은 이들하고 관계가 없다.
Signal이 발생하면 커널은 scheduling을 할 때 개별 signal handler를 불러준다.
scheduling 코드는 커널 모드에 있는 코드이므로, 먼저 사용자 모드로 전환을 한 후 프로세스의 signal handler를 부르고 다시 커널 모드로 복귀를 한다.
Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 10. Process Scheduling
차례
Introduction
Scheduling Policy
The Scheduling Algorithm
System Calls Related to Scheduling
Introduction
시간 공유 시스템에서 리눅스는 하나의 프로세스에서 다른 쪽으로 짧은 시간에 변환하여 여러 개의 프로세스가 동시에 실행되어지는 것처럼 보이게 한다.
세가지로 구성
스케줄링 정책
스케줄링 알고리즘
스케줄링에 관계된 시스템 콜
Scheduling Policy
스케줄링 알고리즘의 몇가지 목적
빠른 프로세스 반응 시간, 백그라운드 수행에 대한 효과적 처리, 프로세스 기아상태 방지, 높고 낮은 우선순의 프로세스의 조화 등
이러한 프로세스에 대한 선택 및 방법을 결정하는 것이 sheduling policy
리눅스 스케줄링은 time-sharing 기법에 기초
스케줄링 정책은 우선순위에 따르는 프로세스들의 순으로 구성
프로세스의 현재 우선순위를 위해 복잡한 알고리즘이 사용되며 각 프로세스는 얼마나 적절하게 CPU에 지정되어 있는 가에 관계되어 있다.
리눅스에서는 프로세서 우선순위가 동적이며 스케줄러는 프로세스가 무엇을 하고 있는지 추적하고 주기적으로 조정한다. 오랜 시간동안 CPU 사용을 못한 프로세스는 동적으로 우선순위가 증가하게 되며 오랫동안 실행되었던 프로세스는 우선순위가 내려가게 된다.
스케줄링을 말할 때 프로세스는 I/O-bound와 CPU-bound로 구분되며 전자는 I/O 디바이스를 주로 사용하거나 I/O 동작에 많은 시간을 사용하는 경우이며 후자는 CPU 시간에 많은 시간이 소요되는 애플리케이션이 속한다.
Interactive processes
사용자에 의해 즉각적으로 반응하는 경우이며 쉘, 텍스트 에디터, 그래픽 프로그램등이 속한다.
Batch processes
사용자와 작용이 없는 경우이며 주로 백그라운드로 실행된다. 컴파일러, DB검색엔진 등이 속한다.
Real-time processes
엄격한 스케줄링이 요구되며 우선순위가 낮은 프로세스에 의해 block되지 않는다.
로봇 컨르롤러, 센서 데이터 수집 프로그램 등이 속한다.
리눅스에서 real-time 프로그램이 스케줄 알고리즘으로 정확히 인식한다면 interactive 및 batch 프로그램을 구별할 필요가 없게 된다. 응답 시간을 제공하기 위하여 리눅스는 CPU-bound 프로세스 보다 I/O-bound 프로세스를 더 선호한다.
리눅스는 비선점형 커널을 가지고 있기 때문에 대부분의 real-time 응용 프로그램에서 요구하는 사항들을 지원하지 않는다.
Process Preemption
리눅스 프로세스는 preemptive
예로 텍스트 편집 및 컴파일러의 두가지 프로그램을 생각해 본다.
에디터 프로그램은 컴파일러보다 동적인 우선순위를 가지고 있으나 종종 suspend되기도 한다. 이는 사용자는 시간 및 자료 입력에 있어 여러가지 동적인 상황에 있게 되기 때문이다.
그러나 사용자가 키를 누르자 마자 인터럽트가 발생되고 커널은 에디터 프로세스를 wakeup 시키고 현재 프로세스보다 동적으로 에디터 프로그램의 동적 우선순위를 결정하게 된다.
결과적으로 에디터의 실행은 빠르게 복원되고 사용자가 입력한 문자들은 화면에 나타난다. 문자들이 나타날 때 에디터는 다른 키 입력을 기타리기 위해 자신을 suspend 시키며 컴파일러 프로세스는 실행 복원을 할 수 있게 된다.
실시간 운영체제는 preemtive 커널이다. 이는 커널모드에서 실행되고 있는 프로세스는 어떤 명령후에 인터럽트될 수 있고 유저모드에서 가능하다. 리눅스 커널은 선점형 커널이 아니다. 이는 프로세스는 유저모드에서 실행될때만 선점이 가능하다.
How Long Must a Quantum Last?
Quantum duration은 시스템 성능에 중요한 요소 중의 하나이다.
너무 짧으면 태스크 스위치에 의한 시스템 오버헤드가 발생되고 너무 길게되면 동시에 생성 가능한 프로세스 발생이 어렵게 된다.
예로 두명의 유저가 동시에 쉘 상에서 같은 명령어를 실행한다고 가정한다면 한 명령어는 CPU-bound이고 다른 쪽은 interactive 애플리케이션이 된다. 두가지 쉘은 새로운 프로세스를 생성하고 사용자 명령어를 실행한다. 이런 프로세스는 같은 우선순위를 갖게 된다. 스케줄러가 실행을 위해 CPU-bound 프로세스를 택한다면 다른 프로세스는 실행되기 이전에기다리고 있을 것이다. 따라서 이 기다리는 시단이 길어지면 시스템은 반응이 상당히 느리게 보일 것이다.
The Scheduling Algorithm
리눅스 스케줄링 알고리즘은 CPU 시간을 epoch로 나눔으로써 이루어 진다. 하나의 epoch에서 모든 프로세스는 epoch가 시작될 때 계산되는 특정 시간 quantum을 가지고 있다.
일반적으로 서로 다른 프로세스는 다른 quantum duration을 가지고 있다. 프로세스가 시간quantum이 다 없어졌을 때 선점되고 다른 프로세스에 의래 교체된다. 물론 프로세스는 quantum이 없어지지 않는한 같은 epoch에서 스케줄러에 의해 몇번씩 선택된다. 실행되고 있는 모든 프로세스들이 자신의 quantum이 없어질 때 epoch가 종료된다.
각 프로세스는 기본 시간 quantum을 가지고 있으며 이는 이전 epoch에서 quantum이 없어져스케줄러에 의해 프로세스에게 할당된 값이다. 사용자는 시스템콜을 이용하여 이 값들의 변경이 가능하다.
정적 우선순위 : 주로 사용자에 지정되며 real-time 프로세스가 속함. 1에서99 범위
동적 우선순위 : 일반적인 프로세스이며 기본 시간 quantum의 합이며 CPU 시간의 tick 수가 필수적인 요소
Data Stucture Used by the Scheduler
need_resched : 스케줄 함수를 발생하기 위한 플래그
policy : 스케줄링 클래스
SCHED_FIFO
SCHED_RR
SCHED_OTHER
rt_priority : 실시간 프로세스의 정적 우선순위 일반 프로세스는 생성 안함
priority : 프로세스의 기본 시간 quantum
counter : quantum이 없어지기까지 프로세스에 남은 CPU 시간의 tick 수
The schedule() Function
Direct invocation
스케줄러가 현재의 프로세스를 즉시 block하는 경우
적절한 대기 큐에서 current를 insert

current 상태를 변경

schedule() 실행

리소스가 가용한지 점검하고 그렇지 않다면 2단계로 이동

리소스가 가용하다면 대기 큐에서 current를 제거

Lazy invocation
스케줄러는 need_resched의 current 필드를 1로 셋팅해서 lazy way로 처리
current가 CPU 시간의 quantum을 사용할 때 update_process_times() 함수에 의해 수행
프로세스가 wakeup되고 우선순위가 현재의 프로세스 보다 높아지게 되며 이 task는 reschedule_idle() 함수에 의해 수행된다.
sched_setsechduler() 또는 sched_yield() 시스템 콜이 다루어진다.
Actions performed by schedule()
먼저 current 값은 prev 로컬 변수에 저장되고 prev 의 need_resched 필드 값을 0으로 세팅한다. schedule()는 prev 상태를 점검하고 블록되지 않은 펜딩 시그널을 가지고 있고 인터럽트 가능한 상태이면 함수는 프로세스를 wake up 시킨다. 여기서는 prev에 프로세서를 할당한것과 동일한 것은 아니고 단지 prev에 실행을 위한 선택의 기회가 주어진 것이다.
prev가 실행 상태가 아니면 schedule()은 외부 리소스를 기다려야 하기 때문에 프로세스 자신에 의해 직접 생성된다. 따라서 prev는 반드시 실행 큐 목록에서 삭제되어야 한다.
다음은 schedule()은 다음 시간 quantum으로 실행되기 위해 프로세스를 선택해야 한다. 함수는 실행 큐 목록을 점검하고 init_task의 next_run 필드에 의해 참조된 프로세스로부터 시작한다. 우선순위가 높은 프로세스의 프로세스 디스트립터 포인터를 next 프로세스에 저장한다.
이제 schedule()은 가장 좋은 것들을 결정하기 위해 실행 프로세스에서 goodness() 함수를 반복해서 실행한다.
프로세스는 선택되어지고 프로세스 스위치가 일어난다.
How Good Is a Runnable Process?
스케줄링 알고리즘의 핵심은 실행 큐 목록에 있는 모즌 프로세스들 사이에서 가장 좋은 것을 인식하는 것이다. goodness() 함수가 이를 수행하며 입력 파라미터인 prev와 p로 받는다. goodness()에 의한 리턴 값인 c값은 p의 goodness를 측정한다.
c = -1000
p는 선택되어서는 안되며 이 값은 실행 큐 목록이 단지 init_task를 가지고 있을 때 리턴된다.
c = 0
p의 quantum이 없어진 경우
0 < c < 1000
p는 quantum이 존재하는 일반적 프로세스
c >= 1000
p가 real-time 프로세스이며
The Linux/SMP Scheduler
리눅스 스케줄러는 SMP 구조에서를 지원하기 위해 약간 변형된다. 실제로 각 프로세서는 각자 schedule() 함수를 실행하나 프로세서는 시스템 성능 향상을 위해 서로 정보를 교환해야 한다.
CPU 1에서 몇 초간 프로세스를 실행되고 있고 CPU 2에서 마지막으로 실행되고 있는 높은 우선순위의 프로세스가 실행될려고 한다. 이제 커널은 CPU 1에 있는 놓은 우선순위에 프로세스를 즉시 실행해야 하는가 아니면 CPU 2의 프로세스 실행이 가능한지를 참조해야 하는가에 대한 딜레마에 직면하게 된다.
시스템 성능을 향상시키기 위하여 Linux/SMP는 경험적 규칙을 적용하였다. 선택 방법은 항상 타협적이며 교환은 대부분 각 CPU 안에 있는 하드웨어 캐쉬의 크기에 의해 결정되며 하드웨어 캐쉬가 큰 CPU가 프로세스를 유지하는데 유리하도록 되어있다.
Linux/SMP scheduler data structure
aligned_data 테이블은 각 프로세서를 위한 하나의 데이터 구조를 가지고 있르며 현재 프로세스의 디스크립터를 얻기 위해 사용된다. 각 요소들은 schedule() 함수에 의해 구성되어 있다.
몇몇의 SMP 관련 필드는 프로세스 디스크립터 안에 포함되어 있으며 특히 프로세스의 평균 quantum duration에 대한 추적 기능을 가진 것도 있다.
The schedule() function
SMP 시스템에서 schedule() 함수가 실행될 때 다음의 과정으로 이루어 진다.
1. schedule()의 초기 부분 수행
2. this_cpu 로컬 변수에 실행 프로세서의 논리적 식별자를 저장한다.
3. sched_data 로컬 변수를 초기화 한다.
4. 실행되어질 새로운 프로세스를 선택하기 위해 반복적으로 goodness()을 실행한다.
5. 필요하면 동적 우서순위를 위해 프로세스를 재생성한다.
6. sched_data -> curr 에서 next를 설정한다.
7. next-> has_cpu를 1로, next->processor를 this_cpu로 설정한다.
8. t 로컬 변수에 현재의 Time Stamp Counter를 저장한다.
9. this_slice 로컬 변수에 prev의 마지막 시간 분할 duration을 저장한다.
10. sched_data->last_schedule를 t로 설정한다.
11. prev의 avg_slice 필드를 (prev->avg_slice+this_slice)/2로 설정한다.
12. context switch를 수행한다.
13. 이전 프로세스로 복귀한다.
14. prev의 has_cpu 필드를 0으로 설정한다.
The reschedule_idle() function
reschedule_idle() 함수는 프로세스 p가 실행 가능하도록 될 때 일어난다. SMP 시스템에서는 프로세스가 CPU의 현재 프로세스에 선점가능한지 아닌지 결정한다.
1. p가 real-time 프로세스이면 항상 preemption 수행을 시도하며 3단계로 간다.
2. 현재 프로세스가 어떤 조건을 만족하도록 되어 있는 CPU가 있으면 즉시 복귀한다.
3. p->processor CPU가 idle이면 그것을 선택한다.
4. goodnedd(tsk,p) – goodness(tsk,tsk)의 과정으로 CPU를 선택한다.
5. CPU가 선택되면 need_resched 필드를 설정하고 해당 프로세서에 reschedule 메시지를 보낸다.
Performance of the Scheduling Algorithm
The algorithm does not scale well
존재하는 프로세스 수가 아주 많으면 한번에 모든 동적 우선순위를 계산한다는 것은 비효율적이다. 리눅스는 동적 우선순위 재계산을 매번하는 것이 아니라 시간에 대한 quantum이 없어질때만 수행되면 오버헤드를 크게 줄일 수 있다.
The predefined quantum is too large for high system loads
사용자에 의한 시스템 반응은 system load에 크게 영향을 주게되며 이는 실행, CPU 시간을 기다리고 있는 프로세스의 평균 수치이다. 리눅스에서는 미리 정의된 시간 quantum은 아주 높은 시스템 로딩을 가지기 위해 크게 나타나게 된다.
I/O-bound process boosting strategy is not optional
I/O-bound 프로세스는 interactive 프로그램을 위하여 짧은 반응 시간을 보증하는 좋은 방법이나 완벽한 방법은 아니다. 예로서 하드 디스크나 네트워크 응용 프로그램으로부너 많은 양의 데이터를 읽어들이는 데이터베이스를 생각해 보면 이는 원격 호스트로부터 느린 상태로 데이터를 수집하게 된다. 이러한 프로세스가 짧은 반응 시간이 필요 없더라도 스케줄링 알고리즘에 의해 발생된다.
Support for real-time applications is weak
비선점형 커널은 real-time application에 적합하지 않으며 이는 프로세스가 인터럽트나 exception을 다루는 커널 모드에서 약간의 시간을 보내기 때문이다. 이 시간 동안 실행 가능하게된 real-time 프로세스는 복귀되지 못한다.
System Calls Related to Scheduling
The nice() System Call
nice() 시스템 콜은 기본 우선순위를 변경하도록 프로세스에 허용하며sys_nice() 서비스 루틴은 nice() 시스템 콜을 다룬다.
The getpriority() and setpriority() System Calls
nice() 시스템 콜은 단지 프로세스가 기능을 가지도록 영향을 주는 것이나 getpriority(), setpriority() 는 주어진 그룹에서 모든 프로세스의 기본 우선순위에 적용된다.
System Calls Related to Real-Time Process
The sched_getscheduler() and sched_setscheduler() system calls
sched_getscheduler() 시스템 콜은 pid 파라미터에 의해 확인된 프로세스가 적용된 현재의 스케줄링 정책을 다룬다.
sched_setscheduler() 시스템 콜은 pid 파라미터에 의해 확인된 프로세스에 대한 관련 파라미터 및 스케줄링 정책을 동시에 다룬다.
The sched_getparam() and sched_setparam() system calls
sched_getparam() 시스템 콜은 pid에 의해 확인된 프로세스에 대한 스케줄링 파라미터를 가져온다.
sched_setparam() 시스템 콜은 sched_setscheduler()와 비슷하나 policy 필드 값에 대해서만 약간의 다른 점을 가지고 있다.
The sched_yield() system call
sched_yield() 시스템 콜은 suspend 되지 않고 자발적으로 CPU 사용을 내주는 프로세스를 다룬다.
The sched_get_priority_min() and sched_get_priority_max() system calls
위의 시스템 콜들은 각각 policy 파라미터에의해 확인된 스케줄링 정책이 사용되는 real-time 정적 우선순위 값의 최대, 최소치를 리턴한다.
The sched_rr_get_interval() system call
sched_rr_get_interval() 시스템 콜은 real-time 프로세스에 대한 round robin time quantum을 얻는 기능을 가지고 있다.
Linux 2.4에서 스케줄링 알고리즘은 SMP에 대한 기능 향상이 중점
Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 11. Kernel Synchronization
차례
Introduction
Kernel Control Paths
Synchronization Techniques
The SMP Architecture
The Linux/SMP Kernel
Introduction
Kernel은 실행 중인 process나 외부 interrupt 요청에 응답을 해야하고 이러한 처리는 순차 처리가 아닌 삽입(interleaved)방식으로 이루어진다. 이러한 과정에서 race conditon이 발생할 수 있으므로 합당한 synchronization 기법을 통해 제어 되어야 한다.
여기서는 이러한 synchronization technices에 대해 알아보고 SMP architecture의 hardware 기능과 리눅스에서 사용하는 technics에 대해서 알아본다.
Kernel Control Paths
Kernel Control Paths : kernel 요청(interrupts or exceptions)을 처리하기 위해 Kernel Mode에서 실행되는 명령들 [ ex) systemcall() ~ ret_from_sys_call() ]
Kernel function은 다음 2가지 경우의 요청에 의해 실행된다.
User Mode에서 실행돼는 process가 exception을 일으킬 때.
외부 device에 의해 interrupt 될 때.
일반적으로 kernel control paths는 순차적으로 처리되지만 다음의 경우 CPU는 kernel control path를 삽입한다.
context switch 발생 할 때 ( schedule() 실행 될 때 )
CPU가 interrupt enable돼 있는 상태에서 kernel control paths를 실행중 일 때 interrupt이 발생 할 때.
Kernel control paths 삽입 할 때는 영향을 받는 모든 data stucture는 하나의 critical section에 보관되어 져야 한다.
Synchronization Techniques
다음 4가지의 synchonization technices 구분지어 race conditions을 피하면서 kernel control paths를 삽입하는 방법에 대해 알아본다.
Nonpreemptability of processes in Kernel Mode
Atomic operations
Interrupt disabling
Locking
Nonpreemptability of Processes in Kernel Mode
Linux kernel은 nonpreemptive(즉, Kernel mode에서 실행되는 process는 다른 process에 의해 preempt돼지 못함) 특별히 linux에서는 다음의 단정들이 항상 유효
Kernel Mode에서 실행되는 process가 없으면 다른 process에 의해 교체될수 있다.(단,이전의 process가 임의로 끝났을 때를 제외)
Interrupt or exception handling은 Kernel Mode에서 실행중인 process를 중단시킬 수 있다. (그러나, handling이 종료된 후 process의 kernel control paths는 제기된다.)
Interrupt or exception handling을 수행하는 kernel control paths는 다른 interrupt or exception handling을 수행하는 control path에 의해 중단될수 있다.
Nonblocking system calls을 수행하는 kernel control paths는 다른 system call에 의해 시작되는 control path를 위해 atomic이다. 이것은 많은 kernel function의 수행을 단순하게 한다.
Atomic Operations
race condition을 방지하기위한 가장 쉬운 방법은 chip level에서 이 동작을 "atomic"하게 함으로서 얻을수 있다.
atomic operation : 하나의 assemble language instruction으로 수행하는 것
make zero or one memory access
Read/modify/write assembly language (ex:inc,dec)
Read/modify/write assembly language의 opcode에 lock byte(0xf0)가 붙어 있는 것(multiprocess system에서 사용)
opcode에 rep byte(0xf2,0xf3)가 붙어 있는 instruction은 atomic이 아니다.
linux kernel에서 제공하는 atomic assenble language instruction을 수행하는 함수
Ref: Table 11-1. atomic operation in C
Interrupt Disabling
critical section이 너무 커 atomic operation으로 정의할수 없을 때 사용.
cli,sti assemble language instruction을 사용 interrupt on/off
interrupt disabling 방법에 의해 사용되는 critical section은 매우 짧다.
좀 더 긴 critical region은 locking 방법에 의해 수행
Locking Through Kernel Semaphores
리눅스에서 제공하는 2종류의 locking
kernel semaphores : uniprocessor systems과 multiprocessor system 사용.
spin lock : multiprocessor system에서 사용.
struct semaphore 정의
count : 0보다 크면 resource free, 0보다 같거나 작으면 resouce busy(이것의 절대값은 resource를 기다리는 control paths 갯수)
wait : resouce를 기다리며 잠들어 있는 모든 process를 포함하는 wait queue의 주소.
waking : resource가 freed될때 하나의 process만 획득할수 있게 하는 변수
down(), up()에 의해 수행
Linix에서 semaphore사용
Slab cache list semaphore
Memory descriptor semaphore
Inode semaphore
Avoiding Deadlocks on Semaphores
linux는 semaphore 요청에서 deadlock에 약간의 문제를 가지고 있음
하지만 2개의 semaphore locks을 가지고 있는 경우 주어진 address순으로 처리 함으로써 deadlock을 방지할수 있다.
The SMP Architecture
SMP kernel을 이해하기 위해 간단히 Pentium dual-processing systems의 기능에 대해 살펴보자.
Common Memory
모든 메모리는 같은 메모리를 공유한다.
Bus와 각 RAM chip 사이에 Memory abiter를 사용
Hardware Support to Cache Synchronization
각 CPU가 가지고 있는 local hardware cache를 동기화시킨다.(cache snooping)
Ref)Figure 11-1. The caches in a dual processor
SMP Atomic Operations
lock prefix가 붙은 instruction을 사용
Distributied Interrupt Handling
8259A PIC를 대체하는 I/O APIC(I/O Advanced Programmable Interrupt Controller)제공
Ref)Figure 11-2. APIC system
The Linux/SMP Kernel
semaphore와 spin locks방법 사용
Main SMP Data Structures
process descriptor는 current macro통해 얻음 (uniprocessor system과 같음)
NR_CPUS : CPU 갯수
process descriptor는 process와 processor의 관계를 나타내기 위해 다음 추가적인 fields를 가진다.
has_cpu : 현재 process가 실행중인지 아닌지.
processor : process를 실행하고 있는 CPU의 logical number
시스템 초기화시 각 CPU에 대응하는 swapper processes생성
Spin Locks
multiprocessing 환경을 위한 locking기법
다른 process에 의해 닫혀진 lock을 발견하면 그 주위를 반복해서 spin. 그 외 semaphore와 동일
각 process가 자신의 CPU에 속해 있고 resource를 기다리면서 spin하는 게 좀 더 효율적임 (overhead가 작다)
spin locks function은 atomic read/modify/write operations
spin_lock / spin_unlock macro [Ref)Table 11-3]
Read/Write Spin Locks
concurrency를 증가시키기 위해 사용
concurrenct read를 허용함으로써 시스템 성능을 향상시킴
Ref)Figure 11-4 ,Table 11-4
Linux/SMP Interrupt Handling
I/O APIC에 의해 각 CPU의 Local APIC로 전달
발생한 interrupt는 오직 하나의 CPU에서만 처리해야한다.(IRQ_INPROGRESS flagi check)
Linux/SMP Bottom Half Handling
Interrupt handler와 같지만 다른 buttom halves와 병행수행 하지 못한다.
BH실행중 interrupt disabling 할수 없음
Global and Local Kernel Locks
Global kernel lock(kernel_flag)은 여러가지의 kernel data structure를 보호하는데 사용
Virtual file system과 file handling에 관계된 모든 data structure
Networking과 관련된 대부분의 kernel data structure
IPC(interprocess communication에 대한 모든 kernel data structure
그다지 중요하지 않은 몇가지의 kernel data structure
file에 관계된 모든 system call service routine은 global kernel lock 획득이 필요(많은 system call이 Linux/SMP에서 병행실행되지 못함)
lock_kernel() / unlock_kernel()
작은 locks 사용(Ref:Table 11-5) system performance 향상
Interprocessor Interrupts(IPI)
SMP architecture의 일 부분
CPU사이의 메세지를 교환하기 위해 사용

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 12. The Virtual Filesystem
차례
The Role of the VFS
VFS Data Structures
Filesystem Mounting
Pathname Lookup
Implementations of VFS System Calls
File Locking
The Role of the VFS
가상파일시스템(VFS) : kernel software layer
표준 유닉스 파일 시스템과 관련된 모든 시스템 콜을 처리한다.
application program layer à Kernel software layer à specific file system layer
장점
서로 다른 종류의 파일시스템에 일반적인 인터페이스를 제공한다.
Figure 12-1. VFS role in a simple file copy operation
VFS는 추상계층이다.
Cp는 파일시스템 타입을 알 필요가 없다.
VFS는 일반적인 시스템 콜로 수행된다.
VFS에 의해 지원되는 3가지 부류
Disk-based filesystems
하드디스크, 플로피, 씨디롬 같은 블록디바이스에 저장된다.
리눅스는 /dev/loop0와 같은 virtual block devices도 핸들 할 수도 있다.
Network filesystems
다른 네트웍의 컴퓨터에 속한 파일 시스템에 쉽게 접근할 수 있다.
지원되는 filesystem으로는 NFS, Coda, AFS, SMB, NCP가 있다.
Special filesystems
/proc filesystem은 사용자가 커널 데이터 구조의 내용에 접근할 수 있는 간단한 interface를 제공한다.
/dev/pts filesystem은 Open Group’s Unix98표준에 기술된 pseudo-terminal을 지원하는데 사용한다.
The common File Model
리눅스의 /디렉토리는 Ext2이며 다른 파일 시스템은 root filesystem에 mount되어 있다.
VFS는 모든 파일시스템을 지원하는 common file model이다.
Specific filesystem은 물리적인 구조를 VFS의 일반적인 파일 모델로 변환시켜 구현 한다.
몇몇 non-Unix disk-based filesystem은 디렉토리 트리에 각 파일이 있는 File Allocation Table(FAT)를 사용한다.
이 디렉토리들은 파일이 아닌데, 리눅스에서는 FAT-based filesystem을 필요할 때 디렉토리와 유사한 파일을 즉석으로 구현한다.
이러한 파일은 커널 메모리에 객체로 존재한다.
The common File Model
VFS 이용한 copy
read() à sys_read()àMS-DOSàfileàf_opàread(…)
write()…
File은 Object-oriented(data structure+method)?
효율성 문제로 객체지향을 쓰지 않음
객체의 methods와 비슷한 function을 가리키는 Data structure로써 객체를 구현
객체타입을 구성하는 파일 모델
The superblock object
The inode object
The file object
The dentry object
The common File Model
Figure 12-2 Interaction between processes and VFS objects
3 개의다른프로세스가같은 파일을열었을때
3 개의프로세스는각각자신의파일객체로사용
Dentry object à같은 inode객체참조(hard link)
Dentry cache à속도향상
System Calls Handled by the VFS
Table 12-1. Some System Calls Handled by the VFS
Lower-level procedure 를실행하지않고 VFS 만으로 file operation 을수행할수있다.
VFS Data Structures
Superblock Objects
Table 12-2. The Fields of the Superblock Object
Superblock는 Mount된 Filesystem당 하나이다.
Circular doubly linked list로 구성
List_head
Figure 12-3. The superblock list

U field
Specific filesystem에 속하는 superblock 정보를 포함한다.

디스크에 접근하지 않고 메모리에서 superblock의 u union field를 직접 조작할 수 있다.

문제점

Corrupted filesystem - 시스템에 전원이 나갈 때
Super_operations table
Inode Objects
Table 12-3. The Fields of the Inode Object
파일시스템에필요한모든정보는 inode 에의해서처리된다.
Inode 는유일하며파일이존재하는만큼오래남는다.
Circular doubly linked list 로구성
“in use” 혹은 “dirty” list 에속하는 Inode객체는 hash table 에포함된다.
Hash table 는커널이 inode number 와 superblock 의주소를알때 inode객체를검색하는속도가향상된다.
Inode_operations table
File Objects
Table 12-4. The Fields of the File Object
각 file객체는다음의 Circular doubly linked list 중하나를포함한다.
“unused”파일객체의리스트
파일객체를위한메모리캐쉬와 superuser 를위한예약에작용하는 list,

superuser 가시스템에있는동적메모리를모두썼다하더라도파일을오픈하도록해준다.

“in use”파일객체리스트
리스트의 각 element 는프로세스에의해적어도한번은사용된다.

File_operation tabIe
Special Handling for Directory File Objects
각 프로세스가 자신의 내용을 동시에 변경하려 할 때 문제 발생
일반적인 파일에서 자주 수행하는 명시적 locking은 locked된 디렉토리의 subtree 전체에 다른 프로세스들의 접근을 막기때문에 디렉토리에서는 적당하지 않다.

따라서 파일 객체의 f_version은 각 디렉토리 파일을 일관성 있게 관리하기 위하여 inode객체의 i_version과 함께 사용한다.

Readdir() system call
이것이 발생하면 디렉토리 entry가 리턴되고 다음에 발생할 같은 시스템콜이 다음 디렉토리 entry를 리턴하므로 디렉토리 파일 포인터가 업데이트 된다.
그러나 동시에 접근하려는 다른 프로세스에 의해 디렉토리는 수정된다.
일관성있는 체크를 할 수 없으므로 readdir() system call은 잘못된 디렉토리 entry 를 리턴한다.
Special Handling for Directory File Objects
Readdir()를 적당하게 수정
이 문제를 해결하기 위해서 version stamp역할을 하는 global_event를 이용한다.

디렉토리 파일의 inode객체가 변경될때마다, global_event는 1이 증가하고, 새로운 version stamp는 객체의 i_version field에 저장된다.

파일 객체가 생성되거나 파일 포인터가 변경될 때마다 global_event는 1이 증가하고, new version stamp는 객체의 f_version field에 저장된다.

Readdir() system call이 수행될때, VFS는 i_version과 f_version field에 포함된 version stamp가 일치하는지를 체크한다.

만약 그렇지 않다면 디렉토리는 readdir()의 수행이전의 명령을 수행한 후에 다른 프로세스에 의해 변경되었을 수 있다.

Special Handling for Directory File Objects
Readdir() 의지속적인문제발생
전체디렉토리를다시읽음으로써디렉토리의파일포인터를재계산한다.
System call 은프로세스의마지막 readdir() 에의해리턴된 entry 의다음값으로즉시디렉토리 entry 를리턴한다.
F_version 은 readdir() 이실제디렉토리상태로동기화된것을가리키기위해 I_version 으로설정한다.
Dentry Objects
디렉토리 entry 를메모리에서읽으면, VFS 에의해서 dentry structure 의 dentry객체가바뀐다.
프로세스가찾은경로의각각의 component 로구성된 Dentry객체는커널에의해생성된다.
Dentry객체는 inode 와유사하다
/tmp/test pathname 을찾을때
커널은 / 디렉토리를위해 dentry객체를생성한다.
두번째 / 디렉토리의 tmp entry 를위한 dentry객체를생성한다.
세번째 /tmp디렉토리의 test entry 를위한 dentry객체를생성한다.
Dentry객체는디스크의이미지와는다르다.
따라서 dentry 구조에는변경된객체를나타내는 field 가없다.
Dentry객체는 dentry_cache 라고불리는 slab allocator cache 에저장된다.
따라서 dentry객체는 kmem_cache_alloc() 와 kmem_cache_free() 에의해생성과소멸된다.
Table 12-5. The Fields of the Dentry Object
Dentry object 의 4 가지상태
Free, Unused, Inuse, Negative. P-346
Dentry Cache
Dentry object 의사용이끝났다할지라도나중에또필요( 반복적인접근) 하게되므로캐쉬에저장된다.
Dentry Cache 의효율을위한데이터구조 2 가지
In-use, unused, negative state 에대한 dentry 객체의집합
Unused : double linked list – LRU

In use : double linked list – hard links 도포함됨

Negative :마지막 hard link 가지워지면 unused 의 LRU 로옮겨짐

Hash table
파일이름과디렉토리가주어지면연관된 dentry 객체를빨리찾아줌

Dentry_operations table
Filesystem Mounting
파일시스템을 사용하기 전에 수행하는 2가지 작업
Registration
system boot혹은 파일시스템 모듈이 구현될 때 load된다.
파일 시스템이 register되면, 여러 종류의 파일 시스템이 시스템디렉토리 트리에 마운트 될 수 있다.
Mounting
각 파일 시스템은 자신의 root directory를 가진다.
시스템 디렉토리 트리의 root를 root filesystem이라고 한다.
다른 파일 시스템은 시스템 디렉토리 트리에 마운드 될 수 있다.
시스템이 boot할때
root filesystem의 major number를 찾는다.
커널 컴파일이나 boot strap loader가 초기화 될 때 /dev에 명시된다.
Mounting a Generic Filesystem
Root filesystem 이초기화되면추가적으로파일시스템이마운트된다.
각각은시스템디렉토리트리에자신의 mount point 를가진다.
Table 12-9. Filesystem Mounting Options
Mounting a Generic Filesystem
Sys_mount()
프로세스가 filesystem을 마운트 할 수 있는지 체크한다.
get_fs_type()에 의해 적당한 file_system_type의 포인터를 얻는다.
만약 파일시스템이 /dev/hda1과 같은 하드웨어 디바이스를 마운트하려고 하면 device가 존재하는지를 체크한다.
만약 파일시스템이 하드웨어 디바이스를 참조하지 않고 마운트 되면 get_unnamed_dev()의 발생에 의해 major number가 0인 진짜가 아닌 블록 디바이스를 얻는다.
Do_mount()…필요한 파일시스템을 마운트 하기위해 실행
Dir_name과 유사한 Dir_d dentry object가 위치한 Namei()가 발생된다.(a)

연속된 마운트와 언마운트를 위한 Mount_sem 세마포어가 실행된다.

Dir_dàd_inode가 디렉토리의 inode인지 체크하고, 이미 마운트 된 디렉토리는 파일시스템의 루트가 아닌지 체크한다.

새로운 파일시스템의 Superblock object sb를 얻기 위해 Read_super()가 발생한다. Superblock object의 S_root 필드는 마운트된 파일시스템의 루트 디렉토리의 dentry object를 가리킨다.(b)

다른 프로세스가 superblock를 사용하지 않는지, 프로세스가 이미 같은 파일시스템에 마운트 되지 않았는지 체크한다.

마운트 파일시스템의 list에 새로운 element를 삽입하기 위해 Add_vfsmnt()가 발생한다.

Root 디렉토리에 파일시스템을 마운트하기 위해, Superblock의 s_root field에 Dir_d의 D_mounts field를 설정한다.

Dir_d에 마운트된 파일시스템의 root디렉토리의 dentry 객체의 D_covers field를 설정한다.(c)

Mount_sem 세마포어를 release한다.

Unmounting a Filesystem
Sys_umount()…filename과 flag 집합의 파라미터로 구성
프로세스가 filesystem을 언마운트 할 수 있는지 체크한다

Dentry 객체에 연관된 dentry pointer를 얻기위해 filename에 Namei()가 발생한다.

만약 filename이 mount point를 참조하면, dentryàd_inodeài_sbàs_dev에서부터 장치 식별자를 얻는다.

그렇지 않고, filename이 device file을 참조하면, dentryàd_inodeài_rdev에서부터 장치 식별자를 얻는다.

Dentry object를 release하기 위해 dput()을 발생한다.

장치의 버퍼를 flush한다.

Mount_sem 세마포어를 요구한다.

Sys_umount()
Do_umount()
마운트 된 파일시스템 Superblock의 sb pointer를 얻기 위해 Get_super()를 발생된다.

dev 장치를 참조한 Dentry object를 제거하기 위하여 Shrink_dcache_sb()를 발생된다.

dev장치를 참조한 모든 “dirty” 버퍼를 Disk에 쓰기 위한 Fsync_dev()를 발생된다.

만약 dev가 root device이면 unmount 할 수 없다.

언마운트 된 파일시스템의 root 디렉토리와 일치하는 Dentry object의 counter가 1보다 큰지 아닌지 체크한다.

Sbàs_rootàd_covers의 카운터를 감소시킨다.

Sbàs_rootàd_coversàd_mounts를 sbàs_rootàd_covers로 설정한다. 파일시스템의 root디렉토리 inode를 가리키는 inode link를 제거한다.

Sbàs_root point와 sbàs_root를 NULL로 설정하기 위해, Dentry object를 Release한다.

만약 superblock가 변경되었고 write_super superblock의 method가 정의 된다면 superblock의 put_super() method를 수행한다.

Sbàs_dev를 0으로 설정한다.

마운트된 파일시스템의 list로부터 적당항 엘리먼트를 제거시키는 remove_vfsmnt()가 발생한다.

Dev장치에 참조하기 위해 모든 “dirty” buffer에 남아 있는 디스크에 쓰기 위해, F_fsync_dev()가 발생한다.
Mount_sem세마포어를 Release한다.
Pathname Lookup
프로세스는 open(), mkdir(), rename(), stat()와 같은 VFS시스템 콜을 수행하려면 파일을 확인해야 한다.
만약 pathname이 절대경로인 /이면, currentàfsàroot로부터 디렉토리를 찾기 시작한다.
상대경로이면 currentàfsàpwd로부터 디렉토리를 찾기 시작한다.
초기 디렉토리의 inode를 가지고 있으면 code는 일치하는 inode의 첫번째 이름과 맞는지 entry를 조사한다.
디렉토리 파일은 inode를 disk로 부터 읽고, 일치하는 inode를 조사하여 두번째 이름과 일치하는 entry를 가진다.
이 절차는 path에 포함된 각각의 이름에 대하여 반복된다.
Dentry cache는 최근에 사용한 dentry object 메모리에 보관되어 있기 때문에 수행 속도가 향상된다.
Implementations of VFS System Calls
The open() System Call
Sys_open()
Open할 Pathname : Filename
접근 flag : flags
퍼미션 bit mask : mode
성공 : 파일 discriptor, 실패 : -1
The read() and write() System Calls
Read(), Write()
File descriptor : fd
메모리 영역의 Address : buf
한번에 전송할 byte수 : number
성공 : byte의 number, 실패 : -1
File Locking
동기화의 문제 - lock
Advisory lock(POSIX : fcntl(), BSD : flock())
Advisory Locking 는 OS 가특정프로세스에의해 Locking 된파일에대하여 정확한자료를유지하되,다른프로세스에의해 Locking 된파일에대하여쓰기를막지않는것을말한다.
프로세스는 advisory lock 을무시하고적절한권한이있다면 Lock 된파일에쓰기를할수있다.
Mandatory lock(System V Release 3)
호출프로세스가접근하려는파일에대해 lock 을위반하지않는가를검사하기위해 kernel 로하여금 open, read, write 를검사하는방식
Read lock, write lock
어떤 lock이든 read locks는 공유되고 여러 프로세스가 lock을 걸 수 있다.
write locks는 exclusive이며 단지 하나의 프로세스만이 lock을 걸 수 있다.
같은 file region에 다른 프로세스들이 read lock을 걸었을 때, write lock을 걸 수 없다.
Table 12-11. Whether a Lock Is Granted
Linux File Locking
Linux 에서 locking
Advisory locks
fcntl() - FL_POSIX타입

flock() - FL_LOCK타입

mandatory locks
Lockf() – System V

mount()시스템콜의 MS_MANDLOCK flag 를사용하여파일시스템당 enable 와 disable 할수있다.
디폴트값은 mandatory locking switch off 이다.
두 가지 lock 은공존하며서로에게영향을주지않는다.
fcntl() 이 file 에 lock 을걸면 flock() 는나타나지않는다.
FL_POSIX lock(프로세스와 inode에 관련)
프로세서가 죽거나 파일 디스크립터가 closed될 때 Lock는 자동으로 release된다.
절대 fork()를 통해 child에게 상속되지 않는다.
FL_LOCK lock(File object에 관련)
Lock이 요구될 때 커널은 같은 파일 객체를 참조하는 다른 lock으로 바꾼다.
파일 객체가 fput()에 의해 free될때 파일객체를 참조하는 모든 FL_LOCK locks은 destoryed된다.
다른 FL_LOCK은 같은 파일(inode)의 다른 프로세스에 의해 설정된 locks를 읽고, 여전히 active상태로 남는다.

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 13. Managing I/O Devices
차례
I/O Architecture
Associating Files with I/O Devices
Device Drivers
Character Device Handling
Block Device Handling
Page I/O Operations
I/O Architecture
컴퓨터의 수행에 있어 data path는 CPU, RAM과 컴퓨터와 연결된 I/O 디바이스들 사이에서의 정보 흐름을 제공해야 한다. 이를 bus라고 하며 컴퓨터 내부의 통신 채널이다.
ISA, EISA, PCI, MCA등 방식
Data bus
병렬로 데이터를 전송하는 라인의 그룹, (Pentium은 64bit data bus)
Address bus
병렬로 주소를 전송하는 라인의 그룹 (Pentium은 32bit address bus)
Control bus
연결된 회로에 제어 정보를 전송하는 라인의 그룹
I/O Ports
I/O bus에 연결된 각 디바이스는I/O port라는 I/O address의 set을 가지고 있다.
CPU는 control register에 디바이스에 보내진 명령어 들을 저장하고 status register를 통해 디바이스의 내부 상태를 표시한 값을 읽어들인다. 또한 CPU는 input register를 통해 byte들을 읽어 디바이스의 데이터를 가져오고 output register로 byte들을 써서 데이터를 push시킨다.
(p.374, figure 13-2)
I/O Interfaces
I/O interface는 I/O port 그룹과 상응하는 디바이스 컨트롤러 사이에 있는 하드웨어 회로이다.
이는 I/O port에 있는 값을 디바이스 명령이나 데이터로 해석하거나 변환하는 기능을 가진다.
Custom I/O interfaces
하나의 특정 하드웨어 디바이스에 정해진 인터페이스, 내/외부 디바이스 포함
General-purpose I/O interfaces
몇몇의 다른 하드웨어 디바이스를 연결하기 위해 사용된다. 대부분 외부 디바이스로 사용.
Custom I/O interfaces
Keyboard Interface, Graphic interface, Disk interface, Bus mouse interface, Network interface
General-purpose I/O interfaces
Parallel port, Serial port, Universal serial bus(USB), PCMCIA interface, SCSI interface
Device Controllers
복잡한 디바이스들은 구동을 위해 디바이스 컨트롤러가 사용된다.
I/O interface로부터 받은 고수준 명령어를 해석하며 전기적 신호에 대한 적절한 결과를 보내어 특수한 동작을 수행하도록 한다.
디바이스로부터 수신된 전기적 시그널을 변환하고 해석하며 상태 레지스터의 값을 수정한다.
Direct Memory Access (DMA)
Direct Memory Access Controller(DMAC)라는 보조 프로세서가 있으며 이는 RAM과 I/O device사이에 데이터를 전송하기 위하여 사용된다.
DMAC는 대부분 disk driver에 의해 사용되며 한번에 많은 양을 전송하는 속도가 느린 디바이스에 적용 가능하다.
Associating Files with I/O Devices
Device Files
Type
block 또는 character로 구분
Major number
디바이스 타입을 결정하는 1~255의 숫자
Minor number
같은 major number를 공유하는 디바이스들 사이를 구분하는 숫자
Block devices
하나의 I/O 동작에서 고정된 데이터 블록을 전송하며 디바이스에 저장된 블록은 랜덤하게 어드레싱되어 있다.
Charactor devices
하나의 I/O 동작에서 임의의 데이터를 전송하며 대부분 순차적으로 어드레싱되어 있다.
Network cards
파일시스템을 사용하지 않고 디바이스 이름과 네트워크 주소 간의 관계를 설정하여 사용된다. 따라서 파일 시스템 관련 시스템 콜을 사용하지 않고 네트워크 주소와 관련된 시스템 콜을 사용한다.
VFS Handling of Device Files
디바이스 파일은 일반 파일이나 디렉토리와 다르게 구성되어 있으며 VFS는 어플리케이션에서 디바이스 파일과 일반 파일과의 차이를 조정해 주는 역할을 가지고 있다.
디바이스 파일에서 시스템 콜은 일반 파일 시스템에서 사용하는 함수 대신에 디바이스와 관련된 함수로 사용할수 있도록 전환시켜 주는 기능이 있다.
I/O디바이스 제어를 위한 디바이스 관련된 함수를 device driver로 불린다.
Device files class descriptor
major number, name, fops : major number, 디바이스 클래스 숫자, 파일 수행 테이블에서의 포인터
Open a device file
inode object의 I_rdev 필드에서 디바이스 드라이버의 major number를 얻어낸다.
디바이스 파일에 대한 적절한 파일 수행을 설정한다.
파일 수행 테이블의 open method를 invoke한다.
Device Drivers
Level of Kernel Support
No support at all : in, out 어셈블리를 이용하여 I/O 포트에 직접 제어하는 경우
Minimal support : 커널은 하드웨어를 인식하지 못하고 단지 I/O interface만 이용하는 경우
범용 I/O interface와 연결된 외부 하드웨어 디바이스(외장 하드디스크)
이 경우 커널은 I/O 인터페이스만 다룬다.
Extended support : 커널에서 하드웨어 디바이스를 인식하고 I/O interface를 다루는 경우
내장 하드디스크와 같이 I/O 버스와 직접 연결된 디바이스와 같은 경우
Monitoring I/O Operations
I/O 동작이 수행되는 동안은 예측이 어려운 상태에 놓이게 되며 이는 랜덤 이벤트나 human factor 등에 의존적이다.
Polling Mode
CPU가 I/O 동작이 완료된 시그널이 있을 때 까지 디바이스 상태 레지스터를 반복적으로 점검하는 것이다. Spin Locks에 기반
Interrupt Mode
I/O 컨트롤러가 IRQ 라인을 통해 I/O 동작 종료에 대한 시그널링이 가능하는 경우에만 사용된다.
Accessing I/O Ports
in, out, ins, outs 어셈블리 언어
I/O 포트가 어떤 I/O 디바이스에 지정이 되어 있는가를 감지하고 실제로 하드웨어 디바이스가 존재하는 포트를 iotable에 저장한다.
/proc/ioports 파일
Requesting an IRQ
usage counter는 현재 디바이스 파일을 액세스하는 프로세스의 수를 점검하며 이 카운터는 open method에는 증가하고 release method에는 감소하게 된다.
request_irq()
free_irq()
Putting DMA to Work
I/O driver에서 성능 향상을 위해 DMAC을 사용
driver는 bus 타입에 따라 DMA 동작이 수행
DMA for ISA bus
각 ISA DMAC은 제한된 채널 수를 제어할수 있으며 각 채널은 독립 내부 레지스터를 포함하므로 DMAC은 동시에 여러 개의 데이터 전송을 제어할 수 있게된다.
DMA for PCI bus
DMAC이 I/O 인터페이스에 통합되어 있어 PCI 버스에서의 DMA 사용은 간단하다.
각 하드웨어 디바이스는 직접 PCI 버스 신호를 제어하므로 DMA 채널 할당이 필요없게된다.
Device Controller’s Local Memory
일부 하드웨어 디바이스는 메모리를 포함하는 경우가 있으며 이는 I/O 공유 메모리로 불린다.
Mapping address
For most devices connected to the ISA bus
0xa0000 ~ 0xfffff
For some old devices using the VESA Local Bus(VLB)
0xe00000 ~ 0xffffff
For devices connected to the PCI bus
큰 물리적 어드레스에 매핑
Accessing the I/O shared memory
I/O 공유 메모리 위치는 PAGE_OFFSET 보다 큰 주소로 표현되어야 한다.
I/O 물리 주소가 시스템 물리적 메모리 주소보다 큰 경우에는 커널 page table을 I/O 물리 주소 맵을 포함하도록 수정해야 한다.
ioremap() 함수 사용
Character Device Handling
Logitech bus mouse의 드라이버 동작 예
/dev/logibm, major 10 minor 0
bus_mouse_fops 테이블을 가지고 open_mouse() 함수가 실행
1. bus mouse가 연결되어 있는지 점검
2. IRQ를 요청
3. mouse 데이터 구조를 초기화
4. bus mouse 인터럽트 enable을 위해 0x23e 제어 레지스터에 0 값 셋팅
mouse_interrupt() 함수
1. 0x23e 제어 레지스터에 명령을 쓰거나 0x23c 입력 레지스터에 값을 읽어드리는 상태 요청
2. mouse 데이터 구조를 update
3. bus mouse 인터럽트를 재가능하도록 하기 위해 0x23e 제어 레지스터에 0 값을 셋팅
마우스 상태를 알기위해 /dev/logibm 파일을 읽어들이고 real_mouse() 함수를 실행
Block Device Handling
리눅스 커널에서 지원하는 블록 디바이스 핸들러
VFS를 통해 일정한 인터페이스 제공
디스크 데이터에 대한 효율적인 읽기 기법
데이터에 대한 디스크 캐시 제공
커널은 기본적으로 I/O 데이터 전송에 두 가지로 구분
Buffer I/O operations
전송된 데이터는 디스크 기반의 데이터를 위한 커널의 일반 메모리 저장소인 버퍼에 저장

Page I/O operations
전송된 데이터는 일반 파일에 속한 데이터를 가진 페이지 프레임에 저장

Sector, Block, and Buffers
블록 디바이스에서 데이터 전송은 sector라는 몇 바이트의 그룹 형태로 되어있다.
대부분 디스크 디바이스의 sector는 512 byte로 구성한다.
블록 디바이스 드라이버는 한 작업에 대해 block 단위의 큰 수를 전송하기도 한다.
sector는 하드웨어 디바이스에서 데이터를 전송하는 기본 단위이고 block은 디바이스 드라이버에 의해 요청된 I/O 작업에 속한 몇 바이트의 그룹 단위이다.
각 block은 내용을 저장하기 위해 커널에 의해 사용된 RAM 메모리 영역인 buffer를 필요로 한다. buffer 크기는 항상 block 크기와 일치한다.
An Overview of Buffer I/O Operations
그림 13-3(p.395) 버퍼 I/O 작업에 대한 블록 디바이스 핸들러 구조
블록 디바이스 드라이버는 VFS layer를 가진 high-level driver와 하드웨어 디바이스를 다루는 low-level driver의 두 part로 구분된다.
커널은 block_read(), block_write() 함수 제공
getblk() 함수로 한번 액세스한 블록을 캐쉬에서 점검
캐쉬에 없다면 ll_rw_block() 함수로 low-level 상태로 직접 액세스
Role of Read-Ahead
많은 디스크 액세스는 순차적이며 파일은 몇몇의 섹터 그룹으로 저장되어 있으므로 디스크 헤드의 이동이 거의 없이 빠르게 가져올 수 있다. 프로그램이 파일을 읽거나 카피할 때 순차적으로 액세스 하게될 것이다.
Read-ahead는 실제적으로 요청되기 전에 블록 디바이스에 대해 몇몇의 블록을 읽어들이는 향상된 기능을 가진다. 대부분의 경우에 read-ahead는 디스크 수행 성능을 향상시켜 많은 섹터 그룹을 참조하는 명령을 덜 수행하도록 한다.
Read-ahead는 랜덤 액세스를 위해서는 사용할 수 없으며 커널에서 read-ahead를 중지 시킨다.
The block_read() and block_write() Functions
block_read() 및 block_write() 함수는 프로세스가 디바이스 파일을 읽거나 쓰기 수행을 할 때마다 high-level 디바이스 드라이버에 의해 실행된다.
The bread() and breada() Functions
bread() 함수는 특정 블록이 버퍼 캐시 안에 이미 포함되어 있는지를 점검하고 그렇지 않다면 함수는 블록 디바이스로부터 직접 읽어 들이게 된다.
breada()는 bread()와 비슷하나 하나의 request에 추가하여 여분의 블록을 읽어들이는 기능을 가진다. 성능에 대한 고려 요구됨.
Buffer Heads
buffer head는 각 버퍼와 관련된 buffer_head의 디스크립터이며 이는 커널이 버퍼 헤드를 점검이 각 버퍼에서 수행되기 이전에 어떻게 버퍼를 다루는 가에 대한 모든 정보를 가지고 있다.
b_dev 필드와 b_rdev 필드 -> RAID 시스템에는 논리 블록과 이에 상응하는 실제 블록 number가 존재
Block Device Requests
VFS layer의 프로세스 혹은 다른 커널 구성요소가 디스크 블록을 읽거나 쓸 때 block device request를 발생시킨다.
각 블록 디바이스 드라이버는 자신의 request queues를 관리하며 각 물리적 블록 디바이스에 대한 queue를 요청하여 각 request들이 디스크 성능 향상을 위해 정렬된다.
각 블록 디바이스 request는 request descriptor로 나타내며 requst 데이터 구조체에 저장된다.
그림 13-4(p.404)는 세가지 블록을 포함하는 request descriptor를 나타내고 있다.
두개의 버퍼는 RAM에서 연속되어 있고 다른 한 개의 버퍼는 따로 떨어져 있다.
버퍼 헤드는 블록 디바이스에서 논리 블록을 식별하고 블록은 반드시 인접해 있어야 한다. 각 논리 블록은 두가지 sector를 포함한다. sector 필드는 디스트에 첫번째 블록의 첫번째 섹터를 가리키며 각 버퍼의 b_reqnext 필드는 다음의 buffer head를 가리킨다.
Requests Queues and Block Device Driver Descriptors
request queue는 request descriptor로 구성된 리스트가 간단하게 링크되어 있으며 각 request descriptor에 next 필드는 queue에 있는 next item을 가리키고 마지막 요소는 null 값을 갖는다. 이 리스트는 첫번째는 디바이스 식별자, 다음은 초기 섹터 수에 따라 정렬된다.
디바이스 드라이버는 각 디스크에 대한 하나의 request queue를 가지나 어떤 디바이스 드라이버는 드라이버에 의해 다루어지는 모든 물리적 디바이스의 request를 포함하는 하나의 requset queue를 가지는 경우도 있다.
The ll_rw_block() Function
ll_rw_block() 함수는 블록 디바이스의 request를 생성하며 커널 및 디바이스 드라이버 곳곳에서 생성된다.
make_request() 함수
두가지 substep을 수행
1. request queue가 비어있다면 새로운 request descriptor를 끼워 넣고 앞으로 시간에 대한 strategy routine을 위한 스케줄링을 하게된다.

2. request queue가 비어있지 않다면 새로운 request descriptor를 끼워 넣고 이미 queue된 다른 request에 대하여 하나의 묶음을 만들게 된다. 여기에서는 strategy routine에 대한 스케줄링이 필요 없게 된다.

Low-Level Request Handling
Low-level 디바이스 드라이버는 다음의 구조를 가짐
strategy routine은 queue에 있는 현재 request를 다루고 블록 디바이스 컨트롤러를 설정하여 데이터 전송이 완료될 때 인터럽트를 발생시킨다. 그리고 strategy routine은 종료된다.
블록 디바이스 컨트롤러가 인터럽트를 발생시킬 때 인터럽트 핸들러는 bottom half로 구동된다. Bottom half 핸들러는 queue에 request를 제거하고 queue의 다음 request를 위해 strategy routine을 재실행한다.
Page I/O Operations
프로세스가 일반 파일에 대한 read(), write() 시스템 콜을 다루는 경우
프로세스가 메모리에 파일을 매핑한 페이지의 위치를 읽어드리는 경우
커널이 디스크에 파일 메모리 매핑에 관련된 dirty page를 다루는 경우
swapping in, out에서 커널이 모든 페이지 프레임에 대한 내용을 디스크로부터 읽거나 저장하는 경우
linux 2.4
새로운 리소스 관리 서브시스템 구성(IRQ lines, DMA channels, I/O ports 등)
plug and play 강화, UBS bus, PCMCIA card 등
block device driver에서는 logical volume manager 지원
raw I/O devices라는 character 디바이스 소개(DBMS와 같은 응용 프로그램을 커널 캐쉬를 만들지 않고 직접 디스크에 액세스 하도록 허용)
Intelligent Input/Output(I2O) 하드웨어 지원

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 14. Disk Caches
차례
Introduction
The Buffer Cache
The Page Cache
Introduction
여기서는 linux에서 가능한 disk access를 줄이고 시스템 성능을 향상시키는 disk cache에 대해 알아본다.
disk cache : 일빈적으로 disk에 저장되어 있는 data의 일부를 RAM상에 저장하는 software mechanism. buffer cache와 page cache
buffer cache : buffer는 disk block의 data를 저장하는 memory area로써 이러한 buffer들을 저장하는 disk cache.
page cache : regular files에 속한 data를 담고 있는 page frames를 저장하고 있는 disk cache.
The Buffer Cache
Buffer cache는 상대적으로 느린 disk의 검색이나 data를 저장하는 동안 process가 기다리는 시간을 덜어주는 것이 주 목적.
Buffer에 관한 정보는 buffer head에 저장 유지한다.
Buffer cache는 다음 두 종류의 data structure로 구성.
Buffer heads
hash table
Buffer Head Data Structures
Buffer head data structure는 bh_cachep라 불리는 slab allocator cache를 가지고 있다.
일박적으로 buffer head는 다음 상태중 하나에 상태에 존재한다.
Unused buffer head
Buffer head for a free buffer
Buffer head for cached buffer
Asynchronous buffer head
이러한 buffer head들을 취급하기 위해 kernel에 의해 사용되는 data structure와 method에 대해 알아보자.
The list of unused buffer heads
모든 unused buffer head 간단한 linked list에 수집된다.
새로운 buffer head를 얻기 위해 get_unused_buffer_head() 호출.
Lists of buffer heads for free buffers
Free buffer에 대한 7개의 buffer head list가 정의 되어 있다. buffer size(512, 1024, 2048, 4096, 8192, 16384, 32768bytes
Lists of buffer heads for cached buffers
Buffer가 buffer cache에 있을 때 buffer head에 상응하는 flags들이 현재의 상태를 나타냄 (BH_Uptodate, BH_Lock, BH_Lock)
BUF_CLEAN, BUF_DIRTY, BUF_LOCKED macro 사용 각각의 buffer head를 수집.
The hash table of cached buffer heads
Buffer cache에 속해 있는 buffer heads의 주소는 hash table에 삽입된다.
insert_into_queues(), remove_from_queues()
Lists of asynchronous buffer heads
Asynchronous buffer heads는 page I/O file operation에 사용.
Page frame은 buffer group으로 이루어져 있다.
The getblk() Function
Buffer cache에 대한 주 service routine
Buffer cache에 buffer head가 없을 때 kernel이 cache에 새로운 entry를 생성할 때 호출
Buffer Usage Counter
Buffer head의 b_count field는 그에 상응하는 buffer의 사용 counter.
safety lock으로 동작.
getblk() 증가.
brelse() or bforget() 감소.
Buffer Allocation
Buffer들은 buffer pages라 불리우는 전용 pages에 저장된다.
하나의 buffer page내의 buffer들은 모든 같은 크기를 같는다.
Ref) figure 14-1
grow_buffers(), create_buffers()
Writing Dirty Buffers to Disk
System의 성능 향상을 위해 dirty buffer를 block device에 쓰는 것을 지연시킨다.
Delayed-write strategy의 단점.
Hardware or power supply에 문제가 발생 하면 더 이상 RAM의 내용을 회복할수 없으므로 update된 data를 잃게 된다.
Buffer cache의 크기가 커진다.
그러므로 다음의 상황에서 dirty buffers를 flush한다.
Buffer cache가 꽉 차고 더 많은 buffer가 필요하거나 dirty buffer의 수가 너무 많을 때.- bdflush kernel thread 실행.
Buffer가 dirty 상태로 너무 많은 시간동안 있었을 때. - kupdate kernel thread 실행.
sync(), fsync(), fdatasync() system call
The bdflush kernel thread
시스템 초기화시 생성, bdflash() 수행
Ref) Table 14-2
kernel thread는 다음의 경우에 동작한다.
dirty buffer의 퍼센티지가 임계값을 초과 했을 경우.

Buffer allocation에서 grow_buffers()에서 새로운 buffers를 얻지 못했을 경우.

Buffer cache에서 일부 buffer를 해제 함으로써 kernel이 free page를 얻으려고 할때

Magic SysRq Key가 눌려질때.

The kupdate kernel thread
Older dirty buffers를 flush.
kupdate() -> sync_old_buffers()
The sync(), fsync(), and fdatasync() system calls
sync() : flushes all dirty buffers
fsync() : process가 특정한 open file에 속한 모든 블럭을 flush 할 수 있게 허용.
fdatasync() : fsync()와 비슷하지만 파일의 inode block은 flush하지 않는다.
The Page Cache
Buffer cache보다 매우 간단.
Page I/O operation에 의해 접근되는 data에 대한 disk cache.
Page Cache Data Structure
Page cache는 다음 두개의 data structure를 이용.
A page hash table : page descriptor의 address를 빠르게 알아내기 위해 사용.
An inode queue : page descriptor의 list.
add_page_to_hash_queue(), remove_page_from_hash_queue()
add_page_to_inode_queue(), remove_page_from_inode_queue()
Page Cache Handling Functions
find_page() -> page_hash()
add_to_page_cache() -> add_page_to_hash_queue()
remove_inode_page() -> remove_page_from_hash_queue() -> remove_page_from_hash_queue() -> __free_page()
Tuning the Page Cache
Free memory가 줄어들면 kernel은 가장 오래 사용되지 않은 page를 해제함으로써 page cache를 줄인다.
하지만 미리 정해진 최소값 이하로 page cache size가 내려가진 않는다.(min_percent parameter 정의)

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 15. Accessing Regular Files
차례
Introduction
Reading and Writing a Regular File
Memory Mapping
Introduction
이 장은 커널에서 사용자 주소공간으로의 이동만 다룬다.
Read()
Page-based
커널은 언제나 데이터의 전체페이지를 한번에 전송한다.
만약 몇바이트의 데이터를 읽기 위해 read()를 호출했는데 RAM에 그 자료가 없다면 커널에 새로운 페이지 프레임을 할당한다.
Write()
Disk-based filesystem
파일사이즈가 변하므로 커널은 디스크에서 물리적 블록을 allocate와 release를 해야 한다.
파일시스템에 의존적이다.
Reading and Writing a Regular File
Reading from a Regular File
Generic_file_read() : read method
Read-Ahead for Regular Files
Data 를페이지단위로읽는다.
Figure 15-1. Read-ahead window and read-ahead group
Read-ahead window
파일의연속된위치에있는페이지의 set

Read-ahead group
마지막의 read-ahead작업에요구되는 page

Read-Ahead for Regular Files
Read-ahead operations
Try_to_read_ahead()
페이지가 이미 페이지 캐쉬에 있는지를 체크

Generic_file_readahead()
파일의 Read-ahead window와 read-ahead group을 갱신

Nonsequential access(outside the read-ahead window)
Read-ahead가 수행될 때 2가지 경우가 생긴다
Page가 unlocked 인 경우(모든 data가 page cache에 있는 경우)

아무 일도 일어나지 않는다.
Page가 locked 인 경우(실 데이터가 완전히 전송되지 않는 경우 or update)

Read-ahead를 수행
Next read-ahead를 위해 short read-ahead를 준비한다.
Sequential access(inside the read-ahead window)
Generic_file_readahead() 수행시 lock 에따른 4 가지경우
1)프로세스는마지막 read-ahead operation 에의해디스크로부터전송된접근페이지를가리킨다.이경우에수행되는 read-ahead 는 long read-ahead window 를사용한다. Low-level블록디바이스드라이버를사용한다.

2)프로세스는 next-to-last read-ahead 연산에서디스크로부터전송된페이지에접근한다.커널은순차적으로읽는다.

3)프로세스는 last read-ahead 연산에서요구된페이지에접근한다.

4)프로세스는 next-to-last read-ahead연산에서요구된페이지에접근한다.이경우에커널은다른 read-ahead 를수행한다.

Writing to a Regular File
Write() system call
프로세스를호출한 User Mode address space 로부터 kernel data structures 로데이터를옮기고,다음에디스크로옮긴다.
파일객체의 write method 는 write operation 에정의된 각파일시스템타입을허용한다.
Disk-based filesystem
정규파일을쓰기위한페이지캐쉬를직접사용하지않는다.
디스크캐쉬는리눅스구버전부터버퍼캐쉬로사용해왔다.
그러나 network-based filesystems 은언제나정규파일에쓰기위하여페이지캐쉬를사용한다.
Writing to a Regular File
Writing시 동기화 문제가 발생(페이지 캐쉬를 고려하지 않으므로)
유효한 데이터는 버퍼캐쉬에 있지만 페이지 캐쉬에는 없다.
write method가 file의 위치가 바뀔 때, 그 위치에 일치하는 페이지 캐쉬내의 어떠한 페이지도 더 이상 의미 있는 데이터를 포함하지 않는다.
예) 한 프로세스는 정확한 데이터를 읽는다고 생각하지만, 다른 프로세스에 의해서 쓰여져 변하므로 실패 할 수 있다.
문제 해결
update_vm_cache()
disk-based filesystem의 모든 write method는 읽기에 사용한 페이지 캐쉬를 갱신한다.

Memory Mapping
Memory Mapping
Memory region은 disk-based filesystem의 파일에 관련이 있다.
memory region 페이지의 Byte 접근은 정규파일에 일치하는 바이트의 연산으로 커널에 의해 전환된다.
mmap() system call
새로운 메모리 매핑을 생성
매핑이 생성되면 프로세스는 새로운 memory region의 memory locations으로부터 간단하게 파일에 저장된 데이터를 읽을 수 있다.
만약 메모리 매핑이 공유되면 프로세스는 같은 메모리 위치에 간단히 write 함으로써 그 파일을 수정할 수 있다.
munmap() system call
메모리 매핑을 destroy나 shrink할 때 사용
두 종류의 memory mapping
Shared
Memory region의 페이지에서의 write연산은 디스크의 파일을 수정할 수 있다.
만약 프로세스가 공유 메모리 매핑의 페이지에 쓴다면 같은 파일의 다른 모든 프로세스가 가지는 내용이 변한다.
Private
프로세스가 파일을 읽기 위해 매핑을 생성할 때, 또는 그것을 쓰지 못하게 할 때 사용한다.
Private mapping은 shared mapping보다 더 효율적이다.
그러나 privately mapped에서 어떤 write operation은 더 이상 파일에 페이지 맵을 생성시키지 않기 때문에, 디스크에서 파일을 바꾸지 않거나 같은 파일에 접근하는 다른 프로세스에게 바뀐 것을 보여주지 않는 경우도 있다.
Memory Mapping Data Structures
Figure 15-4. Data structures related to memory mapping
Data structures가 서로 어떻게 linked되었는지를 보여준다.
각 inode객체의 I_mmap 필드는 현재 map file의 모든 메모리 region을 포함하는 doubly linked list의 첫번째 element를 가리킨다.
만약 I_mmap이 NULL이면 파일은 어떠한 memory region에 의해서도 mapped되지 않는다.

vm_area_struct descriptors를 포함하는 List는 memory region을 나타내고 vm_next_share와 vm_pprev_share fields로 구현된다.
각 memory region descriptor의 Vm_file 필드는 mapped file의 file object의 주소를 포함한다.
만약 그 field가 null이면 memory region은 메모리 매핑에 사용되지 않는다.

File object는 커널이 메모리 매핑된 것과 파일이 매핑된 두 프로세스를 식별하는 필드를 포함한다.
First mapped location의 위치는 memory region descriptor의 vm_offset 필드에 저장된다.
Mapped file 위치의 길이는 단순히 memory region의 길이이다. 따라서 vm_start와 vm_end 필드로부터 계산할 수 있다.
Shared mapping 매핑의 페이지는 언제나 페이지 캐쉬에 포함된다.
Private memory 매핑의 페이지는 수정되지 않는 긴 페이지 캐쉬에 포함되어 있다.
프로세스가 private memory mapping의 페이지를 수정하려고 하면, 커널은 페이지 프레임을 복사하고 프로세스 페이지 페이블에 복사된 원래의 페이지 프레임으로 대신한다Copy On Write)

심지어 메모리 매핑에 더 이상 속하지 않는다 하더라도, 복사에 의해 대치시킨다. 차례로, 더 이상 유효한 데이터를 디스크의 파일에 나타내지 않기 때문에 복사는 페이지 캐쉬에 삽입 되지 않는다.

memory-maped file 을참조하는페이지캐쉬에포함된페이지의 page descriptor 를보여준다.
이 descriptor 는 next 와 prev필드를통하여구현된 doubly linked list 에삽입된다.

첫번째 list element 의주소는 inode 객체의 I_pages필드에있다.

한번더, private memory mapping 의페이지를수정하면이 list 에는속하지않는다.

그림의 First memory region 은 3 개의페이지로되어있다.하지만단지두페이지프레임만그것에할당되어있다.

Operations Associated with a Memory Region
Memory region descriptor는 superblock, inode, file objects와 같은 객체이다.
Memory mapping functions은 다른 파일시스템이 자신의 메모리 매핑을 구현하는 것을 허락한다.
대부분의 파일 시스템은두개의 memory region operations의 표준 테이블에 의존한다.
Table 15-2. Methods Used by file_shared_mmap and by file_private_mmap
File_shared_mmap

File_private_mmap

Method값이 NULL이면 커널은 default function을 수행하거나 아무 함수도 실행하지 않는다.

만약 nopage가 NULL이면 디스크의 어떤 파일에도 map이 없는 것이다.

Creating a Memory Mapping
mmap() system call
새로운 memory mapping 을생성하기위해서사용
Mmap() system call
새 memory region 에있는첫번째위치의선형주소를리턴
Destroying a Memory Mapping
munmap() system call
프로세스가메모리매핑에서 destroy 될때호출
Demand Paging for Memory Mapping
프로세스가 페이지 중 하나에 접근하려고 할때, “page fault” exception이 발생할 수 있으므로 효율성때문에, 페이지 프레임은 생성 후 바로 메모리 매핑에 할당 되지 않는다.
do_no_page()
커널은 페이지 테이블 엔트리를 체크해서 entry가 null일 때 발생된다.
Do_no_page()는 페이지 프레임 할당과 페이지 테이블 갱신과 같은 demand paging의 모든 타입에 일반적인 operations을 수행한다.
Demand paging algorithm의 핵심은 memory region의 nopage method의 구성이다.
디스크에 맵 파일이 있는 Memory regions을 핸들링 할 때, nopage method는 페이지 캐쉬내의 요청된 페이지의 시작을 검색해야 한다.
프로세스가 접근한 페이지를 포함하는 페이지 프레임의 주소를 리턴 한다.
Flushing Dirty Memory Mapping Pages to Disk
Msync() system call
프로세스가 공유 메모리 매핑에 속한 디스크 dirty page를 flush하는데 사용한다.

파라미터로써 선형주소의 interval의 시작 주소를 받는다.

Sys_msync() service routine
선형주소 interval에 포함된 각 memory region에 m_sync_interval()을 발생시킨다.

Filemap_sync() function
memory region에 포함된 데이터를 디스크에 복사한다.

Memory region에 포함된 linear address interval과 같은 Page Table entries를 찾는다.


Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 16. Swapping ; Methods for free memory
차례
Introduction
What Is Swapping?
Swap Area
The Swap Cache
Transferring Swap Pages
Page Swap-Out
Page Swap-In
Freeing Page Frames
Introduction
커널이 메모리 확보를 위해 디스크 공간을 활용하는 swapping
disk cache는 여유 메모리를 이용하여 시스템 성능을 향상시키는 것이고 swapping은 액세스 속도를 활용하여 주소 메모리 공간을 확장하는 것이다.
What Is Swapping?
프로세스에 효과적으로 사용되는 주소 공간을 확장하기 위해
프로세스를 로딩하는 동적 메모리의 공간을 확보하기 위해
Which kind of Page to Swap Out
page가 프로세스의 anonymous 메모리 영역에 속하는 경우
수정된 page가 프로세스의 private 메모리 영역에 속하는 경우
page가 IPC 공유 메모리 영역에 속하는 경우
How to Distribute Pages in the Swap Areas
swap 영역은 slot 형태로 구성되며 disk seek time을 최소화하는 연속된 slot에 page를 저장하는 방식을 가진다. 속도가 빠른 disk에 저장된 swap 영역이 큰 우선순위를 갖는다.
How to Select the Page to Be Swapped Out
Least Recently Used(LRU) 알고리즘이 사용되며 page의 저장된 시점에 맞추어 카운터를 가지고 있다. 가장 오래된 page가 swapped out된다.
When to Perform Page Swap-out
swapping out은 커널이 낮은 메모리를 가지고 있을 때 유용하며 커널은 대부분의 critical funtions에 의해 이용되는 free page frame을 가진다.
Swap Area
각 swap area는 page slot이 순차적으로 구성되어 있으며 이는 swapped-out page를 가진 4096 byte 블록으로 구성된다.
리눅스에서는 swap 파티션을 생성하며 /sbin/mkswap을 이용하여 새로운 swap 영역을 설정한다.
Swap Area Descriptor
각 active swap area는 swap_info_struct descriptor를 가짐(Table 16-1, p461).
swap_map 필드는 카운터 배열로서 각 swap 영역 page slot을 나타냄
swap_info 배열은 MAX_SWAPFILES swap 영역 디스크립터를 가짐
Swapped-out Page Identifier
Page가 swap out 될 때 식별자는 page의 엔트리로 page table에 저장되어 활용된다.
Null entry : page가 process address space에 속하지 않는 경우
첫번째 0이 아닌 30개의 주요 비트와 마지막 0인 2비트 : page가 현재 swapped out인 경우
1인 최소 비트 값 : page가 RAM에 속해있는 경우
Activating and Deactivating a Swap Area
swap area가 초기화 되면 superuser는 /bin/swapon 또는 /bin/swapoff를 이용하여 swap area를 설정, 해제가 가능하게 된다. 이 응용 프로그램들은 swapon(), swapoff() 시스템 콜을 사용한다.
sys_swapon()
speicialfile : 디바이스 파일 또는 swap area를 구성하는 일반 파일의 pathname
swap_files : 주요 swap area를 나타내는 15개의 주요 비트 값
sys_swapoff()
해제되려는 파티션은 몇몇의 프로세스를 가지고 있는 page를 포함하고 있기 때문에 swap area를 검색하소 모든 존재하는 page들을 swap in 해야한다.
Finding a Free Page Slot
빈 메모리가 있을 때 커널은 많은 page들을 짧은 시간에 swap out하게 된다. 이는 disk seek를 최소화하며 page를 연속적으로 slot에 저장하는 중요한 점이 된다.
Swap area의 시작 부분부터 시작하는 경우와 마지막으로 할당된 page slot부터 시작하는 경우
리눅스는 hybrid 방식을 취하며 이는 다음의 상황 이외에 언제나 마지막으로 할당된 page slot에서부터 시작된다.
swap area의 마지막에 도달되었을 경우
SWAPFILE_CLUSTER free page slot이 swap area의 초기에서부터 마지막으로 재 시작되어 할당되는 경우
Allocating and Releasing a Page Slot
두가지 pass가 필요
첫번째 pass는 같은 우선순위를 가지는 area가 있는 경우 free slot에 대해 round-robin 방식으로 area를 검색한다.
Free page slot을 찾지 못했을 경우에 두번째 pass는 swap area 목록의 첫번째 부분으로부터 수행되며 모든 swap area를 점검하게 된다.
The Swap Cache
리눅스에서는 page frame이 몇몇의 프로세스들 사이에서 공유될 경우는 다음과 같다.
page frame은 공유 메모리 맵핑과 관계되는 경우
page frame은 계속 새로운 프로세스가 생성되어 가기 때문에 Copy On Write에 의해 다루어 지는 경우
page frame은 IPC 공유 메모리 자원에 할당되는 경우
(Figure 16-4, p472)
멀티 프로세스에서 swapped out된 공유 page에서 커널에 의해 수행되는 과정을 나타낸 것이다.
1. (a)에서 P는 A, B의 page table에 존재
2. (b)에서 P는 A의 주소 공간으로부터 swapped out
3. (c)에서 P는 A, B 모두의 주소 공간으로부터 swapped out되었으나 swap cache에 여전히 포함
4. (d)에서는 Buddy system(6장 memory management)으로 릴리즈됨
Transferring Swap Pages
다수의 asynchronous swap 수행이 너무 많아 단지 synchronous I/O 수행이 시작되는 경우
page를 가진 프로세스가 swaped in 또는 out되는 동안 소멸되는 경우
또 다른 프로세스가swap out 하려고 하는 page에 swap in 하려는 경우
Locking the Page Frame and the Page Solt
다른 디스크 액세스 타입과 같이 swap page를 위한 I/O 데이터 전송은 blocking operation이 존재한다. 커널은 동일한 page frame이나 page solt을 포함하여 동시 전송을 피하도록 해야한다.
PG_locked 플래그가 off될때 까지 기다리는 wait_on_page() 함수를 사용하며 이 함수가 리턴되면 page frame이 lock 수행되며 커널은 I/O 동작 동안 page frame의 내용을 액세스할 수 있게 된다.
The rw_swap_page() Function
buffer : swap in 또는 out되기 위한 page를 포함하는 page frame의 초기 주소
entry : swapped-out page identifier
rw : swap in을 위한 READ, swap out을 위한 WRITE의 데이터 전송을 나타내는 플래그
wait : kernel이 I/O 동작이 완료될 때 까지 block 유무를 나타내는 플래그
프로세스가 디스크로부터 요청된 페이지가 전송되기 까지 suspend되야 하므로 swap-in 동작은 page fault가 synchronous(wait이 1)로 수행되며
swap-out 동작은 프로세스가 완료될 때 까지 suspend될 필요가 없으므로 asynchronou(wait이 0)로 수행된다.
The read_swap_cache_async() Function
entry : swapped-out page identifier
wait : 커널이 swap의 I/O 동작이 완료될 때 까지 현재 프로세스를 suspend되도록하는 플래그
wait 파라미터는 I/O swap 동작이 synchronous 또는 asynchronous 되야 하는지를 결정해야한다.
The rw_swap_page_nocache() Funtion
어떤 경우에는 커널은 swap cache 사용 없이 swap area에서부터 page를 읽어 드릴 수 있게 된다.
swapon() 시스템 콜이 수행될 때 커널은 swap area의 첫번째 page를 읽고 즉시 page frame를 버리게 된다. IPC 공유 메모리의 Swapped-out page는 swap cache에 포함되지 않게 된다.
Page Swap-Out
priority : 0~6의 값을 가지며 커널이 swap되기 위한 page 위치를 설정하는데 얼마나의 시간을 사용하는가를 나타낸다.
gfp_mask : 함수에서 메모리 할당에 대한 결과를 요청하면 할당 함수에 gfp_mask 파라미터의 copy 값을 넘겨 주게 된다.
swap_out() 함수는 현재 프로세스를 검색하고 각 프로세스의 page table를 참조하여 page를 swap out한다. 이 함수는 다음의 경우가 발생되면 즉시 중단된다.
함수가 성공적으로 page를 swap out하는 경우
함수가 blocking 동작을 수행하는 경우
함수가 프로세스의 수를 검색한 후에 swap out에 실패하는 경우
The try_to_swap_out() Function
이 함수는 주어진 page frame을 버려야하는지 swap out해야 하는지를 수행한다.
tsk : 프로세스 descriptor pointer
vma : 메모리 영역 descriptor pointer
address : 페이지의 초기 주소
page_table : address를 맵핑한 tsk의 page table entry 주소
함수는 page를 성공적으로 swap out하거나 I/O 동작을 blocking하게되면 1을 리턴하고 swap out이 진행되어 있으면 0을 리턴하게된다.
Swapping Out Pages from Shared Memory Mappings
공유 메모리 맵핑에서 page는 디스크에 일반 파일로 저장된 것과 같게되며 커널은 swap area에 다시 저장하지는 않으나 관련 파일들을 update를 하는 경우는 있다.
공유 메모리 맵핑 영역은 자체 swapout method를 사용한다.
filemap_swapout() 함수는 page를 디스크에 저장하기 위해 filemap_write_page() 함수를 호출한다.
이 경우에 filemap_write_page() 함수는 dead lock과 같은 경우가 있기 때문에 do_write_page() 함수를 실행하지 않는다.
kpiod라는 kernel thread를 사용하며 여기에 나타나는 queue 형태의 디스크립터를 이용하여 작업을 수행한다.
Page Swap-In
Swap-in은 프로세스가 디스크에서 swapped out된 주소 공간 내에 page를 어드레싱할 때 발생한다.
다음의 경우에 Page Fault exception 핸들러가 swap-in 동작을 유발하게 된다.
Exception이 발생된 주소를 포함하는 page가 유효하고 현재 프로세스의 메모리 영역에 속한 경우
Page가 메모리에 존재하지 않고 Page Table entry에서 Present 플래그가 clear된 경우
Page와 연계된 Page Table entry가 swapped-out page identifier를 포함하여 존재하는 경우
리눅스는 각 메모리 영역이 swap-in 수행을 위해 수정된 함수를 포함하도록 하며 이 함수가 필요로하는 영역은 swapin 필드에 포인터를 저장한다.
Freeing Page Frames
Cache에 있는 unused page frame을 재요청하는 경우
프로세스의 임의의 메모리 영역에 속하는 페이지를 swap out 하거나 메모리 매핑에 관련된 page를 수정하는 경우
IPC 공유 메모리 영역에 속하는 page를 swap out하는 경우
Monitoring the Free Memory
nr_free_pages 변수
min : 주요 작업 수행을 위해 커널에 등록된 page frame의 최소 수
high : 커널이 가용한 free memory를 가지고 있음을 나타내고 3 x freepage.min의 값을 가짐
Reclaiming Pages from the Page, Swap, and Buffer Caches
disk cache로부터 page frame을 다시 요구하기 위해 커널은 shrink_mmap() 함수를 사용하게 된다. Page cache, swap cache, buffer cache에 속한 page frame을 풀게 되면 1을 리턴하고 그렇지 않은 경우에는 0을 리턴하게 된다.
Reclaming Pages from the Dentry and Inode Caches
Dentry object는 크지는 않지만 free 시키는 것은 데이터 구조체를 해제하여 많은 메모리를 확보해야하는 효과가 있다.
shrink_dcache_memory() 함수가 dentry cache로부터 dentry object를 제거하는 기능을 수행한다. (12장 참조)
The try_to_free_pages() Function
Free page frame의 수가 freepages.min의 값보다 작아지거나 현재 프로세스의 PF_MEMALLOC 플래그가 clear 되는 경우
새로운 prio_request descriptor를 할당하기 위해 값이 작아지는 경우
The do_try_to_free_pages() Function
do_try_to_free_pages() 함수는 try_to_free_pages() 또는 kswapd kernel thread에 의해 발생되며 이 함수는 gfp_mask 파라미터 값을 받고 최소 page frame을 해제시키기 위해 사용된다.
The kswapd Kernel Thread
kswapd kernel thread는 메모리 활용을 위한 또 다른 커널 메커니즘이다.
Memory allocation request는 해제된 page frame을 기다리기 위해 현재 프로세스를 block할수 없는 interrupt나 exception handler에 의해 수행될 때 I/O 데이터 전송을 할 수 없게 된다.
이러한 경우에 kswapd kernel thread가 매 10 second 마다 수행되며 kswapd() 함수가 존재한다.

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 17. The Ext2 Filesystem
차례
General Characteristics
Disk Data Structures
Memory Data Structures
Creating the Filesystem
Ext2 Methods
Managing Disk Space
Reading and Writing an Ext2 Regular File

General Characteristics
Ext2 file system의 기능:
Ext2 filesystem을 생성할때, block size를 선택할수 있다.(1024 ~ 4096)
Ext2 filesystem을 생성할때, inode 갯수를 선택할수 있다.(사용 가능한 disk 공간을 효율적으로 극대화)
Disk blocks들은 그룹화되어 있고 각 그룹은 data blocks과 inode포함한다.(평균 disk seek time이 작다.)
실제 사용되기 전 regular file에 대한 disk data block을 미리 할당(file fragment를 줄임)
Symblic link 제공
Systme crash시 영향을 최소화 하기 위해 신중한 file-updating stategy 수행.
Boot시 filesystem 상태를 자동 검사 (/sbin/e2fsck)
변경할수 없는 file과 append-only file 지원
새로운 file에 대한 Unix System V R4와 BSD의 Group ID 의미 호환.
Disk Data Structures
Figure 17-1. Layouts of an Ext2 partition and of an Ext2 block group
Block group내의 각 block은 다음 정보중 하나를 가지고 있다.
Filesystem's superblock
Block group descriptors
Data block bitmap
inode bitmap
Data block
Super block과 Group descriptor는 각 block group에 존재하지만 kernel은 block group 0에 있는 것만 사용.
/sbin/e2fsck 에서 group 0에 있는 super block과 group descriptor가 손상되었을때 다음 block group에 있는 걸 사용해 복구.
Superblock
ext2_super_block structure에 존재(Table 17-1. The field of the ext2 superblock)
Group Descriptor and Bitmap
Table 17-2. The field of the ext2 group descriptor.
Inode Table
Table 17-3. The fields of an ext2 disk inode.
How Various File Types Use Disk Blocks
Regular file
Directory : data block은 ext2_dir_entry_2 structure를 가진다.(Table 17-4. The fields of an ext2 directory entry
Symbolic link :
Device file, pipe, and socket : data block이 불필요..
Memory Data Structures
효율적인 사용을 위해서 ext2 partition에 있는 disk data structure에 저장 되어 있는 대부분의 정보들은 file system이 마운트 될때 RAM에 복사된다.
Ext2 disk data structure를 최신으로 유지하기 위해 buffer cache사용.
The ext2_sb_info and ext2_inode_info Structure
Ext2 filesystem이 mount될때, VFS superblock의 u field는 ext2_sb_info type의 구조체로 load.
Ext2 file과 관계된 inode object를 초기화할때는 ext2_inode_info 구조체로 load.
Bitmap Caches
모든 bitmap을 Memory에 유지하는 것은 비효율적.
2개의 EXT2_MAX_GROUP_LOADED 크기의 cach에 각각 최근에 사용된 inode bitmap과 data bitmap을 cach.
LRU policy 사용
Figure 17-4. Ext2 memory data structures
Creating the Filesystem
/sbin/mke2fs에 의해 생성.
위 program은 다음의 동작을 수행.
superblock과 group descriptor 초기화.
Defective block 검사, 발견되면 list를 만듬.
각 block group에 super block, group descriptor, inode table 그리고 2개의 bitmap이 저장될 disk block을 예약.
각 block group의 inode and data bitmap을 0 으로 초기화.
inode table 초기화.
/ root directory 생성.
lost+found directory 생성.
inode bitmap과 data bitmap update (/, /lost+found가 생성 됐으므로)
Defective block이 있으면 /lost+found directory에 그룹화 시켜 놓는다.
Ext2 Methods
Ext2 Superblock Operations
Super block methods의 주소는 ext2_sops의 포인터 배열에 저장되어 있다.
Ext2 Inode Operations
Table 17-8. Ext2 Inode operations for regular and directory files
Ext2 File Operations
Table 17-9. Ext2 file operations
Managing Disk Space
Inodes와 data blocks을 할당 해제 하는 방법에 대해 알아 보자.
Space management에서 반드시 고려해야 할 2가지의 주요한 문제.
File fragmentation
Time-efficient
Creating Inodes
ext2_new_inode()
다음의 동작을 수행.
get_empty_inode()
lock_super()
새로운 inode가 directory인지 파일인지 판단. 각 block group에 할당.
load_inode_bitmap()
disk inode 할당.
bg_free_inode_count 감소, bg_used_dirs_count 증가.(in block group descriptor)
s_free_inodes_count 감소.(in disk superblock)
Inode object fields 초기화.
새로운 inode object를 inode_hashtable에 삽입.
mark_inode_dirty()
unlock_super()
새로운 inode object의 주소 반환.
Deleting Inodes
ext2_free_inode()
다음 동작을 수행.
lock_super()
Inode number와 inode갯수를 계산.
load_inode_bitmap()
clear_inode()
bg_free_inodes_count 증가. bg_used_dirs_count 감소.
s_free_inodes_count증가.
inode bitmap에서 그 disk inode에 해당하는 bit를 clear.
unlock_super()
Data Blocks Addressing
Data block은 file내에서의 상대 위치(file block number)나 disk partition내에서의 위치(logical block number)에 의해서 참조된다.
file block number와 logical block number를 연결해주는 mapping할수 있는 함수를 제공.
Figure 17-5. Data structure used to address the file's data blocks
i_block(in the disk inode)은 logical block number를 가지는 EXT2_N_BLOCKS의 array.(즉 file의 data blocks수를 나타냄)
File Holes
Regular file에서 NULL값을 갖는 부분. disk의 data block에 저장되지 않는다.
Disk space 낭비를 막기위해 사용
Allocationg a Data Block
ext2_getblk() -> ext2_alloc_block()
Ext2 filesystem은 data blocks의 preallocation을 수행 (요청한 block보다는 최대 8개의 인접한 block을 얻는다.)
ext2_getblk()은 goal parameter(logical block number)를 다음 방법에 의하여 설정한다.
만약 block이 할당되어 있거나, 전에 할당된 것이 연속적인 file block number를 가진다면 goal은 전 block의 logical block number + 1
만약 첫번째 방법이 적용되지 않고, 적어도 하나의 block이 file에 전에 할당되었다면 goal은 이러한 block의 logical block number중의 하나이다.
위 방법이 적용되지 않는다면, goal은 block group의 첫번째 block의 logical block number이다.
ext2_alloc_block()은 이 goal이 이미 file에 할당된 block을 참조하면 그것의 logical number를 반환하고. 그렇지 않다면. ext2_new_block()호출.
Releasing a Data Block
ext2_free_blocks()
Reading and Writing an Ext2 Regular File
generic_file_read()
ext2_file_wirte()
Ext2's write는 다음의 동작을 수행.
File에 대한 superuser privilege 제거.
file이 O_APPEND flag를 가지고 열렸다면, 파일끝은 offset으로 설정.
O_SYNC flag 가지고 열렸다면, i_osync set
File offset, filesystem block size, file block number, block내에서의 상대 offset을 계산.
ext2_getblk() -> ll_rw_block() ->update_vm_cache() -> ll_rw_block()
Updates the i_size field.
i_ctime과 i_mtime을 xtime.tv_sec으로 설정. inode를 dirty로 marks.
Updates the variable *ppos.
File에 기록한 byte수를 반환.

Understanding the Linux Kernel :
이 문서는 Understandig the LINUX KERNEL by Daniel P. Bovert & Marco Cesati의 책을 내부 세미나를 위해 요약한 내용입니다.
Chapter 18 . Process Communication
차례
Introduction
Pipes
FIFOs
System V IPC
Introduction
User Mode process는 그들 사이에 동기화 할 수 있고 데이터를 서로 교환할 수 있다.
VFS에서 lock과 unlock을 이용해서 프로세스간 통신을 하며 동기화 한다.
Unix kernel은 시스템 콜의 집합이 있어서 파일시스템의 고려 없이 프로세스간 통신을 할 수 있다.
Pipes and FIFOs(named pipes)
Semaphores
Messages
Shared memory regions
Pipes
Pipes
Unix 의모든특징을제공하는프로세스간통신메커니즘이다.
Pipe 는프로세스사이의단방향흐름이다.
$ ls | more = $ ls > temp
$ more < temp
장점
Shell 문장이작고간단해진다
Temporary regular files 을생성시키고후에삭제시킬필요가없다.
Using a Pipe
Pipe(file descriptor1, file descriptor2)
=read(file descriptor1)+write(file descriptor2)
POSIX
Half-duplex pipes : 2 file descriptors
System V Release 4
Full-duplex pipes
Linux
각 pipe 의 file descriptor 는여전히 one-way 이지만,다른것을사용하기전에그들중하나를 close 할필요가없다.
Ls | more
Pipe() : 3, 4 àFork() àClose()
Ls
Dup2(4,1) àClose() : 3, 4 àExecve() : /bin/ls
More
Dup2(3,0) à Close() : 3, 4 àExecve() : /bin/more
Pipe Data Structures
Race conditions
커널은 pipe buffer 에동시접근하는것을금지한다.
Pipe_inode_info data structure 의 Lock 을사용
Creating and Destroying a Pipe
Pipe 는 disk image 와는다른 VFS객체의집합으로구현된다.
Pipe() à sys_pipe() à do_pipe()
Reading from a Pipe
Pipe_read()
Pipe size가 0일때, Return하거나 다른 프로세스가 pipe에 어떤 데이터를 쓸 때까지 기다릴지를 결정
Pipe_inode_info data structure의 Lock 필드를 체크한다.
만약 null이 아니면 다른 프로세스는 현재 pipe를 접근하는 중이다.이 경우, 현재의 프로세스를 지연시키거나 즉시 system call을 종료한다.

Lock field를 증가한다.
필요한 byte수를 Pipe버퍼로부터 사용자 주소 공간에 copy한다.
Lock field를 감소시킨다.
Pipe wait queue에서 잠자는 모든 프로세르를 깨우기 위해서 Wake_up_interruptible()을 발생시킨다.
사용자 주소공간에 copy된 Byte 개수를 리턴한다.
Writing into a Pipe
Pipe_write()
Pipe 가적어도하나의프로세스를읽었는지체크
Pipe inode 의 I_sem세마포어를 release 한다.
쓰여진바이트수가 pipe 의버퍼크기안에있는지체크
맞다면, operation 은 atomic 이어야 하고버퍼가모든 byte 를쓰기에충분한공간이있는지체크한다.

만약버퍼크기보다크다면, operation 은 free space 만큼만쓴다.따라서적어도 1 free byte 가있는지체크한다.

만약버퍼가충분한공간이없고 write operation 이 blocking 이면 pipe 의 wait queue 에현재프로세스를삽입하고,몇몇데이터가파이프로부터읽힐때까지 suspend 된다.
Pipe_inode_info data structure의 lock field를 체크한다.
만약 null이 아니면, 다른 프로세스는 현재의 파이프를 읽는 중이다. 따라서 write operation이 blocking인지 nonblocking에 따라 현재의 프로세스를 suspend하거나 write를 즉시 종료 시킨다.

Lock field를 증가시킨다.
사용자 주소공간에서 Pipe buffer로 요구된 byte수만큼 copy한다.
요구된 모든 데이터가 쓰여졌다면 lock field를 감소시킨다.
Pipe wait queue에서 잠자는 모든 프로세스를 깨우기 위하여 Wake_up_interruptible()을 호출한다.
I_atomic_write 세마포어와 얻어진 I_sem 세마포어를 release시킨다.
Pipe buffer에 쓰여진 byte의 수를 리턴한다.
FIFOs
Pipe의 장점
Simple
Flexible
통신 매커니즘의 효율성
Pipe의 단점
이미 존재하는 pipe에 대해서는 open할 방법이 없다.
이것은 임의의 두 프로세스가 같은 조상의 프로세스로부터 pipe가 생성된 것이 아니라면, 같은 pipe를 공유하는 것이 불가능한 것을 의미한다.
해결(special file type)
Named pipe or FIFO
FIFO files
Device file 과유사
,Disk inode 를가지고있으나, Data block 를사용하지는않는다.
,Disk inode 로어떠한프로세스라도접근할수있다.
FIFO 의장점
FIFO filename 은 system 의디렉토리트리에포함된다.
FIFO 는두개이상의프로세스에의한 data교환을임시로저장하는 kernel buffer 를포함한 unnamed pipe 와유사하다.
Kernel buffer 를사용하기때문에 FIFO 는 temporary files 보다효율적이다.
Creating and Opening a FIFO
프로세스는 Mknod() system call에 의해서 FIFO를 생성한다.
Linux에서는 FIFO를 사용하기 위하여 POSIX의 Mkfifo()를 사용한다.
생성된 FIFO는 open(), read(), write(), close() system call에 의해서 접근될 수 있다.
Open()
POSIX에서 named pipes를 호출
I/O 연산과 다른 프로세스가 FIFO 접근에 따른 접근 타입에 의존적
Process가 reading, writing, reading이나 writing 할 때, FIFO를 open한다.
System V IPC
Interprocess Communcation
세마포어에 의하여 다른 프로세스로 자신을 동기화
다른 프로세스 혹은 자신에게 메시지를 받거나 보냄
다른 프로세스와 메모리 영역을 공유
IPC data structure
프로세스가 IPC resource(a semaphore, a message queue, shared memory segment) 를요청할때,동적으로생성된다.
이때, IPC resource 는프로세스에의해 released 되지않는다면메모리에유지된다.
32-bit IPC key
프로세스가 같은 타입의 IPC resource를 요청하기때문에, 각각의 새로운 resource는 시스템 directory tree와 비슷한 file pathname인 32-bit IPC key에 의해 식별된다.
IPC resource
file descriptor와 유사한 32-bit IPC 식별자를 가진다.
IPC 식별자
커널에 의해 IPC resource에 할당되고, IPC key가 프로그래머에 의해 free될 때까지 system에서 유일하다.
두개 이상의 프로세스가 IPC resource간 통신을 원할 때, resource의 IPC 식별자를 참조한다.
Using an IPC Resource
IPC resource는 semaphore, message queue, shared memory segment를 바탕으로 semget(), msgget(), shmget()과 같은 함수 발생에 의해 생성된다.
성공 : positive IPC identifier
실패 : Table 18-6. Error Codes Returned While Requiring an IPC Identifier
잘못된 자원을 참조하는 것을 최소화 시키기 위해서, 커널은 free되는 것 만큼 빨리 IPC식별자를 recycle하지 않는다.
대신 자원에 할당된 IPC식별자는 이전에 할당된 같은 타입의 자원보다 항상 크다.
IPC Semaphores
커널 semaphore와 매우 유사하며, Multiple process를 공유데이터 구조에 접근하고 제어하는데 counter를 사용한다.
만약 protected resource가 존재
semaphore는 양수

만약 protected resource가 현재 존재하지 않을때
Semaphore는 음수 혹은 0

자원에 접근하기를 원하는 프로세스는 세마포어 값이 1 감소된다.
이것은 만약 이전의 값이 양수였다면, 자원을 사용하는 것을 허락한다.

그렇지 않으면 세마포어가 양수가 될 때까지 프로세스는 기다린다.

프로세스가 protected resource를 내어 주었을 때, 세마포어 값은 1 증가한다.
이렇게 다른 프로세스는 세마포어가 깨어나기를 기다리게 된다.

IPC Semaphores
Undoable semaphore operations
프로세스가갑자기종료됐을때,시작된작업을 undo할수없다.
따라서 undoable선언을통해서커널지속적인상태의세마포어를리턴하게한다.
프로세스는 semop() 의 SEM_UNDO flag명시에의해 undoable 작업을요구할수있다.
IPC Messages
프로세스는 IPC messages를 이용해서 서로 통신할 수 있다.
프로세스에 의해 발생된 각 메시지는 다른 프로세스가 그것을 읽을 때까지 IPC message queue에 보내어 진다.
메시지의 구성
고정된 크기 : header
변수의 길이 : text
프로세스가 IPC message queue로부터 메시지를 읽으면, 커널은 그것을 destroy 시킨다.
따라서 단지 하나의 프로세스만 주어진 메시지를 받을 수 있다.
Msgsnd()
Msgrcv()
IPC Shared Memory
Shared memory segment 에서일반적인데이터구조에접근하는두개이상의프로세스를접근하게한다.
Shared memory segment 에포함된 data structure 에접근하기를원하는각프로세스는새로운메모리주소공간에추가해야된다.
이러한페이지프레임은요구페이징을통해쉽게커널이핸들링할수있다.
IPC Shared Memory
Demand paging for IPC shared memory segments
Shmat()에 의해 process에 추가된 페이지는 dummy page이다. 이 함수는 프로세스 주소 공간에 새로운 메모리 영역을 추가한다.
그러나 프로세스 페이지 테이블을 수정하지는 않는다.
따라서, 프로세스가 shared memory segment에 접근하려고 할 때, 페이지 폴트가 발생한다.
예외 핸들러는 faulty 주소가 프로세스 주소 공간 내부에 있는지, page table entry가 null인지를 결정하고, do_no_page()가 발생한다.
이 함수는 nopage method가 메모리 영역에 정의되어 있는지를 체크한다.
이 method가 실행되고 Page Table entry가 return된 주소로 설정된다.