감자튀김 공장🍟

선점형 스케줄링 Round Robin (RR) 스케줄링 설계 방침 : 모든 프로세스에게 공편한 실행 기회를 주기 위해 일정 시간 간격으로 프로세스들을 번갈아 실행시킨다. 알고리즘 : 큐에 대기중인 프로세스들을 타임 슬라이스 주기로 돌아가면서 선택하는 방법이다. 도착하는 프로세스들은 큐의 끝에 삽입되며, RR은 준비 리스트의 맨 앞에 있는 프로세스를 선택한다. 성능과 문제점 : RR은 공정하고, 기아 현상이 없으며, 구현이 쉽다는 장점이 있다. 하지만 잦은 스케줄링으로 인해 스케줄링 때마다 소요되는 컨텍스트 스위칭 오버헤드가 크다는 단점이 있다. 프로세스도착 시간실행 시간(예상 값) P1 0 4 P2 1 3 P3 2 1 P4 5 3 SRTF (Shortest Remaining Time First) 설계 방..

CPU scheduling CPU 스케줄링이란 메모리에서 실행을 기다리는 프로세스 중, 하나를 선택하는 과정이다. CPU 스케줄링의 목표는 CPU의 유휴시간 줄이기, 컴퓨터 시스템 처리율 향상이다. CPU 스케줄링의 기준 높은 CPU 활용률(CPU utilization) - 컴퓨터의 전체 가동 시간에 대한 CPU의 사용 시간의 비율 처리율 극대화(maximize throughput) - 단위 시간 당 처리하는 프로세스의 개수를 극대화 공정성(fairness) - 모든 프로세스에게 CPU 사용 시간을 공평하게 배분 응답 시간 최소화(minimize response time) - 대화식 사용자에 대한 응답 시간을 최소화 대기 시간 최소화(minimize waiting time) - 프로세스가 준비 리스트에서..

Context Switching 현대의 멀티스레드 운영체제에서 실행 단위는 더 이상 프로세스가 아니라 스레드이다. 프로세스는 여러 개의 스레드들이 실행될 때 자원을 공유하는 컨테이너로 그 역할이 바뀌었다. 그렇기 때문에 여기서 말하는 Context Switching은 Thread 기반으로 이루어졌음을 미리 알린다. Context Switching CPU는 한번에 하나의 프로세스만 처리할 수 있다. 여러 프로세스를 처리해야 하는 상황에서 현재 실행중인 Task(프로세스, 스레드)의 상태를 PCB에 저장하고 다음에 진행할 Task의 상태값을 읽어 적용하는 과정을 말한다. (다른 프로세스에게 CPU를 할당해 작업을 수행하는 과정을 말한다.) 스레드 컨텍스트와 컨텍스트 스위칭 Context Switching 과..

프로세스간 통신의 필요성 응용프로그램은 여러 프로세스(multi process)를 생성하고 각 프로세스에게 하나씩 작업을 맡겨, 동시에 여러 작업을 처리할 수 있다. 응용프로그램에 따라 각 프로세스들이 독립적으로 작업을 처리하기도 하지만, 프로세스들이 서로 데이터를 주고받으면서 협력해야 하는 경우도 있다. 또한 다중 프로세스(multi process)는 프로세스 사이에 데이터 혹은 변수 공유가 되지 않으며, 현대의 다중 작업 응용프로그램은 멀티 스레딩으로 작성되기 때문에 프로세스 간 통신의 필요성이 더더욱 필요하다. IPC (Inter Process Communication) 프로세스들의 주소 공간은 완전히 분리되어 있어서, 두 프로세스 사이에는 코드를 제외한 어떤 메모리 공간도 공유되지 않는다. 프로세..

시스템 콜(system call) 응용 프로그램은 함수 호출(function call)을 통해 다른 함수들을 실행한다. 하지만 응용 프로그램은 커널에 있는 함수를 함수 콜(system call)의 방법으로 호출할 수 없다. 왜냐하면, 커널 코드 안에 들어 있는 함수의 이름을 알 수도 없을 뿐더러, 설사 안다고 하더라도 응용 프로그램이 커널 코드와 링크할 수 없기 때문이다. 응용 프로그램에서 커널에 작성된 함수를 호출하는 다른 방법이 제공되는데, 그것이 바로 시스템 콜(system call)이다. 시스템 콜(system call)의 유형 1. fork() 현재 프로세스와 동일하게 생긴 자식 프로세스를 만든다. fork()는 코드 ,데이터, 스택, 힙 등 부모 프로세스와 완벽히 동일한 자식 프로세스를 만들고..

