데샤봇


IPC랑은 별개지만 중요



프로세스 핸들에는 커널 오브젝트 상태가 존재한다.

상태 : 리소스의 현재 상황을 알리기 위함


프로세스가 작동중이면

커널 오브젝트 상태 : Non-Signaled

작동중이 아니라면

커널 오브젝트 상태 : Signaled


그 밖에 다른 상태 정보들도 존재한다.


위의 예는 프로세스만을 대상으로 설명했지만 기타 리소스별로 나타내는 의미가 다른데 많고 번잡해도 중요한 것들이 존재



WailForSingleObject() 함수는 전달한 임의의 프로세스 커널 오브젝트 상태가 Signaled 상태로 변경되기를 기다리는 함수다.


함수에 커널 오브젝트 핸들을 전달하고, 얼마나 기다릴 것인지? 기다린다.



CPU 코어가 많아서 멀티프로세스 환경에서 연산을 분배해서 나눠가져야 하는 상황이 있는데, 이러한 멀티프로세스 환경에서 사용가능할 함수를 사용해


CPU 코어의 부담을 나눈다.



이런 식으로 진행하고자 한다.


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
/*
        NonStopAdderManager.cpp
*/
#include <stdio.h>
#include <windows.h>
#include <tchar.h>
int _tmain(int argc, TCHAR* argv[])
{
    STARTUPINFO si1 = { 0, };
    STARTUPINFO si2 = { 0, };
    PROCESS_INFORMATION pi1;
    PROCESS_INFORMATION pi2;
    DWORD return_val1;
    DWORD return_val2;
    TCHAR command1[] = _T("Branch1.exe 1 5");
    TCHAR command2[] = _T("Branch2.exe 6 10");
    DWORD sum = 0;
    si1.cb = sizeof(si1);
    si2.cb = sizeof(si2);
    CreateProcess(NULL,
        command1,
        NULL,
        NULL,
        TRUE,
        0,
        NULL,
        NULL,
        &si1,
        &pi1
    );  //CreateProcess 1
    CreateProcess(NULL,
        command2,
        NULL,
        NULL,
        TRUE,
        0,
        NULL,
        NULL,
        &si2,
        &pi2
    );  //CreateProcess 2
    CloseHandle(pi1.hThread);
    CloseHandle(pi2.hThread);
    //WaitForSingleObject(pi1.hProcess, INFINITE);
    //WaitForSingleObject(pi2.hProcess, INFINITE);
    GetExitCodeProcess(pi1.hProcess, &return_val1);
    GetExitCodeProcess(pi2.hProcess, &return_val2);
    if (return_val1 == -1 || return_val2 == -1)
        return -1; //비정상적 종료
    sum += return_val1;
    sum += return_val2;
    _tprintf(_T("total : %d \n"), sum);
    CloseHandle(pi1.hProcess);
    CloseHandle(pi2.hProcess);
    return 0;
}
cs


44, 45 : WFS 함수


CreateProcess 1, CreateProcess 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
        PartAdder.cpp
*/
#include <stdio.h>
#include <windows.h>
#include <tchar.h>
int _tmain(int argc, TCHAR* argv[])
{
    if (argc != 3)
        return -1;
    DWORD start = _ttoi(argv[1]);
    DWORD end = _ttoi(argv[2]);
    DWORD total = 0;
    for (DWORD i = start; i <= end; i++)
        total += i;
    return total;
}
cs



만약 주석을 해제하지 않는다면 결과로 518이 나온다.


각각의 return_val변수가 259를 담고 있는데, 오류코드인가? 값이 고정되어 있는 것을 보면 오류코드가 맞는 듯 한데...


이러면 만약 adder가 259를 리턴하면 어쩌려고 이런 값을 뱉는거지?


잘모르겠군


주석을 해제하면 정답이 잘 나온다.

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

컴구세번째 함수호출  (0) 2019.10.08
프로세스간 통신(IPC)2  (0) 2019.10.01
프로세스간 통신  (0) 2019.09.26
커널 오브젝트, 핸들의 종속관계  (0) 2019.09.26
커널 오브젝트 오브젝트 핸들  (0) 2019.09.26

즐



1 Program != 1 Process


1 Program == n Process


하나의 프로그램을 이루기 위해 n개의 프로세스가 서로 데이터 통신을 해야하는 경우가 종종 있다.


이 때, 프로세스간 통신이 원활히 이루어져야 좋은 프로그램이 될 것



프로세스의 메모리는 안정성을 이유로 OS에 의해 분리되어있다. (고립되어있다.)


그렇기 때문에 프로세스간 공유할 메모리 공간을 확보해야하는데, 그러한 공간을 OS가 또한 제공해준다.


이러한 기법을 Inner Process Communication, IPC라 부른다.


프로세스간 통신

프로세스간 데이터 송수신 -> 메모리 공유


-> 데이터를 순차적으로 보내는 것이 아니라, A프로세스가 공유가 가능한 어떠한 메모리 공간을 생성, B프로세스는 그곳에 보낼 데이터를 집어넣는다.

A프로세스는 생성한 메모리 공간을 확인, 데이터가 있으면 데이터를 받아온다.



메일슬롯


IPC 데이터 통신 기법의 하나. Receiver는 데이터를 받을 수 있는 우체통을 만들기 위해 함수를 호출한다. OS는 그러한 함수 호출을 통해 Receiver와 Sender가 접근 가능한 메모리 공간을 마련한다.


Receiver가 "서울 100번지"라는 이름의 주소를 설정해 OS에 요청하면, 주소를 알고 있는 Sender가 주소에 데이터를 붙여서 전송하면 OS가 그것을 보고 해당 주소에 보낸다.


핵심 함수는 우체통 생성, 전송, 송신의 3가지 함수다.(추가적으로 하나 더 있다.)


여기서 중요한 점은 이러한 방식의 기법이 단방향이라는 것이다. 


일반적으로 통신은 양방향이지만, 이러한 우체통의 송수신 방식은 단방향이기때문에 Sender는 데이터를 보낼수는 있지만, 받을수는 없다.


또한 n개의 Receiver가 동일한 주소의 우체통을 생성할수도 있다. 이 경우 Sender가 해당 주소로 데이터를 전송할 때 한번에 각각 Receiver가 데이터를 받을 수 있다. 


이를 브로드캐스팅이라고 한다.



Receiver


CreateMailSlot

우체통을 만든다


Sender


CreateFile

우체통과의 길을 뚫는다.


밑의 OX는 단방향 통신의 특성을 보여준다.


왜 송수신을 하는데 함수 이름이 File인가?


근본적으로 메일슬롯 방식은 메모리 공유다. 파일 기반으로 구현이 되어 있어서 기존 함수를 사용하는 것이다.


