• 내가 만든 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T_MAX_SIZE 10
#define C_MAX_SIZE 50
 
HANDLE hMutex;
HANDLE Rsemaphore;
HANDLE Csemaphore;
LPCTSTR Restaurant;
LPCTSTR Clean;
 
int N = 1;
int Alltime = 0;
int group;
int Cleantime = 3;
int exitcnt = 0;
 
DWORD WINAPI C_Number(LPVOID CTime)
{
    int GN = group;
 
    WaitForSingleObject(Rsemaphore, INFINITE);
 
    int eat = (int)CTime;
    int Num = 0;
    int before = Alltime;
 
    Num = N++;
    if (eat == 0) {
        printf("%d번째 그룹(%d명) Take Out\n\n", Num, GN);
    }
    else {
        printf("%d번째 그룹 입장(%d명), 입장시간 : %d분, 소요시간 : %d분\n\n", Num, GN, before, eat);
        Sleep(eat * 100);
        before += eat;
        printf("%d번째 그룹 퇴장\n\n", Num);
 
        WaitForSingleObject(Csemaphore, INFINITE);
        before += Cleantime;
        printf("종업원이 %d번째 그룹이 사용한 테이블을 청소하는 중입니다.\n\n", Num);
        Sleep(Cleantime * 100);
        printf("%d번째 그룹이 사용한 테이블 청소 완료!\n\n", Num);
 
        ReleaseSemaphore(Csemaphore, 1NULL);
    }
    Alltime = before;
    ReleaseSemaphore(Rsemaphore, 1NULL);
 
    return 0;
}
 