프로그램이란? 실행 가능한 파일의 형태로 하드 디스크나 USB 등의 저장 장치에 저장된 파일이다. Process 프로세스 (process) 프로그램이 메모리에 로딩되어 실행 중인 작업 운영체제로부터 시스템 자원을 할당받는다. 할당 받는 시스템 자원 CPU 시간 주소 공간 Code, Data, Stack, Heap의 구조로 되어있는 독립된 메모리 영역 한 프로세스는 다른 프로세스의 변수나 자료구조에 접근할 수 없으며, 접근을 위해서는 IPC 통신이 필요하다. 특징 프로세스는 메모리에 적재되어야 실행된다. 프로세스들은 서로 독립적인 메모리 공간을 가진다. 커널은 각 프로세스의 메모리 위치와 크기 정보를 관리한다. 프로세스마다 고유한 번호가 할당된다. 기본적으로 프로세스마다 최소 1개의 스레드를 갖는다. (메..

인터럽트 (Interrupt) 운영체제와 하드웨어 장치 사이의 인터페이스 하드웨어 장치들이 CPU에게 하드웨어 신호(인터럽트 신호)를 물리적으로 발생시켜, 입출력 완료나 타이머 완료 등을 CPU에게 알리는 방법이다. CPU가 입터럽트 신호를 받게 되면, 현재 하던 일을 멈추고 발생한 인터럽트의 요청을 처리하는 코드를 실행한다. 하드웨어 인터럽트 CPU의 하드웨어 신호에 의해 발생 입출력 장치, 타이밍 장치, 전원 등 외부적인 요인으로 발생 전원 이상, 기계 착오, 외부 신호, 입출력 소프트웨어 인터럽트 명령어의 수행에 의해 발생 Trap이라고 부르며, 잘못된 명령이나 데이터를 사용할 때 발생 예외 상황(Exeption) : 프로그램이 허용되지 않은 연산을 수행하려고 할 때, 자동적으로 발생한다. ex) ..

연결 리스트 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(Linked List)라고 한다. 연결 리스트는 배열의 단점을 보완하고자 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 연결 리스트 기본 구조와 용어 노드(Node): 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 3가지 종류의 연결 리스트가 있다 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 단순 연결 리스트 구현 구조 typedef struct ListNode { int data; struct ListNode* next; } ListNode; ​ 구조체 내부에 데이터를 저장하는 dat..

순회 이진 트리에서 데이터를 탐색하는 방법은 크게 세 가지 방법이 있다. 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 전위 순회 전위 순회는 Root를 제일 먼저 처리합니다. 순서 Root (자기 자신) 왼쪽 자식 오른쪽 자식 위의 트리에서 전위 순회로 순회를 한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서입니다. 중위 순회 중위 순회는 Root를 가운데 순번에서 처리합니다. 순서 왼쪽 자식 Root (자기 자신) 오른쪽 자식 위의 트리에서 중위 순회로 순회를 한다면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 순서입니다. 후위 순회 후위 순회는 Root를 가장 마지막에서 ..

트리(Tree) 트리는 계층적인 자료를 표현하는데 적합한 자료구조이다. 데이터의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다. 트리의 용어 노드 (Node): 트리를 구성하고 있는 각 요소 ex) A, B, C ... J, K 간선 (Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node: 최상위 계층에 존재하는 노드 ex) A Level: 트리의 특정 깊이를 가지는 노드의 집합 ex) A의 level은 1, E의 level은 3 차수 (Degree): 어떤 노드가 가지고 있는 자식 노드의 개수 ex) B의 차수는 2, D의 차수는 3 깊이 (Depth, Height): 어떤 트리에서 노드가 가질 수 있는 최대의 레벨 ex) 위의 트리에서 깊이는 4 단말 노드(..