다른 의미로는 파일 기반으로 구현되어 있다는 것을 노출한 것이다.


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
/*
        MailReceiver.cpp
*/
#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#define SLOT_NAME    _T("\\\\.\\mailslot\\mailbox")
int _tmain(int argc, LPTSTR argv[])
{
    HANDLE hMailSlot;  //mailslot 핸들
    TCHAR messageBox[50];
    DWORD bytesRead;  // number of bytes read
          /* mailslot 생성*/
    hMailSlot = CreateMailslot(SLOT_NAME, 0, MAILSLOT_WAIT_FOREVER, NULL);
    if (hMailSlot == INVALID_HANDLE_VALUE)
    {
        _fputts(_T("Unable to create mailslot!\n"), stdout);
        return 1;
    }
    /* Message 수신*/
    _fputts(_T("******** Message ********\n"), stdout);
    while (1)
    {
        if (!ReadFile(hMailSlot, messageBox, sizeof(TCHAR) * 50, &bytesRead, NULL))
        {
            _fputts(_T("Unable to read!"), stdout);
            CloseHandle(hMailSlot);
            return 1;
        }
        if (!_tcsncmp(messageBox, _T("exit"), 4))
        {
            _fputts(_T("Good Bye!"), stdout);
            break;
        }
        messageBox[bytesRead / sizeof(TCHAR)] = 0; //NULL 문자 삽입
        _fputts(messageBox, stdout);
    }
    CloseHandle(hMailSlot);
    return 0;
}
cs


7 : .의 위치에는 컴퓨터 이름을 넣어야 한다. .의 의미는 나 자신을 의미한다. Receiver는 사용자 컴퓨터에서 실행하기 때문에 .밖에 올 수 없다. 나 자신의 위치에 데이터를 받아야지


14 : 두번째 인자는 버퍼 크기를 의미한다. 0은 허용최대치

세번째 인자는 데이터가 우체통에 들어올때까지 계속 기다릴것인지를 묻는 옵션이다. 이 경우 Blocked 상태가 되는 것


24 : ReadFile의 첫번째 인자는 슬롯을 지정하는 것이다. hMailSlot로 CreateMailSlot함수를 호출하면 슬롯이 생성되면서 슬롯의 핸들이 반환된다. 그 핸들을 넣어 Read의 대상(슬롯)을 지정한다

두번째 인자는 읽은 데이터를 저장할 버퍼를 의미한다

세번째 인자는 읽는 데이터의 최대 크기를 의미한다

네번째 인자는 실제로 읽은 데이터 크기를 얻기 위해 존재한다.

다섯번째 인자는 보류


