Think Positive!

S-DES.exe

정보보안 과제로

C언어로 만든 암 복호화 시뮬레이터 ^^

콘솔창이긴 하지만 제법 볼만하게 만들었당.. ㅋ

앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고, bakery 알고리즘 에서는 N개 이상의 프로세스의 상호 배제를 티켓과 프로세스 번호를 이용하여 구현 하는 방법 이다. 이번 Test-and-set 을 이용한 상호 배제는 atomic function 을 사용해서 함수의 조건을 비교 할 때엔 한 프로세스가 점령을 하면 다른 프로세스가 개입을 할 수 없도록 선점해서 사용하는 개념으로 상호 배제를 하는 기법 이다.

알고리즘

Jbaci로 구현한 소스코드

const int TRUE = 1; //TRUE 를 1로 정의

const int FALSE = 0; //FALSE 를 0으로 정의

const int PCOUNT = 5; // process 의 개수 정의.

int lock = 0; // 공용 lock 변수.

int waiting[PCOUNT]; //프로세스 번호가 가까운 사람에게 자리를 주기위하여 waiting배열 선언.

int n; // 연산을 위한 공용 변수 n

atomic int Test_and_set(int& loc) // atomic 함수로 함수에 진입하고 나면 다른 프로세스가 간섭 할수 없다.

{ // 인자 값을 &를 써서 주소 값으로 받은 이유는 공용변수 lock 을 직접적으로

int TAS; // 호출 할 경우 함수 밖의 값을 불러 오는 것이기 때문에 다른 프로세스의 간섭

TAS = loc; // 이 일어날 수 있다.

loc = TRUE; // lock 변수의 값을 다른 TAS변수에 저장하고 lock변수 안의 값을 1로 세팅을 한 //다.

return TAS; // 그리고 초기의 lock변수 의 값인 TAS의 값을 반환을 한다.

}

void enter_region(int i) //임계구역의 진입을 조건에 의해서 각 프로세스가 상호 배제가 되도록 하는 함수

{

int j; // for 문을 위한 변수

// int key = FALSE; // 키 값을 선언하고 초기화를 해준다.

// 현제 key 값이랑 밑의 와일문을 주석 처리 해놓았는데 이유는 아래 소스분석

waiting[i] = TRUE; //에서 설명 하겠습니다. waiting[]배열에 자신의 프로세스번호에 해당하는 곳에

// key = TRUE; // 값을 참으로 설정 한다.

while( (waiting[i]) && Test_and_set(lock) ) // 여기서 waiting값은 참이므로 뒤의 Test_and_set함수

{ //에서 참이 나오면 대기상태가 되고 거짓이 나오면

} //while 문을 통과하여 임계구역에 진입하게 됩니다.

// while( (waiting[i]) && key ) // 주석문은 원 알고리즘을 보고 처음 코딩했던 소스입니다.

// {

// key = Test_and_set(lock); //Test_and_set의 함수의 리턴 값을 담아 다음 조건에서 비교를함.

// }

waiting[i] = FALSE; // 임계구역에 진입 했으므로 waiting변수를 0으로 해준다.

// 변수를 0으로 해주는 이유는 leave_region에서 인근 프로세스에게

//임계구역을 넘겨줄 때 쓰임.

cout<<i<<" process is enter_region"<<endl; //프로세스가 들어왔다는 문구 출력

n=0; // 공용변수 n의 초기화

cout<<i<<" process's calculate start!"<<endl; // 프로세스 계산 시작 문구 출력

for(j=0; j<5; j=j+1) //1씩 더하는 연산

{ //여기서 간섭이 생긴다면 n이 공용변수이므로

n = n+1; //n의 값이 5가 나오지 않을 것임.

}

cout<<i<<" process's calculate result is "<<n<<endl; // 계산 결과를 출력하는 문구.

}

void leave_region(int i) // 일을 다 하고 임계구역을 나간후에 연산하는 함수