int main(int argc, char*argv[])
{
    srand(time(NULL));
    int C_Eatting_Time;
    int Alleat = 0;
    int Gcnt = 0;
    int employee = 0;
    int Maxgroup = 0;
    int pack = 0;
    printf("한 테이블당 최대로 앉을 수 있는 손님의 수를 입력해주세요 : ");
    scanf_s("%d"&Maxgroup);
    printf("종업원의 총 수를 입력해주세요 : ");
    scanf_s("%d"&employee);
    HANDLE hThread[C_MAX_SIZE];
    DWORD ThreadId[C_MAX_SIZE];
 
    Rsemaphore = CreateSemaphore(NULL10, T_MAX_SIZE, Restaurant);
    Csemaphore = CreateSemaphore(NULL, employee, employee, Clean);
    hMutex = CreateMutex(NULL, FALSE, NULL);
 
    for (int number = 0; number < C_MAX_SIZE; number += group) {
        pack = rand() % 101;
        group = (rand() % Maxgroup) + 1;
        C_Eatting_Time = (rand() % 21+ 10;
        if ((number + group) > C_MAX_SIZE) {
            group = C_MAX_SIZE - number;
        }
        if (pack <= 30) {
            C_Eatting_Time = 0;
            hThread[Gcnt] = CreateThread(NULL0, C_Number, (LPVOID)C_Eatting_Time, 0&ThreadId[Gcnt]);
        }
        else {
            Alleat += C_Eatting_Time;
            hThread[Gcnt] = CreateThread(NULL0, C_Number, (LPVOID)C_Eatting_Time, 0&ThreadId[Gcnt]);
        }
        Gcnt++;
        Sleep(1);
    }
 
    WaitForMultipleObjects((Gcnt - 1), hThread, TRUE, INFINITE);
    printf("식당이 영업을 한 시간 : %d분\n\n", Alltime);
    printf("손님들의 평균 식당 이용 시간 : 약 %d분\n\n", (Alleat / (Gcnt - 1)));
 
    return 0;
}
cs
  • 포장할 확률을 30%로 설정
  • 이전과 마찬가지로 난수를 발생시켜 30이하로 발생하면 포장, 그 이후로는 원래대로 동작
  • 포장을 하는 경우는 식당 이용시간을 0으로 생각
  • 결과 동영상
  • 포장을 할 수 있게 만들었더니 처리 시간이 더욱 빨라짐

    • 내가 작성한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T_MAX_SIZE 10
#define C_MAX_SIZE 50
 
HANDLE hMutex;
HANDLE Rsemaphore;
HANDLE Csemaphore;
LPCTSTR Restaurant;
LPCTSTR Clean;
 
int N = 1;
int Alltime = 0;
int group;
int Cleantime = 3;
int exitcnt = 0;
 
DWORD WINAPI C_Number(LPVOID CTime)
{
    int GN = group;
 
    WaitForSingleObject(Rsemaphore, INFINITE);
 
    int eat = (int)CTime;
    int Num = 0;
    int before = Alltime;
 
    Num = N++;
    printf("%d번째 그룹 입장(%d명), 입장시간 : %d분, 소요시간 : %d분\n\n", Num, GN, before, eat);
    Sleep(eat * 100);
    before += eat;
    printf("%d번째 그룹 퇴장\n\n", Num);
 
    WaitForSingleObject(Csemaphore, INFINITE);
    before += Cleantime;
    printf("종업원이 %d번째 그룹이 사용한 테이블을 청소하는 중입니다.\n\n", Num);
    Sleep(Cleantime * 100);
    printf("%d번째 그룹이 사용한 테이블 청소 완료!\n\n", Num);
 
    ReleaseSemaphore(Csemaphore, 1NULL);
    Alltime = before;
    ReleaseSemaphore(Rsemaphore, 1NULL);
 
    return 0;
}
 
int main(int argc, char*argv[])
{
    srand(time(NULL));
    int C_Eatting_Time;
    int Alleat = 0;
    int Gcnt = 0;
    int employee = 0;
    int Maxgroup = 0;
    printf("한 테이블당 최대로 앉을 수 있는 손님의 수를 입력해주세요 : ");
    scanf_s("%d"&Maxgroup);
    printf("종업원의 총 수를 입력해주세요 : ");
    scanf_s("%d"&employee);
    HANDLE hThread[C_MAX_SIZE];
    DWORD ThreadId[C_MAX_SIZE];
 
    Rsemaphore = CreateSemaphore(NULL10, T_MAX_SIZE, Restaurant);
    Csemaphore = CreateSemaphore(NULL, employee, employee, Clean);
    hMutex = CreateMutex(NULL, FALSE, NULL);
 
    for (int number = 0; number < C_MAX_SIZE; number += group) {
        group = (rand() % Maxgroup) + 1;
        C_Eatting_Time = (rand() % 21+ 10;
        Alleat += C_Eatting_Time;
        if ((number + group) > C_MAX_SIZE) {
            group = C_MAX_SIZE - number;
        }
        hThread[Gcnt] = CreateThread(NULL0, C_Number, (LPVOID)C_Eatting_Time, 0&ThreadId[Gcnt]);
        Gcnt++;
        Sleep(1);
    }
 
    WaitForMultipleObjects((Gcnt - 1), hThread, TRUE, INFINITE);
    printf("식당이 영업을 한 시간 : %d분\n\n", Alltime);
    printf("손님들의 평균 식당 이용 시간 : 약 %d분\n\n", (Alleat / (Gcnt - 1)));
 
    return 0;
}
cs
  • 시뮬레이션 시작 전에 최대 일행 수와 테이블 청소를 할 일행 수를 입력
  • 난수를 발생시켜 그룹을 생성
  • 스레드를 그룹만큼만 생성
  • Counting Semaphore를 하나 더 생성시켜 종업원이 청소를 하는 동안 스레드가 끝나지 않도록 함
  • 테이블 청소가 완료되면 대기하고 있던 그룹이 입장
  • 결과 동영상
  • 일행으로 그룹을 만들어서 그룹 단위로 식사시간을 정하니 50명 각각 처리하는 것보다 빠른 시간 처리를 확인할 수 있었음
  • 테이블 청소 시간을 추가하여 종업원 수에 따라 총 처리 시간의 변화를 확인할 수 있음
  • 청소가 끝나기 전까지 다음 손님이 입장하지 못함
    • 기능을 추가하였을 때, 변화가 있는지 알아보기 위해 스레드들의 총 처리시간과 평균 이용시간을 계산하는 코드를 추가해보자
    • 내가 만든 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T_MAX_SIZE 10
#define C_MAX_SIZE 50
 
HANDLE hMutex;
HANDLE Rsemaphore;
LPCTSTR Restaurant;
 
int N = 1;
int Alltime = 0;
 
DWORD WINAPI C_Number(LPVOID CTime)
{
    WaitForSingleObject(Rsemaphore, INFINITE);
 
    int eat = (int)CTime;
    int Num = 0;
    int before = Alltime;
 
    Num = N++;
    printf("%d번 손님(%d) 입장, 소요시간 : %d분\n\n", Num, GetCurrentThreadId(),eat);
    Sleep(eat * 100);
    printf("%d번 손님(%d) 퇴장\n\n", Num, GetCurrentThreadId());
    Alltime = before + eat;
    printf("진행시간 : %d분\n\n", Alltime);
 
    ReleaseSemaphore(Rsemaphore, 1NULL);
 
    return 0;
}
 
int main(int argc, char*argv[])
{
    srand(time(NULL));
    int C_Eatting_Time;
    int Alleat = 0;
    HANDLE hThread[C_MAX_SIZE];
    DWORD ThreadId[C_MAX_SIZE];
 
    Rsemaphore = CreateSemaphore(NULL10, T_MAX_SIZE, Restaurant);
    hMutex = CreateMutex(NULL, FALSE, NULL);
 
    for (int number = 0; number < C_MAX_SIZE; number++) {
        C_Eatting_Time = (rand() % 21+ 10;
        Alleat += C_Eatting_Time;
        hThread[number] = CreateThread(NULL0, C_Number, (LPVOID)C_Eatting_Time, 0&ThreadId[number]);
    }
 
    WaitForMultipleObjects(C_MAX_SIZE, hThread, TRUE, INFINITE);
    printf("손님들의 평균 식사 시간 : 약 %d분\n\n", (Alleat / 50));
 
    return 0;
}
cs

  • 결과 동영상
  • 손님이 퇴장했을 때 식당을 열었을 때부터 얼마나 시간이 흘렀는지 확인할 수 있음
  • 50명의 손님이 평균적으로 식사하는 시간을 알 수 있음
  • 이제 기능을 추가했을 때, 식당 운영시간이 얼마나 줄었는지 확인할 수 있게 되었음
  • 조건

  • 내가 만든 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define T_MAX_SIZE 10
#define C_MAX_SIZE 50
 
HANDLE Rsemaphore;
LPCTSTR Restaurant;
 
int N = 1;
 
DWORD WINAPI C_Number(LPVOID CTime)
{
    int eat = (int)CTime;
    int Num = 0;
    WaitForSingleObject(Rsemaphore, INFINITE);
    Num = N++;
    printf("%d번 손님(%d) 입장\n", Num, GetCurrentThreadId());
    Sleep(eat * 100);
    printf("%d번 손님(%d) %d분 후 퇴장\n", Num, GetCurrentThreadId(), eat);
    ReleaseSemaphore(Rsemaphore, 1NULL);
 
    return 0;
}
 
int main(int argc, char*argv[])
{
    srand(time(NULL));
    int C_Eatting_Time;
    HANDLE hThread[C_MAX_SIZE];
    DWORD ThreadId[C_MAX_SIZE];
 
    Rsemaphore = CreateSemaphore(NULL10, T_MAX_SIZE, Restaurant);
 
    for (int number = 0; number < C_MAX_SIZE; number++) {
        C_Eatting_Time = (rand() % 21+ 10;
        hThread[number] = CreateThread(NULL0, C_Number, (LPVOID)C_Eatting_Time, 0&ThreadId[number]);
        Sleep(1);
    }
 
    WaitForMultipleObjects(C_MAX_SIZE, hThread, TRUE, INFINITE);
 
    return 0;
}
cs

  • 결과 동영상
  • 번호표를 받은 순서대로 들어오지만 식사시간에 따라 퇴장시간이 달라지는 것을 확인할 수 있음

 

Dining-Philosophers Problem

  • 내용
  • 5명의 철학자들은 평생 정해진 원탁의 자리에서 살아야 함
  • 철학자들이 하는 일은 철학하는 것과 음식을 먹는 것 두 가지뿐이라고 모델링
  • 접시는 각자 하나씩 총 5개가 있고 젓가락은 접시 양 옆에 한 짝씩 존재하여 이 또한 5개
  • 식사를 하는 철학자는 접시 양 옆의 젓가락을 들고 식사를 할 수 있음
  • 한 사람씩 식사를 하고 싶다면 순서대로 젓가락을 사용할 수 있지만 동시에 모든 사람이 배가 고파진다면 젓가락이 부족
  • 만약 모든 철학자들이 젓가락을 한 짝씩 들고 있다면 모두 식사를 하지 못하게 될 것
  • 각자의 철학자에 맞춰서 구성을 해본다면(해결 방안)

  • 실제 구현

  • 잘 생각해볼 것

임계 영역 프로그래밍

  • 기본 코드

  • 두 개의 스레드로 동작
  • 메인 프로그램

  • 두 스레드를 생성
  • 앞의 코드 for(;;)에 sleep(1) 함수를 추가해 보자 - 그 순간에 스케줄링을 시켜줌

  • 임계 영역(Critical Section) 접근 동기화

  • g_var라는 int형 변수를 선언한 후 사용
  • 첫 번째 스레드는 g_var를 1로 만들고 Sleep(1)을 한 후 g_var 값을 출력

  • 두 번째 스레드는 g_var를 2로 만들고 Sleep(1)을 한 후 g_var 값을 출력
  • 원하는 결과

  • 실제 결과

  •  Sleep을 하는 동안 공유 변수 g_var의 값이 다른 스레드에서 바뀌기때문
  • Sleep을 빼고 확인해볼 것

유저 모드의 동기화

  • 임계 구역 기반의 동기화
  • 화장실에 걸어 놓은 열쇠(비유)

  • CRITICAL SECTION의 변수를 설정(화장실 열쇠) - CRITICAL_SECTION gCriticalSection;
  • 변수 초기화(열쇠 걸어 놓음)

  • Critical Section의 변수를 사용하여 임계 영역으로 들어감.(화장실 열쇠를 획득)

  • 키를 반환하고 임계 구역을 빠져나옴.(화장실 열쇠를 반환, 다시 걸어놓음)

  • 형식

  1. 임계 영역에 하나라도 들어가 있다면 나머지 프로세스들은 대기
  • 실제 프로그램 코드

  1. 각 스레드의 for문 안의 내용을 critical section으로 묶음
  2. 임계 영역에 sleep이 있으므로 스케줄링은 할 수 있으나 다른 스레드에 의해 값은 바뀌지 않음
  3. LeaveCriticalSection 이후에 여러 코드를 추가하여 어떻게 실행되는지를 확인해보자

커널 모드의 동기화

  • 뮤텍스(Mutex) 기반의 동기화

  • 구조는 동일
  • 사용하는 함수의 이름이 달라짐
  • 운영체제가 개입 - wait 할 때, CPU를 사용하게 할 수도 있고 안 할 수도 있음 -> 유저 레벨에서 할 수 없었던 일을 할 수 있음
  • 세마포어(Semaphore) 기반의 동기화

  • 세마포어(세마포어 오브젝트)를 생성하는 함수

  • 시뮬레이션

  1. 한 테이블에는 1명씩 총 10명이 동시에 식사를 할 수 있음
  2. 각 사람마다 초기값을 가지고 있음(식사시간)
  3. 치우는 시간은 없다고 가정
  4. 이러한 프로그램을 이용하여 여러 가지 요소들을 예측하여 최적의 환경을 만들어낼 수 있음(아르바이트생의 수, 일을 해야 하는 시간 등)

Deadlocks

  • The Deadlock Problem
  • 한 프로세스가 자원을 요청했을 때, 그 자원을 사용할 수 없게 된다면 대기상태가 됨
  • 대기 중인 프로세스가 요청한 자원들이 다른 대기 중인 프로세스에서 점유되어 있을 때, 이 프로세스 상태를 변경시킬 수 없는 경우를 교착상태라고 함
  • 두 개의 프로세스가 한 개의 구동기를 점유한다고 가정
  • 만약 프로세스가 다른 구동기를 요청한다면 두 개의 프로세스는 교착상태가 됨

  1. 어떤 한 자원을 가지고 있고 다른 자원을 또 가지려고 대기
  2. 두 자원을 다 가지면 어떤 일을 하겠다는 것
  3. 두 프로세스가 각각 자원 하나씩을 가지게 된다면 계속 대기해야 하는 상황
  • Bridge Crossing Example(외나무다리)

  • 마주오는 두 개의 자동차를 생각해보자
  • 하나의 차량이 돌아가기 전까지는 누구도 빠져나갈 수 없게 됨
  • 교착상태 -> 기아상태가 발생
  • System Model
  • 시스템은 경쟁할 프로세스들 사이에서 유한한 수의 자원들로 구성
  • 자원은 R1~Rm까지 존재(CPU cycle, memory space, I/O devices 등)
  • 이들 각각 자원들은 동일한 다수의 인스턴스를 가지고 있음(Ri has Wi instances)
  • 프로세스는 자원을 사용하기 전에 요청을 해야 함
  • 사용한 후에는 해제해야 함
  • Deadlock Characterization
  • 아래 네 가지 특징을 모두 가지고 있을 경우 교착상태 - 교착상태일 때 이러한 특징을 가지고 있음(필요조건 o, 충분조건 x)
  • Mutual exclusion(상호 배제) : 하나의 프로세스는 한 번에 하나의 자원만 사용할 수 있도록 되어있음
  • Hold and wait(점유 및 대기) : 최소한 하나의 자원을 점유하고 있는 프로세스가 있는데, 이 프로세스는 다른 프로세스에 의해 점유된 다른 자원을 추가로 얻기 위해서 기다리고 있는 상태
  • No preemption(비선점) : 점유된 자원은 강제적으로 해제될 수 없고 점유하고 있는 프로세스가 그 테스크를 종료한 후에 자원이 저절로 해제됨
  • Circular wait(순환 대기) : 대기하고 있는 프로세스의 집합에서 P0 -> P1, P1 -> P2 ... Pn-1 -> Pn, Pn -> P0로 점유한 자원을 대기하는 것이 고리를 형성하여 순환하는 상태
  • Resorce-Allocation Graph(자원 할당 그래프)
  • 교착상태는 시스템 자원 할당 그래프라는 방향 그래프로 표명할 수 있음
  • Vertices(정점)와 Edges(간선)로 이루어져 있음
  • V(정점)는 2가지 형태로 구성되어 있음 - P(시스템 내 모든 프로세스들의 집합), R(시스템 내 모든 자원들로 이루어진 집합)
  • Request edge - Pi가 Rj를 요청하는 요청선(Pi -> Rj)
  • Assignment edge - Rj가 Pi에 할당된 것을 의미하는 할당선(Rj -> Pi)
  • 그림으로 나타내면

  1. 프로세스는 원
  2. Resource는 사각형인데 안에 작은 사각형이 있는 것은 여러 디스크(D, C, E 등)가 할당된 것을 의미
  3. 프로세스 Pi가 자원 Rj를 요청하고 있는 것
  4. Rj이 가지고 있는 것들 중 하나가 Pi에 할당(Rj안의 인스턴스 하나가 할당)
  • 3개의 프로세스의 예

  1. P1은 R1을 요청
  2. R1의 인스턴스는 P2에 할당
  3. P2는 R3를 요청
  4. R3의 인스턴스는 P3에 할당
  5. R2의 인스턴스는 P1과 P2에 할당
  6. 순환 그래프가 그려지지 않는다면 교착상태가 아님
  • 또 다른 예

  1. P3가 R2에 자원을 요청하지만 R2의 자원을 P1과 P2가 사용 중
  2. P3는 R2에 자원이 돌아올 때까지 대기
  3. P1과 P2도 마찬가지로 R1과 R3에 각각 자원을 요청하였으나 이미 사용 중이기 때문에 대기하는 중
  4. 따라서 3개의 프로세스가 전부 기다리게 됨 -> 교착상태
  • 또 다른 예 2

  1. P1 -> R1 -> P3 -> R2 -> P1으로 순환이 형성 -> 교착상태인가?
  2. P4나 P2가 끝나고 자원을 돌려주면 돌려받은 자원을 P1과 P3에 할당할 수 있으므로 교착상태는 생기지 않음
  3. 순환이 형성된다고 해서 무조건 교착상태는 아님
  • Basic Facts
  • 그래프가 주기를 가지지 않으면 교착상태는 존재하지 않음
  • 그래프가 주기를 가지면
    1. 자원이 인스턴스를 하나만 가지고 있다면 반드시 교착상태
    2. 자원이 인스턴스를 여러 개 가지고 있다면 다른 프로세스가 해제할 경우 돌려받은 자원을 할당해 줄 수 있으므로 교착상태에서 벗어날 수 있음 -> 가능성은 있으나 항상 교착상태는 아님
  • 교착상태를 처리하는 방법
  • 시스템이 교착상태가 되지 않도록 보장하는 프로토콜을 만드는 방법
  • 시스템이 교착상태가 되도록 허용한 후에 이를 회복하는 방법을 만듦
  • 이러한 문제를 무시하고 교착상태가 생기지 않는다고 생각, 운영체제에 교착상태가 절대 발생하지 않는 척 -> 교착상태가 발생하지 않도록 운영 프로그램 개발자가 알아서 사용
  • 교착상태의 예방(Prevention)
  • 아래 네 가지 중 하나를 안생기게 하면 교착상태에 빠지지 않음
  • Mutual Exclusion : 공유 자원을 요청하지 않음, 비공유 자원을 전제로 함
  • Hold and Wait : 점유 대기 조건이 시스템에서 발생하지 않으려면, 프로세스가 자원을 요청할 때마다 다른 자원들을 점유하지 않도록 보장해야 함 -> 자원 이용률이 낮아짐

  • No Preemption(비선점)

  • Circular Wait(순환 대기) : 모든 자원 형태들에게 전체 순서를 부여하고, 각 프로세스가 열거된 상태에서 순서(오름차순)를 정해 자원을 요청하는 프로토콜을 사용하는 것
  • Deadlock Avoidance(교착상태 회피)
  • 자원을 요청하는데 필요한 추가의 앞선 정보(additional a priori information)를 요청하는 알고리즘 작성으로 교착 상태를 회피

  • Safe State(안전 상태)
  • 특정한 순서대로 각 프로세스의 자원을 할당할 수 있게 되었을 때, 교착상태를 방지할 수 있으면 이것을 안전 상태라고 함
  • 하나의 프로세스가 이용 가능한 자원을 요청할 때, 시스템은 즉각적인 자원 할당이 안전상태를 벗어나는 것을 매번 결정하게 됨
  • 모든 프로세스의 안전 순서(안전상태를 유지하는 순서)가 존재하면 이 시스템은 안전 상태에 있다고 말할 수 있음

  1. 시스템이 안전 상태에 있다면 교착상태는 아님
  2. unsafe 하다면 교착 상태가 생길 수 있음
  3. 시스템이 불안정 상태로 들어가지 못하도록 하는 것이 교착 상태 회피 알고리즘 -> 시스템이 항상 안전 상태에 머무르도록 하는 것
  • 안전한 상태가 있는가를 살펴보자

  1. 자원은 총 12개
  2. P0는 최대 10개를 요청할 수 있고 5개 할당
  3. P1은 최대 4개를 요청할 수 있고 2개 할당
  4. P2는 최대 9개를 요청할 수 있고 2개 할당
  5. 3개가 남아있음
  6. 만약 P0~2가 동시에 최대 수요량만큼을 요청했다면 자원이 부족해짐 -> 교착상태
  7. 이 상황에서 P0가 나머지 수요량인 5개의 자원을 요청한다면 2개가 부족하므로 교착상태가 발생
  8. 최대는 넘지 않게 각각의 요구를 만족할 수 있는 순서가 있느냐를 봐야 함
  9. P0는 5개가 필요하고 P1은 2개, P2는 7개가 필요하므로 나머지 자원(3개)을 할당했을 때 최대 수요를 만족하는 P1에 우선적으로 자원을 할당
  10. P1이 끝났다면 남은 자원은 5개가 되어 P0에 모두 할당 -> 최대 수요를 만족
  11. 마지막으로 남은 자원 10개를 P2에 7개 할당 -> P2 만족
  12. 이 순서로 할당하지 않는다면 교착 상태가 발생할 수 있음

  • Resource-Allocation Graph Algorithm
  • 앞서 한 것들을 요청 가능선, 요청선, 할당선 등으로 구체화시켜 나타냄

  1. 점선 : 요청 가능선 -> 요청이 되어 자원 할당을 받는다면 할당선으로 바뀜
  2. 실선(R1 -> P1) : 할당선
  3. 실선(P2 -> R1) : 요청선

  • Banker's Algorithm
  • 앞의 리소스로 설명한 것을 Multiple instances에 대해 어떻게 이 알고리즘을 바꿔야 하는지를 정리한 것
  • 자원 할당 그래프의 알고리즘은 다수개의 자원 유형을 갖는 시스템에서 적용할 수 없음
  • 다수개의 자원 유형을 갖는 시스템에서 적용하기 위한 알고리즘
  • 새로운 프로세스가 시스템에 들어가면 필요로 하는 각 자원 형태들의 최대수를 미리 선언하고 알고 있어야 함
  • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 다음에 안전상태로 남아있는지를 결정해야 함
  • 안전상태로 남아있으면 할당하고 그렇지 않으면 다른 프로세스들이 자원을 충분히 해제할 때까지 대기
  • 은행가 알고리즘은 은행이 모든 고객의 수요를 충족시킬 수 있도록, 현금을 할당하는 데 기인한 알고리즘
  • Data Structures for the Banker's Algorithm

  1. 여러 개의 프로세스가 여러 개의 자원들을 필요로 함
  2. 필요로 하는 자원들을 어떻게 관리를 할 수 있는지 -> 안전한 상태를 유지할 수 있는지
  • Safety Algorithm(꼭 해볼 것! 시험에 매번 나옴)

  1. 어떻게 유지가 되는지를 잘 보면 됨
  • 예시

  1. 프로세스는 5개
  2. 자원은 세 가지
  3. 현재 각 프로세스가 할당받은 자원들과 최대로 할당받아야 하는 양, 남은 자원의 양
  4. 꼭 해볼 것

  • Resource-Request Algorithm for Process Pi - 추가 요청

  • 예시) P1이 (1,0,2)를 추가로 요청했을 경우 -> 어떻게 업데이트를 할 것인가

  1. 남아있는 자원(3,3,2)이 (2,3,0)으로 줄어듦
  • Deadlock Detection
  • 시스템이 교착상태로 들어가도록 하는 것 까지는 허용
  • 교착상태가 발생했는지 파악하기 위해서 시스템 상태를 탐지
  • 탐지를 했다면 회복(Recovery)
  • Single Instance of Each Resource Type

  • Resource-Allocation Graph를 Wait-for Graph로 단순화 -> 교착상태가 생겼는지를 한눈에 볼 수 있음(순환 고리 형성)

  • Several Instances of a Resource Type

  • 교착상태가 발생하고 여러 개의 인스턴스가 있을 경우의 설명
  • Detection Algorithm

  • 표현법이 Need가 아닌 Request가 됨
  • Detection-Algorithm Usage - 언제 탐지 알고리즘을 호출할 것인가?
  • 교착 상태 발생 빈도수
  • 교착 상태가 발생했을 때, 영향을 받는 프로세스의 수
  • 교착 상태가 자주 발생하면 탐지 알고리즘도 더 자주 호출해야 함 -> 운영체제가 하는 일이 많아져서 효율이 떨어짐
  • Recovery from Deadlock : Process Termination
  • 순환 대기를 탈피하기 위해서 단순히 프로세스 하나를 중지시키는 것
  • 교착상태 프로세스들로부터 자원을 선점하는 것

  • Recovery from Deadlock : Resource Preemption
  • 자원 선점에 의한 방법 - 잘 읽어볼 것

  • Combined Approach to Deadlock Handling(복합적인 방법)

 

두 개 이상의 프로세스가 동작하고 있을 경우의 알고리즘

 

가장 낮은 번호를 받은 프로세스가 가장 먼저 임계 영역에 들어갈 수 있음

 

번호 부여는 증가하는 방식으로 하지만 우연히 같은 번호를 받을 수 있음 -> 은행에서는 번호표 지급기가 1개뿐인 이유


Bakery Algorithm

  • Notaion <= lexicographical order (ticket #, process id #)

  • (a, b) < (c, d)는 a와 b를 비교하고 b와 c를 비교한다는 의미
  • max는 이중 가장 큰 값을 의미
  • 공유 데이터(shared data)
  • boolean choosing[n]; 
  • int number[n];
  • 이 두 값의 초기값은 각각 모두 false와 0
  • 알고리즘 코드

  1. 각각의 프로세스들이 이 형태의 구조로 되어있어서 각자가 알아서 판단
  2. 하나의 프로세스만 임계 영역에 들어감 - 프로세스들은 각자의 임계 영역이 있음
  3. choosing을 true로 만듦 -> 이제 번호표를 받을 것이라는 의미
  4. 현재 대기 중인 가장 큰 번호보다 1이 큰 number를 받음
  5. 번호를 받은 후에는 choosing이 flase가 됨
  6. for문에서 0~n까지의 번호를 확인하게 됨
  7. 첫 번째 while문은 어떤 프로세스가 번호표를 받고 있는 중에는 잠시 대기한다는 의미
  8. 두 번째 while문은 서로를 존중해주는 알고리즘
  9. number가 0이라는 것은 아직 번호표를 받지 못했거나 이미 끝난 프로세스라는 의미(임계 영역에 들어가지 않겠다는 의미)
  10. 어떤 번호가 0이 아니면 현재 자신의 번호와 비교하여 작은 지를 비교 -> 작다면 우선순위에서 밀리므로 대기
  11. 만약 내 번호가 n개의 프로세스들의 번호 중에 가장 작다면 임계 영역에 들어간 후 번호를 0으로 바꿈
  12. 우연하게 같은 번호의 번호표를 받을 경우에는 프로세스 고유번호를 비교하여 더 작은 프로세스가 먼저 임계 영역에 들어갈 수 있음
  13. choosing과 number 또한 critical section문제를 가지기 때문에 이러한 조건을 준 것(동시에 같은 번호를 받을 수 있음)
  14. 앞 시간에 배운 3가지 조건을 만족하는지 확인해볼 것
  • Synchronization Hardware
  • 베이커리 알고리즘은 훌륭하고 좋은 알고리즘(n개의 프로세스가 동시에 작동 가능) -> 모두 SW적으로 구현이 되어 있으므로 복잡함
  • 이런 것들을 제공하는 하드웨어적인 명령어가 있고 제공받는 명령어가 CPU에 있다면? - Synchronization Hardware
  • 조건을 판별해본 뒤에 한 word의 값을 바꾸거나 word사이의 내용을 바꿔치기하는 작업들을 Atomic 하게 처리
  • Synchronization Hardware는 자신이 어떤 일을 하는 동안에 쪼개지지 않고 한 번에 실행되어야 함
  • ex) test and set이라는 명령어

  1. CPU의 하나의 명령어 - 쪼개지지 않고 atomic 하게 실행
  2. 어떤 CPU가 혹은 어떤 hardware 시스템이 test and set 명령어를 지원한다면 쉽게 critical section을 구현 가능
  3. lock이라는 boolean변수를 선언하고 TestAndSet(&lock - 주소)로 사용
  4. 두 프로세스의 처리 속도가 다른 경우(Pi가 빠름(먼저 처리), Pj가 그 후)
  5. TestAndSet에 들어간 Pi의 rv(리턴 값)가 flase가 되고 lock값은 ture가 됨 -> 그 후 임계 영역에 들어감
  6. Pj는 그 후에 실행되는데, 아직 Pi가 임계 영역을 끝내지 않았으므로 lock은 아직 true이고 따라서 rv값 또한 true -> while문에서 대기
  7. Pi가 나오면 lock이 false가 되고 Pj가 while문을 탈출하게 됨 -> 임계 영역 접근 가능
  8. Pi는 Pj가 실행되는 동안 while문에서 대기
  • 두 프로세스의 속도가 같은 경우를 생각해보자
  • Swap이라는 명령도 존재하므로 232 page 환인하고 예제 해결해 볼 것

Semaphores(정수 변수)

  • 영역을 나눠서 각각 하나씩 처리하는 것은 같지만(atomic) 실제로 돌아가는 것은 조금 다름
  • 임계 영역 중 하나를 제외한 모든 프로세스들이 while문에서 대기 - Busy waiting(바쁜대기)
  • 대기만 하는 것이 아니라 대기하는 동안 계속 무언가를 검사해야 함 - CPU 사용
  • 동작을 하지는 않지만 동작하는 순간을 기다리기 위해 CPU를 사용 - CPU는 바쁘지만 일은 못함
  • 불필요한 CPU의 동작이 문제
  • 단지 두 개의 개별적인 atomic 한 연산(wait와 signal)을 가지고 접근 가능

  • wait(S)
  1. 만약 S값이 0보다 작거나 같으면 동작을 하지 않음(no-operation)
  2. while문에 대기시키지 말고 no-op부분에서 할 수 있는 일을 시키라는 의미
  3. S가 0보다 작거나 같은 동안에는 no-op를 실행하고 벗어나면 S값을 줄임
  • Signal(S) : 단순하게 S를 증가시키는 연산
  • Critical Section of n Processes
  • 공동 semaphore인 mutex라는 변수를 공유 initially mutex = 1(1로 초기화)
  • 사용 방식

  1. P0가 접근 - 데이터 구조에 mutex를 1로 주고 wait에 넣음
  2. mutex가 0보다 작거나 같지 않으므로 mutex 값을 1 감소시키고 critical section에 들어감
  3. 그 후 P1이 들어왔을 때 mutexr값이 0이므로 no-op 실행(waiting 시킴 - CPU를 사용하지 않고 대기)
  4. P0가 critical section을 벗어나면 mutex를 1 증가시킨 후(signal) remainder section실행
  5. 그 순간 대기 중이던 P1은 waiting상태에서 ready queue로 넘어감
  6. 어느 순간에 P1이 다시 CPU를 차지하게 되면 공유 변수인 mutex가 1이므로 wait에서 1 감소시킨 후 critical section에 들어갈 수 있음
  • Semaphore Implementation
  • semaphore의 정의

  1. value값을 줌 - S
  2. 프로세스 리스트를 만듦 -> block 시켜서 suspend시킴(waiting영역에 넣음) - 동작을 안 함
  3. busy waiting 문제 해결
  • 자세하게 살펴보자

  1. wait(S)에서 Semaphore의 value값을 1 감소시키고 0보다 작을 경우 이 프로세스를 wait list에 집어넣고 block시킴(waiting)
  2. signal(S)에서 value값을 1 증가시키고 만약 0보다 작거나 같을 경우 wait list에서 제외시키고 wakeup시킴
  3. 운영 프로세스가 동작하는 것이 아니라 운영체제가 이 동작들을 맡아서 처리
  4. 효율적으로 동기화 문제를 해결할 수 있음
  • Semaphore as a General Synchronization Tool

  1. 하나의 프로세스는 우선적으로 자신의 일을 하고 나머지 프로세스는 wait를 시킴
  2. Pi가 critical section을 수행하는 동안 Pj는 wait
  3. Pi가 다 끝난 후 signal -> Pj는 대기상태에서 나와 자신의 일을 수행
  4. 운영체제 기능을 이용하여 Busy waiting을 안 하게 하는 것
  • Deadlock and Starvation

  • semaphore가 2개인 경우
  1. P0는 S를 먼저 wait 하고 Q를 그 후에 wait 함, P1은 반대로 수행
  2. 수행을 마친 후 순서대로 signal을 해줌
  3. 프로세스 하나가 먼저 수행된 후 다음 프로세스가 수행되면 상관이 없지만 한 줄씩 번갈아가며 수행된다면 문제가 생김
  4. critical section에 들어가기 전, S와 Q가 0보다 작아지게 되므로 두 프로세스 모두 blocking 됨
  5. 두 프로세스 모두 blocking 되어 누군가 꺼내주기를 기다리지만 나갈 수 없는 상태가 됨 - deadlock(교착) 상태
  6. 프로세스가 실행되면서 정해놓은대로 잘 진행되지만 한 프로세스가 계속 blocking 당하는 상황 - starvation상태
  • Two Types of Semaphores
  • Counting semaphore(계수) - 정수값에 제한을 가지지 않음
  • Binary semaphore(이진) - 0 또는 1로 한정 -> 구현하기 쉬움(계수 세마포어도 구현 가능)

Classical Problems of Synchronization

  • Bounded-Buffer Problem
  • 공유 데이터 : full, empty, mutex;
  • 초기값 : full = 0, empty = n, mutex = 1
  • Producer Process

  1. 첫 번째 wait는 비어있는지를 확인하는 것 - 채울 것이 있는 상태인지
  2. 두 번째 wait는 사용할 수 있는지를 확인하는 것
  3. 첫 번째 signal은 critical section 사용을 끝냈음을 의미
  4. 두 번째 signal은 다 채웠음을 의미
  • Consumer Process

  1. 첫 번째 wait는 채워져 있는지 확인
  2. 두 번째 wait는 사용할 수 있는지 확인
  3. 첫 번째 signal은 다 사용했음을 의미
  4. 두 번째 signal은 하나를 다 비웠음을 의미
  5. 잘 보고 이해해볼 것
  • Readers-Writers Problem
  • text 파일을 편집하는 중에 이 파일을 다른 사용자가 열려고 할 때
  1. 접근을 아예 하지 못하게 하는 방법
  2. 파일을 편집 중임에도 불구하고 읽게 해 줄 수는 있음
  3. 어떤 방식이든 하나의 방법(알고리즘)을 정해놓고 세마포어로 어떻게 해결할 것인지 살펴보는 것은 우리가 해야 할 일
  • 공유 데이터 : mutex, wrt;
  • 초기값 : mutex = 1, wrt = 1, readcount = 0
  • 흐름
  1. writer가 공유데이터에 배타적으로 접근(두 개 이상이 동시에 쓸 수 없음)
  2. 데이터를 두 개 이상이 읽고 있다면 쓰기는 안됨
  3. 어떤 기준을 가지고 동작하는지를 잘 봐야 함
  4. 이 기준은 언제든 바뀔 수 있으며 바뀔 때 이미 짜여 있던 코드를 수정할 수 있어야 함
  • Writer Process

  1. 세마포어의 값을 확인하고 쓸 수 있는 상태면 write 해줌
  2. 그 후 signal - 끝났음을 알림
  3. 쓸 수 있느냐 없느냐를 확인하는 것
  • Reader Process

  1. 쓰는 사람은 하나밖에 없지만 읽는 사람은 여러 명이 될 수 있음
  2. 첫 번째는 readcounter를 변경하기 위함
  3. if문은 readcounter가 1일 경우(첫 번째 read process인지를 물어보는 것)
  4. 첫 번째 read process일 때, 쓰는 중인 프로세스가 있는지 확인하는 것 -> 있으면 기다림
  5. read counter가 2 이상이면 signal을 거쳐 아래 내용을 수행 -> 2개 이상이면 안 기다리고 바로 넘어간다는 의미
  6. 첫 번째 read process가 기다리는 중에 다음 read process가 들어오더라도 첫 번째 wait에서 대기
  7. write process가 끝나면 내려감
  8. signal로 인해 mutex가 증가하고 대기하고 있던 나머지 read process들은 모두 readcounter를 증가시키면서 reading is performed부분으로 한꺼번에 들어감 -> 두 개 이상의 read process들은 동시에 읽을 수 있음을 의미
  9. read가 끝나면 readcount가 1 감소
  10. write는 그냥 할 수 있으면 write 하는 것이지만 read는 위와 같이 동작
  11. 한 줄 한 줄 의미를 확인하며 잘 생각해볼 것
  12. 읽는 동안에 다른 readers와 writers는 어떻게 동작해야 하는지를 잘 생각해볼 것

Background

  • 야구 : 20명 정도의 선수들이 시합 -> 각자의 역할이 있음(투수가 공을 던져야 시작, 타자가 공을 치거나 포수가 공을 받음, 공이 어느 방향으로 가느냐에 따라 달라짐)
  • 각 선수들을 스레드로 보면 각 스레드들은 독립적으로 하는 일이 정해져 있음
  • 스레드들 간의 일부 순서가 있고 상호 순서가 지켜져야만 한다.
  • 시스템 내의 상호 협조 프로세스 -> 다른 프로세스 실행에 영향을 받음, 주소 공간을 공유하거나 파일에 의해서 데이터의 공유가 허용됨
  • 공유 데이터에 대한 동시 접근은 데이터의 불일치로 이어짐 -> 반드시 해결해야 됨

Bounded-Buffer

  • Producer process

  • in과 out이 같은지를 비교했을 때와 달리 정해진 크기의 BUFFER_SIZE와 같은지를 비교하도록 바꿨음
  • count변수로 loop를 반복시킴
  • Consumer process

  • 값을 꺼낼 때 counter를 줄임 -> 포인터 대신 개수로 비교
  • 수정된 알고리즘에는 counter라는 공유 변수가 있음
  • 두 프로세스는 counter값을 변화시키면서 사용, 비교
  • 어느 한순간의 counter가 5라고 가정
    • 두 프로세스가 한 번씩 counter에 접근한다면 5->6->5로 값이 변하는 것이 맞음
    • 그러나 count++와 count--는 CPU입장에서 하나의 명령인가?
  • assembly에서 본 count++
  1. register1 = counter -> CPU가 값을 레지스터에 읽어옴
  2. register1 = register1 + 1 -> 그 레지스터 값을 1 증가시킴(아직 counter값은 5)
  3. counter = register1 -> counter에 6을 저장
  • count--
  1. register2 = counter -> CPU가 값을 레지스터에 읽어옴
  2. register2 = register2 - 1 -> 그 레지스터 값을 1 감소시킴
  3. counter = register2 -> counter에 레지스터값을 저장
  • 두 프로세스를 동시에 실행시켰다면 어셈블리에서 총 6개의 명령이 실행됨 -> 이것들이 무조건 순서대로 실행이 되는가? (x)
  • 엄청나게 많은 프로세스의 사용이 반복된다면 정말 우연히도 6개의 명령이 섞일 수도 있음

  • counter를 증가시키는 producer의 프로세스가 진행되는 중에 counter의 값을 바꾸기 전에 consumer의 프로세스가 실행되어 버림
  • counter의 값이 6? 4? 나중에 바뀌는 값으로 들어가 버림 -> 오류 발생(counter를 다루는 명령어가 atomic하지 못했다.)

Race Condition

  • 위의 문제점을 레이스 컨디션이라고 함 -> 한 프로세스에서만 접근하도록 만들어야 한다.
  • 분리할 수 없는 명령이라고 생각하는 것이 섞이지 않도록 나누는 것(동기화)

Critical Section Problem(임계 영역)

  • 두 개의 프로세스로 이루어진 시스템
  • 각 프로세스는 임계 영역이라는 code segment내에 가짐
  • 이 임계 구역은 공유 데이터를 처리하는 각각의 프로세스가 가지는 것
  • 한 프로세스가 공유데이터를 처리하는 동안 다른 프로세스가 접근할 수 없는 구역
  • 프로세스가 협조할 수 있도록 프로토콜을 설계
  • 각 프로세스는 임계 구역에 진입하기 위한 허가권을 운영체제에 요청
  • 진입 구역, 임계 구역, 출구 구역, 자유구역으로 나누고 그 구역에 맞게 처리해줌

  1. 위와 같이 구역을 나눠서 생각
  2. 임계 구역에 해당하는 부분은 분리되지 않음
  3. 임계 구역 앞에 있는 것을 entry section, 뒤에 있는 것을 exit section이라고 함
  4. entry section : 필요한 세팅, 설정, 관계없는 일들을 모아둠
  5. exit section : 일부분, 임계 구역에 관련된 나머지 일들을 처리
  6. remainder section : 위와 관련 없는 나머지 일들을 하는 부분

Solution to Critical-Section Problem

  • 상호 배제(Mutual Exclusion) - p1가 임계 구역에서 실행된다면 다른 프로세스들은 임계 구역에서 실행될 수 없다.(단 하나만)
  • 진행(Progress) - 임계구역에서 실행되는 프로세스가 없는 상태에서 임계 구역으로 진입하려는 프로세스가 있으면 잔류 구역에서 실행되지 않고 있는 프로세스들만 다음에 임계 구역으로 진입할 수 있는 대상이 되고 이 구역은 무한하게 연기할 수 없다.
  • Bounded Waiting(한계 대기) : 프로세스가 임계 구역으로의 진입을 요청한 후에 그 요청이 허용될 때까지 다른 프로세스들도 임계 구역에 진입하도록 허용하는 시간 간격에도 한계를 두어야 한다.(무한하게 대기하면 안 됨)
  • 각 프로세스들은 무조건 대기하는 것이 아니라 진행되고 있어야 한다.

  • P0, P1은 turn이라는 공유 변수를 가짐
  • 만약 turn이 i다 라는 조건을 만족하면 임계 구역으로 들어갈 수 있음
  • i = 0, j = 1
  • Pi : turn값이 i와 다르면 무한루프 -> 처음에는 같기 때문에 critical section으로 들어감
  • 끝난 후 turn을 j로 바꿈 -> 나머지를 수행 -> 반복
  • Pj : i가 실행되는 동안 while문에서 대기 -> turn이 j가 되는 순간 탈출 -> 임계 영역에 들어감
  • 두 프로세스가 동시에 진행된다면? -> i와 j값이 다르므로 어쨌든 하나는 대기, 하나는 실행됨
  • 상호 대기 만족
  • turn은 0으로 초기화되었는데, P1이 먼저 들어왔다면 P0이 들어오기 전까지 기다려야 하므로 진행(Progress)과 한계 대기(Bounded Waiting)를 만족하지 못함
  • 반드시 번갈아서 진행되는 알고리즘이므로 하나의 프로세스 실행 후 다음 프로세스가 응답하지 않을 시 대기해야 한다.

  • 플레그 2개를 선언함 -> flag[i]를 true, j를 flase로 정함
  • Pj는 플레그가 flase이므로 while문을 통과하여 Pi가 실행됨 -> Pj가 응답하지 않더라도 계속 Pi가 실행될 수 있음
  • Pj는 flag[i]는 ture일 때 임계 구역에 들어가지 못하고 대기 -> Pi가 실행된 후 flase가 되는 순간 Pj가 실행됨
  • Pj가 실행되는 동안, Pi 역시 임계 영역에 들어가지 못함
  • 번갈아서 실행할 필요가 없어짐
  • 상호 배제 만족, 그러나
  • 두 프로세스가 타이트하게 문맥 교환을 하는 경우
    1. 한 줄씩 번갈아가며 실행된다고 가정해보자
    2. flag를 각각 true로 바뀌면 두 플래그가 전부 true로 바뀐 후 while문에 접근하므로 두 프로세스 모두 대기
    3. 두 플레그 중 하나가 바뀌어야 프로세스 하나가 실행될 수 있음
  • 마지막 알고리즘 - Peterson's Solution
  • 앞의 두 가지의 문제를 잘 종합하여 둘 다 쓰면서 아무 문제없이 진행될 수 있음

  • 프로세스가 하나씩 실행되는지
  • 대기하는 경우가 발생하는지
  • 타이트하게 문맥 교환이 이루어질 경우
  • Code Segment만 존재하는 예

  • CODE SEGMENT로 시작 ASSUME으로 이름을 지정
  • MOV로 AH, AL레지스터에 값을 대입 -> AX = 1234H
  • ADD로 AH + AL 후 결과 값을 AH에 저장
  • 프로그램을 종료할 때 빨간 네모 안의 명령을 실행 -> 인터럽트 호출(시스템 콜) - 트랩
  • 데이터 정의 의사 명령어

  • 데이터를 정의하기 위해 지시자가 필요
  • Byte단위, word단위 등 단위가 정해져 있음
  • 8086은 16bit이므로 DW를 사용
  • 하나를 써도 되고 여러 개를 써도 됨 -> 콤마로 구분
  • 초기값이 없는 경우 0자리에?를 넣으면 자리만 가지고 있고 값은 없음
  • ex) 문자 출력 프로그램

  1. 코드 세그먼트, 데이터 세그먼트가 각각 1개씩 존재
  2. 실행은 별개의 문제이므로 데이터 세그먼트의 주소를 넘겨주기 위해 MOV AX, DATA와 MOV DS, AX를 써준다.
  3. AX를 거치는 이유는 MOV명령에 데이터 이름을 레지스터에 바로 쓰는 경우가 존재하지 않기 때문 -> 범용 레지스터를 거쳐서 저장
  4. INT 21H를 기점으로 나뉜다. -> 4CH는 프로그램을 종료, 2는 문자 하나를 콘솔에 출력하는 시스템 콜
  5. DL에 A를 넣고 출력 -> CX에 4243H를 넣고 CH를 출력(42 - B) -> DL에 CL값(43 - C)을 넣고 출력
  • 주소 지정 방식(Addressing mode)
  • 즉치 주소 지정 방식(Immediate addressing)

ex) MOV AX, 1234H

ex) DAT EQU(define) 1234H

  • 직접 방식(Register addressing; Direct addressing) - 레지스터의 내용을 직접 전송