38 : 커널오브젝트의 소멸을 돕기 위해 UC를 내리기 위한 CloseHandle 함수다.



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
/*
        MailSender.cpp
*/
#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#define SLOT_NAME _T("\\\\.\\mailslot\\mailbox")
int _tmain(int argc, LPTSTR argv[])
{
    HANDLE hMailSlot;  //mailslot 핸들
    TCHAR message[50];
    DWORD bytesWritten;  // number of bytes write
    hMailSlot = CreateFile(SLOT_NAME, GENERIC_WRITE, FILE_SHARE_READ, NULL,
        OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
    if (hMailSlot == INVALID_HANDLE_VALUE)
    {
        _fputts(_T("Unable to create mailslot!\n"), stdout);
        return 1;
    }
    while (1)
    {
        _fputts(_T("MY CMD>"), stdout);
        _fgetts(message, sizeof(message) / sizeof(TCHAR), stdin);
        if (!WriteFile(hMailSlot, message, _tcslen(message) * sizeof(TCHAR), &bytesWritten, NULL))
        {
            _fputts(_T("Unable to write!"), stdout);
            CloseHandle(hMailSlot);
            return 1;
        }
        if (!_tcscmp(message, _T("exit")))
        {
            _fputts(_T("Good Bye!"), stdout);
            break;
        }
    }
    CloseHandle(hMailSlot);
    return 0;
}
cs


7 : 같은 컴퓨터기때문에 .이 찍혀야한다. 이게 왜 있냐면 네트워크로 연결되어 있는 서로 다른 컴퓨터에서도 사용이 가능하다. 

근데, TCP/IP를 사용하는것이 일반적이다. 이거 잘 안씀


13 : 첫번째 인자는 연결 슬롯의 이름이다

두번째 인자는 Read인지, Write인지를 결정하는 옵션이다.

다섯번째 인자는 생성 방식을 의미한다. OPEN_EXISTING은 새로 만들것인지, 존재하는 것을 연결할 것인지 뭐 그런것

Sender의 CreateFile은 그 인자가 대체로 고정되어있는 편이다. 일단 읽고 넘어가라고함


24 : 첫번째 인자는 주소정보를 지정하는 것이다

두번째 인자는 전송 데이터를 담은 버퍼다

세번째 인자는 최대 전송 데이터 크기다

네번째 인자는 전송 결과를 의미한다.

다섯번째는 보류


36 : 클로즈핸들ㅇㅇ



결과 

왼쪽은 Sender

오른쪽은 Receiver


마치 소켓통신같군


추가할거더잇음 함수좀더봐야함

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

프로세스간 통신(IPC)2  (0) 2019.10.01
Signaled Non-Signaled  (0) 2019.09.27
커널 오브젝트, 핸들의 종속관계  (0) 2019.09.26
커널 오브젝트 오브젝트 핸들  (0) 2019.09.26
프로세스, 스케줄러  (0) 2019.09.25

즐




사용자에 의해 프로세스 A가 실행된다.

-> 프로세스 A의 부모 프로세스는 OS다


프로세스 A에 의해 프로세스 B가 실행된다.

-> 프로세스 B의 부모 프로세스는 A다.


프로세스 B에 의해 파일이 실행된다.

-> 파일의 부모 프로세스는 프로세스 B다.


프로세스는 실행될 때 프로세스, 프로세스 커널 오브젝트, 프로세스 핸들이 실행된다.


프로세스는 프로세스 핸들 테이블을 가지고 있다.(사진 참고)


프로세스 핸들 테이블에는 프로세스가 들고 있는 핸들 키, 그리고 핸들 대상이 존재한다.


프로세스 A

프로세스 핸들 번호는 운영체제로부터 부여받는다. 프로세스 A가 실행되면 프로세스 A의 핸들 테이블에 자신의 커널 오브젝트를 지정하는 핸들 값이 생성된다.


위 경우 핸들값은 3이다. 프로세스 A의 커널 오브젝트 UC(Usage Count)가 1로 올라갔다.


프로세스 B

프로세스 A로부터 생성된 프로세스 B도 생성과 동시에 커널 오브젝트와, 핸들 테이블, 운영체제로부터 생성된 핸들값이 핸들 테이블에 저장된다. 위 경우 값은 3이다.


또한, 프로세스 B의 커널 오브젝트에 접근할 수 있는 핸들값이 프로세스 B를 생성한 프로세스 A에도 리턴된다. 위 경우 값은 7이다.


즉, 프로세스 B의 커널 오브젝트 UC는 프로세스 B 자신의 핸들과, 프로세스 A의 핸들로 인해 2가 된다.






프로세스 B의 설명으로, 부모 프로세스도 핸들 테이블에 자식 프로세스의 커널 오브젝트 접근 핸들이 저장된다는 것을 알게 되었다.


프로세스 A 역시 부모 프로세스 OS가 존재하기 때문에, 프로세스 A 커널 오브젝트 UC는 2가 된다.


파일


파일은 프로세스가 아닌 단순 리소스이기 때문에 제어가 불가능하다. 즉 프로그램 코드가 없기 때문에 스스로 커널 오브젝트를 제어할 수 없다.


이 경우 파일의 커널 오브젝트는 생성이 되지만 그 커널 오브젝트에 접근이 가능한 것은 파일의 부모 프로세스인 프로세스 B다. 그렇기 때문에 위 경우의 파일 커널 오브젝트의 UC는 1이다.


정리로 인해, 핸들 테이블은 프로세스에 종속적이라는 사실을 알게 되었다.



만약 프로세스 B를 종료한다면, 프로세스 B를 종료해도 프로세스 B의 커널 오브젝트는 사라지지 않는다.


그 이유는 프로세스 A가 프로세스 B의 커널 오브젝트에 접근하는 핸들을 가지고 있기 때문이다.


레퍼런스 카운팅 방식과 비슷하게, 임의의 프로세스 커널 오브젝트에 접근하고 있는 핸들이 하나라도 있다면 커널 오브젝트는 사라지지 않는다.



라고 했는데...



1. 프로세스 A를 생성했을 때, 프로세스 핸들 테이블에 자기 자신을 가리키는 핸들이 정말 생성 되는가?


2. 자식 프로세스 B를 종료했을 때, 부모 프로세스 A는 자식 프로세스 B의 커널 오브젝트 핸들을 가지고 있을 필요가 있을까?


부모 프로세스가 자식 프로세스의 커널 오브젝트 핸들을 가지고 있어야 하는 이유


일반적인 코드에서, return 0;를 사용하는 의미는 프로그램을 정상 종료하겠다는 의미다. 


여기서 값 0, 1, -1 등은 해당 프로세스의 커널 오브젝트에 들어간다.


이때 부모 프로세스가 자식 프로세스의 실행에 밀접한 관련이 있다면 자식 프로세스의 동작 유무, 종료 유무는 상당히 중요한 부분이 있는데


만약 자식 프로세스가 비정상적 종료코드를 받거나 정상적 종료코드를 커널 오브젝트에 받은 채 프로세스와 커널 오브젝트를 동시에 소멸시켜 버린다면


부모 프로세스는 자식 프로세스가 정상적인 종료가 되었는지, 비정상적 종료가 되었는지 알 길이 없다.


그래서 임의의 프로세스 커널 오브젝트에 관심을 가지고 있는 프로세스가 하나라도 있으면 임의의 프로세스는 소멸되더라도 프로세스 커널 오브젝트는 사라지지 않는다.


ANSI함수와 Windows 시스템 함수


C표준인 ANSI함수를 실행하면 윈도우 환경에서 ANSI함수는 윈도우 시스템 함수를 호출한다. 마찬가지로, ANSI함수를 유닉스 환경에서 실행하면 유닉스 시스템 함수를 호출한다.


ANSI함수는 각각 OS의 시스템 함수를 랩핑한채 존재하는 것이다.


여기서 주의해야 할 점은 윈도우 시스템 함수를 랩핑되지 않은 함수이기 때문에 빠르다고 생각할 것이 아니라(물론 빠르긴 하지만)


윈도우 시스템 함수, 유닉스 시스템 함수들은 ANSI함수에 비해 제공하는 기능이 훨씬 많다는 측면에서 생각해야 한다.


프로세스 핸들 테이블은 자기 자신의 핸들값을 가지고 있을까?


사실 임의의 프로세스를 생성하더라도 자기 자신의 핸들값이 핸들 테이블에 들어가지는 않는다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    //우선순위를 변경하는 함수
    //GetCurrentProcess() 현재 프로세스의 핸들 정보를 가져오는 함수
    //HIGH_PRIORITY_CLASS 우선순위를 높이는 매크로
    SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
    while (1)
    {
        //Sleep()함수는 Blocked 상태로 변환된다. 우선순위를 포기하는 것
        //우선순위를 관찰하기 위해선 Ready 상태로 두어야 한다.
        for (DWORD i = 0; i < 10000; i++)
            for (DWORD i = 0; i < 10000; i++);    //Busy Waiting!!
        _fputts(_T("Operation2.exe \n"), stdout);
    }
    return 0;
}
 
cs


여기서 GetCurrentProcess()는 OS로부터 임의의 핸들 값을 부여받아 핸들 테이블에 집어넣은 값이 아니라. 고유한 값을 가지는 특정 상수다. 

(자기 자신을 호출하는 IP주소처럼)


즉 핸들 테이블의 내용물은 증가하지 않지만, 커널 오브젝트의 UC는 증가한다. 그냥 프로세스와 같이 들고있는 것이다.



STARTUPINFO si = { 0 };

생성 정보를 담는다


PROCESS_INFORMATION pi;

프로세스 정보를 담는다


핸들 정보는 프로세스 정보를 담은 pi에 들어간다.


커널 오브젝트는 종속적으로 여러 프로세스에 의해 접근이 가능하다


다른건 별거없다. 부모 프로세스가 자식 프로세스의 우선순위를 변경하는 예제다.



CloseHandle(pi.hProcess);


핸들을 끊는 함수다. 자식 프로세스 정보를 담고있는 변수 pi의 핸들을 닫겠다고 OS에 요청을 보내면 OS가 pi 커널 오브젝트의 UC를 1 내린다.



커널 오브젝트의 종속 관계

 

“커널 오브젝트는 Windows 운영체제에 종속적이다.”

 

‘종속’이라는 단어는 뜻이 상당히 넓다. 기본적으로 종속이라는 말은 독립적이지 못하다는 뜻이다.

 

예를 들어, 도서 대여점에 가면 많은 양의 도서가 있다.

 