{

int j; //다른 프로세스 아이디를 담을 변수

j = (i+1) % PCOUNT; // 현재 프로세스에서 +1을 하고 전체 프로세스 수로 나누어 남은 값. 즉

// 현재 계산 하고난 다음번호의 프로세스 번호를 담음. ex) 0->1

while( (j != i) && !(waiting[j]) ) //j와 i가 같다면, 주변 프로세스 한 바퀴 검사 한 것이므로 더 이상

{ // 검색하지 않는다. 그리고 waiting에 0이 있다면 이미 실행한 프로

j = (j+1) %PCOUNT; //세스 이므로 다음 프로세스로 넘긴다 .

} // while 문장 안은 다음의 뒷 프로세스를 검색하는 것임.

if( j==i ) // 한 바퀴다 돌아도 임계구역에 들어갈 프로세스가 없다면

{ //lock 공용변수를 풀어주고 끝낸다.

lock = FALSE;

}

else //누군가 인접한 프로세스가 대기하고있다면 그 프로세스에게 먼저 기회를 준다.

{

waiting[j] = FALSE;

}

cout<<i<<" process is leave_region"<<endl; // 임계구역을 탈출했다는 문구

}

void process(int i) // thread

{

{

enter_region(i);

leave_region(i);

}

}

void main()

{

int i;

for(i=0; i<PCOUNT; i=i+1) // waiting배열을 초기화 함.

{

waiting[i] = FALSE;

}

cobegin // 병행으로 프로세스 5개를 실행함.

{

process(0);

process(1);

process(2);

process(3);

process(4);

}

}

baci에서 실행화면

Jbaci에서 실행화면

BaskinRobbins.exe

C언어로 작성 해보았던 베스킨 라빈스 31 게임이다.

31을 외치면 지는 게임으로, 컴퓨터가 좀 똑똑하다...

ㅎㅎ

운영체제 수업시간에 공부했었던 빵집알고리즘(Bakery Algoritm) 에 관한 설명이다.

내용

앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고 이번 bakery 알고리즘 에서는 N개 이상의 프로세스의 상호 베제 가 되도록 구현하는 방법이다. 간단하게 빵집 알고리즘을 설명을 하면 프로세스에 먼저 온 순서대로 번호표를 부여하고, 그 번호표가 우선인 프로세스부터 작업을 시켜주는 것이다. 만약 두 프로세스가 동시에 접근을 하여 번호표가 같아진다면, 프로세스 번호가 낮은 순서로 우선순위를 정하여, 상호간에 연산에 있어서 간섭이 일어나지 않도록 하는 방법이다.

다음은 알고리즘이다.

Jbaci를 이용해서 구현해본 소스코드이다.

const int TRUE = 1; // TRUE변수를 1로 상수화

const int FALSE = 0; // FALSE변수를 0으로 상수화

const int PNUM = 10; // 프로세스의 생성 개수를 상수화 하여 프로세스의 개수가 늘고 줆에 있어 이수치만 //수정하면 된다.

const int N = 5; //연산의 계산을 하기위한 상수

int n; //공용 변수

int number[PNUM]; //프로세스의 티켓의 값을 저장할 배열

int choosing[PNUM]; //프로세스가 번호표를 뽑았는지 아닌지를 기억하는지를 저장할 배열

int MAX() //티켓을 나눠주는 함수. 티켓 이 저장되어있는 number배열의 값들을 조사하여서 가장

{ //큰 값을 반환하여 주는 역할을 합니다.

int i; // for문을 사용하기위한 변수

int j; // for문을 사용하기위한 변수

int MAXNUM = 0; //가장 큰 번호표를 담을 변수 초기값을 0으로 설정해준다. 아무도 번호표가

for(i=0; i<PNUM; i=i+1) // 없을시 0을 반환하기 위해.

{ // 프로세스의 개수만큼을 비교한다.

for(j=0; j<PNUM; j=j+1)

{

if(number[i]<number[j]) //2중 for문을 이용하여 각자리를 비교 하고,

{

MAXNUM = number[j]; //가장 큰값을 MAXNUM변수에 저장한다.

}

}

}

return MAXNUM; //MAXNUM 변수를 반환해준다.

}