ex) MOV AH, DH

     MOV DS, AX

ex) MOV AX, DH (X) -> 두 레지스터의 사이즈가 같아야 함

ex) MOV DX, [BX] -> 주소 값을 가져옴

  • 간접 방식(Memory reference addressing; Indirect addressing) - 전송하는 값이 저장되어 있는 번지를 지정(값이 메모리 내에)

ex) MOV AX, DAT -> 변수 이름 = 데이터가 들어가 있는 번지

     MOV AX, [BX+DI+4] -> 번지의 내용(계산) pointer 개념

  1. 없는 경우도 있음 -> 셋 중 하나 이상은 있어야 함
  2. 숫자만 사용할 때 8bit만 가능
  3. [BP + 0]으로만 사용 가능

  1. Data segment는 없지만 Code segment에 데이터가 선언되어있음
  2. 데이터가 있는 경우에는 반드시 MOV AX, CODE와 MOV DS, AX를 사용
  3. MOV BX, OFFSET BUFFER는 BUFFER의 주소 값을 BX에 넣는다는 의미 -> e를 가리킴
  4. BX+SI는 e에서 2칸 옆, 즉 a를 가리킴 -> a를 출력 -> +1 -> m을 출력
  5. CR후 LF는 줄 바꿈
  6. +2를 해서 p가 출력 -> 프로그램 종료

  1. 주소를 나타내는 값을 쓰고자 할 때, 크기를 지정해줌(BYTE, WORD 등)
  • 역 워드 형식 - 순서를 바꿔서 저장

  1. 4243H의 경우 43 42로 저장
  • 덧셈 명령

  • OP1에 OP2를 더해서 OP1에 저장
  • ADC의 경우 Carry Flag도 더해줌

  1. 32비트끼리 연산의 경우 16비트 자리를 각각 정해서 따로 더한 후 합침
  2. 올림이 발생하는 경우에 Carry Flag도 더해줌 -> ADC사용

  1. ADD를 사용하는 BX와 DX는 하위 16비트, ADC를 사용하는 AX, CX는 상위 16비트
  2. 응용