이 도서들은 도서 대여점에 등록된 고객들만 대여할 수 있다.

 

그렇다면, 이 책들은 누구에게 종속적일까?

 

당연히 도서 대여점에 종속적이다.

 

도서 대여점에 있는 도서는 특정 고객에게 소유되는 물건이 아니다. 따라서 어느 누구라도 대여 관계가 깨끗하면 대여가 가능하다.

 

이를 위해, 도서 대여점에서는 도서를 소유하고 관리한다.

 

때문에, 고객은 임의로 도서를 폐기 할 수 없지만 대여점은 임의로 폐기 할 수 있다.

 

그렇다면, 커널 오브젝트가 Windows 운영체제(커널)에 종속적인 이유를 들겠다.

 

첫 째, 도서(커널 오브젝트)는 고객(프로세스)에 종속적이지 않고, 도서 대여점(운영체제)에 종속적인 관계로, 도서의 폐기(커널 오브젝트의 소멸)은 도서 대여점(운영체제)에 의해 결정된다.

 

둘 째, 도서(커널 오브젝트) 는 고객(프로세스)에게 종속되는 것이 아니므로, 여러 고객(여러 프로세스)에 의해 대여(접근) 이 가능하다.



저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

Signaled Non-Signaled  (0) 2019.09.27
프로세스간 통신  (0) 2019.09.26
커널 오브젝트 오브젝트 핸들  (0) 2019.09.26
프로세스, 스케줄러  (0) 2019.09.25
컴퓨터를 디자인하자  (0) 2019.09.23



커널

-> 기존에 커널 = OS였지만 시대가 변하면서 점차 의미가 분리되었다.


커널 오브젝트

커널에 의해 관리되는 리소스 정보를 담고 있는 데이터 블록

-> 윈도우에 의해 생성되고 소멸되는 리소스를 관리하기 위한 데이터 블록을 커널 오브젝트라고 한다.


-> 커널과 커널 오브젝트는 다르다. 커널 오브젝트는 프로세스와 밀접한 관련이 있다.


또한 파이프 커널 오브젝트, 프로세스 커널 오브젝트, 쓰레드 커널 오브젝트는 각각 다르게 디자인되어있다.



사용자가 프로세스를 실행하면 프로세스만 실행되는 것이 아니라 os로 인해 프로세스에 대한 커널 오브젝트가 생성되고 커널 오브젝트는 프로세스 정보를 담고있고 관리하기 위한 커널 오브젝트가 생성된다.


또한 커널 오브젝트를 관리하기 위한 커널 오브젝트 관리 구조체도 생성된다. 커널 오브젝트 관리 구조체로 인해 커널 오브젝트가 생성된다.



예)

프로세스를 생성하면 프로세스 커널 오브젝트가 생성된다.


만약 사용자가 이 프로세스의 연산 우선순위를 높이고 싶다고 생각하고 실제로 우선순위를 높이기 위해서는 커널 오브젝트에 접근하여야 하는데, 커널 오브젝트는 임의의 접근이 불가능하다.


이 때 커널 오브젝트를 다루기 위해 필요한 것이 핸들로, 사용자가 os에 프로세스를 실행하도록 요청하면 os는 프로세스와, 프로세스 커널 오브젝트와, 프로세스 커널 오브젝트 핸들(프로세스 핸들)을 생성한다.


핸들은 os에 의해 특정 숫자로 넘버링된 이름을 가지고 있는데(실제로 int형 정수로 구성되어 있다.) 이를 이용하여 커널 오브젝트에 접근할 수 있게 된다.



Operation2.exe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    //우선순위를 변경하는 함수
    //GetCurrentProcess() 현재 프로세스의 핸들 정보를 가져오는 함수
    //HIGH_PRIORITY_CLASS 우선순위를 높이는 매크로
    SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
    while (1)
    {
        //Sleep()함수는 Blocked 상태로 변환된다. 우선순위를 포기하는 것
        //우선순위를 관찰하기 위해선 Ready 상태로 두어야 한다.
        for (DWORD i = 0; i < 10000; i++)
            for (DWORD i = 0; i < 10000; i++);    //Busy Waiting!!
        _fputts(_T("Operation2.exe \n"), stdout);
    }
    return 0;
}
cs


Operation1.exe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <tchar.h>
#include <Windows.h>
 
int _tmain(int argc, TCHAR* argv[])
{
    STARTUPINFO si = { 0, };
    PROCESS_INFORMATION pi;
    si.cb = sizeof(si);
    TCHAR command[] = _T("branch.exe");
    CreateProcess(NULL, command, NULL, NULL, TRUE, 0, NULL, NULL, &si, &pi);
    while (1)
    {
        for (DWORD i = 0; i < 10000; i++)
            for (DWORD i = 0; i < 10000; i++);
        _fputts(_T("Operation1.exe \n"), stdout);
    }
    return 0;
}
cs


싱글코어 기반의 출력결과

않이


듀얼이상에선 순서대로 나온다.

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

프로세스간 통신  (0) 2019.09.26
커널 오브젝트, 핸들의 종속관계  (0) 2019.09.26
프로세스, 스케줄러  (0) 2019.09.25
컴퓨터를 디자인하자  (0) 2019.09.23
64비트 기반 프로그래밍, GetLastError  (0) 2019.09.23

프로세스란?


일반인 : 실행중인 프로그램


개발자 : 메모리 구조(OS에 의해 할당되는 메인 메모리의 리소스 뿐 아니라 가상 메모리의 리소스까지 포함), 실행중인 프로그램에 독립적인 레지스터 Set, etc


요즘 프로세스는 컨텍스트 스위칭을 피하기 위해 레지스터 Set을 여러개 만들어 스위칭에 의한 오버헤드를 피하고 있다.




스케줄러 : 운영체제에서 제공해주는 소프트웨어 장치(혹은 블럭)


공평한 스케줄링 알고리즘도 큰 이슈중 하나다



Running 상태 : CPU에 의해 실행중인 상태

Ready 상태 : 스케줄러에 의해 선택되길 기다리는 상태, 실행 준비는 다 끝난 상태

Blocked 상태 : 연산중에서 ALU(CPU)에 의존적인 연산이 있고, I/O연산처럼 의존적이지 않은 연산이 있다. Running상태는 CPU 연산이 진행되는 중이고, Blocked 상태는 현재 I/O 연산중인 프로세스를 뜻한다.

I/O연산이 끝나면 Blocked 상태가 끝나고 Ready 상태로 변한다.




컨텍스트 스위칭은 일반적으로 멀티태스킹 환경에서 1초에도 수십번씩 한다.

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

