race condition : 초기값이 5일 때, 동시에 접근 시 Producer는 5 > 6, Consumer는 5 > 4로 Counter 값을 바꾸므로 결과적으로 카운터값이 6>4로 변경될 가능성 존재
fork()의 race condition
fork 실행 시 반환값은 PID
두 프로세스가 동시에 fork 호출 시 같은 PID를 갖는 두 프로세스가 생성될 수 있음
/* Producer Process */while (true) {
/* produce an item in next produced */while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = next_produced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
/* Consumer Process */while (true) {
while (counter == 0)
; /* do nothing */
next_consumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
/* consume the item in next consumed */
}
Critical-Section Problem
다수의 프로세스/스레드 생성 시 한 번에 하나의 작업만 실행될 수 있는 구간
공용 데이터 접근시의 충돌 방지
do
{
/* Ask Permission to enter critical section *//* Critical Section *//* Exit Critical Section */
...
}while(...);
Critical Section 문제의 해결 조건
Mutual Exclusion : 프로세스 P가 Critical Section에 접근 시 다른 프로세스는 해당 구간을 실행하면 안됨(Critical Section의 정의)
Progress : Critical Section에 실행 중인 프로세스가 없을 경우, 이 구간에 진입하고자 하는 프로세스를 지연 없이 진입시켜야 함
Bounded Waiting : 프로세스 A가 Critical Section에 있을 때, 새 프로세스가 진입하고자 할 경우 A가 끝나는 것을 대기해야 하나, 무한정 대기해서는 안됨 (Critical Section 진입 시 우선순위의 조정 필요)
OS의 Critical-Section Handling : Non-Preemptive
인터럽트 없이 커널 설계
구현이 쉽고, 오류를 신경쓸 필요성이 낮아짐
공유 데이터 접근 시 우선한 작업이 처리되어야 나머지 처리가 가능하므로 시스템 반응성, 성능이 떨어지게 됨
busy wait : Critical Section에 접근하지 못한 나머지 변수들은 while loop를 돌면서 대기
spin lock : 무한루프를 돌면서 대기하는 형태(busy wait)
Semaphores
Mutex Lock의 경우 한 번에 하나의 프로세스만 Critical Section 진입
Semaphore의 경우 정수 변수 S 값의 설정에 따라 진입 가능한 프로세스 수 설정 가능
wait(S) : 대기 중인 프로세스 조정
signal(S) : 실행이 완료된 프로세스 release
자원 관리에 주로 사용
Busy wait이 없는 Semaphore
프로세스 sleep(), wakeup() 확인
wait : 프로세스 실행이 불가능한 경우 프로세스를 sleep queue에 추가 후 sleep
signal : 프로세스가 추가 실행이 불가능하면서 waiting중인 프로세스 존재 시 해당 프로세스 wakeup
프로세스 리스트 접근 시 mutex section 구현 필요
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
//add this process to S->list;
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
//remove a process P from S->list;
wakeup(P);
}
}
Monitor
mutex/semaphor의 고레벨 구현
monitor 내에 선언한 함수는 컴파일 단계에서 wait-signal이 구현됨
condition variable
변수에 여러 프로세스가 동시 접근 시 signal - wait 구현
Liveness
Progress, Bounded Waiting으로 보장
프로세스가 일정 시간 내에 실행되는 것을 보장
보장되지 않을 경우 알 수 없는 이유로 시스템이 멈추는 등의 문제 발생
Deadlock
둘 이상의 프로세스가 서로의 자원을 필요로 하는 상황
서로의 wait을 위해 서로의 자원을 필요로 하는 상황
P0의 Q wait을 위해서는 P1이 대기하는 Q가 필요
P1의 S wait을 위해서는 P0이 대기하는 S가 필요
Starvation
프로세스가 공유 자원(Critical Section, Semaphore, ...)을 무한히 대기하는 현상
pid t_pid; /* process identifier */long state; /* state of the process */unsignedint time_slice /* scheduling information */structtask_struct *parent;/* this process’s parent */structlist_headchildren;/* this process’s children */structfiles_struct *files;/* list of open files */structmm_struct *mm;/* address space of this process */
Process Scheduling
CPU 활용을 최대한으로 하는 것이 목적
Queue 자료구조를 이용하여 관리
Job queue : 시스템 내 모든 프로세스
ready queue : ready / waiting 상태의 프로세스
device queue
각 장치별로 queue head 존재
프로세스가 device 사용 요청 시 해당 queue에 PCB가 연결
프로세스의 동작 순서
생성된 프로세스는 ready queue로 할당
동작하는 프로세스는 CPU로 이동
I/O request 시 > I/O queue 할당 후 I/O 접근
time slice expire > ready queue 할당 후 CPU 할당
child fork / interrupt > 작업 후 ready queue 할당
scheduler
프로세스가 I/O를 많이 쓰는지, CPU를 많이 쓰는지를 판단(I/O bound, CPU bound)
short term(CPU scheduler)
현재 프로세스 바로 다음에 할당할 프로세스 선택
Long term(job scheduler)
데이터센터 등 대형 시스템에서 사용
다수의 작업을 모아서 한번에 효율적으로 처리
Context Switch
프로세스 상태를 저장하고 새 프로세스로 전환
상태를 저장 - 불러오고 새로 실행하는 과정의 overhead가 매우 큼
파일 입/출력을 많이 하는 프로그램이 느린 이유
Operations on Process
Process Create
부모 프로세스는 자식 프로세스를 생성
트리 자료구조를 형성
부모 프로세스는 자식 프로세스의 관리 가능(권한, 공유 등)
부모-자식 프로세스의 동시 동작시 대기 혹은 병렬 처리 가능
새 프로세스 생성 시, 부모 프로세스를 복사 후 프로그램 실행
UNIX의 프로세스 생성 명령어 - fork()
자식 프로그램은 exec()명령어로 프로그램 실행
부모 프로세스 wait : 자식 프로세스가 종료할 때까지 대기
Process Terminate
완료 시 exit 후 상태 데이터를 반환
자원을 과도하게 사용하는 등 프로세스 종료가 필요할 경우 abort()도 가능
cascading termination : 부모 프로세스가 먼저 종료시 하위 프로세스도 종료
자식 프로세스가 사라져도 자원 회수 등을 위해 PCB는 여전히 존재
부모 프로세스는 wait()으로 exit될 때까지 대기해야 함
wait 없이 프로세스 종료 시 : Zombie Process
wait 없이 부모 프로세스 종료 시 : Orphan Process
interprocess communication
프로세스 간의 정보 교환
교환 모델
message passing : 커널에서 제공하는 메세지 큐를 이용한 정보 교환
shared memory : 프로세스 간 공유 공간 할당
Producer-Consumer Problem
데이터의 생산자(Producer)와 소비자(Consumer) 관계
버퍼를 한정할지(bound), 안할지(unbound)의 문제
Shared memory
통신하고자 하는 프로세스 간에 공유하는 메모리
OS가 아닌 사용자 level에서 통신 조절
같은 메모리에 다른 프로세스가 동시에 조작 시 문제 존재
프로그래밍이 어려우나
Message Passing
send / receive를 이용하여 프로세스 간에 데이터 전송
프로세스 간의 링크 설정 필요
2개 이상의 프로세스 연결 / 통신 방향(단방향, 쌍방향) 등을 고려
direct Communication
데이터를 받을 프로세스 명시 send/receive(process, message)
pid가 바뀔 경우 접근 불가
Indirect Communication
mailbox(port)를 이용한 데이터 공유
같은 process 연결에서 여러 개의 link 형성 가능
mailbox 생성 > 데이터 교환 > mailbox 삭제 과정으로 진행
Synchronization
Blocking : 데이터 송신 / 수신 중 한쪽이 끝날때까지 다른쪽은 불가
non-blocking : 송/수신에 제한 x, 오류 방지를 위해 데이터가 없는 경우 return 등으로 다른 행동을 하기 위한 별도 조치 필요