CODE SEGMENT
ASSUME CS:CODE, DS:DATA
	MOV AX, DATA
	MOV DS, AX

	MOV AX, VAR1
	MOV BX, VAR2
	MOV CX, VAR3
	MOV DX, VAR4

	ADD BX, DX
	ADC AX, CX
	MOV VAR1, AX
	MOV VAR2, BX

	MOV AH, 4CH
	INT 21H
CODE ENDS

DATA SEGMENT
	VAR1	DW	1223H
	VAR2	DW	8000H
	VAR3	DW	2000H
	VAR4	DW	8123H
DATA ENDS

END

 

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA
	
	MOV AX, DATA
	MOV DS, AX

	MOV AX, VAR1
	ADD AH, AL

	MOV VAR2, AH

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	1234H
	VAR2	DB	?
DATA ENDS

END

CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX

	MOV BX, OFFSET VAR1

	MOV AH, [BX]
	MOV AL, [BX+1]

	ADD AH, AL
	MOV VAR2, AH

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	1234H
	VAR2	DB	?
DATA ENDS

END

  • 응용 프로그램 - 분기와 반복
  • 증가, 감소 명령

  1. INC에 OP(레지스터나 메모리)를 넣으면 1 증가
  2. DEC에 OP를 넣으면 1 감소
  3. 16비트, 8비트 둘 다 가능
  • 키 입력 방법

  1. 키보드에서 입력받을 수 있음
  2. 에코가 있는 입력은 AH 1번, 없는 입력은 AH 8번 -> 화면에 출력되는지 안되는지의 차이
  3. 키보드로부터 입력을 받을 때까지 기다림 AH로 시스템 콜을 호출하고 입력받은 값을 AL에 저장
  4. 입력받은 값들을 차례대로 출력
  • 비교 명령어

  1. 비교하여 같으면 플레그를 1로 만들고 다르면 0으로 만듦
  2. 플레그 값에 따라 명령을 달리 수행

  1. 두 값의 AND연산 결과에 따라서 플레그를 달리해줌
  2. CL이나 ZF의 값이 변하면서 플레그가 달라짐
  • 분기 명령어의 비교

  1. AX와 0을 비교
  2. 같으면 JE를 0으로
  3. 플레그의 값에 따라 점프하는 라인이 달라짐

  1. 값을 입력 받음
  2. DL에 저장
  3. DL값을 1 증가시킨 후 출력
  4. JMP로 다시 처음으로 돌아감 -> 무조건 분기(무한루프)

  1. AX = 0, CX = 1
  2. AX + CX = 1
  3. CX += 1
  4. CX와 10 비교
  5. JBE -> 작거나 같으면
  6. SUM10으로 돌아감
  7. 11이 되는 순간 JBE를 안 거치고 다음으로 넘어감 -> 10번 반복
  8. 1~10까지 AX에 더한 것을 TOTAL에 저장

  1. A : 크다
  2. B : 작다
  3. E : 같다
  4. N : 아니다
  5. A> B이면 JA -> CMP A, B 후에 JA를 쓰면 A가 큰 경우의 조건문 => JNBE는 작거나 같지 않다(크다)
  6. A>=B이면 JNB(작지 않다), JAE(크거나 같다)

  1. 플레그 레지스터를 이용한 분기
  2. 한 번 읽어볼 것

  1. 에코 있는 입력을 받음, AL에 저장
  2. 20H(스페이스)와 비교
  3. 같으면 EXIT로 점프 -> 프로그램 종료
  4. 아니면 'A'와 비교
  5. 'A'보다 작으면 PRINT로 점프 -> 입력받은 값을 출력 -> NEXT로 돌아가서 다시 입력 받음
  6. 아니면 'Z'와 비교
  7. 'Z'보다 크면 PRINT
  8. 위의 조건들을 살펴보았을 때, 스페이스를 입력받으면 프로그램 종료, A보다 작으면 출력, Z보다 크면 출력이므로 대문자 A~Z까지의 문자만 조건문에 걸리지 않고 넘어갈 수 있음
  9. 대문자인 경우 AL에 'a' - 'A'(대소문자 차이)를 더해줌 -> 대문자를 소문자로 바꿔줌
  10. 소문자를 출력
  11. 대문자를 소문자로 바꾸는 경우도 생각해보자
  • 예제