커널 오브젝트, 핸들의 종속관계  (0) 2019.09.26
커널 오브젝트 오브젝트 핸들  (0) 2019.09.26
컴퓨터를 디자인하자  (0) 2019.09.23
64비트 기반 프로그래밍, GetLastError  (0) 2019.09.23
문자셋 SBCS, MBCS, WBCS  (0) 2019.09.19


프로그래머 관점


컴퓨터 구조를 잘 아는 프로그래머도 컴퓨터 디자인에 참여

 -> 명령어를 짜거나 한다.


컴퓨터 디자인은 레지스터와 명령어 디자인


-> CPU, GPU를 짜기 위해서는 하드웨어 전문가가 ASIC 등을 이용해 로직을 짠다. 이용해 로직을 짠다. GPU같은 경우는 그래픽 프로세싱을 위한 알고리즘 전문가도 필요하며, 컴퓨터 기기와 조화를 이루게 하기 위해 인터페이스 전문가도 들어가게 된다. 여기에 프로그램 개발자 또한 포함되는데, 개발자들은 명령어 디자인과 같은 기기 실 사용에 관련이 있는 부분에 관여를 한다.


레지스터 디자인의 핵심


레지스터는 몇 비트로 구성할 것인가?

 -> 32비트 컴퓨터라면 레지스터 또한 32비트, 64비트 컴퓨터라면 64비트로 디자인 하는게 일반적이다. 성우횽은 16비트로 해보겠다고 한다.


몇 개 정도로 레지스터를 구성할 것인가?

-> 레지스터는 많으면 많을수록 좋다. 성우횽은 일단 8개로 해보겠다고 한다.


레지스터 각각을 무슨 용도로 사용할 것인가?

-> 레지스터는 범용적으로 사용하기보단 일반적으로 특정 용도를 가지고있다. 성우횽은 r4 ~ r7까지 용도를 주었다.

r4 : instruction register

r5 : stack pointer

r6 : link register

r7 : program counter


r0 ~ r3 레지스터는 연산을 위한 범용 레지스터다.



명령어 구조 및 명령어 디자인




명령어의 기본 모델


16비트 명령어

 -> 레지스터를 16비트로 만들자고 했기 때문에 명령어 또한 16비트가 되어야 한다.


사칙연산 명령어 구성


16비트 명령어 안에는 예약, 연산자, 저장소, 피연산자1, 피연산자2가 들어가 있다.


명령어 디자인이 되어 있어야 ALU가 명렁어를 해독할 수 있다. CPU디자인이 명령어 디자인과 병행되어야 하는 이유고, 하드웨어 전문가와 소프트웨어 전문가가 협업해야 하는 이유다.


이 경우 연산자에 3비트, 저장소에 3비트, 피연산자 각각 4비트로 구성했다.

-> 하지만 명령어에 따라 명령어 구성이 달라질 수 있다.(Store, Load 참고) 명령어 구성요소는 고정되어있지 않다.


연산 결과는 일단 레지스터에 저장한다. CPU 역시 마찬가지다. 여기서 레지스터가 8개이기때문에 저장소 3비트로 표현이 충분하다.


피연산자에는 레지스터 or 숫자가 올 수 있다. 이렇듯 조건이 붙게 되면 그만큼 비트를 조건 판독에 할애해야 한다. 첫번째 비트가 0이면 숫자, 1이면 레지스터라는 약속을 두거나 하는 등의 양보를 해야 한다는 것.


RISC와 CISC


명령어가 단순한 CPU 구조를 RISC(Reduced)라고 부른다. CISC(Complexed)는 복잡한 명령어를 뜻한다. 사용자가 원하는 명령을 다 적용시킬 수 있다.


RISC는 명령어 조합이 다양하지 않다. CISC로 한줄짜리 명령어를 RISC로 수십 줄 가량이 필요한 경우가 생긴다. 하지만 속도면에서는 RISC를 사용하는 것이 더 효율적이다.


RISC CPU의 연산 단계는 Fetch, Decode, Execution로 이루어지는데, 이 단계는 각각 1클락에 이루어진다고 보면 된다.


예를 들어 하나의 명령어를 실행하는데 드는 클락 비용은 3클락이다. 그 말은 5개 명령어를 수행하는데 드는 클락은 15클락이 되는 것이다.(3 * 5 = 15)


하지만 한 명령어를 3클락에 수행하지 못하는 경우를 주로 CISC라고 부르는데, 만약 3클락에 다 해결할 수 있으면 첫번째 명령어를 Fetch할때 다른 명령어를 Decode할 수 있고, 명령어를 Decode할 때 다른 명령어를 Execution 할 수 있다.

 -> 즉, Fetch와 Decode와 Execution을 한 클락에 동시 수행이 가능하다는 것이다.


-> 7클락에 5개의 명령어를 처리할 수 있다. n개의 명령어를 처리하는데 필요한 클락 수는 +2개가 된다는 것이다.


그렇기 때문에 CISC보다 적은 클락 수로 똑같은 일을 할 수 있는 것이다. -> 고성능 컴퓨터에서 RISC가 더 좋은 이유


반드시 클럭이 높다고 좋은 것이 아니라, 한 클럭 당 얼마나 효율적으로 연산을 수행하는가도 중요


클럭수가 낮으면 또한 열도 적게 발생한다.


결론 RISC 짱



LOAD와 STORE 명령어는 사칙연산 연산자와 명령어 구조가 다르다. 

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

커널 오브젝트 오브젝트 핸들  (0) 2019.09.26
프로세스, 스케줄러  (0) 2019.09.25
64비트 기반 프로그래밍, GetLastError  (0) 2019.09.23
문자셋 SBCS, MBCS, WBCS  (0) 2019.09.19
Stored Program Concept  (0) 2019.09.18

성우형 목소리너무좋아요

운영체제 

모델 

char 

short 

int 

long 

ptr

windows 

LLP64 

1바이트 

2바이트 

4바이트 

4바이트 

8바이트 

UNIX 

LP64 

1바이트 

2바이트 

4바이트 

8바이트 

8바이트 



압도적감사


64비트와 32비트 공존의 문제점


절대 기본자료형으로 포인터를 캐스팅하지말자


1
2
int arr[10] = { 0 };
int arrVal = (int)arr;
cs


물론 32비트에서도 좋은건 아니다


Windows 스타일 자료형


반드시 외울 필요는 읍다


Polymorphic 자료형


1
2
3
4
5
6
7
8
9
10
11
#if defined(_WIN64)
    typedef __int64 LONG_PTR;
    typedef unsigned __int64 ULONG_PTR;
    typedef __int64 INT_PTR;
    typedef unsigned __int64 UINT_PTR;