int NUM(int j, int i) //각 프로세스의 티켓번호를 비교하여 결과값을 돌려주는 함수.

{

if(number[j] < number[i]) // i프로세스가 현제 실행하는 프로세스 이므로 i 프로세스의 티켓이

{ // 더 낮을 때 루프를 탈출해야 하므로 number[j]<number[i]조건에서 참

return 1; // 일때는 1을 리턴 해주어 대기하게 만든다.

}

else if(number[j] > number[i]) // 위와 반대로 i프로세스의 티켓이 더 작을 때는 while루프를 빠져나갈

{ //수 있도록 0을 리턴해준다.

return 0;

}

else // 그리고 나머지경우는 두 프로세스간 티켓번호가 같을때 인데,

{ //이렇게 번호가 같을때는 두프로세스의 번호를 비교를 한다.

if(j<i) // 역시 i 프로세스가 현제 실행하는 프로세스이므로 i 프로세스의

return 1; //번호가 더 높을 때는 대기 상태를 가져야 하므로 1을 반환해주고,

else if(j>i) // 번호가 더 낮을 때는 0을 반환해주어 while루프를 빠져나가도록

return 0; // 해준다.

}

}

void enter_bakery(int i) //빵집알고리즘의 시작

{

int j; // 현제프로세스와 비교할 다른 프로세스들의 번호를 지정할 변수.

int k; // 조건을 통과하여 프로세스가 일을 수행 할 때 계산연산 for문을 위한 변수

choosing[i] = TRUE; // 티켓을 받기 전 의 상태를 저장.

number[i] = MAX()+1; // MAX함수를 통해서 이미 발부된 티켓 중 가장 높은 값의 다음값을 받는다.

choosing[i] = FALSE; // 티켓을 받은 후 의 상태를 저장.

for(j=0; j<PNUM; j=j+1) //이for문으로 모든 프로세스 티켓 과 프로세스번호로 통과 가능한지를 검사함

{

while(choosing[j]) //이 while 문에서 프로세스가 티켓을 받았는지를 검사함.

{ // 티켓을 받지 않았으면 대기상태로 빠짐.

// cout<<j<<" Process is Waiting until get a ticket"<<endl;

} //출력문은 출력 할 때 출력창이 너무 지저분해져서 주석처리 하였습니다.

while( (number[j] != 0) && (NUM(j, i)) ) // 이 while 문에서 티켓의 번호를 비교 검사함.

{ // 혹시 티켓의 번호가 같다면 NUM 함수 안에서 프로세스 번호를 비교함.

// cout<<j<<" Process is Busy Waiting"<<endl;

} //이 출력문 역시 출력창이 너무 지저분해져서 주석처리하고 출력하였습니다.

}

cout<<i<<"process's tiket"<<number[i]<<endl; //현제 수행하고 있는 프로세스의 티켓번호를 출력

n = 0;

cout<<i<<" process is calculating.."<<endl; //1을 5번 더하는 연산을 함

for(k=1; k<=N; k=k+1)

{

n = n+1;

}

cout<<i<<" process's calculate result is "<<n<<endl; // 완료된 결과를 보여줌.

}

void leave_bakery(int i) //프로세스가 연산을 하고나면 Busy Waiting중인 프로세스를 풀어주는 함수

{

cout<<i<<" process is calculate complete"<<endl;

number[i] = 0; //연산을 다 한 프로세스의 티켓을 0으로 바꾸어주면 while문의 number[j] !=0

} // 조건에서 false가 되므로 Busy Waiting상태가 풀리게 됨.

void process(int process) //일꾼의 역할을 하는 스레드

{

enter_bakery(process);

leave_bakery(process);

}

void main() //메인 함수

{

int i;

for(i=0; i<PNUM; i=i+1) // 처음의 number[i]배열과 choosing배열을 초기화 합니다.

{

number[i] = 0;

choosing[i] = TRUE;

}

cobegin

{

process(3); //10개의 프로세스를 병행 수행합니다.

process(2);

process(1);

process(0);

process(4);

process(5);

process(6);

process(7);

process(8);

process(9);

}

}