CODE SEGMENT
	ASSUME CS:CODE
	MOV CX, 10

LOOP1:	MOV AH, 8
	INT 21H

	CMP AL, 20H
	JE EXIT

	CMP AL, 'a'
	JB PRINTZ

	CMP AL, 'z'
	JA PRINTZ

	MOV DL, AL
	MOV AH, 2
	INT 21H

	LOOP LOOP1

EXIT:	MOV AH, 4CH
	INT 21H

PRINTZ:	MOV DL, '0'
	MOV AH, 2
	INT 21H
	DEC CX
	CMP CX, 0
	JE EXIT
	JMP LOOP1

CODE ENDS
END
  • 반복 명령어

  1. LOOP는 CX의 값을 필수로 사용 -> 카운터의 기능
  2. CX의 값만큼 반복 -> 1씩 줄여가며 반복
  3. 중간에 CX값을 바꿔버리면 횟수가 바뀌어 무한루프가 발생할 수 있음

  1. 참고만 할 것 -> 너무 깊다!
  • 응용 코드 작성

  1. 모델 스몰 부분은 그대로 써줌
  2. 스택 - 시작 부분
  3. 데이터 - 데이터 세그먼트 대신에 써줌 - 더 간편하게 사용 가능
  4. @data : get data segment -> 반드시 써야 하는 부분, 세그먼트 이름 대신에 써야하는 것
  5. 나머지 부분은 포맷, 똑같이 써도 되고 이전에 배운 것들처럼 써도 됨
  6. int 21h의 9번 기능 -> 2번은 문자 하나, 9번은 문자열을 출력
  7. 문자가 끝나는 부분은 $로 끝을 냄 -> 처음부터 $전까지 출력
  8. dx에 prompt의 시작 주소를 넣어줌 -> 시작 주소의 문자열을 출력($까지)
  9. 21번 -> 에코 있는 입력
  10. 입력받은 값에서 20h를 빼고 char에 저장
  11. msg의 시작 주소를 dx에 넣고 출력 -> 0Dh.0Ah. 는 줄 바꿈
  12. 9번은 시작 주소로부터 $까지 출력하는 함수
  13. 실행 예

  • 도스 command line에서의 실행 예

  • 스택의 동작

  • 16bit 컴퓨터이므로 push와 pop은 2byte씩 이루어짐
  • push로 OP의 값을 stack에 저장, pop으로 stack의 데이터를 OP에 저장

  1. AX, BX PUSH
  2. PUSHF는 플레그를 PUSH 한다는 의미
  3. POP은 OP를 꺼낸다는 뜻이 아니고 정해진 순서대로 꺼내서 OP에 저장한다는 의미
  • 서브루틴 사용법

  • 서브루틴은 C언어에서 위치를 호출하는 것
  • CALL은 되돌아올 주소를 자동으로 stack에 저장한 후 lable로 점프 -> 진행하다가 return을 만나면 저장해 두었던 주소를 pop 하여 되돌아감

  1. 레이블을 콜 하여 점프 후 RET를 만나면 다시 돌아감

  • 잘 읽어보고 만들어볼 것
  • 정답

  • 코드를 이해하여 앞과 비교해보고 직접 작성도 해볼 것
  • AND와 SHIFT를 사용한 코드
CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX
	MOV CX, 12

LOOP1:	MOV DX, VAR1
	SHR DX, CL
	AND DX, 000FH

	CMP DL, 0AH
	JAE LEVEL1
	
	ADD DL, '0'
	MOV AH,2
	INT 21H
	
	CMP CL, 0
	JE EXIT

	SUB CL, 4

	JMP LOOP1

LEVEL1:	ADD DL, 'A'-0AH
	MOV AH,2
	INT 21H

	CMP CL, 0
	JE EXIT

	SUB CL, 4

	JMP LOOP1

EXIT:	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT
	VAR1	DW	2B3FH

DATA ENDS

END
  • 10진수 출력
CODE SEGMENT
	ASSUME CS:CODE, DS:DATA

	MOV AX, DATA
	MOV DS, AX

	MOV CX, 0
	MOV AX, 0

	MOV AX, VAR1
	MOV SI, 10

LOOP1:
	MOV DX, 0
	DIV SI
	PUSH DX
	INC CX
	CMP AX, 0
	JNE LOOP1

PRINT:	
	POP DX
	ADD DL, '0'
	MOV AH, 2
	INT 21H
	
	DEC CX
	CMP CX,0
	JNE PRINT

	MOV AH, 4CH
	INT 21H

CODE ENDS

DATA SEGMENT

	VAR1	DW	1234H

DATA ENDS

END
  • PROC에 의한 서브루틴 작성 - 참고

  • System Call의 예

  • 비디오 스테이터스를 돌려줌
  • 설명
  • 입력값을 주면 하는 일, 출력 값

  • 스크롤을 up, down 해주는 시스템 콜

  • prompt를 어디로 옮길 것인지
  • 커서 포지션
  • 예제들 -> 동작시켜볼 것

  • 예제의 내용

  1. 출력한 것을 박스 안에서 스크롤할 수 있음
  2. 출력해놓고 스크롤시키는 프로그램
  3. 응용으로 스크롤 속도를 늦추거나 반대방향으로 스크롤 되게 수정해볼 수 있음 -> 이것도 해볼 것

+ Recent posts