#else
    typedef long LONG_PTR;
    typedef unsigned long ULONG_PTR;
    typedef int INT_PTR;
    typedef unsigned int UINT_PTR;
#endif
cs


왜 UINT_PTR인데 *가 읍냐?

 -> 포인터 연산을 할 때, 포인터 값으로 무언가 연산을 해야할 때 사용하라고 _PTR을 붙였다.


예제


1
2
3
4
5
6
7
8
9
10
11
12
UINT CalDistance(UINT a, UINT b)
{
    return a - b;
}
int _tmain(void)
{
    INT val1 = 10;
    INT val2 = 20;
    _tprintf(_T("position &d, %d \n"), (UINT)&val1, (UINT)&val2);
    _tprintf(_T("distanc : &d \n"), CalDistance((UINT)&val1, (INT)&val2));
    return 0;
}
cs


1
2
3
4
5
#if defined(_WIN64)
    typedef unsigned __int64 UINT_PTR;
#else
    typedef unsigned int UINT_PTR;
#endif
cs



오류의 확인


GetLastError 함수와 에러코드


윈도우즈 프로그래밍에선 에러 로그를 저장하기 위에 전역 공간에(아마 데이터 공간?) 로그를 저장시키는데 이 에러 로그에 접근하는 함수가 바로 GetLastError 함수다.


 MSDN 홈페이지에 에러 코드별로 다 설명이 되어있으니 필요하면 참고


1
2
3
4
5
6
7
8
9
10
11
12
13
14
int _tmain(void)
{
    HANDLE hFile =
        CreateFile(        //Windows system 함수,
            _T("ABC.DAT"), GENERIC_READ, FILE_SHARE_READ,
            NULL, OPEN_EXISTING, FILE_ATRIBUTE_NORMAL,
            NULL);
    if(hFile == INVALID_HANDLE_VALUE)
    {
        _tprintf(_T("error code: %d \n"), GetLastError());
        return 0;
    }
    return 0;
};
cs


실행 결과

1 error code: 2


여기서 ABC.DAT이란 파일은 없다. 걍 없는 파일을 불러오려고 했을 때 어떤 오류가 나오는지 확인하는 것


INVALID_HANDLE_VALUE는 에러가 발생했는지를 체크하는 함수가 아니라, 에러가 있을때 그 에러가 있음을 알려주는 함수다.


또한, CreateFile 함수 호출 후 바로 GetLastError 함수가 호출되었는데, 이렇듯 GetLastError는 LastError이기때문에 특정 함수 호출 후 바로 GetLastError함수를 호출해야 그 기능을 온전히 할 수 있다.

저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

프로세스, 스케줄러  (0) 2019.09.25
컴퓨터를 디자인하자  (0) 2019.09.23
문자셋 SBCS, MBCS, WBCS  (0) 2019.09.19
Stored Program Concept  (0) 2019.09.18
힙 단편화, Windows Low Fragmentation Heap(LFH)  (0) 2019.09.18

문자셋의 종류와 특성


SBCS (Single Byte Character Set)

문자를 표현하는데 1바이트 사용

아스키 코드


MBCS (Multi Byte Character Set)

한글은 2바이트, 영문은 1바이트 사용


WBCS (Wide Byte Character Set)

문자를 표현하는데 2바이트 사용

유니코드


WBCS를 위한 두가지


- char를 대신하는 wchar_t

- "ABC"를 대신하는 L"ABC


main.cpp 유니코드 버전