운영체제 수업시간에 공부했었던 피터슨 알고리즘에 관한 내용이다.

내용

병행 프로세스에서 순서를 지켜서 프로세스가 연산을 할 때 경고 변수와 잠금 변수를 사용하여, 간섭이 일어나지 않도록 하기 위한 알고리즘을 소스코드로 구현합니다.

미리 한번 해보았던 예제 코드의 for문으로 변수의 값을 1씩 5번 증가 시키는 것을 사용하여, 프로세스가 연산하는 값들을 출력하게끔 구현 하여 보았다.

Jbaci를 이용하여 테스트한 소스코드

이전에 올려둔 jBaci 툴을 사용하는 방법을 정리 ㅎ

이전에 올려둔 jbaci파일을 다운 받아서 압축을 풀면 run.bat파일이 있다. 그 파일을 실행하면 CMD 창과 함께 다음과 같은 화면이 나온다.

 최초 실행화면  

여기서 에디트에다 테스트 소스를 다음과 같이 입력해본다.

cobegin 문은 병렬로 프로세스들을 실행할때 사용하는 구문이다.

작성이 완료 되었으면 저장을 하는데 저장 할 때, 파일명.cm으로 저장을 한다

저장이 된후에 컴파일 을 눌러주면 소스가 이상이 없을시 다음과 같은 문구가 와 CMD창에도 변화가 생긴다. 그리고 .cm이 있는 폴더에 파일명.lst와 파일명.pco 파일이 생성이 된다.

제대로 완료가 되었으면 Run 탭을 눌르면 다음과 같은 창이 나온다.

Go 버튼을 눌르면 실행이 되는데 옆에 Processes 탭에서 각 프로세스를 더블클릭하면 다음과 같이 각 프로세스별 상황이 다 출력된다.

참고 ) 디버그 하는방법

1.  Run화면에서 Step Pcdoe 를 눌르면 한스텝씩 계속해서 진행이된다.

2. Go를 누른후 Pause를 눌르고 Step Source를 눌르면 한스텝씩 진행이된다.

jbaci1-4-5.zip

baci 툴을 더 쉽게 사용할수 있도록 만든

Jbaci 툴입니다.

badosxe-2005Nov09.zip

BACI 툴 입니다. 운영체제 교육 자료

FND500 (캐소드) FND507(애노드) 방식 (FND : Flexible Numeric Display)

모든 LED의 공통단자가 VCC에 물려 있어 각 단자에 GND를 연결할 때 불이 들어오는 방식이 Common-anode 방식

anode를 검색해보면 양극 이라는 뜻이다. 즉, 공통단자에다가 양극(VCC)을 물리는 것이 anode방식이란 뜻

모든 LED의 공통단자가 GND 에 물려 있어 각 단자에 VCC를 연결할때 불이 들어오는 방식이 Common-cathode 방식

cathode를 검색해 보면 음극 이라는 뜻이다. 즉, 공통단자에다가 음극(GND)를 물리는 것이 cathode방식이란 뜻

헷갈리지 말자 ! ㅎㅎ

해밍코드_데이터전송값_구하기.exe

컴퓨터 구조론 시간에 했던.

해밍코드를 이용한 데이터 전송 비트 값을 구하는 프로그램

해밍 코드란?

해밍코드는 에러정정 코드(error correction code) 중 가장 간단한 형태의 코드로 한 비트에 에러를 검출하고 자동으로 정정까지 해주는 코드이다. 패리티 비트를 가지며 문자 코드의 경우 4개의 여분 비트를 가지고 있다.

관계식 (해밍 코드를 만드는식)

2의p승 >= m + p + 1

p : 페리티 비트의 수

m : 정보 비트의 수

페리티 비트 수는 각각 데이터 사이에 들어가서 전송중 애러가 있는지를 검출한다 2의 지수승 자리에 들어가서 검출함

2의 1승 2의 2승 2의 3승 2의 4승 .. 이런식으로 들어가므로

