#2-1. System Structure & Program Execution

: 운영체제를 설명하기 앞서 하드웨어적인 동작을 설명.


 



컴퓨터란? : cpu + memory


memory = cpu의 작업공간


* cpu는 매 클럭 사이클마다 instruction(기계어)를 하나씩 읽어서 실행을 하게된다.

  => cpu의 운명.


- register : cpu안에는 memory보다 더 빠른 메모리 저장 공간이 있다

- mode bit : 지금 cpu에서 사용되는것이 운영체제인지 or 사용자명령인지 구분해주는 것.


 => 1 : 사용자 프로그램 수행

      0 : 모니터모드. 커널모드 (os가 cpu사용)

 v. 보안을 해칠수 있는 중요 명령어는 모니터 모드에서만 실행가능.

 v. interrupt 발생시, mode bit 0으로 set.

 v. 사용자 프로그램에 cpu넘기기 전에 mode bit 1로 set.

 

    => 보안을 목적으로 instruction set을 나누어 놓았다.



* timer

: 특정프로그램이 cpu를 독점하는것을 막는것 (무한루프 방지)

 v. 매 클럭 틱 때마다 1씩 감소

 v. 셋팅해놓은 시간이 끈나면 ‌interrupt를 넣어준다.

 v. cpu는 intertupt line을 체크한다.

 

=> 즉, cpu의 time sharing 구현을 위한 하드웨어!!



* I/O device


- device controller : I/O device는 각각 작은 cpu역할을 하는 컨트롤러가 있다.


cf> device driver : 각 장치에 맞게 접근할 수 있게 해주는 SW모듈.


- local buffer : device controller들도 작은 메모리 공간이 필요한데, 이곳은 로컬 버퍼라고 부른다.

 v. 실제 I/O는 device와 로컬 버퍼 사이에서 일어남.

 v. I/O가 끈나면 컨트롤러가 interrupt로 cpu에 그 사실을 알림.



* DMA controller :  이러다 보면 cpu가 너무 interrupt를 너무 많이 당하게 된다. 그래서 이것이 필요하다. (직접 메모리 접근 가능)


=> 즉, DMA는 cpu를 효율적으로 사용하기 위해 필요한것.


* memory controller : DMA와 CPU의 교통정리를 해주는 컨트롤러.


* 모든 입출력 명령은 특권 명령이다.

- 시스템콜 : 사용자 프로그램이 os의 커널함수를 호출하는것.

 : 일반 함수 호출과는 조금 다르다. 

 프로그램이 interrupt를 걸면서(mode bit=0) 시스템콜을 하게된다.

 이 인터럽트를 Trap 이라고 한다.

 

   v. Exception   : 프로그램 오류를 범한 경우.

   v. System call : 프로그램이 커널함수를 호출하는 경우.

   v. trap이 걸리면 cpu가 os로 넘어가게 된다.

cf> 일반 함수 호출은 memory 주소를 바꾸는 것으로 가능하다.


???) 

Q. I/O를 요청하는 interrupt : SW 인터럽트(trap)

   I/O가 끈난다면     : HW 인터럽트를 이용해서 끈난것을 알려준다.


 

=> 현대의 os는 interrupt에 의해서 구동된다.

'cs > os' 카테고리의 다른 글

#3-3. Thread  (0) 2017.12.29
#3-2. Process  (0) 2017.12.27
#3-1. Process  (0) 2017.12.27
#2-2. System Structure & Program Execution  (0) 2017.12.25
# Thread  (0) 2017.12.17

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


1. 문제 이해


n을 입력 받았을때 나누기3, 나누기2, 빼기1 3가지 연산을 사용하여 1로 만들때, 최소 연산수를 구하는 문제 입니다.


2. 접근 방법


다이나믹 프로그램으로 문제 해결을 해보겠습니다. 

이 표현이 맞는지는 모르겠으나, 작은문제에서 큰문제를 해결해 나가는 bottom-up 방식으로 문제를 해결했습니다.


3. 문제 해결


for문으로 완전 탐색을 하되, 크게 3가지로 분류했습니다.


1. 3의 배수인가?                                => 3곱해서 올 수 있고, 1 더해서 올 수 있다.

2. 2의 배수인가?                                => 2곱해서 올 수 있고, 1 더해서 올 수 있다.

3. 3의배수, 2의배수 모두 아닐 경우        => 1더해서 밖에 올 수 없다.


이 루틴을 이용했습니다.


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
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 1000001
 
using namespace std;
 
int dp[MAX_SIZE];
 
int main() {
    int n;
    scanf("%d", &n);
 
    int res = 0;
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    for (int i = 4; i <= n; i++) {
        if (i % 3 == 0) {
            dp[i] = min(dp[i / 3], dp[i - 1]) + 1;
        }
        else if (i % 2 == 0) {
            dp[i] = min(dp[i / 2], dp[i - 1]) + 1;
        }
        else {
            dp[i] = dp[i - 1] + 1;
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}
cs


'Algorithm > solution' 카테고리의 다른 글

#2140. 지뢰찾기  (0) 2017.12.29
#6305. 로또  (0) 2017.12.26
#10815. 숫자카드  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23

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


1. 문제 이해


전형적인 탐색 문제입니다. 


2. 접근 방법


완전 탐색을 하되, 이분탐색으로 시간을 줄이도록 하겠습니다. 

저는 재귀로 이분탐색 함수를 작성할 것입니다.

재귀로 함수를 작성할때는 무한 루프에 빠지지 않게 탈출 조건을 먼저 만들도록 합니다!!


3. 문제 해결


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
#include <algorithm>
#include <cstdio>
#define MAX_SIZE 500001
using namespace std;
 
int n, m;
int my[MAX_SIZE];
int chk[MAX_SIZE];
 
bool bs(int l, int r, int find) {
    int mid = (l + r) / 2;
 
    if (l > r) {
        return false;
    }
    else {
        if (my[mid] == find) return true;
        else if (my[mid] > find) return bs(l, mid - 1, find);
        else return bs(mid + 1, r, find);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &my[i]);
    }
    sort(my, my + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &chk[i]);
    }
 
    for (int i = 0; i < m; i++) {
        int left = 0, right = n - 1;
        
        if (bs(0, n - 1, chk[i])) {
            printf("1 ");
        }
        else {
            printf("0 ");
        }
    }
    printf("\n");
    return 0;
}
cs


※ 항상 void로 함수를 작성하던 버릇에서 벗어나 좀더 세련되게 짜보았다.

※ cin, cout 보다는 scanf, printf가 빠르다!!

'Algorithm > solution' 카테고리의 다른 글

#6305. 로또  (0) 2017.12.26
#1463. 1로 만들기  (0) 2017.12.24
#1065. 한수  (0) 2017.12.24
#1654. 랜선자르기  (0) 2017.12.23
#11866. 조세퍼스 문제  (0) 2017.12.01

+ Recent posts

티스토리툴바