인프런 워밍업 클럽 2기 - CS 전공지식 스터디 2주차 발자국
운영체제 2주차 학습 요약 CPU 스케쥴링 알고리즘SJF (Shortest Job First)짧은 작업 시간을 가진 프로세스에 먼저 CPU를 할당하는 방식버스트 타임이 긴 프로세스는 계속 실행되지 않을 수 있고, 어떤 프로세스가 얼마나 실행될지 예측이 어려움RR (Round Robin)시간을 균등하게 분배하여 각 프로세스에 순차적으로 CPU를 할당하는 방식컨텍스트 스위칭으로 인해 처리량이 늘어남MLFQ (Multi Level Feedback Queue)프로세스의 우선순위를 동적으로 조절하여 CPU를 효율적으로 할당하는 방식오늘날 운영체제에서 가장 일반적으로 사용됨프로세스 동기화여러 프로세스가 공유 자원에 동시에 접근할 때 순서를 정하여 데이터의 일관성을 유지하는 것프로세스간 통신의 종류한 컴퓨터 내에서 프로세스간 통신하는 방법 : 파일 or 파이프를 이용한 프로세스 내에서 쓰레드간 통신하는 방법 : 데이터 or 힙영역을 이용네트워크를 이용하여 통신하는 방법 : 소켓통신, RPC공유자원과 임계영역공유자원은 프로세스 혹은 스레드간 통신할 때 공동으로 이용하는 변수나 파일 같은 것들공유자원은 여러 프로세스가 공유하고 있기 때문에 각 프로세스의 접근 순서에따라 결과가 달라질 수 있음임계영역은 프로세스 혹은 스레드가 동시에 사용하면 안되는 영역 (접근 순서등의 이유로 결과가 달라지는 영역)경쟁조건은 공유자원을 서로 사용하기 위해 경쟁하는 것임계구역 문제를 해결하기 위한 조건상호배체임계영역엔 하나의 프로세스만 접근해야 함한정대기기다리는 프로세스는 언제가는 임계영역에 접근 할 수 있어야함진행의 융통성한 프로세스가 다른 프로세스의 일을 방해해서는 안됨세마포어 & 모니터뮤텍스는 공유자원을 lock()과 unlock()을 이용하여 프로세스의 접근을 제어하는 메커니즘여러 프로세스의 접근을 관리할 수 있으면 세마포어 (뮤텍스는 동기화 대상이 오직 하나임)세마포어는 잘못된 사용으로 임계영역을 보호받지 못할 수 있음 (세마포어를 사용하지 않고 임계구역에 들어간 경우)이를 해결한 방식이 모니터모니터는 공유자원을 숨기고 접근에 대한 인터페이스만 제공하여 공유자원에 안전하게 접근하게 하는 메커니즘운영체제가 처리하는게 아니라 프로그래밍 언어차원에서 지원하는 방법임교착상태 (데드락)두개 이상의 프로세스들이 서로가 가진 자원을 기다리다 아무도 작업을 진행하지 못하는 상태데드락 필요조건상호배제비선점점유대기원형대기은행원 알고리즘총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고, 교착상태가 발생하지 않는 수준이 되도록 자원을 할당하는 알고리즘검출 & 회복교착상태는 어떻게 검출하지?가벼운 교착상태 검출 (타이머)일정시간마다 작업을 조작하고 교착상태가 발생하면 체크포인트로 롤백무거운 교착상태 검출 (순환구조)교착상태를 일으킨 프로세스를 강제 종료시키고 다시 실행 시킬때 체크포인트로 롤백오버헤드가 발생하지만 억울하게 종료되는 프로세스는 발생하지않음메모리레지스터 (32bit 또는 64bit)캐시CPU와 메인메모리 속도 차이 때문에 미리 데이터를 저장하는 임시공간메인메모리 (RAM)프로세스를 로드, 휘발성보조기억장치 (SSD, HDD)디스크 저장, 비휘발성물리 주소 - 물리적인 메모리 주소논리 주소 - 사용자 관점에서 본 상대적 주소, 사용자는 논리 주소를 통해 물리 주소로 접근메모리 할당방식가변분할방식메모리에 연속해서 프로세스를 할당단점으로 외부 단편화가 발생할 수 있음고정분할방식메모리를 정해진 크기로 나누어 프로세스를 할당단점으로 내부 단편화가 발생할 수 있음버디시스템메모리를 2의 제곱 수로 분할하여 할당하는 방식가변분할방식과 고정분할방식을 합친 방법 알고리즘 & 자료구조 2주차 학습 요약 재귀 & 재귀적으로 생각하기재귀는 자기 자신을 다시 호출하는 함수를 말함어떤 문제를 해결하기 위해 문제의 부분 문제를 같은방식으로 해결하는 과정하향식 풀이에서 활용됨 (하위 문제를 기반으로 해결)하노이탑 구현하기세개의 기둥과 서로 다른 크기의 원반들이 있을때 가장 큰 원반이 아래에 있고 위로 갈수록 작은 원반으로 이루어져있음하나의 기둥에 있는 원반들을 다른 기둥으로 옮겨야 함기둥 A에 있는 원반을 기둥 C로 옮기기 (하향식 접근으로 풀이) 처음 시작 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐 모두 옮김그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편) 캡쳐자바코드public class HanoiTop { void hanoi(int count, String from, String to, String temp){ if(count == 0) return; hanoi(count - 1, from, temp, to); System.out.printf("원반 %d를 %s에서 %s로 이동\n", count, from, to); hanoi(count - 1, temp, to, from); } public static void main(String[] args) { HanoiTop hanoiTop = new HanoiTop(); hanoiTop.hanoi(3, "A", "C", "B"); } } 버블정렬앞에 있는 숫자와 옆에 있는 숫자를 비교해서 자리를 바꾸는 알고리즘자바코드public class BubbleSort { void bubbleSort(int[] arr) { // 사이클 - 자리교체는 (배열의 갯수 - 1) 번 수행함 for (int i = 0; i < arr.length - 1; i++) { // 횟수 - 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회 // 시작점이 (arr.length-i-1)번 임 for (int j = 0; j < (arr.length - i - 1); j++) { // 앞의 데이터가 뒤에 데이터보다 더 크다면? if (arr[j] > arr[j + 1]) { // 데이터 자리변경 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } public static void main(String[] args) { int[] arr = {2, 3, 1, 4}; // 정렬 전 - arr = [2, 3, 1, 4] System.out.println("정렬 전 - arr = " + Arrays.toString(arr)); BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(arr); // 정렬 후 - arr = [1, 2, 3, 4] System.out.println("정렬 후 - arr = " + Arrays.toString(arr)); } } 선택정렬정렬되지 않은 배열의 첫번째 원소를 시작으로 마지막 원소까지 탐색하여 가장 작은 값을 정렬되지 않은 첫번째 배열로 가져오는 알고리즘자바코드public class SelectionSort { void selectionSort(int[] arr) { // 1 사이클의 순회는(배열의 갯수 - 1) 번 수행됨 for (int i = 0; i < arr.length - 1; i++) { int minValueIndex = i; // 가장 작은 값을 탐색하기위해 순회 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minValueIndex]) { // 작은값 저장 minValueIndex = j; } } // 자리 변경 int temp = arr[i]; arr[i] = arr[minValueIndex]; arr[minValueIndex] = temp; } } public static void main(String[] args) { int[] arr = {4, 2, 1, 3}; // 정렬 전 - arr = [4, 2, 1, 3] System.out.println("정렬 전 - arr = " + Arrays.toString(arr)); SelectionSort selectionSort = new SelectionSort(); selectionSort.selectionSort(arr); // 정렬 후 - arr = [1, 2, 3, 4] System.out.println("정렬 후 - arr = " + Arrays.toString(arr)); } } 회고2주차 스터디를 진행하면서 정해진 진도도 학습하면서, 스터디안에 발표스터디에 참여해서 복습도 하는 과정이었어요. 적어보였던 운영체제의 내용이 생각보다 많아서 정리하는데 은근 시간이 오래 걸리더라구요. 그래도 스터디안의 발표 스터디에 참여하여 정리내용을 발표하고 다른 스터디원들의 발표내용도 듣고 헷갈리는 부분도 토론해서 도움이 많이 되었던 한 주 였던것 같습니다.스터디 발표 정리 자료 캡쳐그리고 이번 알고리즘 강의에서는 항상 어렵게 느꼈던 재귀에 대해 조금은 이해한게 너무 좋았습니다.어떤 문제를 해결하기 위해 문제의 부분 문제를 같은 방식으로 분해하여 해결한다.!! 재귀함수 내에서 자기 자신을 호출할 때 이 함수가 벌써 구현이 되어있다고 가정하고 재귀함수를 구현한다.!! 많이 연습해봐야겠지만 그래도 재귀적으로 생각하는 방법을 느낄 수 있었던 것 같습니다.마지막 1주가 남았는데, 끝까지 열심히 해서 끝까지 완주해야겠네요. 화이팅