1번째자리 2번째자리 4번째자리 8번째 자리에 들어감

전송할 데이터가

1 0 1 1 0 1 1 1   이라면

관계 식에 의해서 m = 8 이되고 p 는 4가 된다. 

16 >= 8 + 4 + 1 이므로

여기서 이제 페리티비트수를 집어넣어주면된다

p1  |  p2  |  1  |  p3 |   0 |   1  |  1  |  p4  |  0  |  1  |  1  |  1    이렇게 p의 자리에 0과 1중의 숫자를 계산해서 넣으면 완료

여기서 짝수 페리티랑 홀수 페리티가 있는데, 두 페리티는 반대 개념이며, 짝수 페리티만 설명 해 보겠다.

p1  의 값은 1, 3, 5, 7, 9, 11, 13 번째 비트를 점검하여 1의 개수가 짝수 개가 되도록 하면된다.

여기서는 p1, 1, 0, 1, 0, 1 로써 p1을 제외 하고 1의 갯수가 3개 이므로 짝수 페리티비트를 만들려면  p1의 값이 1이 되어야한다.

p2의 값은 2, 3, 6, 7, 10, 11, 14 번째 자리를 점검하고

여기서는 p2, 1, 1, 1, 1, 1  14번자리는 없음

이므로 1이 5개가 되고 짝수페리트를 맞추려면 역시 p2가 1이 되어야 6개로 짝수개가 된다.

여기서 점검할 자리를 결정하는것은 2진수 의 비트수를 검사하는것인데

예제 데이터(p1,p2,1,p4,0,1,1,p8,0,1,1,1)의 순서로 보면

p1의 경우 1번째 자리이므로 이진수로 0001

p2의 경우 2번째 자리이므로 이진수로 0010

 1 의 경우 3번째 자리이므로 이진수로 0011

p4의 경우 4번째 자리이므로 이진수로 0100

 0 의 경우 5번째 자리이므로 이진수로 0101

 1 의 경우 6번째 자리이므로 이진수로 0110

 1 의 경우 7번째 자리이므로 이진수로 0111

p8의 경우 8번째 자리이므로 이진수로 1000

 0 의 경우 9번째 자리이므로 이진수로 1001

 1 의 경우10번째 자리이므로 이진수로 1010

 1 의 경우11번째 자리이므로 이진수로 1011

 1 의 경우12번째 자리이므로 이진수로 1100

이 된다. 여기서 p1을 결정할때 확인해봐야하는 요소는 이진수로 끝자리가 1인것,  p2를 결정할때 확인해봐야하는 요소는 이진수로 끝에서 두번째자리가 1인 것 p4를 결정할때 확인해봐야하는 요소는 이진수로 끝에서 3번재자리가 1인것 이런식으로 확인을 하면된다.

그렇게 해서 완성된 해밍코드는 (짝수페리티)

1(p)  1(p)  1  1(p)  0  1  1  1(p)  0  1  1  1

를 전송한다.

만약 전송비트가 위와같으나 수신비트가

1(p)  1(p)  1  1(p)  0  0(오류)  1  1(p)  0  1  1  1 

이렇다면 수신측에서 검사를 통하여 오류를 잡아낼수있다.

패리티 자리로 검사를 하는데

p1 = 1, 3, 5, 7, 9, 11 번의 자리의 1의 개수를 검사한다. 짝수개이므로 0

p2 = 2, 3, 6, 7, 10, 11번의 자리의 1의 개수를 검사한다. 홀수개이므로 1

p4 = 4, 5, 6, 7, 12번의 자리의 1의 개수를 검사한다. 홀수개 이므로 1

p8 = 8, 9, 10, 11, 12번의 자리에서 1의 개수를 검사한다. 짝수개 이므로 0 이된다.

순서대로 나열하면

p8   p4  p2  p1

0     1    1    0

이므로 (0110)이진수 는 6을 나타냄

6번째 자리의 숫자가 오류라는 판정임 따라서 6번의 0 을 1로 정정해주면 오류가 해결된다.