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
문제2) Multi에서는 Core1이 interrupt 해봤자 Core2,3,4 등이 돌아감..
> 동기화 어려움
2. Two process (SW)
a) load() ,store() // assm
> atomic ( load,store 중 interrupt X , 실행보장)
b) int turn; (공유) //CS 에 진입후 값 변경
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 의 중요성
: 아무때나 C/S 를 하면 둘다 waitting 걸림
>
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라면 소용X
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 내 Memory의 순서/ 가시성을 정함
> Strangly model : Processor(CPU) : 메모리 변경 시 다른 All Processer 에게도 바로 보임 O
> Weakly model : """ : 메모리(RAM) 변경시 """" 바로 보임 X
>> Memory Barrier :: Instruction Reordering 방지 + Strangly model
> Memory Barrier 실행전의 모든 load, store 의 완료 를 보장 // atomic
+ 즉각적으로 메모리 변경이 모든 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의 값/상수 -> 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) 에 가상 주소를 할당 //설계
// 심볼테이블에 변수의 주소만 할당
// 그 변수의 공간은 아직X
> OS) 실행시 elf를 읽어 가상>실제 물리적 주소로 매핑(CPU 내 MMU)
// 실제 주소에 공간 할당
가상,물리로 나누는 이유?
: 안전성 + 유연성 + 효율성”
1. 실수로 동일한 가상 주소 사용시 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 1 이기 때문에 wait 유지 // 0이아니면 while문 true
4. CS 종료후에는 lock =0 으로 다시 1번부터
> but 이것도 bounded 보장X
>>
Bounded-waiting ! : 훨씬복잡
: 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 이됨
// temp에 v 값을 넣어놨으므로
}
>> increment 를 보장! // atomic
Mutex Locks : API 제공) Mutex lock
bool 변수 -> lock 이 유효한지..
> acquire() : lock 하고 CS acquire
> release() : lcok 해제
> atomic
>while 문 내에서 lock 을 얻기위해 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) //wait 함수 나올때 mutex-- 하고
// mutex<0 이므로 다른놈들 lock
CS // CS 후에
signal(mutex) // 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