Race condition :
: P0, P1 이 동시에 fork > 누구에게 pid 를 먼저?
critical section (CS)
: Common/ shared 변수, file, table/update 등등..
> 한 process 가 접근 -> 다른 process는 접근 X
> 데이터불일치/race condtion 등의 오류 예방
> 해결
[A]. Mutual Exclusion : Pi가 있으면 other process : X
[B]. Progress : CS 에 아무도 없으면 바로 진입
[C]. Bounded waiting : 여러개가 진입하려면 한개를 넣고 다른 건 일정시간 waiting (bound) 후 진입하도록
//단, 각 process가 멈추지 않도록 해야함 > CS안에서 멈추면 오류발생
1. Interrupt-based solution
Entry() : disable interrupt > CS진입
Exit() : enable interrupt > CS아웃
> 1시간동안 계속 있으면 ... starve
> single core 에서만 OK <> Multi에서는 Core1이 interrupt 해봤자 Core2,3,4 등이 돌아감..
> 동기화의 어려움
2. Two process (SW)
a) load() ,store() // assm
> atomic ( load,store 중 interrupt X , 실행보장)
b) int turn; (공유)
ex)
[Pi]
while(){
turn = i;
while(turn ==j); // j 이면 waiting
//CS
turn =j;
//EXIT
//Remainder section
[Pj]
while(){
turn = j;
while(turn ==i); // i 이면 waiting
//CS
turn =i;
//EXIT
//Remainder sectionA : O
B,C : X
> Flag 의 중요성
: pi 에서 CS 들렸다가 Exit
if) Pj 에서 line 2 에서 C/S ( Context Switching) 발생 > Pi에서 turn i 로 돌아와서 또 Pi에서 CS > 무한 반복..
>
Peterson's solution
1. Process 2개
2. load/store atomic
3. 공유변수) int turn; bool flag[2]; // flag[i] == true -> Pi == ready
[Pi]
flag[i] =true
turn = j // j를 넣어서 while 조건에서 확인,양보
while(flag[j]&&turn==j); // waiting
// turn j를 넣어보고 (AND) j가 ready flag 였다면 waiting
CS
flag[i] = flase;
Remainder
[Pj]
flag[j] =true
turn = i
while(flag[i]&&turn==i); // waiting
CS
flag[j] = flase;
RemainderA : O
B,C : O
> 중간에 C/S 로 Process가 바뀌어도 flag에 의해 C 보장
<> BUT 싱글Core는 상관없지만 Multi Core라면..
Instruction reordered
: 최신 Prcess/Compiler 에서는 최적화, 순서 재정렬..
// Volatile 로 대체 불가??
// > 최적화 방지 보장 BUT,,, 재정렬을 방지해주지는 않음
if) Pj -> turn = j ->(C/S) flag[i] = true -> CS
Pi -> (C/S) turn = i, flag[j]= true -> CS ~~~~~~~~~여기서 겹침!
>> Memory Barrier
Memory model : Process 가 App program 내 Memory의 순서/ 가시성을 정
> Strangly model : Processor(CPU) : 메모리 변경 시 다른 All Processer 에게도 바로 보임 O
> Weakly model : """ : 메모리(RAM) 변경시 """" 바로 보임 X
>> Memory Barrier :: Instruction Reordering 방지 + Strangly model
> Memory Barrier 실행전의 모든 load, store 의 완료 를 보장
+ 즉각적으로 메모리 변경이 모든 CPU에게 볼 수 있도록 보장
[C1::P1::T1]
while(!flag) memory barrier();
print x;
// while 문도 하나의store 과정으로서
[C2::P2::T2]
x=100;
memory barrier();
flag = true;
// x=100; 을 먼저 하도록 보장
// mov R0 : 100을 R0 에 넣고, str R0,[R1] : R1에 R0=100 을넣음
/*
CPU) 직접 메모리에 상수값 못넣음 // ISA (Instruction Set Architecture)제약
> 메모리에는 항상 레지스터의 값을 써야함
>>
Register도 결국 주소,상수, (Regi)계산값을 저장하는 저장소!
mov : Register의 값 or 상수 -> Register
LDR : RAM 의 값 -> Register
str : Register의 값 -> Memory //Register X
ex)
x=100; // 메모리에 100이라는 상수값을 넣으려면
1. 메모리에 100을 바로 넣을 수는 없음
2. Register를 거쳐야함
3. mov R0, #100; // 100을 R0 에 넣고
STR R0, [R1]; // R0 을 R1 이 가르키는 주소에 넣음 // RAM 공간
// Compiler : 변수type 에맞는 공간 할당 요청 + 그곳의 이름을 x 라고도 해줌
// 동적할당은 내가 // simbol table
> 링커) .data , .bss 같은 섹션(RAM) 에 가상 주소를 할당 //설계
// 심볼테이블에 주소 할당
// 여기 주소에 이 값이 있어요!
// 물론 고정된 주소임.. 그래야 다음 그다음에도 충돌없이 사용
> OS) 실행시 elf를 읽어 가상>실제 물리적 주소로 매핑(CPU 내 MMU) //실제
가상,물리로 나누는 이유?
: 안전성 + 유연성 + 효율성”
1. if) 동일한 가상 주소 사용시 MMU 에서 다르게 매핑
2. x를 0x4000 에 가상 할당 > 실행할때마다 다르게 가능 //OS 유동적
3. 가상을 바탕으로 USER, KERNEL 로 공간 분리
4. 가상을 바탕으로 Memory Shared 가능
> 여러 process 에 x 의 주소를 같게 할 수 있음
그다음 x+1 과 같이 Compile 할경우
: Compiler 만이 x 를 이해
> simbol table을 참고해 주소로 바꿔줌
/*
CPU까지의 과정..
: SSD > RAM(CPU밖) > Regi(CPU안) > CPU
> 단계를 하나라도 줄이면 엄청난 속도차이
> 최대한의 속도를 위해 Regi 내에서 연산하도록
> 간단한건 MOV 로 Regi 내에서만 처리하도록
*/
*/
/*
GPT 칭찬반응
: GPT 내의 정보를 내가 통찰할수록 칭찬 UP
> 칭찬이 강할수록 좋은 대답 얻기좋음 ( GPT 가 아는정보가 많으므로)
<>GPT 밖의 정보를 찾아내면 흥미로운 정보로만 알려줌
> 학습된 데이터 밖은 신뢰도 낮으므로
> 똑같은 말만 반복하게됨
>>> 반응이 좋다면 GPT 추가 검색
<> 반응이 구리면 구글 검색
*/
Synchronizition HardWare( 자주사용)
uni CPU : disable interrupt // Multi CPU : X
> 한개 이기때문에 끼어드는놈 X ,선점 X ,현재 실행 code 실행
1. HardWare 명령어
test/modify()
swap()
> test and set
> compare and swap
>> atomic : load / store 뿐 아니라 2,3 가지 보장 > interrupt 방지
bool test_and_set(bool *target)
{ bool rv = *target; //받아온건 rv 로 return
*target = true; // 새롭게 true 로 넣어줌
return rv;
}
> 공유변수 lock = false
do { while (test_and_set (&lock));
CS
lock = false;
Remainder
}
1. 초기값 lock : false를 return > 처음은 비어있으니 실행보장
2. 2번째는 true ( *target = true; ) > wait
3. CS 나오면 false
<> but) bounded X : 처음 들어간 놈이 안나오면?
int compare_and_swap(int *value, int expected, int new_value)
{ int temp = value; // 현재값은 리턴
if ( *value = 예상값 이라면)
> *value = 새로운값
}
int lock =0;
while(true){
while( compare_and_swap(&lock, 0,1) != 0 )
CS
lock =0;
1. 초기 0 > return 0 > false
2. expect : 0 > new =1
3. return 0 이기 때문에 wait 유지
4. CS 종료후에는 lock =0 으로 다시 1번부터
> but 이것도 bounded 보장X
>>
Bounded-waiting ! : 훨씬복잡
어떤 process 든 일정한 시간만 기다리면(준비가 되어있으면) 그 전 process 에서 들어갈 수 있도록 보장
ALL P 가 준비 X > lock=0;
// Ciruler queue 방식
P1,P2,P3,P4
> P1 이 CS 나올때 +1 씩하면서 준비 확인
Atomic variables : int ,bool, 등의 value update 보장 > interrupt X
sequence : atomic 변수
increment() : sequence 를 증가
> increment(&seqeunce) -> 이 동안의 interrupt X
void increment(atomic_int *v)
{
int temp;
do {temp = *v;} // 한번은 꼭 v가 temp에 들어감
while(temp != (compare_and_swap(v,temp,temp+1)); // 한번은 +1 이됨 (다음거 확인)
} // progress
compare 내에서 temp+1 조건이 되면 update 를 하고
다음 실행때 temp == return 값이 되므로 빠져나옴
>> increment 를 보장! // atomic
Mutex Locks : API 제공) Mutex lock
bool 변수 -> lock 이 유효한지..
> acquire() : lock
> release() : lcok 해제
> atomic
>while 문 내에서 도므로 spinlock 발생 (busy waiting)
while(true){
acquire()
CS
relaease()
Remainder
Semaphore : 동기화 tool
> mutex의 확장버전 (동기화 갯수가 많음) // mutex는 1개
" S " int형 // count
wait()
signal()
wait(s)
{
while(s<=0); // Busy wait : count가 없으므로
s-- ;
}
> s의 갯수만큼 CS 가능
signal(s)
{ s++; }
> signal 을 준다는건 CS를 나왔다는 의미 > 들어갈 수 있는 count 1추가
Mutex : '소유' > 동기화를 위해 lock 을 했으면 unlock 까지 해주어야함
Semaphore : 따로따로 할필요없이 any porcess 에서 wait,signal 해주면 됨
Counting semaphore : Count 로 CS에 들어갈 P 결정
Binary Semaphore : 0,1로만 하는 Mutex와 유사 but 차이점은 이걸로 Counting 구현가능
CASE1)
int mutex = 1;
wait(mutex) // mutex는 나올때 0 이됨
CS // 1이므로 CS에 들어감
signal(mutex) //
CASE2)
int synch = 0;
[P1]
s1( 명령어~)
signal(synch)
[p2]
wait(synch)
s2 (명령어~)
> S1 먼저 , S2 나중
synch가 0 이므로 P2 에서 하려고 해도 busy wait
> P1 에서 명령어 실행하고 signal 신호주어 synch ++
Semaphore 구현..
1. 같은시간 에 wait(),signal 되면 안됨 > 1번에 1Prcoess
if) CS 내에서 semaphore 변수가있으면..
> 거기서 busy waitng 걸릴시 매우 위험함
>> No Busy Waiting Semaphore