1
2
3
4
5
6
7
8
9
10
int wmain(int argc, wchar_t* argv[])
{
    for(int i = 0; i < argc; ++i)
    {
        fputws(argv[i], stdout);
        fputws(L"\n", stdout);
    }
 
    return 0;
{
cs


windows.h MBCS & WBCS 동시 지원 매크로




나는 왜 windows 헤더 안에 매크로를 저렇게 덕지덕지 붙여놨나 했는데, 호환성 이유 때문이었구나 싶다.




저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

프로세스, 스케줄러  (0) 2019.09.25
컴퓨터를 디자인하자  (0) 2019.09.23
64비트 기반 프로그래밍, GetLastError  (0) 2019.09.23
Stored Program Concept  (0) 2019.09.18
힙 단편화, Windows Low Fragmentation Heap(LFH)  (0) 2019.09.18

Stored Program Concept (폰노이만 아키텍쳐)

아아.. 폰노이만


프로그램을 메모리에 저장하는 방식으로 컴퓨터가 디자인 되어야 한다.


Fetch

- CPU 내부로 명령어 이동

명령어는 메모리에 저장되어서 CPU에 의해 CPU 내부로 Fetch되어야 한다.

Bus를 타고...


Decode

- 명령어 해석

Fetch된 명령어를 해석

- 컨트롤 유닛


Execution

- 연산을 진행

해석한 명령어를 연산

- 보통은 ALU를 생각

ALU에 의해 연산된다고 생각해도 무방



메모리: Stored Program Concept의 근간을 이룸




Stored Program Concept를 바탕으로 컴퓨터구조에 접근하면 이러한 그림이 떠오르게 된다. 즉, 컴구와 폰노이만 아키텍쳐를 별개로 기억할 것이 아니라 둘이 엮어서 이해해야 한다는 것이다.


버스 시스템


데이터 버스

- 데이터 이동

어드레스 버스

- 주소 이동

컨트롤 버스

- 컨트롤 신호 이동


CPU

 데이터 버스

 메모리

 어드레스 버스

 컨트롤 버스


저작자표시

'운영체제 > 윈도우 시스템' 카테고리의 다른 글

프로세스, 스케줄러  (0) 2019.09.25
컴퓨터를 디자인하자  (0) 2019.09.23
64비트 기반 프로그래밍, GetLastError  (0) 2019.09.23
문자셋 SBCS, MBCS, WBCS  (0) 2019.09.19
힙 단편화, Windows Low Fragmentation Heap(LFH)  (0) 2019.09.18

https://www.acmicpc.net/problem/11066


거의 일주일동안 푼 문제, 답을 봐도 뭔소린지 모르겠어서 멘탈이 터졌다.


문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.


예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.


소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.


입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.


출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.


예제 입력 1 

2

4

40 30 30 50

15

1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1 

300

864


코드는 다음과 같다.

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
#include <iostream>
 
#define min(a,b)            (((a) < (b)) ? (a) : (b))
 
long long dp[501][501];
long long sum[501];
int T, K;
 
int main()
{
    std::cin >> T;
    for (int testCase = 0; testCase < T; ++testCase)
    {
        std::cin >> K;
        for (int i = 1; i <= K; ++i)
        {
            std::cin >> sum[i];
            sum[i] += sum[i - 1];
        }
        for (int x = 2; x <= K; ++x)
            for (int y = 1; y + x - 1 <= K; ++y)
            {
                dp[y][x + y - 1] = 2147483647;
                for (int m = y + 1; m - y < x; ++m)
                    dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
            }
        std::cout << dp[1][K] << '\n';
 
 
        for (int y = 0; y <= K + 2; ++y)
        {
            for (int x = 0; x <= K + 2; ++x)
            {
                std::cout.width(3);
                std::cout << dp[y][x] << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}
cs


예제 1의 설명으로는 좀 애매한 부분이 있어서.. 예제 2의 동작원리를 보게 되었다.



행렬은 이러한 숫자들로 구성이 되어 있는데,


3중 반복문이 어떻게 동작하는지 살펴봐야 한다.


1
2
3
4
5
6
7
for (int x = 2; x <= K; ++x)
    for (int y = 1; y + x - 1 <= K; ++y)
    {
        dp[y][x + y - 1] = 2147483647;
        for (int m = y + 1; m - y < x; ++m)
            dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
    }
cs



행렬은 x좌표가 2에서 시작한다. y는 x좌표의 값을 더해(-1도 추가) 입력받은 K장까지 증가하게 된다. int y = 1; y + x - 1 <= K; ++y


 y는 1부터 15까지 모든 행을 다 순회하기 때문에 1에서 시작한다. y + x - 1 <= K인 이유는 y <= K일 경우에 행렬 오버플로가 발생하기 때문


m은 양옆의 원소들을 비교하기 위해 존재하는 반복문이다. 자세한 동작은 계속 설명하면서 다시 보자.


첫번째 반복의 상황에선 x = 2, y = 1일 때, m = y + 1이 2, 즉 1 < 2(m - y < x) 이기 때문에 x = 2, y = 1, m = y + 1 일 때



dp[y][x + y - 1]이 2147483647(INT_MAX)이고,


min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1])

 =

dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

dp[2][2] + dp[1][1] + sum[2] - sum[0]

0              +    0        +  22(sum[2])   -  0(sum[0])

이기 때문에 22가 들어가게 되는 것이다.


y가 2일 때는 25(sum[x + y - 1] = sum[3]) - 1(sum[y - 1] = sum[1]) 이다.


즉,

dp[3][3] + dp[2][2] + sum[3] - sum[1] = 24이다.


아직까진 반복문 m이 한번밖에 돌지 않는다. 또한 동작도 납득할 수 있는 수준이다.



이제 x = 3 일 때, y가 어떻게 동작하는지 알아야 한다.


for (int m = y + 1; m - y < x; ++m)이다. 즉 m = 2일때, m - y < x(2 - 1 < 2), 반복문은 두번 반복된다.


m = 2 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[2][3] + dp[1][2](0 + 24) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 24 + 25 = 49 이다. dp[y][x + y - 1]는 49이다.


m = 3 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[3][3] + dp[1][1](22 + 0) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 22 + 25 = 47 이다. 49 > 47 이기 때문에 dp[y][x + y - 1]는 47이다.



혼란스러운 머리를 부여잡고 여기까지 따라왔다면 이것 또한 이해할수있따


dp[1][4]는 (22 + 7) + (1 + 21 + 3 + 4) = 58 이고, 

dp[2][5]는 (19 + 0) + (21 + 3 + 4 + 5) = 52 이다.


사진상의 행렬 비교 순서는 m = 2 일 때,

(35 + 0) + (1 + 21 + 3 + 4)

(7 + 22) + (1 + 21 + 3 + 4)

(0 + 47) + (1 + 21 + 3 + 4)


이 중 가장 작은것은 58이기 때문에, dp[1][4]는 58이 들어가는 것



같은 원리다. 계산은 이와 같은 로직으로 돌아가게 된다.


어째서 이러한 동작을 하게 되냐면,


잘 모르겠다ㅎ 대충 이분해서 최솟값을 계산하는 것은 얼추 알 것 같다. 설명할 자신은 없지만



첫 번째 사진은 1, 21 ~ 32 중 최소 비용을 쓴 크기 (839 + 0) + sum[15]

두 번째 사진은 1 ~ 21, 3 ~ 32 중 최소 비용을 쓴 크기 (739 + 22) + sum[15]

...

n  번째 사진은 1 ~ 35, 5 ~ 32 중 최소 비용을 쓴 크기 (515 + 144) + sum[15]

515 : 1 ~ 35 중 최소 비용

144 : 5 ~ 32 중 최소 비용

... K번까지 돌아가는 것이다.


그냥 그러려니 하고 암기하자...

저작자표시

'알고리즘' 카테고리의 다른 글

2. C++언어 역사 개요..?  (0) 2019.10.07
1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23

ESP - Stack pointer register


ESP 레지스터 : 스택의 크기를 조정할 때 사용되는 레지스터. 스택의 최상단 주소값을 가진다.

 -> 스택의 크기를 나타냄


Intel CPU에서는 스택이 거꾸로 자란다.


ESP는 다음 번 DATA를 PUSH할 위치가 아닌, 다음에 POP 했을 때 뽑아낼 데이터의 위치를 가리킨다.

 -> std::stack::top()의 주소라고 생각하면 될듯.


어셈블리에서 esp에 PUSH를 하면 esp 값이 n감소한다.


 n? : msvc 2017 기준, 0C0h(192) 감소한다. 밑의 디스어셈블리 참고


감소하는 이유는 다음과 같다. 높은주소 → 낮은주소


EBP - Base pointer register


EBP 레지스터 : 스택프레임 형태로 저장된 함수의 지역변수, 전달 인자를 참조 & 값의 수정 시 사용되는 레지스터.


현재 스택의 가장 바닥을 가리키는 포인터.


새로운 함수 B가 호출되면, EBP 레지스터 값은 지금까지 사용했던 스택 A의 위를 가리킨다. 그리고 새로운 스택(함수 공간)이 시작


따라서 EBP는 새로운 함수가 호출되거나, 현재 실행중인 함수가 종료되면 값이 달라진다.


새로운 함수를 호출할 때, EBP 레지스터 값

전달 인자를 ESP 레지스터로 참조할 수는 있지만 어셈블리 코드 유지가 힘들다.


EBP는 고정적이지만 ESP는 명령을 수행 시 값이 변하기 때문에 매번 수정해주어야 하기 때문.




00E85720 push ebp : 이전 스택의 베이스 주소(따로 첨부는 안했지만 main함수였음)를 저장


00E85721 mov ebp, esp  : 현재 스택의 꼭대기(esp)를 새로운 스택의 base(ebp)로 복사

(새로운 스택의 시작)


그 밑에도 뭐가 주루룩 있지만 일단 여기까지만



기본적인 레지스터 종류


일반 레지스터

EAX, EBX, ECX, EDX


일반주소 레지스터

ESP, EBP, ESI, EDI


그 외 레지스터

EIP



EAX (Extended Accumulator Register)

 - 산술, 논리연산


산술, 논리연산의 중심이 되는 레지스터

주로 이 레지스터를 사용해 산술, 논리 연산을 수행


함수의 리턴 값을 저장하는 레지스터다.

(그렇기 때문에 리턴값이 2개 이상이 될 수 없다.)


EBX (Extended? Base Register)

 - 간접 주소 지정


간접 주소 지정 시 사용된다.

ebx 1000

jmp 1000 //직접 지정

jmp ebx // 간접 지정


int a[5] 에서 배열의 메모리 접근 시 a[2]를 사용되는 0 ~ 4, 이러한 인덱스 넘버가 바로 간접 번지이다.

 - a의 3번째 주소에 접근해라!


ECX (Extended? Count Register)

 - 반복 카운터


루프와 같은 명령의 반복 수행이 필요할 때 반복 횟수 지정에 주로 사용, (while, for과 다르다. 어셈블리를 위한 반복이다)


ex) ECX에 5를 넣었을 때, ECX 값이 0이 될 때까지 반복한다. ECX 값은 감소한다.


EDX (Extended? Data Register)

 - EAX를 도와주는 역할


아 귀찮다. 나중에 더 필요하면 공부함

저작자표시

'프로그래밍' 카테고리의 다른 글

클린 코드(미완)  (0) 2023.03.01
COM  (0) 2020.11.06
XML, XML DOM  (0) 2020.11.06
FSM  (0) 2019.07.24
더블과 플로트, FPU에 관해 (6 / 2)  (0) 2019.06.09

https://www.acmicpc.net/problem/1912



 

 시간 제한

 2 초 

 메모리 제한

 128 MB

 제출

 51339

 정답

 14220

 맞은 사람

 9806

 정답 비율 

 27.120%


문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.


예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.


입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


기존 코드


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
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) 
{ 
    return first > second ? first : second;
}
 
int main()
{
    int n = 0;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
    }
    dp[0] = arr[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n);
    std::cout << dp[n - 1];
    return 0;
}
cs

시간 20ms


바꾼 코드


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
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) { return first > second ? first : second; }
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    int n = 0;
    std::cin >> n;
    dp[0] = -1001;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n + 1);
    std::cout << dp[n];
    return 0;
}
cs

시간 8ms


어이어이 너무 쉬운거 아니냐고 wwwwwww


LIS LCS에서 뚝배기터지고 나온 문제라 와 시발 얼마나 어려울까 해쓴ㄴ데


문제가 생각보다 너무 쉬울것같아서 아.. 뭔가 어려운게 있겠지? 있겠지? 해서

(코드 짠시간보다 이게 될까 안될까 고민하는 시간이 더 길었다)


부들부들 떨면서 제출했는데 그냥 통과대버렷다


쉬운문제는 맞는것같은데 왤캐 정답률이 낮지


히히ㅣㅎ킿킿ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

저작자표시

'알고리즘' 카테고리의 다른 글

1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23

https://www.acmicpc.net/board/view/28163


5시간동안 개삽질하고


답 5분 보고 어이없어서


멘탈터짐


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
unsigned int max(unsigned int first, unsigned int second)
{
    return first > second ? first : second;
}
 
unsigned int dp[1001][1001];
 
int main()
{
    std::string A, B;
    std::cin >> A >> B;
    for (int y = 1; y <= A.size(); ++y)
    {
        for (int x = 1; x <= B.size(); ++x)
        {
            if (A[y - 1] == B[x - 1])
                dp[y][x] += dp[y - 1][x - 1] + 1;
            else
                dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]);
        }
    }
    for (int y = 0; y <= A.size(); ++y)
    {
        for (int x = 0; x <= B.size(); ++x)
        {
            std::cout << dp[y][x]; //dp[A.size()][B.size()]가 정답
        }
        std::cout << '\n';
    }
    return 0;
}
 
cs


2차원배열을 이용하는 것도 참


생각도 못했다


걍 너무 내가 병신쪼다같고 막.. 그래....


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
unsigned int getlen(int it, unsigned int n)
{
    //KJFSDFLKDF
    int tmp = 1;
    int pos = n;
    for (unsigned int i = it; i < str1.size(); ++i)
    {
        //findPos = prePos;
        //KJSDFKSDFLKDFJS SKDJKFLSKDJFLKSDJF
        auto finder = str2.find(str1[i], pos);
        if (finder == std::string::npos) continue;
        if (dp2[finder] != 0 && dp2[finder] <= tmp) { ++pos; --i;  continue; }
        unsigned int j = finder;
        while (j < str2.size())
        {
            if (dp2[j] != 0) break;
            ++j;
            //if (tmp > dp2[j] && str2[j] == str1[i]) break;
        }
        if (tmp > dp2[j] && dp2[finder] != 0) { ++pos; --i;  continue; }
        if (j == str2.size())
        {
            dp2[finder] = ++tmp;
        }
        else
        {
            if (str1[i] == str2[j] && tmp < dp2[j]) continue;
            dp2[finder] = dp2[j];
            tmp = dp2[j];
            dp2[j] = 0;
        }
        //prePos = finder;
        //int jtmp = 0;
        //for (unsigned int j = i + 1; j < str1.size(); ++j)
        //{
        //    findPos = finder;
        //    finder = str2.find(str1[j], findPos);
        //    if(finder == std::string::npos) continue;
        //    ++jtmp;
        //    if (finder == str2.size() - 1) break;
        //}
        //cnt = cnt > tmp + jtmp ? cnt : tmp + jtmp;
    }
    std::cout << '\n';
    cnt = cnt > tmp ? cnt : tmp;
    for (int i = 0; i < str2.size(); ++i)
        std::cout << dp2[i] << ' ';
    return cnt;
}
 
int main()
{
    std::cin >> str1 >> str2;
    int dcnt = 0;
    for (unsigned int i = 0; i < str1.size(); ++i)
    {
        cnt = 0;
        auto startPoint = str2.find(str1[i]);
        if(startPoint == std::string::npos) continue;
        std::cout << str2[startPoint] << ' ';
        dp1[dcnt++] = getlen(i + 1, startPoint + 1);
    }
    std::sort(dp1, dp1 + str1.size());
    std::cout << dp1[str1.size() - 1];
    return 0;
}
cs


똥꼬쑈의 흔적


결국 대패배


저작자표시

'알고리즘' 카테고리의 다른 글

백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22

+ Recent posts

티스토리툴바